Update for Ds
[u/mrichter/AliRoot.git] / ITS / AliITSIntMap.cxx
1 //////////////////////////////////////////////////////////////////////
2 // Author: Henrik Tydesjo                                           //
3 // This class implements the use of a map of integers.              //
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//
6 //////////////////////////////////////////////////////////////////////  
7
8 #include "AliITSIntMap.h"
9 #include "AliITSIntMapNode.h"
10 #include <TMath.h>
11 #include <TError.h>
12
13 AliITSIntMap::AliITSIntMap():
14   fNrEntries(0),
15   fRoot(NULL),
16   fFastAccess(kFALSE),
17   fFastAccessSerialize(kFALSE),
18   fFastAccessArray(NULL),
19   fDummyIndex(0)
20 {}
21
22 AliITSIntMap::AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries):
23   fNrEntries(nrEntries),
24   fRoot(root),
25   fFastAccess(kFALSE),
26   fFastAccessSerialize(kFALSE),
27   fFastAccessArray(NULL),
28   fDummyIndex(0)
29 {}
30
31 AliITSIntMap::AliITSIntMap(const AliITSIntMap& imap):
32   fNrEntries(0),
33   fRoot(NULL),
34   fFastAccess(kFALSE),
35   fFastAccessSerialize(kFALSE),
36   fFastAccessArray(NULL),
37   fDummyIndex(0)
38 {
39   // copy constructor
40   *this = imap;
41 }
42
43 AliITSIntMap::~AliITSIntMap() {
44   Clear();
45 }
46
47 AliITSIntMap& AliITSIntMap::operator=(const AliITSIntMap& imap) {
48   // assignment operator
49   if (this!=&imap) {
50     this->Clear();
51     fRoot = CloneNode(imap.fRoot);
52     fFastAccess=kFALSE;
53     fFastAccessSerialize=kFALSE;
54     fFastAccessArray=NULL;
55     fDummyIndex=0;
56   }
57   return *this;
58 }
59
60 void AliITSIntMap::Clear() {
61   // clear the whole map
62   ClearFastAccess();
63   ClearNode(fRoot);
64 }
65
66 void 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
78 AliITSIntMap* 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
86 AliITSIntMapNode* 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()));
89 }
90
91 Bool_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)
93   UInt_t entriesBefore = fNrEntries;
94   InsertNode(key,val,fRoot,0);
95   if (fNrEntries>entriesBefore) return kTRUE;
96   else return kFALSE;
97 }
98
99 void 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);
104     fNrEntries++;
105     fFastAccess=kFALSE;
106     fFastAccessSerialize=kFALSE;
107     UInt_t balanceHeight = (UInt_t) (TMath::Log(fNrEntries+1)/TMath::Log(2)+1);
108     if ( (height-balanceHeight)*(height-balanceHeight) > fNrEntries ) {
109       Balance();
110     }
111   }
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)
119     //    Warning("AliITSIntMap::InsertNode","Node with key %d already in map. Not inserted.",key);
120   }
121 }
122
123 Bool_t AliITSIntMap::Remove(Int_t key) {
124   // remove a node from the map (returns true if the node was found)
125   UInt_t entriesBefore = fNrEntries;
126   RemoveNode(key,fRoot);
127   if (fNrEntries<entriesBefore) return kTRUE;
128   else return kFALSE;
129 }
130
131 void 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());
146     }
147     else {
148       AliITSIntMapNode* moveNode = FindMaxNode(node->Left());
149       node->SetKey(moveNode->Key());
150       node->SetVal(moveNode->Val());
151       RemoveNode(moveNode->Key(),node->Left());
152     }
153   }
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
164 Bool_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
174 AliITSIntMapNode* 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
181 AliITSIntMapNode* 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());
186 }
187
188 AliITSIntMapNode* AliITSIntMap::Find(Int_t key) const {
189   // finds a node and returns it (returns NULL if not found)
190   return FindNode(key,fRoot,0);
191 }
192
193 AliITSIntMapNode*  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 ***
201 //    UInt_t balanceHeight = (UInt_t) (TMath::Log(fNrEntries+1)/TMath::Log(2)+1);
202 //    if ( (height-balanceHeight)*(height-balanceHeight) > fNrEntries ) {
203 //      Balance();
204 //    }
205     return node;
206   }
207 }
208
209 Int_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
221 void 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
230 AliITSIntMapNode* 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
240 void 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
250 void AliITSIntMap::InitFastAccess(){
251   // initializes the fast access array
252   if (fFastAccess) return;
253   ClearFastAccess();
254   if (fNrEntries>0) {
255     fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
256     fDummyIndex=0;
257     InitFastAccessNode(fRoot);
258     fFastAccess=kTRUE;
259   }
260 }
261
262 void 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
270 void AliITSIntMap::InitFastAccessSerialize(){
271   // initializes the fast access array
272   if (fFastAccessSerialize) return;
273   ClearFastAccess();
274   if (fNrEntries>0) {
275     fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
276     fDummyIndex=0;
277     InitFastAccessSerializeNode(fRoot);
278     fFastAccessSerialize=kTRUE;
279   }
280 }
281
282 void 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
290 Int_t AliITSIntMap::GetKeyIndex(UInt_t index) {
291   // returns the key of the node at position 'index' in the map
292   // returns -1 if out of bounds
293   if (index<fNrEntries) {
294     if (!fFastAccess && !fFastAccessSerialize) InitFastAccess();
295     return fFastAccessArray[index]->Key();
296   }
297   return -1;
298 }
299
300 Int_t AliITSIntMap::GetValIndex(UInt_t index) {
301   // returns the value of the node at position 'index' in the map
302   // returns -1 if out of bounds
303   if (index<fNrEntries) {
304     if (!fFastAccess && !fFastAccessSerialize) InitFastAccess();
305     return fFastAccessArray[index]->Val();
306   }
307   return -1;
308 }
309
310 AliITSIntMapNode* 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;
319     }
320   }
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     }
328   }
329   return NULL;
330 }
331
332 void AliITSIntMap::PrintEntries() const {
333   // prints all the entries (key,value pairs) of the map
334   printf("*** Map Entries: (key , value)***\n");
335   PrintNode(fRoot);
336   printf("*********************************\n");
337 }
338
339 void 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
347 UInt_t AliITSIntMap::GetTreeHeight() const {
348   // returns the height of the tree
349   return GetTreeHeightNode(fRoot);
350 }
351
352 UInt_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 }