]>
Commit | Line | Data |
---|---|---|
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 | |
13 | AliITSIntMap::AliITSIntMap(): | |
14 | fNrEntries(0), | |
53ae21ce | 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) | |
b15de2d2 | 29 | {} |
30 | ||
31 | AliITSIntMap::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 | 43 | AliITSIntMap::~AliITSIntMap() { |
44 | Clear(); | |
45 | } | |
b15de2d2 | 46 | |
47 | AliITSIntMap& 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 | ||
60 | void AliITSIntMap::Clear() { | |
61 | // clear the whole map | |
53ae21ce | 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())); | |
b15de2d2 | 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) | |
53ae21ce | 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); | |
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 | ||
123 | Bool_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 | ||
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()); | |
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 | ||
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()); | |
b15de2d2 | 186 | } |
187 | ||
188 | AliITSIntMapNode* 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 | ||
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 *** | |
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 | ||
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 | |
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 | ||
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 | |
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 | 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) { | |
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 | 300 | Int_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 | ||
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; | |
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 | ||
332 | void 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 | |
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 | } |