]>
Commit | Line | Data |
---|---|---|
b15de2d2 | 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 | |
03fc6773 | 21 | for (UInt_t index=0; index<imap.fNrEntries; index++) { |
b15de2d2 | 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(); | |
03fc6773 | 33 | for (UInt_t index=0; index<imap.fNrEntries; index++) { |
b15de2d2 | 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 | } |