7fd59977 |
1 | // Lastly modified by : |
2 | // +---------------------------------------------------------------------------+ |
3 | // ! szy ! Modified Assign method ! 7-05-2003! 3.0-00-2! |
4 | // +---------------------------------------------------------------------------+ |
5 | // File: TCollection_IndexedDataMap.gxx |
6 | // Created: Fri Jan 8 19:25:35 1993 |
7 | // Author: Remi LEQUETTE |
8 | // <rle@phylox> |
9 | |
10 | |
11 | #include <Standard_DomainError.hxx> |
12 | #include <Standard_MultiplyDefined.hxx> |
13 | #include <Standard_NoSuchObject.hxx> |
14 | #include <Standard_OutOfRange.hxx> |
15 | #include <TCollection_BasicMapIterator.hxx> |
16 | |
17 | //======================================================================= |
18 | //function : TCollection_IndexedDataMap |
19 | //purpose : |
20 | //======================================================================= |
21 | |
22 | TCollection_IndexedDataMap::TCollection_IndexedDataMap |
23 | (const Standard_Integer NbBuckets): |
24 | TCollection_BasicMap(NbBuckets,Standard_False) |
25 | { |
26 | } |
27 | |
28 | //======================================================================= |
29 | //function : TCollection_IndexedDataMap |
30 | //purpose : |
31 | //======================================================================= |
32 | |
33 | TCollection_IndexedDataMap::TCollection_IndexedDataMap |
34 | (const TCollection_IndexedDataMap& Other) : |
35 | TCollection_BasicMap(Other.NbBuckets(),Standard_False) |
36 | { |
37 | if (Other.Extent() != 0) |
38 | Standard_DomainError::Raise("TCollection:Copy of non empty IndexedDataMap"); |
39 | } |
40 | |
41 | //======================================================================= |
42 | //function : Assign |
43 | //purpose : |
44 | //======================================================================= |
45 | |
46 | TCollection_IndexedDataMap& TCollection_IndexedDataMap::Assign |
47 | (const TCollection_IndexedDataMap& Other) |
48 | { |
49 | // very simple implementation |
50 | // not optimal (recompute the hashcode values) |
51 | |
52 | if (this == &Other) return *this; |
53 | Clear(); |
54 | // ReSize(Other.NbBuckets()); |
55 | if (!Other.IsEmpty()) { |
56 | ReSize(Other.Extent()); |
57 | for (Standard_Integer i = 1; i <= Other.Extent(); i++) { |
58 | Add(Other.FindKey(i),Other(i)); |
59 | } |
60 | } |
61 | return *this; |
62 | } |
63 | |
64 | |
65 | |
66 | //======================================================================= |
67 | //function : ReSize |
68 | //purpose : |
69 | //======================================================================= |
70 | |
71 | void TCollection_IndexedDataMap::ReSize(const Standard_Integer N) |
72 | { |
73 | Standard_Integer newBuck; |
74 | Standard_Address newData1=NULL, newData2=NULL; |
75 | if (BeginResize(N,newBuck,newData1,newData2)) { |
76 | if (myData1) { |
77 | TCollection_IndexedDataMapNode** newdata1 = (TCollection_IndexedDataMapNode**)newData1; |
78 | TCollection_IndexedDataMapNode** newdata2 = (TCollection_IndexedDataMapNode**)newData2; |
79 | TCollection_IndexedDataMapNode** olddata1 = (TCollection_IndexedDataMapNode**) myData1; |
80 | TCollection_IndexedDataMapNode *p, *q; |
81 | Standard_Integer i,k1,k2; |
82 | for (i = 0; i <= NbBuckets(); i++) { |
83 | if (olddata1[i]) { |
84 | p = olddata1[i]; |
85 | while (p) { |
86 | k1 = Hasher::HashCode(p->Key1(),newBuck); |
87 | k2 = ::HashCode(p->Key2(),newBuck); |
88 | q = (TCollection_IndexedDataMapNode*)p->Next(); |
89 | p->Next() = newdata1[k1]; |
90 | p->Next2() = newdata2[k2]; |
91 | newdata1[k1] = p; |
92 | newdata2[k2] = p; |
93 | p = q; |
94 | } |
95 | } |
96 | } |
97 | } |
98 | EndResize(N,newBuck,newData1,newData2); |
99 | } |
100 | } |
101 | |
102 | //======================================================================= |
103 | //function : Clear |
104 | //purpose : |
105 | //======================================================================= |
106 | |
107 | void TCollection_IndexedDataMap::Clear() |
108 | { |
109 | if (!IsEmpty()) { |
110 | Standard_Integer i; |
111 | TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**) myData1; |
112 | TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**) myData2; |
113 | TCollection_IndexedDataMapNode *p,*q; |
114 | for (i = 0; i <= NbBuckets(); i++) { |
115 | p = data1[i]; |
116 | while (p) { |
117 | q = (TCollection_IndexedDataMapNode*) p->Next(); |
118 | delete p; |
119 | p = q; |
120 | } |
121 | data1[i] = data2[i] = NULL; |
122 | } |
123 | } |
124 | TCollection_BasicMap::Destroy(); |
125 | } |
126 | |
127 | //======================================================================= |
128 | //function : Add |
129 | //purpose : |
130 | //======================================================================= |
131 | |
132 | Standard_Integer TCollection_IndexedDataMap::Add(const TheKey& K1, const TheItem& I) |
133 | { |
134 | if (Resizable()) ReSize(Extent()); |
135 | TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1; |
136 | Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets()); |
137 | TCollection_IndexedDataMapNode* p; |
138 | p = data1[k1]; |
139 | while (p) { |
140 | if (Hasher::IsEqual(p->Key1(),K1)) |
141 | return p->Key2(); |
142 | p = (TCollection_IndexedDataMapNode*) p->Next(); |
143 | } |
144 | Increment(); |
145 | TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2; |
146 | Standard_Integer k2 = ::HashCode(Extent(),NbBuckets()); |
147 | p = new TCollection_IndexedDataMapNode(K1,Extent(),I,data1[k1],data2[k2]); |
148 | data1[k1] = p; |
149 | data2[k2] = p; |
150 | return Extent(); |
151 | } |
152 | |
153 | |
154 | //======================================================================= |
155 | //function : Substitute |
156 | //purpose : |
157 | //======================================================================= |
158 | |
159 | void TCollection_IndexedDataMap::Substitute(const Standard_Integer I, |
160 | const TheKey& K1, |
161 | const TheItem& T) |
162 | { |
163 | Standard_OutOfRange_Raise_if(I < 1 || I > Extent(), |
164 | "IndexedMap::Substitute"); |
165 | TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1; |
166 | TCollection_IndexedDataMapNode* p; |
167 | |
168 | // check if K1 is not already in the map |
169 | Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets()); |
170 | p = data1[k1]; |
171 | while (p) { |
172 | if (Hasher::IsEqual(p->Key1(),K1)) |
173 | Standard_DomainError::Raise("IndexedMap::Substitute"); |
174 | p = (TCollection_IndexedDataMapNode*) p->Next(); |
175 | } |
176 | |
177 | // Find the node for the index I |
178 | TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2; |
179 | Standard_Integer k2 = ::HashCode(I,NbBuckets()); |
180 | p = data2[k2]; |
181 | while (p) { |
182 | if (p->Key2() == I) |
183 | break; |
184 | p = (TCollection_IndexedDataMapNode*) p->Next2(); |
185 | } |
186 | |
187 | // remove the old key |
188 | Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets()); |
189 | TCollection_IndexedDataMapNode* q = data1[k]; |
190 | if (q == p) data1[k] = (TCollection_IndexedDataMapNode*) p->Next(); |
191 | else { |
192 | while(q->Next() != p) q = (TCollection_IndexedDataMapNode*) q->Next(); |
193 | q->Next() = p->Next(); |
194 | } |
195 | |
196 | // update the node |
197 | p->Key1() = K1; |
198 | p->Value() = T; |
199 | p->Next() = data1[k1]; |
200 | data1[k1] = p; |
201 | } |
202 | |
203 | //======================================================================= |
204 | //function : RemoveLast |
205 | //purpose : |
206 | //======================================================================= |
207 | |
208 | void TCollection_IndexedDataMap::RemoveLast() |
209 | { |
210 | Standard_OutOfRange_Raise_if(Extent() == 0, |
211 | "IndexedMap::RemoveLast"); |
212 | TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1; |
213 | TCollection_IndexedDataMapNode* p; |
214 | TCollection_IndexedDataMapNode* q; |
215 | |
216 | // Find the node for the last index and remove it |
217 | TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2; |
218 | Standard_Integer k2 = ::HashCode(Extent(),NbBuckets()); |
219 | p = data2[k2]; |
220 | q = NULL; |
221 | while (p) { |
222 | if (p->Key2() == Extent()) |
223 | break; |
224 | q = p; |
225 | p = (TCollection_IndexedDataMapNode*) p->Next2(); |
226 | } |
227 | if (q == NULL) |
228 | data2[k2] = (TCollection_IndexedDataMapNode*)p->Next2(); |
229 | else |
230 | q->Next2() = p->Next2(); |
231 | |
232 | // remove the key |
233 | Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets()); |
234 | q = data1[k]; |
235 | if (q == p) data1[k] = (TCollection_IndexedDataMapNode*) p->Next(); |
236 | else { |
237 | while(q->Next() != p) q = (TCollection_IndexedDataMapNode*) q->Next(); |
238 | q->Next() = p->Next(); |
239 | } |
240 | |
241 | Decrement(); |
242 | delete p; |
243 | } |
244 | |
245 | //======================================================================= |
246 | //function : Contains |
247 | //purpose : |
248 | //======================================================================= |
249 | |
250 | Standard_Boolean TCollection_IndexedDataMap::Contains(const TheKey& K1) const |
251 | { |
252 | if (IsEmpty()) return Standard_False; |
253 | TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1; |
254 | Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets()); |
255 | TCollection_IndexedDataMapNode *p1; |
256 | p1 = data1[k1]; |
257 | while (p1) { |
258 | if (Hasher::IsEqual(p1->Key1(),K1)) return Standard_True; |
259 | p1 = (TCollection_IndexedDataMapNode*) p1->Next(); |
260 | } |
261 | return Standard_False; |
262 | } |
263 | |
264 | //======================================================================= |
265 | //function : FindKey |
266 | //purpose : |
267 | //======================================================================= |
268 | |
269 | const TheKey& TCollection_IndexedDataMap::FindKey(const Standard_Integer K2) const |
270 | { |
271 | Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap"); |
272 | TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2; |
273 | Standard_Integer k2 = ::HashCode(K2,NbBuckets()); |
274 | TCollection_IndexedDataMapNode *p2; |
275 | p2 = data2[k2]; |
276 | while (p2) { |
277 | if (p2->Key2() == K2) return p2->Key1(); |
278 | p2 = (TCollection_IndexedDataMapNode*)p2->Next2(); |
279 | } |
280 | Standard_OutOfRange::Raise("IndexedDataMap : missing index !!!"); |
281 | return p2->Key1(); |
282 | } |
283 | |
284 | //======================================================================= |
285 | //function : FindFromIndex |
286 | //purpose : |
287 | //======================================================================= |
288 | |
289 | const TheItem& TCollection_IndexedDataMap::FindFromIndex |
290 | (const Standard_Integer K2) const |
291 | { |
292 | Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap"); |
293 | TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2; |
294 | Standard_Integer k2 = ::HashCode(K2,NbBuckets()); |
295 | TCollection_IndexedDataMapNode *p2; |
296 | p2 = data2[k2]; |
297 | while (p2) { |
298 | if (p2->Key2() == K2) return p2->Value(); |
299 | p2 = (TCollection_IndexedDataMapNode*)p2->Next2(); |
300 | } |
301 | Standard_OutOfRange::Raise("IndexedDataMap : missing index !!!"); |
302 | return p2->Value(); |
303 | } |
304 | |
305 | //======================================================================= |
306 | //function : ChangeFromIndex |
307 | //purpose : |
308 | //======================================================================= |
309 | |
310 | TheItem& TCollection_IndexedDataMap::ChangeFromIndex(const Standard_Integer K2) |
311 | { |
312 | Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap"); |
313 | TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2; |
314 | Standard_Integer k2 = ::HashCode(K2,NbBuckets()); |
315 | TCollection_IndexedDataMapNode *p2; |
316 | p2 = data2[k2]; |
317 | while (p2) { |
318 | if (p2->Key2() == K2) return p2->Value(); |
319 | p2 = (TCollection_IndexedDataMapNode*)p2->Next2(); |
320 | } |
321 | Standard_OutOfRange::Raise("IndexedDataMap : missing index !!!"); |
322 | return p2->Value(); |
323 | } |
324 | |
325 | //======================================================================= |
326 | //function : FindIndex |
327 | //purpose : |
328 | //======================================================================= |
329 | |
330 | Standard_Integer TCollection_IndexedDataMap::FindIndex(const TheKey& K1) const |
331 | { |
332 | if (IsEmpty()) return 0; |
333 | TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1; |
334 | Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets()); |
335 | TCollection_IndexedDataMapNode *p1; |
336 | p1 = data1[k1]; |
337 | while (p1) { |
338 | if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Key2(); |
339 | p1 = (TCollection_IndexedDataMapNode*)p1->Next(); |
340 | } |
341 | return 0; |
342 | } |
343 | |
344 | //======================================================================= |
345 | //function : FindFromKey |
346 | //purpose : |
347 | //======================================================================= |
348 | |
349 | const TheItem& TCollection_IndexedDataMap::FindFromKey(const TheKey& K1) const |
350 | { |
351 | Standard_OutOfRange_Raise_if(IsEmpty(),"TCollection_IndexedDataMap::FindFromKey"); |
352 | TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1; |
353 | Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets()); |
354 | TCollection_IndexedDataMapNode *p1; |
355 | p1 = data1[k1]; |
356 | while (p1) { |
357 | if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Value(); |
358 | p1 = (TCollection_IndexedDataMapNode*) p1->Next(); |
359 | } |
360 | Standard_OutOfRange::Raise("TCollection_IndexedDataMap::FindFromKey"); |
361 | return p1->Value(); |
362 | } |
363 | |
364 | //======================================================================= |
365 | //function : ChangeFromKey |
366 | //purpose : |
367 | //======================================================================= |
368 | |
369 | TheItem& TCollection_IndexedDataMap::ChangeFromKey(const TheKey& K1) |
370 | { |
371 | Standard_OutOfRange_Raise_if(IsEmpty(),"TCollection_IndexedDataMap::ChangeFromKey"); |
372 | TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1; |
373 | Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets()); |
374 | TCollection_IndexedDataMapNode *p1; |
375 | p1 = data1[k1]; |
376 | while (p1) { |
377 | if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Value(); |
378 | p1 = (TCollection_IndexedDataMapNode*)p1->Next(); |
379 | } |
380 | Standard_OutOfRange::Raise("TCollection_IndexedDataMap::ChangeFromKey"); |
381 | return p1->Value(); |
382 | } |
383 | |
384 | |
385 | |
386 | // @@SDM: begin |
387 | |
388 | // Copyright Open CasCade......................................Version 5.0-00 |
389 | // Lastly modified by : szy Date : 7-05-2003 |
390 | |
391 | // File history synopsis (creation,modification,correction) |
392 | // +---------------------------------------------------------------------------+ |
393 | // ! Developer ! Comments ! Date ! Version ! |
394 | // +-----------!-----------------------------------------!----------!----------+ |
395 | // ! rle ! Creation ! 8-01-1993! 5.0-00-2! |
396 | // ! szy ! Modified Assign method ! 7-05-2003! 5.0-00-2! |
397 | // +---------------------------------------------------------------------------+ |
398 | |
399 | // @@SDM: end |