0026937: Eliminate NO_CXX_EXCEPTION macro support
[occt.git] / src / TCollection / TCollection_IndexedMap.gxx
1 // Created on: 1993-01-08
2 // Created by: Remi LEQUETTE
3 // Copyright (c) 1993-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17 #include <Standard_DomainError.hxx>
18 #include <Standard_MultiplyDefined.hxx>
19 #include <Standard_NoSuchObject.hxx>
20 #include <Standard_OutOfRange.hxx>
21 #include <TCollection_BasicMapIterator.hxx>
22
23
24 //=======================================================================
25 //function : TCollection_IndexedMap
26 //purpose  : 
27 //=======================================================================
28
29 TCollection_IndexedMap::TCollection_IndexedMap
30   (const Standard_Integer NbBuckets):
31   TCollection_BasicMap(NbBuckets,Standard_False)
32 {
33 }
34
35 //=======================================================================
36 //function : TCollection_IndexedMap
37 //purpose  : 
38 //=======================================================================
39
40 TCollection_IndexedMap::TCollection_IndexedMap
41   (const TCollection_IndexedMap& Other) :
42   TCollection_BasicMap(Other.NbBuckets(),Standard_False)
43 {
44   if  (!Other.IsEmpty()) { 
45     ReSize(Other.Extent());
46     for (Standard_Integer i = 1; i <= Other.Extent(); i++) {
47       Add(Other(i));
48     }
49   }
50 }
51
52 //=======================================================================
53 //function : Assign
54 //purpose  : 
55 //=======================================================================
56
57 TCollection_IndexedMap& TCollection_IndexedMap::Assign
58   (const TCollection_IndexedMap& Other)
59 {
60   // very simple implementation
61   // not optimal (recompute the hashcode values)
62
63   if (this == &Other) return *this;
64   Clear();
65 //  ReSize(Other.NbBuckets());
66   if  (!Other.IsEmpty()) { 
67     ReSize(Other.Extent());
68     for (Standard_Integer i = 1; i <= Other.Extent(); i++) {
69       Add(Other(i));
70     }
71   }
72   return *this;
73 }
74
75 //=======================================================================
76 //function : ReSize
77 //purpose  : 
78 //=======================================================================
79
80 void TCollection_IndexedMap::ReSize(const Standard_Integer N)
81 {
82   Standard_Integer newBuck;
83   Standard_Address newData1, newData2;
84   if (BeginResize(N,newBuck,newData1,newData2)) {
85     if (myData1) {
86       TCollection_IndexedMapNode** newdata1 = (TCollection_IndexedMapNode**)newData1;
87       TCollection_IndexedMapNode** newdata2 = (TCollection_IndexedMapNode**)newData2;
88       TCollection_IndexedMapNode** olddata1 = (TCollection_IndexedMapNode**) myData1;
89       TCollection_IndexedMapNode *p, *q;
90       Standard_Integer i,k1,k2;
91       for (i = 0; i <= NbBuckets(); i++) {
92         if (olddata1[i]) {
93           p = olddata1[i];
94           while (p) {
95             k1 = Hasher::HashCode(p->Key1(),newBuck);
96             q = (TCollection_IndexedMapNode*) p->Next();
97             p->Next() = newdata1[k1];
98             newdata1[k1] = p;
99             if (p->Key2() > 0) {
100               k2 = ::HashCode(p->Key2(),newBuck);
101               p->Next2() = newdata2[k2];
102               newdata2[k2] = p;
103             }
104             p = q;
105           }
106         }
107       }
108     }
109     EndResize(N,newBuck,newData1,newData2);
110   }
111 }
112
113 //=======================================================================
114 //function : Clear
115 //purpose  : 
116 //=======================================================================
117
118 void TCollection_IndexedMap::Clear()
119 {
120   if (!IsEmpty()) {
121     Standard_Integer i;
122     TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**) myData1;
123 //    TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**) myData2;
124     TCollection_IndexedMapNode *p,*q;
125     for (i = 0; i <= NbBuckets(); i++) {
126       p = data1[i];
127       while (p) {
128         q = (TCollection_IndexedMapNode*) p->Next();
129         delete p;
130         p = q;
131       }
132     }
133   }
134   TCollection_BasicMap::Destroy();
135 }
136
137 //=======================================================================
138 //function : Add
139 //purpose  : 
140 //=======================================================================
141
142 Standard_Integer TCollection_IndexedMap::Add(const TheKey& K1)
143 {
144   if (Resizable())  ReSize(Extent());
145   TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
146   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
147   TCollection_IndexedMapNode* p;
148   p = data1[k1];
149   while (p) {
150     if (Hasher::IsEqual(p->Key1(),K1)) 
151       return p->Key2();
152     p = (TCollection_IndexedMapNode*) p->Next();
153   }
154   Increment();
155   TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
156   Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
157   p = new TCollection_IndexedMapNode(K1,Extent(),data1[k1],data2[k2]);
158   data1[k1] = p;
159   data2[k2] = p;
160   return Extent();
161 }
162
163 //=======================================================================
164 //function : Substitute
165 //purpose  : 
166 //=======================================================================
167
168 void TCollection_IndexedMap::Substitute(const Standard_Integer I,
169                                         const TheKey& K1)
170 {
171   Standard_OutOfRange_Raise_if(I < 1 || I > Extent(), "IndexedMap::Substitute : "
172                                                       "Index is out of range");
173   TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
174   TCollection_IndexedMapNode* p;
175
176   // check if K1 is not already in the map
177   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
178   p = data1[k1];
179   while (p) {
180     if (Hasher::IsEqual(p->Key1(),K1)) {
181       if (p->Key2() != I)
182         throw Standard_DomainError("IndexedMap::Substitute : "
183                                    "Attempt to substitute existing key");
184       p->Key1() = K1;
185       return;
186     }
187     p = (TCollection_IndexedMapNode*) p->Next();
188   }
189
190   // Find the node for the index I
191   TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
192   Standard_Integer k2 = ::HashCode(I,NbBuckets());
193   p = data2[k2];
194   while (p) {
195     if (p->Key2() == I)
196       break;
197     p = (TCollection_IndexedMapNode*) p->Next2();
198   }
199
200   // remove the old key
201   Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
202   TCollection_IndexedMapNode* q = data1[k];
203   if (q == p) data1[k] = (TCollection_IndexedMapNode*) p->Next();
204   else {
205     while(q->Next() != p) q = (TCollection_IndexedMapNode*) q->Next();
206     q->Next() = p->Next();
207   }
208
209   // update the node
210   p->Key1() = K1;
211   p->Next() = data1[k1];
212   data1[k1] = p;
213 }
214
215 //=======================================================================
216 //function : RemoveLast
217 //purpose  : 
218 //=======================================================================
219
220 void TCollection_IndexedMap::RemoveLast()
221 {
222   Standard_OutOfRange_Raise_if(Extent() == 0,
223                                "IndexedMap::RemoveLast");
224   TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
225   TCollection_IndexedMapNode* p;
226   TCollection_IndexedMapNode* q;
227
228   // Find the node for the last index and remove it
229   TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
230   Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
231   p = data2[k2];
232   q = NULL;
233   while (p) {
234     if (p->Key2() == Extent())
235       break;
236     q = p;
237     p = (TCollection_IndexedMapNode*) p->Next2();
238   }
239   if (q == NULL) 
240     data2[k2] = (TCollection_IndexedMapNode*)p->Next2();
241   else 
242     q->Next2() = p->Next2();
243
244   // remove the key
245   Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
246   q = data1[k];
247   if (q == p) data1[k] = (TCollection_IndexedMapNode*) p->Next();
248   else {
249     while(q->Next() != p) q = (TCollection_IndexedMapNode*) q->Next();
250     q->Next() = p->Next();
251   }
252
253   Decrement();
254   delete p;
255 }
256
257 //=======================================================================
258 //function : Contains
259 //purpose  : 
260 //=======================================================================
261
262 Standard_Boolean TCollection_IndexedMap::Contains(const TheKey& K1) const
263 {
264   if (IsEmpty()) return Standard_False;
265   TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
266   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
267   TCollection_IndexedMapNode *p1;
268   p1 = data1[k1];
269   while (p1) {
270     if (Hasher::IsEqual(p1->Key1(),K1)) return Standard_True;
271     p1 = (TCollection_IndexedMapNode*) p1->Next();
272   }
273   return Standard_False;
274 }
275
276 //=======================================================================
277 //function : FindKey
278 //purpose  : 
279 //=======================================================================
280
281 const TheKey& TCollection_IndexedMap::FindKey(const Standard_Integer K2) const
282 {
283   Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedMap");
284   TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
285   Standard_Integer k2 = ::HashCode(K2,NbBuckets());
286   TCollection_IndexedMapNode *p2;
287   p2 = data2[k2];
288   while (p2) {
289     if (p2->Key2() == K2) return p2->Key1();
290     p2 = (TCollection_IndexedMapNode*)p2->Next2();
291   }
292   throw Standard_OutOfRange("IndexedMap : missing index !!!");
293   return p2->Key1();
294 }
295
296 //=======================================================================
297 //function : FindIndex
298 //purpose  : 
299 //=======================================================================
300
301 Standard_Integer TCollection_IndexedMap::FindIndex(const TheKey& K1) const
302 {
303   if (IsEmpty()) return 0;
304   TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
305   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
306   TCollection_IndexedMapNode *p1;
307   p1 = data1[k1];
308   while (p1) {
309     if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Key2();
310     p1 = (TCollection_IndexedMapNode*) p1->Next();
311   }
312   return 0;
313 }