7fd59977 |
1 | // File: NCollection_DoubleMap.hxx |
2 | // Created: Thu Apr 24 15:02:53 2002 |
3 | // Author: Alexander KARTOMIN (akm) |
4 | // <akm@opencascade.com> |
5 | |
6 | #ifndef NCollection_DoubleMap_HeaderFile |
7 | #define NCollection_DoubleMap_HeaderFile |
8 | |
9 | #include <NCollection_TypeDef.hxx> |
10 | #include <NCollection_BaseCollection.hxx> |
11 | #include <NCollection_BaseMap.hxx> |
12 | #include <NCollection_TListNode.hxx> |
13 | #include <Standard_TypeMismatch.hxx> |
14 | #include <Standard_MultiplyDefined.hxx> |
15 | #include <Standard_ImmutableObject.hxx> |
16 | #include <Standard_NoSuchObject.hxx> |
17 | |
18 | #ifdef WNT |
19 | // Disable the warning "operator new unmatched by delete" |
20 | #pragma warning (push) |
21 | #pragma warning (disable:4291) |
22 | #endif |
23 | |
24 | /** |
25 | * Purpose: The DoubleMap is used to bind pairs (Key1,Key2) |
26 | * and retrieve them in linear time. |
27 | * |
28 | * See Map from NCollection for a discussion about the number |
29 | * of buckets |
30 | */ |
31 | template <class TheKey1Type, class TheKey2Type> class NCollection_DoubleMap |
32 | : public NCollection_BaseCollection<TheKey2Type>, |
33 | public NCollection_BaseMap |
34 | { |
35 | // **************** Adaptation of the TListNode to the DOUBLEmap |
36 | public: |
37 | class DoubleMapNode : public NCollection_TListNode<TheKey2Type> |
38 | { |
39 | public: |
40 | //! Constructor with 'Next' |
41 | DoubleMapNode (const TheKey1Type& theKey1, |
42 | const TheKey2Type& theKey2, |
43 | NCollection_ListNode* theNext1, |
44 | NCollection_ListNode* theNext2) : |
45 | NCollection_TListNode<TheKey2Type> (theKey2, theNext1) |
46 | { |
47 | myKey1 = theKey1; |
48 | myNext2 = (DoubleMapNode *) theNext2; |
49 | } |
50 | //! Key1 |
51 | const TheKey1Type& Key1 (void) |
52 | { return myKey1; } |
53 | //! Key2 |
54 | const TheKey2Type& Key2 (void) |
55 | { return this->myValue; } |
56 | //! Next2 |
57 | DoubleMapNode*& Next2 (void) |
58 | { return myNext2; } |
59 | |
60 | //! Static deleter to be passed to BaseList |
61 | static void delNode (NCollection_ListNode * theNode, |
62 | Handle(NCollection_BaseAllocator)& theAl) |
63 | { |
64 | ((DoubleMapNode *) theNode)->~DoubleMapNode(); |
65 | theAl->Free(theNode); |
66 | } |
67 | |
68 | private: |
69 | TheKey1Type myKey1; |
70 | DoubleMapNode *myNext2; |
71 | }; |
72 | |
73 | public: |
74 | // **************** Implementation of the Iterator interface. |
75 | class Iterator |
76 | : public NCollection_BaseCollection<TheKey2Type>::Iterator, |
77 | public NCollection_BaseMap::Iterator |
78 | { |
79 | public: |
80 | //! Empty constructor |
81 | Iterator (void) : |
82 | NCollection_BaseMap::Iterator() {} |
83 | //! Constructor |
84 | Iterator (const NCollection_DoubleMap& theMap) : |
85 | NCollection_BaseMap::Iterator(theMap) {} |
86 | //! Query if the end of collection is reached by iterator |
87 | virtual Standard_Boolean More(void) const |
88 | { return PMore(); } |
89 | //! Make a step along the collection |
90 | virtual void Next(void) |
91 | { PNext(); } |
92 | //! Key1 inquiry |
93 | const TheKey1Type& Key1(void) const |
94 | { |
95 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
96 | if (!More()) |
97 | Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Key1"); |
98 | #endif |
99 | return ((DoubleMapNode *) myNode)->Key1(); |
100 | } |
101 | //! Key2 inquiry |
102 | const TheKey2Type& Key2(void) const |
103 | { |
104 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
105 | if (!More()) |
106 | Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Key2"); |
107 | #endif |
108 | return ((DoubleMapNode *) myNode)->Key2(); |
109 | } |
110 | //! Value access |
111 | virtual const TheKey2Type& Value(void) const |
112 | { |
113 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
114 | if (!More()) |
115 | Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Value"); |
116 | #endif |
117 | return ((DoubleMapNode *) myNode)->Value(); |
118 | } |
119 | //! Value change access - denied |
120 | virtual TheKey2Type& ChangeValue(void) const |
121 | { |
122 | Standard_ImmutableObject::Raise("NCollection_DoubleMap::Iterator::ChangeValue"); |
123 | return * (TheKey2Type *) NULL; // For compiler |
124 | } |
125 | //! Operator new for allocating iterators |
126 | void* operator new(size_t theSize, |
127 | const Handle(NCollection_BaseAllocator)& theAllocator) |
128 | { return theAllocator->Allocate(theSize); } |
129 | }; |
130 | |
131 | public: |
132 | // ---------- PUBLIC METHODS ------------ |
133 | |
134 | //! Constructor |
135 | NCollection_DoubleMap (const Standard_Integer NbBuckets=1, |
136 | const Handle(NCollection_BaseAllocator)& theAllocator = 0L) |
137 | : NCollection_BaseCollection<TheKey2Type>(theAllocator), |
138 | NCollection_BaseMap (NbBuckets, Standard_False) {} |
139 | |
140 | //! Copy constructor |
141 | NCollection_DoubleMap (const NCollection_DoubleMap& theOther) |
142 | : NCollection_BaseCollection<TheKey2Type>(theOther.myAllocator), |
143 | NCollection_BaseMap (theOther.NbBuckets(), Standard_False) |
144 | { *this = theOther; } |
145 | |
146 | //! Assign another collection |
147 | virtual void Assign(const NCollection_BaseCollection<TheKey2Type>& theOther) |
148 | { |
149 | if (this == &theOther) |
150 | return; |
151 | Standard_TypeMismatch::Raise ("NCollection_DoubleMap::Assign impossible"); |
152 | } |
153 | |
154 | //! = another map |
155 | NCollection_DoubleMap& operator=(const NCollection_DoubleMap& theOther) |
156 | { |
157 | if (this == &theOther) |
158 | return *this; |
159 | |
160 | Clear(theOther.myAllocator); |
161 | ReSize (theOther.Extent()-1); |
162 | Iterator anIter(theOther); |
163 | for (; anIter.More(); anIter.Next()) |
164 | { |
165 | TheKey1Type aKey1 = anIter.Key1(); |
166 | TheKey2Type aKey2 = anIter.Key2(); |
167 | Standard_Integer iK1 = HashCode (aKey1, NbBuckets()); |
168 | Standard_Integer iK2 = HashCode (aKey2, NbBuckets()); |
169 | DoubleMapNode * pNode = new (this->myAllocator) DoubleMapNode (aKey1, aKey2, |
170 | myData1[iK1], |
171 | myData2[iK2]); |
172 | myData1[iK1] = pNode; |
173 | myData2[iK2] = pNode; |
174 | Increment(); |
175 | } |
176 | return *this; |
177 | } |
178 | |
179 | //! ReSize |
180 | void ReSize (const Standard_Integer N) |
181 | { |
182 | DoubleMapNode** ppNewData1 = NULL; |
183 | DoubleMapNode** ppNewData2 = NULL; |
184 | Standard_Integer newBuck; |
185 | if (BeginResize (N, newBuck, |
186 | (NCollection_ListNode**&)ppNewData1, |
187 | (NCollection_ListNode**&)ppNewData2, |
188 | this->myAllocator)) |
189 | { |
190 | if (myData1) |
191 | { |
192 | DoubleMapNode *p, *q; |
193 | Standard_Integer i, iK1, iK2; |
194 | for (i = 0; i <= NbBuckets(); i++) |
195 | { |
196 | if (myData1[i]) |
197 | { |
198 | p = (DoubleMapNode *) myData1[i]; |
199 | while (p) |
200 | { |
201 | iK1 = HashCode (p->Key1(), newBuck); |
202 | iK2 = HashCode (p->Key2(), newBuck); |
203 | q = (DoubleMapNode*) p->Next(); |
204 | p->Next() = ppNewData1[iK1]; |
205 | p->Next2() = ppNewData2[iK2]; |
206 | ppNewData1[iK1] = p; |
207 | ppNewData2[iK2] = p; |
208 | p = q; |
209 | } |
210 | } |
211 | } |
212 | } |
213 | EndResize(N,newBuck, |
214 | (NCollection_ListNode**&)ppNewData1, |
215 | (NCollection_ListNode**&)ppNewData2, |
216 | this->myAllocator); |
217 | } |
218 | } |
219 | |
220 | //! Bind |
221 | void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2) |
222 | { |
223 | if (Resizable()) |
224 | ReSize(Extent()); |
225 | Standard_Integer iK1 = HashCode (theKey1, NbBuckets()); |
226 | Standard_Integer iK2 = HashCode (theKey2, NbBuckets()); |
227 | DoubleMapNode * pNode; |
228 | pNode = (DoubleMapNode *) myData1[iK1]; |
229 | while (pNode) |
230 | { |
231 | if (IsEqual (pNode->Key1(), theKey1)) |
232 | Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind"); |
233 | pNode = (DoubleMapNode *) pNode->Next(); |
234 | } |
235 | pNode = (DoubleMapNode *) myData2[iK2]; |
236 | while (pNode) |
237 | { |
238 | if (IsEqual (pNode->Key2(), theKey2)) |
239 | Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind"); |
240 | pNode = (DoubleMapNode *) pNode->Next(); |
241 | } |
242 | pNode = new (this->myAllocator) DoubleMapNode (theKey1, theKey2, |
243 | myData1[iK1], myData2[iK2]); |
244 | myData1[iK1] = pNode; |
245 | myData2[iK2] = pNode; |
246 | Increment(); |
247 | } |
248 | |
249 | //!* AreBound |
250 | Standard_Boolean AreBound (const TheKey1Type& theKey1, |
251 | const TheKey2Type& theKey2) const |
252 | { |
253 | if (IsEmpty()) |
254 | return Standard_False; |
255 | Standard_Integer iK1 = HashCode (theKey1, NbBuckets()); |
256 | Standard_Integer iK2 = HashCode (theKey2, NbBuckets()); |
257 | DoubleMapNode * pNode1, * pNode2; |
258 | pNode1 = (DoubleMapNode *) myData1[iK1]; |
259 | while (pNode1) |
260 | { |
261 | if (IsEqual(pNode1->Key1(), theKey1)) |
262 | break; |
263 | pNode1 = (DoubleMapNode *) pNode1->Next(); |
264 | } |
265 | if (pNode1 == NULL) |
266 | return Standard_False; |
267 | pNode2 = (DoubleMapNode *) myData2[iK2]; |
268 | while (pNode2) |
269 | { |
270 | if (IsEqual(pNode2->Key2(), theKey2)) |
271 | break; |
272 | pNode2 = (DoubleMapNode *) pNode2->Next(); |
273 | } |
274 | if (pNode2 == NULL) |
275 | return Standard_False; |
276 | |
277 | return (pNode1 == pNode2); |
278 | } |
279 | |
280 | //! IsBound1 |
281 | Standard_Boolean IsBound1 (const TheKey1Type& theKey1) const |
282 | { |
283 | if (IsEmpty()) |
284 | return Standard_False; |
285 | Standard_Integer iK1 = HashCode (theKey1, NbBuckets()); |
286 | DoubleMapNode * pNode1; |
287 | pNode1 = (DoubleMapNode *) myData1[iK1]; |
288 | while (pNode1) |
289 | { |
290 | if (IsEqual(pNode1->Key1(), theKey1)) |
291 | return Standard_True; |
292 | pNode1 = (DoubleMapNode *) pNode1->Next(); |
293 | } |
294 | return Standard_False; |
295 | } |
296 | |
297 | //! IsBound2 |
298 | Standard_Boolean IsBound2 (const TheKey2Type& theKey2) const |
299 | { |
300 | if (IsEmpty()) |
301 | return Standard_False; |
302 | Standard_Integer iK2 = HashCode (theKey2, NbBuckets()); |
303 | DoubleMapNode * pNode2; |
304 | pNode2 = (DoubleMapNode *) myData2[iK2]; |
305 | while (pNode2) |
306 | { |
307 | if (IsEqual(pNode2->Key2(), theKey2)) |
308 | return Standard_True; |
309 | pNode2 = (DoubleMapNode *) pNode2->Next2(); |
310 | } |
311 | return Standard_False; |
312 | } |
313 | |
314 | //! UnBind1 |
315 | Standard_Boolean UnBind1 (const TheKey1Type& theKey1) |
316 | { |
317 | if (IsEmpty()) |
318 | return Standard_False; |
319 | Standard_Integer iK1 = HashCode (theKey1, NbBuckets()); |
320 | DoubleMapNode * p1, * p2, * q1, *q2; |
321 | q1 = q2 = NULL; |
322 | p1 = (DoubleMapNode *) myData1[iK1]; |
323 | while (p1) |
324 | { |
325 | if (IsEqual (p1->Key1(), theKey1)) |
326 | { |
327 | // remove from the data1 |
328 | if (q1) |
329 | q1->Next() = p1->Next(); |
330 | else |
331 | myData1[iK1] = (DoubleMapNode*) p1->Next(); |
332 | Standard_Integer iK2 = HashCode (p1->Key2(), NbBuckets()); |
333 | p2 = (DoubleMapNode *) myData2[iK2]; |
334 | while (p2) |
335 | { |
336 | if (p2 == p1) |
337 | { |
338 | // remove from the data2 |
339 | if (q2) |
340 | q2->Next2() = p2->Next2(); |
341 | else |
342 | myData2[iK2] = (DoubleMapNode*) p2->Next2(); |
343 | break; |
344 | } |
345 | q2 = p2; |
346 | p2 = (DoubleMapNode*) p2->Next2(); |
347 | } |
348 | p1->~DoubleMapNode(); |
349 | this->myAllocator->Free(p1); |
350 | Decrement(); |
351 | return Standard_True; |
352 | } |
353 | q1 = p1; |
354 | p1 = (DoubleMapNode*) p1->Next(); |
355 | } |
356 | return Standard_False; |
357 | } |
358 | |
359 | //! UnBind2 |
360 | Standard_Boolean UnBind2 (const TheKey2Type& theKey2) |
361 | { |
362 | if (IsEmpty()) |
363 | return Standard_False; |
364 | Standard_Integer iK2 = HashCode (theKey2, NbBuckets()); |
365 | DoubleMapNode * p1, * p2, * q1, *q2; |
366 | q1 = q2 = NULL; |
367 | p2 = (DoubleMapNode *) myData2[iK2]; |
368 | while (p2) |
369 | { |
370 | if (IsEqual (p2->Key2(), theKey2)) |
371 | { |
372 | // remove from the data2 |
373 | if (q2) |
374 | q2->Next() = p2->Next(); |
375 | else |
376 | myData2[iK2] = (DoubleMapNode*) p2->Next2(); |
377 | Standard_Integer iK1 = HashCode (p2->Key1(), NbBuckets()); |
378 | p1 = (DoubleMapNode *) myData1[iK1]; |
379 | while (p1) |
380 | { |
381 | if (p1 == p2) |
382 | { |
383 | // remove from the data1 |
384 | if (q1) |
385 | q1->Next() = p1->Next(); |
386 | else |
387 | myData1[iK1] = (DoubleMapNode*) p1->Next(); |
388 | break; |
389 | } |
390 | q1 = p1; |
391 | p1 = (DoubleMapNode*) p1->Next(); |
392 | } |
393 | p2->~DoubleMapNode(); |
394 | this->myAllocator->Free(p2); |
395 | Decrement(); |
396 | return Standard_True; |
397 | } |
398 | q2 = p2; |
399 | p2 = (DoubleMapNode*) p2->Next2(); |
400 | } |
401 | return Standard_False; |
402 | } |
403 | |
404 | //! Find1 |
405 | const TheKey2Type& Find1(const TheKey1Type& theKey1) const |
406 | { |
407 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
408 | if (IsEmpty()) |
409 | Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Find1"); |
410 | #endif |
411 | DoubleMapNode * pNode1 = |
412 | (DoubleMapNode *) myData1[HashCode(theKey1,NbBuckets())]; |
413 | while (pNode1) |
414 | { |
415 | if (IsEqual (pNode1->Key1(), theKey1)) |
416 | return pNode1->Key2(); |
417 | pNode1 = (DoubleMapNode*) pNode1->Next(); |
418 | } |
419 | Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find1"); |
420 | return pNode1->Key2(); // This for compiler |
421 | } |
422 | |
423 | //! Find2 |
424 | const TheKey1Type& Find2(const TheKey2Type& theKey2) const |
425 | { |
426 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
427 | if (IsEmpty()) |
428 | Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Find2"); |
429 | #endif |
430 | DoubleMapNode * pNode2 = |
431 | (DoubleMapNode *) myData2[HashCode(theKey2,NbBuckets())]; |
432 | while (pNode2) |
433 | { |
434 | if (IsEqual (pNode2->Key2(), theKey2)) |
435 | return pNode2->Key1(); |
436 | pNode2 = (DoubleMapNode*) pNode2->Next2(); |
437 | } |
438 | Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find2"); |
439 | return pNode2->Key1(); // This for compiler |
440 | } |
441 | |
442 | //! Clear data. If doReleaseMemory is false then the table of |
443 | //! buckets is not released and will be reused. |
444 | void Clear(const Standard_Boolean doReleaseMemory = Standard_True) |
445 | { Destroy (DoubleMapNode::delNode, this->myAllocator, doReleaseMemory); } |
446 | |
447 | //! Clear data and reset allocator |
448 | void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) |
449 | { |
450 | Clear(); |
451 | this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : |
452 | NCollection_BaseAllocator::CommonBaseAllocator() ); |
453 | } |
454 | |
455 | //! Destructor |
456 | ~NCollection_DoubleMap (void) |
457 | { Clear(); } |
458 | |
459 | //! Size |
460 | virtual Standard_Integer Size(void) const |
461 | { return Extent(); } |
462 | |
463 | private: |
464 | // ----------- PRIVATE METHODS ----------- |
465 | |
466 | //! Creates Iterator for use on BaseCollection |
467 | virtual TYPENAME NCollection_BaseCollection<TheKey2Type>::Iterator& |
468 | CreateIterator(void) const |
469 | { return *(new (this->IterAllocator()) Iterator(*this)); } |
470 | |
471 | }; |
472 | |
473 | #ifdef WNT |
474 | #pragma warning (pop) |
475 | #endif |
476 | |
477 | #endif |