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 //////////////////////////////////////////////////////////////////////
8 #include "AliITSIntMap.h"
9 #include "AliITSIntMapNode.h"
11 AliITSIntMap::AliITSIntMap():
16 AliITSIntMap::AliITSIntMap(const AliITSIntMap& imap):
21 for (UInt_t index=0; index<imap.fNrEntries; index++) {
22 this->Insert(imap.GetKey(index),imap.GetVal(index));
26 AliITSIntMap::~AliITSIntMap()
29 AliITSIntMap& AliITSIntMap::operator=(const AliITSIntMap& imap) {
30 // assignment operator
33 for (UInt_t index=0; index<imap.fNrEntries; index++) {
34 this->Insert(imap.GetKey(index),imap.GetVal(index));
40 void AliITSIntMap::Clear() {
41 // clear the whole map
42 while (fNrEntries>0) {
43 Remove(fFirst->GetKey());
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)
50 fFirst = new AliITSIntMapNode(key, val, NULL);
55 AliITSIntMapNode* it1 = fFirst;
56 AliITSIntMapNode* it2 = fFirst->GetNext();
57 while (it2!=NULL && key > it2->GetKey()) {
61 if (key < it1->GetKey()) {
62 fFirst = new AliITSIntMapNode(key, val, it1);
66 else if (key > it1->GetKey() &&
67 ( (it2!=NULL && key < it2->GetKey()) || (it2==NULL) )
69 it1->SetNext(new AliITSIntMapNode(key, val, it2));
77 Bool_t AliITSIntMap::Remove(Int_t key) {
78 // remove a node from the map (returns true if the node was found)
80 AliITSIntMapNode* it1 = fFirst;
81 AliITSIntMapNode* it2 = fFirst->GetNext();
82 while (it2!=NULL && key > it2->GetKey()) {
86 if (key == it1->GetKey()) {
87 fFirst = it1->GetNext();
92 else if (it2 != NULL && key == it2->GetKey()) {
93 it1->SetNext(it2->GetNext());
102 AliITSIntMapNode* AliITSIntMap::Find(Int_t key) const {
103 // finds a node and returns it (returns NULL if not found)
105 AliITSIntMapNode* it1 = fFirst;
106 AliITSIntMapNode* it2 = fFirst->GetNext();
107 while (it2!=NULL && key > it2->GetKey()) {
109 it2 = it1->GetNext();
111 if (key == it1->GetKey()) {
114 else if (it2 != NULL && key == it2->GetKey()) {
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();
129 return it1->GetKey();
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();
144 return it1->GetVal();
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();
159 printf("*********************************\n");