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 //////////////////////////////////////////////////////////////////////
8 #include "AliITSIntMap.h"
9 #include "AliITSIntMapNode.h"
13 AliITSIntMap::AliITSIntMap():
17 fFastAccessSerialize(kFALSE),
18 fFastAccessArray(NULL),
22 AliITSIntMap::AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries):
23 fNrEntries(nrEntries),
26 fFastAccessSerialize(kFALSE),
27 fFastAccessArray(NULL),
31 AliITSIntMap::AliITSIntMap(const AliITSIntMap& imap):
35 fFastAccessSerialize(kFALSE),
36 fFastAccessArray(NULL),
43 AliITSIntMap::~AliITSIntMap() {
47 AliITSIntMap& AliITSIntMap::operator=(const AliITSIntMap& imap) {
48 // assignment operator
51 fRoot = CloneNode(imap.fRoot);
53 fFastAccessSerialize=kFALSE;
54 fFastAccessArray=NULL;
60 void AliITSIntMap::Clear() {
61 // clear the whole map
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());
75 fFastAccessSerialize=kFALSE;
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);
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()));
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;
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)
103 node = new AliITSIntMapNode(key,val,NULL,NULL);
106 fFastAccessSerialize=kFALSE;
107 UInt_t balanceHeight = (UInt_t) (TMath::Log(fNrEntries+1)/TMath::Log(2)+1);
108 if ( (height-balanceHeight)*(height-balanceHeight) > fNrEntries ) {
112 else if (key < node->Key()) {
113 InsertNode(key,val,node->Left(),height);
115 else if (key > node->Key()) {
116 InsertNode(key,val,node->Right(),height);
118 else { // (key==node->Key()): do nothing (avoid duplicates)
119 // Warning("AliITSIntMap::InsertNode","Node with key %d already in map. Not inserted.",key);
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;
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());
137 else if (key > node->Key()) {
138 RemoveNode(key,node->Right());
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());
148 AliITSIntMapNode* moveNode = FindMaxNode(node->Left());
149 node->SetKey(moveNode->Key());
150 node->SetVal(moveNode->Val());
151 RemoveNode(moveNode->Key(),node->Left());
155 AliITSIntMapNode* oldNode = node;
156 node = (node->Left()!=NULL) ? node->Left() : node->Right();
160 fFastAccessSerialize=kFALSE;
164 Bool_t AliITSIntMap::Pop(Int_t& key, Int_t& val) {
165 // removes one entry (root) from tree, giving its key,val pair
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());
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());
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);
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;
197 if (key<node->Key()) return FindNode(key,node->Left(),height);
198 else if (key>node->Key()) return FindNode(key,node->Right(),height);
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 ) {
209 Int_t AliITSIntMap::GetVal(Int_t key) const {
210 // returns the value for the node with key
211 AliITSIntMapNode* node = Find(key);
216 Warning("AliITSIntMap::GetVal","Node with key %d not found in map. Returning -999.",key);
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());
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];
240 void AliITSIntMap::ClearFastAccess(){
241 // clears the fast access array of pointers
242 if (fFastAccessArray!=NULL) {
243 delete [] fFastAccessArray;
244 fFastAccessArray=NULL;
247 fFastAccessSerialize=kFALSE;
250 void AliITSIntMap::InitFastAccess(){
251 // initializes the fast access array
252 if (fFastAccess) return;
255 fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
257 InitFastAccessNode(fRoot);
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());
270 void AliITSIntMap::InitFastAccessSerialize(){
271 // initializes the fast access array
272 if (fFastAccessSerialize) return;
275 fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
277 InitFastAccessSerializeNode(fRoot);
278 fFastAccessSerialize=kTRUE;
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());
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();
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();
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) {
321 if (fTmpInd==index) return node;
323 if (node->Right()!=NULL) {
324 AliITSIntMapNode* tmpResult = FindNodeIndex(index,node->Right());
325 if (tmpResult != NULL) {
332 void AliITSIntMap::PrintEntries() const {
333 // prints all the entries (key,value pairs) of the map
334 printf("*** Map Entries: (key , value)***\n");
336 printf("*********************************\n");
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());
347 UInt_t AliITSIntMap::GetTreeHeight() const {
348 // returns the height of the tree
349 return GetTreeHeightNode(fRoot);
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;