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 }