Line data Source code
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 960 : fNrEntries(0),
15 960 : fRoot(NULL),
16 960 : fFastAccess(kFALSE),
17 960 : fFastAccessSerialize(kFALSE),
18 960 : fFastAccessArray(NULL),
19 960 : fDummyIndex(0)
20 4800 : {}
21 :
22 : AliITSIntMap::AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries):
23 0 : fNrEntries(nrEntries),
24 0 : fRoot(root),
25 0 : fFastAccess(kFALSE),
26 0 : fFastAccessSerialize(kFALSE),
27 0 : fFastAccessArray(NULL),
28 0 : fDummyIndex(0)
29 0 : {}
30 :
31 : AliITSIntMap::AliITSIntMap(const AliITSIntMap& imap):
32 0 : fNrEntries(0),
33 0 : fRoot(NULL),
34 0 : fFastAccess(kFALSE),
35 0 : fFastAccessSerialize(kFALSE),
36 0 : fFastAccessArray(NULL),
37 0 : fDummyIndex(0)
38 0 : {
39 : // copy constructor
40 0 : *this = imap;
41 0 : }
42 :
43 5760 : AliITSIntMap::~AliITSIntMap() {
44 960 : Clear();
45 2880 : }
46 :
47 : AliITSIntMap& AliITSIntMap::operator=(const AliITSIntMap& imap) {
48 : // assignment operator
49 0 : if (this!=&imap) {
50 0 : this->Clear();
51 0 : fRoot = CloneNode(imap.fRoot);
52 0 : fFastAccess=kFALSE;
53 0 : fFastAccessSerialize=kFALSE;
54 0 : fFastAccessArray=NULL;
55 0 : fDummyIndex=0;
56 0 : }
57 0 : return *this;
58 : }
59 :
60 : void AliITSIntMap::Clear() {
61 : // clear the whole map
62 1920 : ClearFastAccess();
63 960 : ClearNode(fRoot);
64 960 : }
65 :
66 : void AliITSIntMap::ClearNode(AliITSIntMapNode* &node) {
67 : // clear this node and all children nodes
68 2512 : if (node==NULL) return;
69 148 : ClearNode(node->Left());
70 148 : ClearNode(node->Right());
71 296 : delete node;
72 148 : fNrEntries--;
73 148 : node = NULL;
74 148 : fFastAccess=kFALSE;
75 148 : fFastAccessSerialize=kFALSE;
76 1404 : }
77 :
78 : AliITSIntMap* AliITSIntMap::Clone() const {
79 : // returns a clone of the map
80 : AliITSIntMapNode* newRoot;
81 0 : newRoot = CloneNode(fRoot);
82 0 : AliITSIntMap* newMap = new AliITSIntMap(newRoot,fNrEntries);
83 0 : return newMap;
84 : }
85 :
86 : AliITSIntMapNode* AliITSIntMap::CloneNode(AliITSIntMapNode* node) const {
87 0 : if (node==NULL) return NULL;
88 0 : else return new AliITSIntMapNode(node->Key(),node->Val(),CloneNode(node->Left()),CloneNode(node->Right()));
89 0 : }
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 296 : UInt_t entriesBefore = fNrEntries;
94 148 : InsertNode(key,val,fRoot,0);
95 296 : if (fNrEntries>entriesBefore) return kTRUE;
96 0 : else return kFALSE;
97 148 : }
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 516 : height++;
102 258 : if (node==NULL) {
103 296 : node = new AliITSIntMapNode(key,val,NULL,NULL);
104 148 : fNrEntries++;
105 148 : fFastAccess=kFALSE;
106 148 : fFastAccessSerialize=kFALSE;
107 148 : UInt_t balanceHeight = (UInt_t) (TMath::Log(fNrEntries+1)/TMath::Log(2)+1);
108 148 : if ( (height-balanceHeight)*(height-balanceHeight) > fNrEntries ) {
109 1 : Balance();
110 1 : }
111 148 : }
112 110 : else if (key < node->Key()) {
113 21 : InsertNode(key,val,node->Left(),height);
114 21 : }
115 89 : else if (key > node->Key()) {
116 89 : InsertNode(key,val,node->Right(),height);
117 89 : }
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 258 : }
122 :
123 : Bool_t AliITSIntMap::Remove(Int_t key) {
124 : // remove a node from the map (returns true if the node was found)
125 0 : UInt_t entriesBefore = fNrEntries;
126 0 : RemoveNode(key,fRoot);
127 0 : if (fNrEntries<entriesBefore) return kTRUE;
128 0 : else return kFALSE;
129 0 : }
130 :
131 : void AliITSIntMap::RemoveNode(Int_t key, AliITSIntMapNode* &node) {
132 : // method to remove a node in the tree (used recursively)
133 0 : if (node == NULL) return; // node not found; do nothing
134 0 : if (key < node->Key()) {
135 0 : RemoveNode(key,node->Left());
136 0 : }
137 0 : else if (key > node->Key()) {
138 0 : RemoveNode(key,node->Right());
139 0 : }
140 0 : else if (node->Left()!=NULL && node->Right()!=NULL) { // Two children
141 0 : if (fNrEntries%2==0) { // for better balance, remove from left or right sub tree
142 0 : AliITSIntMapNode* moveNode = FindMinNode(node->Right());
143 0 : node->SetKey(moveNode->Key());
144 0 : node->SetVal(moveNode->Val());
145 0 : RemoveNode(moveNode->Key(),node->Right());
146 0 : }
147 : else {
148 0 : AliITSIntMapNode* moveNode = FindMaxNode(node->Left());
149 0 : node->SetKey(moveNode->Key());
150 0 : node->SetVal(moveNode->Val());
151 0 : RemoveNode(moveNode->Key(),node->Left());
152 : }
153 : }
154 : else {
155 0 : AliITSIntMapNode* oldNode = node;
156 0 : node = (node->Left()!=NULL) ? node->Left() : node->Right();
157 0 : fNrEntries--;
158 0 : delete oldNode;
159 0 : fFastAccess=kFALSE;
160 0 : fFastAccessSerialize=kFALSE;
161 : }
162 0 : }
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 0 : if (fRoot!=NULL) {
167 0 : key = fRoot->Key();
168 0 : val = fRoot->Val();
169 0 : return Remove(key);
170 : }
171 0 : else return kFALSE;
172 0 : }
173 :
174 : AliITSIntMapNode* AliITSIntMap::FindMinNode(AliITSIntMapNode* node) const {
175 : // returns the node with smallest key in the sub tree starting from node
176 0 : if (node==NULL) return NULL;
177 0 : else if (node->Left()==NULL) return node;
178 0 : else return FindMinNode(node->Left());
179 0 : }
180 :
181 : AliITSIntMapNode* AliITSIntMap::FindMaxNode(AliITSIntMapNode* node) const {
182 : // returns the node with largest key in the sub tree starting from node
183 0 : if (node==NULL) return NULL;
184 0 : else if (node->Right()==NULL) return node;
185 0 : else return FindMaxNode(node->Right());
186 0 : }
187 :
188 : AliITSIntMapNode* AliITSIntMap::Find(Int_t key) const {
189 : // finds a node and returns it (returns NULL if not found)
190 0 : 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 0 : if (node==NULL) return NULL;
196 0 : height++;
197 0 : if (key<node->Key()) return FindNode(key,node->Left(),height);
198 0 : 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 0 : return node;
206 : }
207 0 : }
208 :
209 : Int_t AliITSIntMap::GetVal(Int_t key) const {
210 : // returns the value for the node with key
211 0 : AliITSIntMapNode* node = Find(key);
212 0 : if (node!=NULL) {
213 0 : return node->Val();
214 : }
215 : else {
216 0 : Warning("AliITSIntMap::GetVal","Node with key %d not found in map. Returning -999.",key);
217 0 : return -999;
218 : }
219 0 : }
220 :
221 : void AliITSIntMap::Balance() {
222 : // method to balance the tree
223 : // printf("balance H=%d --> ",GetTreeHeight());
224 2 : if (fNrEntries==0) return;
225 2 : if (!fFastAccess) InitFastAccess();
226 1 : fRoot = BalanceNode(0,fNrEntries-1);
227 : // printf("H=%d\n",GetTreeHeight());
228 2 : }
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 33 : if (lowInd>highInd) return NULL;
234 6 : Int_t thisInd = lowInd+(highInd-lowInd)/2;
235 6 : fFastAccessArray[thisInd]->Left() = BalanceNode(lowInd,thisInd-1);
236 6 : fFastAccessArray[thisInd]->Right() = BalanceNode(thisInd+1,highInd);
237 6 : return fFastAccessArray[thisInd];
238 13 : }
239 :
240 : void AliITSIntMap::ClearFastAccess(){
241 : // clears the fast access array of pointers
242 2060 : if (fFastAccessArray!=NULL) {
243 140 : delete [] fFastAccessArray;
244 70 : fFastAccessArray=NULL;
245 70 : }
246 1030 : fFastAccess=kFALSE;
247 1030 : fFastAccessSerialize=kFALSE;
248 1030 : }
249 :
250 : void AliITSIntMap::InitFastAccess(){
251 : // initializes the fast access array
252 140 : if (fFastAccess) return;
253 70 : ClearFastAccess();
254 70 : if (fNrEntries>0) {
255 70 : fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
256 70 : fDummyIndex=0;
257 70 : InitFastAccessNode(fRoot);
258 70 : fFastAccess=kTRUE;
259 70 : }
260 70 : }
261 :
262 : void AliITSIntMap::InitFastAccessNode(AliITSIntMapNode* node) {
263 : // initializes the fast access array starting from node (used recursively)
264 732 : if (node==NULL) return;
265 148 : InitFastAccessNode(node->Left());
266 148 : fFastAccessArray[fDummyIndex++] = node;
267 148 : InitFastAccessNode(node->Right());
268 514 : }
269 :
270 : void AliITSIntMap::InitFastAccessSerialize(){
271 : // initializes the fast access array
272 0 : if (fFastAccessSerialize) return;
273 0 : ClearFastAccess();
274 0 : if (fNrEntries>0) {
275 0 : fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
276 0 : fDummyIndex=0;
277 0 : InitFastAccessSerializeNode(fRoot);
278 0 : fFastAccessSerialize=kTRUE;
279 0 : }
280 0 : }
281 :
282 : void AliITSIntMap::InitFastAccessSerializeNode(AliITSIntMapNode* node) {
283 : // initializes the fast access array for tree ordering starting from node (used recursively)
284 0 : if (node==NULL) return;
285 0 : fFastAccessArray[fDummyIndex++] = node;
286 0 : InitFastAccessSerializeNode(node->Left());
287 0 : InitFastAccessSerializeNode(node->Right());
288 0 : }
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 296 : if (index<fNrEntries) {
294 286 : if (!fFastAccess && !fFastAccessSerialize) InitFastAccess();
295 148 : return fFastAccessArray[index]->Key();
296 : }
297 0 : return -1;
298 148 : }
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 296 : if (index<fNrEntries) {
304 148 : if (!fFastAccess && !fFastAccessSerialize) InitFastAccess();
305 148 : return fFastAccessArray[index]->Val();
306 : }
307 0 : return -1;
308 148 : }
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 0 : if (node==fRoot) fTmpInd=0;
315 0 : if (node->Left()!=NULL) {
316 0 : AliITSIntMapNode* tmpResult = FindNodeIndex(index,node->Left());
317 0 : if (tmpResult != NULL) {
318 0 : return tmpResult;
319 : }
320 0 : }
321 0 : if (fTmpInd==index) return node;
322 0 : fTmpInd++;
323 0 : if (node->Right()!=NULL) {
324 0 : AliITSIntMapNode* tmpResult = FindNodeIndex(index,node->Right());
325 0 : if (tmpResult != NULL) {
326 0 : return tmpResult;
327 : }
328 0 : }
329 0 : return NULL;
330 0 : }
331 :
332 : void AliITSIntMap::PrintEntries() const {
333 : // prints all the entries (key,value pairs) of the map
334 0 : printf("*** Map Entries: (key , value)***\n");
335 0 : PrintNode(fRoot);
336 0 : printf("*********************************\n");
337 0 : }
338 :
339 : void AliITSIntMap::PrintNode(AliITSIntMapNode* node) const {
340 : // method to print node entry (key,value) (used recursively)
341 0 : if (node==NULL) return;
342 0 : if (node->Left()!=NULL) PrintNode(node->Left());
343 0 : printf("%d , %d\n",node->Key(),node->Val());
344 0 : if (node->Right()!=NULL) PrintNode(node->Right());
345 0 : }
346 :
347 : UInt_t AliITSIntMap::GetTreeHeight() const {
348 : // returns the height of the tree
349 0 : 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 0 : if (node==NULL) return 0;
355 0 : UInt_t leftH = GetTreeHeightNode(node->Left());
356 0 : UInt_t rightH = GetTreeHeightNode(node->Right());
357 0 : if (leftH>=rightH) return leftH+1;
358 0 : else return rightH+1;
359 0 : }
|
