Added two missing includes to allow macro compilation (thanks to Laurent for remarkin...
[u/mrichter/AliRoot.git] / ITS / AliITSIntMap.cxx
CommitLineData
b15de2d2 1//////////////////////////////////////////////////////////////////////
2// Author: Henrik Tydesjo //
3// This class implements the use of a map of integers. //
53ae21ce 4// The values are kept in a binary tree, which is automatically //
5// reordered to be more balanced when the tree height gets too large//
b15de2d2 6//////////////////////////////////////////////////////////////////////
7
8#include "AliITSIntMap.h"
9#include "AliITSIntMapNode.h"
53ae21ce 10#include <TMath.h>
11#include <TError.h>
b15de2d2 12
13AliITSIntMap::AliITSIntMap():
14 fNrEntries(0),
53ae21ce 15 fRoot(NULL),
16 fFastAccess(kFALSE),
17 fFastAccessSerialize(kFALSE),
18 fFastAccessArray(NULL),
19 fDummyIndex(0)
20{}
21
22AliITSIntMap::AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries):
23 fNrEntries(nrEntries),
24 fRoot(root),
25 fFastAccess(kFALSE),
26 fFastAccessSerialize(kFALSE),
27 fFastAccessArray(NULL),
28 fDummyIndex(0)
b15de2d2 29{}
30
31AliITSIntMap::AliITSIntMap(const AliITSIntMap& imap):
32 fNrEntries(0),
53ae21ce 33 fRoot(NULL),
34 fFastAccess(kFALSE),
35 fFastAccessSerialize(kFALSE),
36 fFastAccessArray(NULL),
37 fDummyIndex(0)
b15de2d2 38{
39 // copy constructor
53ae21ce 40 *this = imap;
b15de2d2 41}
42
53ae21ce 43AliITSIntMap::~AliITSIntMap() {
44 Clear();
45}
b15de2d2 46
47AliITSIntMap& AliITSIntMap::operator=(const AliITSIntMap& imap) {
48 // assignment operator
49 if (this!=&imap) {
50 this->Clear();
53ae21ce 51 fRoot = CloneNode(imap.fRoot);
52 fFastAccess=kFALSE;
53 fFastAccessSerialize=kFALSE;
54 fFastAccessArray=NULL;
55 fDummyIndex=0;
b15de2d2 56 }
57 return *this;
58}
59
60void AliITSIntMap::Clear() {
61 // clear the whole map
53ae21ce 62 ClearFastAccess();
63 ClearNode(fRoot);
64}
65
66void AliITSIntMap::ClearNode(AliITSIntMapNode* &node) {
67 // clear this node and all children nodes
68 if (node==NULL) return;
69 ClearNode(node->Left());
70 ClearNode(node->Right());
71 delete node;
72 fNrEntries--;
73 node = NULL;
74 fFastAccess=kFALSE;
75 fFastAccessSerialize=kFALSE;
76}
77
78AliITSIntMap* AliITSIntMap::Clone() const {
79 // returns a clone of the map
80 AliITSIntMapNode* newRoot;
81 newRoot = CloneNode(fRoot);
82 AliITSIntMap* newMap = new AliITSIntMap(newRoot,fNrEntries);
83 return newMap;
84}
85
86AliITSIntMapNode* AliITSIntMap::CloneNode(AliITSIntMapNode* node) const {
87 if (node==NULL) return NULL;
88 else return new AliITSIntMapNode(node->Key(),node->Val(),CloneNode(node->Left()),CloneNode(node->Right()));
b15de2d2 89}
90
91Bool_t AliITSIntMap::Insert(Int_t key, Int_t val) {
92 // insert a new node into the map (returns true if the node was not present before)
53ae21ce 93 UInt_t entriesBefore = fNrEntries;
94 InsertNode(key,val,fRoot,0);
95 if (fNrEntries>entriesBefore) return kTRUE;
96 else return kFALSE;
97}
98
99void AliITSIntMap::InsertNode(Int_t key, Int_t val, AliITSIntMapNode* &node, UInt_t height) {
100 // method to insert a node in the tree (used recursively)
101 height++;
102 if (node==NULL) {
103 node = new AliITSIntMapNode(key,val,NULL,NULL);
b15de2d2 104 fNrEntries++;
53ae21ce 105 fFastAccess=kFALSE;
106 fFastAccessSerialize=kFALSE;
52da6fa6 107 UInt_t balanceHeight = (UInt_t) (TMath::Log(fNrEntries+1)/TMath::Log(2)+1);
53ae21ce 108 if ( (height-balanceHeight)*(height-balanceHeight) > fNrEntries ) {
109 Balance();
b15de2d2 110 }
111 }
53ae21ce 112 else if (key < node->Key()) {
113 InsertNode(key,val,node->Left(),height);
114 }
115 else if (key > node->Key()) {
116 InsertNode(key,val,node->Right(),height);
117 }
118 else { // (key==node->Key()): do nothing (avoid duplicates)
3479cee3 119 // Warning("AliITSIntMap::InsertNode","Node with key %d already in map. Not inserted.",key);
53ae21ce 120 }
b15de2d2 121}
122
123Bool_t AliITSIntMap::Remove(Int_t key) {
124 // remove a node from the map (returns true if the node was found)
53ae21ce 125 UInt_t entriesBefore = fNrEntries;
126 RemoveNode(key,fRoot);
127 if (fNrEntries<entriesBefore) return kTRUE;
128 else return kFALSE;
129}
130
131void AliITSIntMap::RemoveNode(Int_t key, AliITSIntMapNode* &node) {
132 // method to remove a node in the tree (used recursively)
133 if (node == NULL) return; // node not found; do nothing
134 if (key < node->Key()) {
135 RemoveNode(key,node->Left());
136 }
137 else if (key > node->Key()) {
138 RemoveNode(key,node->Right());
139 }
140 else if (node->Left()!=NULL && node->Right()!=NULL) { // Two children
141 if (fNrEntries%2==0) { // for better balance, remove from left or right sub tree
142 AliITSIntMapNode* moveNode = FindMinNode(node->Right());
143 node->SetKey(moveNode->Key());
144 node->SetVal(moveNode->Val());
145 RemoveNode(moveNode->Key(),node->Right());
b15de2d2 146 }
53ae21ce 147 else {
148 AliITSIntMapNode* moveNode = FindMaxNode(node->Left());
149 node->SetKey(moveNode->Key());
150 node->SetVal(moveNode->Val());
151 RemoveNode(moveNode->Key(),node->Left());
b15de2d2 152 }
153 }
53ae21ce 154 else {
155 AliITSIntMapNode* oldNode = node;
156 node = (node->Left()!=NULL) ? node->Left() : node->Right();
157 fNrEntries--;
158 delete oldNode;
159 fFastAccess=kFALSE;
160 fFastAccessSerialize=kFALSE;
161 }
162}
163
164Bool_t AliITSIntMap::Pop(Int_t& key, Int_t& val) {
165 // removes one entry (root) from tree, giving its key,val pair
166 if (fRoot!=NULL) {
167 key = fRoot->Key();
168 val = fRoot->Val();
169 return Remove(key);
170 }
171 else return kFALSE;
172}
173
174AliITSIntMapNode* AliITSIntMap::FindMinNode(AliITSIntMapNode* node) const {
175 // returns the node with smallest key in the sub tree starting from node
176 if (node==NULL) return NULL;
177 else if (node->Left()==NULL) return node;
178 else return FindMinNode(node->Left());
179}
180
181AliITSIntMapNode* AliITSIntMap::FindMaxNode(AliITSIntMapNode* node) const {
182 // returns the node with largest key in the sub tree starting from node
183 if (node==NULL) return NULL;
184 else if (node->Right()==NULL) return node;
185 else return FindMaxNode(node->Right());
b15de2d2 186}
187
188AliITSIntMapNode* AliITSIntMap::Find(Int_t key) const {
189 // finds a node and returns it (returns NULL if not found)
53ae21ce 190 return FindNode(key,fRoot,0);
191}
192
193AliITSIntMapNode* AliITSIntMap::FindNode(Int_t key, AliITSIntMapNode* node, UInt_t height) const {
194 // method to find a node in the tree (used recursively)
195 if (node==NULL) return NULL;
196 height++;
197 if (key<node->Key()) return FindNode(key,node->Left(),height);
198 else if (key>node->Key()) return FindNode(key,node->Right(),height);
199 else { // Match
200// //*** balance if height too high. const above have to be removed if this is needed ***
52da6fa6 201// UInt_t balanceHeight = (UInt_t) (TMath::Log(fNrEntries+1)/TMath::Log(2)+1);
53ae21ce 202// if ( (height-balanceHeight)*(height-balanceHeight) > fNrEntries ) {
203// Balance();
204// }
205 return node;
206 }
207}
208
209Int_t AliITSIntMap::GetVal(Int_t key) const {
210 // returns the value for the node with key
211 AliITSIntMapNode* node = Find(key);
212 if (node!=NULL) {
213 return node->Val();
214 }
215 else {
216 Warning("AliITSIntMap::GetVal","Node with key %d not found in map. Returning -999.",key);
217 return -999;
218 }
219}
220
221void AliITSIntMap::Balance() {
222 // method to balance the tree
223 // printf("balance H=%d --> ",GetTreeHeight());
224 if (fNrEntries==0) return;
225 if (!fFastAccess) InitFastAccess();
226 fRoot = BalanceNode(0,fNrEntries-1);
227 // printf("H=%d\n",GetTreeHeight());
228}
229
230AliITSIntMapNode* AliITSIntMap::BalanceNode(Int_t lowInd, Int_t highInd) {
231 // balances the tree by selecting the center of an index range
232 // (used recursively)
233 if (lowInd>highInd) return NULL;
234 Int_t thisInd = lowInd+(highInd-lowInd)/2;
235 fFastAccessArray[thisInd]->Left() = BalanceNode(lowInd,thisInd-1);
236 fFastAccessArray[thisInd]->Right() = BalanceNode(thisInd+1,highInd);
237 return fFastAccessArray[thisInd];
238}
239
240void AliITSIntMap::ClearFastAccess(){
241 // clears the fast access array of pointers
242 if (fFastAccessArray!=NULL) {
243 delete [] fFastAccessArray;
244 fFastAccessArray=NULL;
245 }
246 fFastAccess=kFALSE;
247 fFastAccessSerialize=kFALSE;
248}
249
250void AliITSIntMap::InitFastAccess(){
251 // initializes the fast access array
6727e2db 252 if (fFastAccess) return;
53ae21ce 253 ClearFastAccess();
b15de2d2 254 if (fNrEntries>0) {
53ae21ce 255 fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
256 fDummyIndex=0;
257 InitFastAccessNode(fRoot);
258 fFastAccess=kTRUE;
259 }
260}
261
262void AliITSIntMap::InitFastAccessNode(AliITSIntMapNode* node) {
263 // initializes the fast access array starting from node (used recursively)
264 if (node==NULL) return;
265 InitFastAccessNode(node->Left());
266 fFastAccessArray[fDummyIndex++] = node;
267 InitFastAccessNode(node->Right());
268}
269
270void AliITSIntMap::InitFastAccessSerialize(){
271 // initializes the fast access array
6727e2db 272 if (fFastAccessSerialize) return;
53ae21ce 273 ClearFastAccess();
274 if (fNrEntries>0) {
275 fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
276 fDummyIndex=0;
277 InitFastAccessSerializeNode(fRoot);
278 fFastAccessSerialize=kTRUE;
b15de2d2 279 }
b15de2d2 280}
281
53ae21ce 282void AliITSIntMap::InitFastAccessSerializeNode(AliITSIntMapNode* node) {
283 // initializes the fast access array for tree ordering starting from node (used recursively)
284 if (node==NULL) return;
285 fFastAccessArray[fDummyIndex++] = node;
286 InitFastAccessSerializeNode(node->Left());
287 InitFastAccessSerializeNode(node->Right());
288}
289
290Int_t AliITSIntMap::GetKeyIndex(UInt_t index) {
b15de2d2 291 // returns the key of the node at position 'index' in the map
292 // returns -1 if out of bounds
53ae21ce 293 if (index<fNrEntries) {
294 if (!fFastAccess && !fFastAccessSerialize) InitFastAccess();
295 return fFastAccessArray[index]->Key();
b15de2d2 296 }
53ae21ce 297 return -1;
b15de2d2 298}
299
53ae21ce 300Int_t AliITSIntMap::GetValIndex(UInt_t index) {
b15de2d2 301 // returns the value of the node at position 'index' in the map
302 // returns -1 if out of bounds
53ae21ce 303 if (index<fNrEntries) {
304 if (!fFastAccess && !fFastAccessSerialize) InitFastAccess();
305 return fFastAccessArray[index]->Val();
306 }
307 return -1;
308}
309
310AliITSIntMapNode* AliITSIntMap::FindNodeIndex(UInt_t index, AliITSIntMapNode* node) const {
311 // method to find the index:th node in the tree (used recursively)
312 // this method should not be needed anymore, since GetKeyIndex/GetValIndex is faster
313 static UInt_t fTmpInd;
314 if (node==fRoot) fTmpInd=0;
315 if (node->Left()!=NULL) {
316 AliITSIntMapNode* tmpResult = FindNodeIndex(index,node->Left());
317 if (tmpResult != NULL) {
318 return tmpResult;
b15de2d2 319 }
b15de2d2 320 }
53ae21ce 321 if (fTmpInd==index) return node;
322 fTmpInd++;
323 if (node->Right()!=NULL) {
324 AliITSIntMapNode* tmpResult = FindNodeIndex(index,node->Right());
325 if (tmpResult != NULL) {
326 return tmpResult;
327 }
b15de2d2 328 }
53ae21ce 329 return NULL;
b15de2d2 330}
331
332void AliITSIntMap::PrintEntries() const {
333 // prints all the entries (key,value pairs) of the map
334 printf("*** Map Entries: (key , value)***\n");
53ae21ce 335 PrintNode(fRoot);
b15de2d2 336 printf("*********************************\n");
337}
53ae21ce 338
339void AliITSIntMap::PrintNode(AliITSIntMapNode* node) const {
340 // method to print node entry (key,value) (used recursively)
341 if (node==NULL) return;
342 if (node->Left()!=NULL) PrintNode(node->Left());
343 printf("%d , %d\n",node->Key(),node->Val());
344 if (node->Right()!=NULL) PrintNode(node->Right());
345}
346
347UInt_t AliITSIntMap::GetTreeHeight() const {
348 // returns the height of the tree
349 return GetTreeHeightNode(fRoot);
350}
351
352UInt_t AliITSIntMap::GetTreeHeightNode(AliITSIntMapNode* node) const {
353 // returns tree height for the sub tree starting from node (used recursively)
354 if (node==NULL) return 0;
355 UInt_t leftH = GetTreeHeightNode(node->Left());
356 UInt_t rightH = GetTreeHeightNode(node->Right());
357 if (leftH>=rightH) return leftH+1;
358 else return rightH+1;
359}