ITS/AliITSIntMap.cxx

   1 //////////////////////////////////////////////////////////////////////
   2 // Author: Henrik Tydesjo                                           //
   3 // This class implements the use of a map of integers.              //
   4 // For simplicity, this version is just a sorted linked list,       //
   5 // but it may be rewritten later for better performance if required.//
   6 //////////////////////////////////////////////////////////////////////
   7
   8 #include "AliITSIntMap.h"
   9 #include "AliITSIntMapNode.h"
  10
  11 AliITSIntMap::AliITSIntMap():
  12   fNrEntries(0),
  13   fFirst(0)
  14 {}
  15
  16 AliITSIntMap::AliITSIntMap(const AliITSIntMap& imap):
  17   fNrEntries(0),
  18   fFirst(0)
  19 {
  20   // copy constructor
  21   for (UInt_t index=0; index<imap.fNrEntries; index++) {
  22     this->Insert(imap.GetKey(index),imap.GetVal(index));
  23   }
  24 }
  25
  26 AliITSIntMap::~AliITSIntMap()
  27 {}
  28
  29 AliITSIntMap& AliITSIntMap::operator=(const AliITSIntMap& imap) {
  30   // assignment operator
  31   if (this!=&imap) {
  32     this->Clear();
  33     for (UInt_t index=0; index<imap.fNrEntries; index++) {
  34       this->Insert(imap.GetKey(index),imap.GetVal(index));
  35     }
  36   }
  37   return *this;
  38 }
  39
  40 void AliITSIntMap::Clear() {
  41   // clear the whole map
  42   while (fNrEntries>0) {
  43     Remove(fFirst->GetKey());
  44   }
  45 }
  46
  47 Bool_t AliITSIntMap::Insert(Int_t key, Int_t val) {
  48   // insert a new node into the map (returns true if the node was not present before)
  49   if (fNrEntries==0) {
  50     fFirst = new AliITSIntMapNode(key, val, NULL);
  51     fNrEntries++;
  52     return kTRUE;
  53   }
  54   else {
  55     AliITSIntMapNode* it1 = fFirst;
  56     AliITSIntMapNode* it2 = fFirst->GetNext();
  57     while (it2!=NULL && key > it2->GetKey()) {
  58       it1 = it2;
  59       it2 = it1->GetNext();
  60     }
  61     if (key < it1->GetKey()) {
  62       fFirst = new AliITSIntMapNode(key, val, it1);
  63       fNrEntries++;
  64       return kTRUE;
  65     }
  66     else if (key > it1->GetKey() &&
  67              ( (it2!=NULL && key < it2->GetKey()) || (it2==NULL) )
  68              ) {
  69       it1->SetNext(new AliITSIntMapNode(key, val, it2));
  70       fNrEntries++;
  71       return kTRUE;
  72     }
  73   }
  74   return kFALSE;
  75 }
  76
  77 Bool_t AliITSIntMap::Remove(Int_t key) {
  78   // remove a node from the map (returns true if the node was found)
  79   if (fNrEntries>0) {
  80     AliITSIntMapNode* it1 = fFirst;
  81     AliITSIntMapNode* it2 = fFirst->GetNext();
  82     while (it2!=NULL && key > it2->GetKey()) {
  83       it1 = it2;
  84       it2 = it1->GetNext();
  85     }
  86     if (key == it1->GetKey()) {
  87       fFirst = it1->GetNext();
  88       delete it1;
  89       fNrEntries--;
  90       return kTRUE;
  91     }
  92     else if (it2 != NULL && key == it2->GetKey()) {
  93       it1->SetNext(it2->GetNext());
  94       delete it2;
  95       fNrEntries--;
  96       return kTRUE;
  97     }
  98   }
  99   return kFALSE;
 100 }
 101
 102 AliITSIntMapNode* AliITSIntMap::Find(Int_t key) const {
 103   // finds a node and returns it (returns NULL if not found)
 104   if (fNrEntries>0) {
 105     AliITSIntMapNode* it1 = fFirst;
 106     AliITSIntMapNode* it2 = fFirst->GetNext();
 107     while (it2!=NULL && key > it2->GetKey()) {
 108       it1 = it2;
 109       it2 = it1->GetNext();
 110     }
 111     if (key == it1->GetKey()) {
 112       return it1;
 113     }
 114     else if (it2 != NULL && key == it2->GetKey()) {
 115       return it2;
 116     }
 117   }
 118   return NULL;
 119 }
 120
 121 Int_t AliITSIntMap::GetKey(UInt_t index) const {
 122   // returns the key of the node at position 'index' in the map
 123   // returns -1 if out of bounds
 124   if (index < fNrEntries) {
 125     AliITSIntMapNode* it1 = fFirst;
 126     for (UInt_t i=0; i<index; i++) {
 127       it1 = it1->GetNext();
 128     }
 129     return it1->GetKey();
 130   }
 131   else {
 132     return -1;
 133   }
 134 }
 135
 136 Int_t AliITSIntMap::GetVal(UInt_t index) const {
 137   // returns the value of the node at position 'index' in the map
 138   // returns -1 if out of bounds
 139   if (index < fNrEntries) {
 140     AliITSIntMapNode* it1 = fFirst;
 141     for (UInt_t i=0; i<index; i++) {
 142       it1 = it1->GetNext();
 143     }
 144     return it1->GetVal();
 145   }
 146   else {
 147     return -1;
 148   }
 149 }
 150
 151 void AliITSIntMap::PrintEntries() const {
 152   // prints all the entries (key,value pairs) of the map
 153   printf("*** Map Entries: (key , value)***\n");
 154   AliITSIntMapNode* it1 = fFirst;
 155   for (UInt_t i=0; i<fNrEntries; i++) {
 156     printf("%d , %d\n",it1->GetKey(),it1->GetVal());
 157     it1 = it1->GetNext();
 158   }
 159   printf("*********************************\n");
 160 }