b311480e |
1 | // Created on: 2002-04-24 |
2 | // Created by: Alexander KARTOMIN (akm) |
973c2be1 |
3 | // Copyright (c) 2002-2014 OPEN CASCADE SAS |
b311480e |
4 | // |
973c2be1 |
5 | // This file is part of Open CASCADE Technology software library. |
b311480e |
6 | // |
d5f74e42 |
7 | // This library is free software; you can redistribute it and/or modify it under |
8 | // the terms of the GNU Lesser General Public License version 2.1 as published |
973c2be1 |
9 | // by the Free Software Foundation, with special exception defined in the file |
10 | // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT |
11 | // distribution for complete text of the license and disclaimer of any warranty. |
b311480e |
12 | // |
973c2be1 |
13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. |
b311480e |
15 | |
7fd59977 |
16 | #ifndef NCollection_DoubleMap_HeaderFile |
17 | #define NCollection_DoubleMap_HeaderFile |
18 | |
19 | #include <NCollection_TypeDef.hxx> |
7fd59977 |
20 | #include <NCollection_BaseMap.hxx> |
21 | #include <NCollection_TListNode.hxx> |
22 | #include <Standard_TypeMismatch.hxx> |
23 | #include <Standard_MultiplyDefined.hxx> |
24 | #include <Standard_ImmutableObject.hxx> |
25 | #include <Standard_NoSuchObject.hxx> |
26 | |
9991c9c2 |
27 | #include <NCollection_DefaultHasher.hxx> |
28 | |
7fd59977 |
29 | /** |
30 | * Purpose: The DoubleMap is used to bind pairs (Key1,Key2) |
31 | * and retrieve them in linear time. |
32 | * |
33 | * See Map from NCollection for a discussion about the number |
34 | * of buckets |
35 | */ |
9991c9c2 |
36 | |
37 | template < class TheKey1Type, |
38 | class TheKey2Type, |
39 | class Hasher1 = NCollection_DefaultHasher<TheKey1Type>, |
ddf2fe8e |
40 | class Hasher2 = NCollection_DefaultHasher<TheKey2Type> > |
41 | class NCollection_DoubleMap : public NCollection_BaseMap |
7fd59977 |
42 | { |
3f5aa017 |
43 | public: |
44 | //! STL-compliant typedef for key1 type |
45 | typedef TheKey1Type key1_type; |
46 | //! STL-compliant typedef for key2 type |
47 | typedef TheKey2Type key2_type; |
48 | |
49 | public: |
7fd59977 |
50 | // **************** Adaptation of the TListNode to the DOUBLEmap |
7fd59977 |
51 | class DoubleMapNode : public NCollection_TListNode<TheKey2Type> |
52 | { |
53 | public: |
54 | //! Constructor with 'Next' |
55 | DoubleMapNode (const TheKey1Type& theKey1, |
56 | const TheKey2Type& theKey2, |
57 | NCollection_ListNode* theNext1, |
58 | NCollection_ListNode* theNext2) : |
e3a6386d |
59 | NCollection_TListNode<TheKey2Type> (theKey2, theNext1), |
60 | myKey1(theKey1), |
61 | myNext2((DoubleMapNode*)theNext2) |
7fd59977 |
62 | { |
7fd59977 |
63 | } |
64 | //! Key1 |
65 | const TheKey1Type& Key1 (void) |
66 | { return myKey1; } |
67 | //! Key2 |
68 | const TheKey2Type& Key2 (void) |
69 | { return this->myValue; } |
70 | //! Next2 |
71 | DoubleMapNode*& Next2 (void) |
72 | { return myNext2; } |
73 | |
74 | //! Static deleter to be passed to BaseList |
75 | static void delNode (NCollection_ListNode * theNode, |
76 | Handle(NCollection_BaseAllocator)& theAl) |
77 | { |
78 | ((DoubleMapNode *) theNode)->~DoubleMapNode(); |
79 | theAl->Free(theNode); |
80 | } |
81 | |
82 | private: |
83 | TheKey1Type myKey1; |
84 | DoubleMapNode *myNext2; |
85 | }; |
86 | |
87 | public: |
88 | // **************** Implementation of the Iterator interface. |
ddf2fe8e |
89 | class Iterator : public NCollection_BaseMap::Iterator |
7fd59977 |
90 | { |
91 | public: |
92 | //! Empty constructor |
ddf2fe8e |
93 | Iterator (void) {} |
7fd59977 |
94 | //! Constructor |
95 | Iterator (const NCollection_DoubleMap& theMap) : |
96 | NCollection_BaseMap::Iterator(theMap) {} |
97 | //! Query if the end of collection is reached by iterator |
ddf2fe8e |
98 | Standard_Boolean More(void) const |
7fd59977 |
99 | { return PMore(); } |
100 | //! Make a step along the collection |
ddf2fe8e |
101 | void Next(void) |
7fd59977 |
102 | { PNext(); } |
103 | //! Key1 inquiry |
104 | const TheKey1Type& Key1(void) const |
105 | { |
e3a6386d |
106 | Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key1"); |
7fd59977 |
107 | return ((DoubleMapNode *) myNode)->Key1(); |
108 | } |
109 | //! Key2 inquiry |
110 | const TheKey2Type& Key2(void) const |
111 | { |
e3a6386d |
112 | Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key2"); |
7fd59977 |
113 | return ((DoubleMapNode *) myNode)->Key2(); |
114 | } |
115 | //! Value access |
ddf2fe8e |
116 | const TheKey2Type& Value(void) const |
7fd59977 |
117 | { |
e3a6386d |
118 | Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Value"); |
7fd59977 |
119 | return ((DoubleMapNode *) myNode)->Value(); |
120 | } |
7fd59977 |
121 | }; |
122 | |
123 | public: |
124 | // ---------- PUBLIC METHODS ------------ |
125 | |
b6a0525b |
126 | //! Empty constructor. |
127 | NCollection_DoubleMap() : NCollection_BaseMap (1, Standard_False, Handle(NCollection_BaseAllocator)()) {} |
128 | |
7fd59977 |
129 | //! Constructor |
b6a0525b |
130 | explicit NCollection_DoubleMap (const Standard_Integer theNbBuckets, |
131 | const Handle(NCollection_BaseAllocator)& theAllocator = 0L) |
132 | : NCollection_BaseMap (theNbBuckets, Standard_False, theAllocator) {} |
7fd59977 |
133 | |
134 | //! Copy constructor |
135 | NCollection_DoubleMap (const NCollection_DoubleMap& theOther) |
ddf2fe8e |
136 | : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator) |
7fd59977 |
137 | { *this = theOther; } |
138 | |
ab2db9a5 |
139 | //! Exchange the content of two maps without re-allocations. |
140 | //! Notice that allocators will be swapped as well! |
141 | void Exchange (NCollection_DoubleMap& theOther) |
142 | { |
ddf2fe8e |
143 | this->exchangeMapsData (theOther); |
ab2db9a5 |
144 | } |
145 | |
5e452c37 |
146 | //! Assignment. |
147 | //! This method does not change the internal allocator. |
ddf2fe8e |
148 | NCollection_DoubleMap& Assign (const NCollection_DoubleMap& theOther) |
7fd59977 |
149 | { |
150 | if (this == &theOther) |
151 | return *this; |
152 | |
5e452c37 |
153 | Clear(); |
229add78 |
154 | Standard_Integer anExt = theOther.Extent(); |
155 | if (anExt) |
7fd59977 |
156 | { |
229add78 |
157 | ReSize (anExt-1); |
158 | Iterator anIter(theOther); |
159 | for (; anIter.More(); anIter.Next()) |
160 | { |
161 | TheKey1Type aKey1 = anIter.Key1(); |
162 | TheKey2Type aKey2 = anIter.Key2(); |
163 | Standard_Integer iK1 = Hasher1::HashCode (aKey1, NbBuckets()); |
164 | Standard_Integer iK2 = Hasher2::HashCode (aKey2, NbBuckets()); |
165 | DoubleMapNode * pNode = new (this->myAllocator) DoubleMapNode (aKey1, aKey2, |
166 | myData1[iK1], |
167 | myData2[iK2]); |
168 | myData1[iK1] = pNode; |
169 | myData2[iK2] = pNode; |
170 | Increment(); |
171 | } |
7fd59977 |
172 | } |
173 | return *this; |
174 | } |
175 | |
ddf2fe8e |
176 | //! Assignment operator |
177 | NCollection_DoubleMap& operator= (const NCollection_DoubleMap& theOther) |
5e452c37 |
178 | { |
ddf2fe8e |
179 | return Assign (theOther); |
180 | } |
181 | |
7fd59977 |
182 | //! ReSize |
183 | void ReSize (const Standard_Integer N) |
184 | { |
fd03ee4b |
185 | NCollection_ListNode** ppNewData1 = NULL; |
186 | NCollection_ListNode** ppNewData2 = NULL; |
7fd59977 |
187 | Standard_Integer newBuck; |
ddf2fe8e |
188 | if (BeginResize (N, newBuck, ppNewData1, ppNewData2)) |
7fd59977 |
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 | { |
9991c9c2 |
201 | iK1 = Hasher1::HashCode (p->Key1(), newBuck); |
202 | iK2 = Hasher2::HashCode (p->Key2(), newBuck); |
7fd59977 |
203 | q = (DoubleMapNode*) p->Next(); |
204 | p->Next() = ppNewData1[iK1]; |
fd03ee4b |
205 | p->Next2() = (DoubleMapNode*)ppNewData2[iK2]; |
7fd59977 |
206 | ppNewData1[iK1] = p; |
207 | ppNewData2[iK2] = p; |
208 | p = q; |
209 | } |
210 | } |
211 | } |
212 | } |
ddf2fe8e |
213 | EndResize (N, newBuck, ppNewData1, ppNewData2); |
7fd59977 |
214 | } |
215 | } |
216 | |
217 | //! Bind |
218 | void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2) |
219 | { |
220 | if (Resizable()) |
221 | ReSize(Extent()); |
9991c9c2 |
222 | Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); |
223 | Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); |
7fd59977 |
224 | DoubleMapNode * pNode; |
225 | pNode = (DoubleMapNode *) myData1[iK1]; |
226 | while (pNode) |
227 | { |
9991c9c2 |
228 | if (Hasher1::IsEqual (pNode->Key1(), theKey1)) |
9775fa61 |
229 | throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind"); |
7fd59977 |
230 | pNode = (DoubleMapNode *) pNode->Next(); |
231 | } |
232 | pNode = (DoubleMapNode *) myData2[iK2]; |
233 | while (pNode) |
234 | { |
9991c9c2 |
235 | if (Hasher2::IsEqual (pNode->Key2(), theKey2)) |
9775fa61 |
236 | throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind"); |
7fd59977 |
237 | pNode = (DoubleMapNode *) pNode->Next(); |
238 | } |
239 | pNode = new (this->myAllocator) DoubleMapNode (theKey1, theKey2, |
240 | myData1[iK1], myData2[iK2]); |
241 | myData1[iK1] = pNode; |
242 | myData2[iK2] = pNode; |
243 | Increment(); |
244 | } |
245 | |
246 | //!* AreBound |
247 | Standard_Boolean AreBound (const TheKey1Type& theKey1, |
248 | const TheKey2Type& theKey2) const |
249 | { |
250 | if (IsEmpty()) |
251 | return Standard_False; |
9991c9c2 |
252 | Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); |
253 | Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); |
7fd59977 |
254 | DoubleMapNode * pNode1, * pNode2; |
255 | pNode1 = (DoubleMapNode *) myData1[iK1]; |
256 | while (pNode1) |
257 | { |
9991c9c2 |
258 | if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) |
7fd59977 |
259 | break; |
260 | pNode1 = (DoubleMapNode *) pNode1->Next(); |
261 | } |
262 | if (pNode1 == NULL) |
263 | return Standard_False; |
264 | pNode2 = (DoubleMapNode *) myData2[iK2]; |
265 | while (pNode2) |
266 | { |
9991c9c2 |
267 | if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) |
7fd59977 |
268 | break; |
269 | pNode2 = (DoubleMapNode *) pNode2->Next(); |
270 | } |
271 | if (pNode2 == NULL) |
272 | return Standard_False; |
273 | |
274 | return (pNode1 == pNode2); |
275 | } |
276 | |
277 | //! IsBound1 |
278 | Standard_Boolean IsBound1 (const TheKey1Type& theKey1) const |
279 | { |
280 | if (IsEmpty()) |
281 | return Standard_False; |
9991c9c2 |
282 | Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); |
7fd59977 |
283 | DoubleMapNode * pNode1; |
284 | pNode1 = (DoubleMapNode *) myData1[iK1]; |
285 | while (pNode1) |
286 | { |
9991c9c2 |
287 | if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) |
7fd59977 |
288 | return Standard_True; |
289 | pNode1 = (DoubleMapNode *) pNode1->Next(); |
290 | } |
291 | return Standard_False; |
292 | } |
293 | |
294 | //! IsBound2 |
295 | Standard_Boolean IsBound2 (const TheKey2Type& theKey2) const |
296 | { |
297 | if (IsEmpty()) |
298 | return Standard_False; |
9991c9c2 |
299 | Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); |
7fd59977 |
300 | DoubleMapNode * pNode2; |
301 | pNode2 = (DoubleMapNode *) myData2[iK2]; |
302 | while (pNode2) |
303 | { |
9991c9c2 |
304 | if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) |
7fd59977 |
305 | return Standard_True; |
306 | pNode2 = (DoubleMapNode *) pNode2->Next2(); |
307 | } |
308 | return Standard_False; |
309 | } |
310 | |
311 | //! UnBind1 |
312 | Standard_Boolean UnBind1 (const TheKey1Type& theKey1) |
313 | { |
314 | if (IsEmpty()) |
315 | return Standard_False; |
9991c9c2 |
316 | Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); |
7fd59977 |
317 | DoubleMapNode * p1, * p2, * q1, *q2; |
318 | q1 = q2 = NULL; |
319 | p1 = (DoubleMapNode *) myData1[iK1]; |
320 | while (p1) |
321 | { |
9991c9c2 |
322 | if (Hasher1::IsEqual (p1->Key1(), theKey1)) |
7fd59977 |
323 | { |
324 | // remove from the data1 |
325 | if (q1) |
326 | q1->Next() = p1->Next(); |
327 | else |
328 | myData1[iK1] = (DoubleMapNode*) p1->Next(); |
9991c9c2 |
329 | Standard_Integer iK2 = Hasher2::HashCode (p1->Key2(), NbBuckets()); |
7fd59977 |
330 | p2 = (DoubleMapNode *) myData2[iK2]; |
331 | while (p2) |
332 | { |
333 | if (p2 == p1) |
334 | { |
335 | // remove from the data2 |
336 | if (q2) |
337 | q2->Next2() = p2->Next2(); |
338 | else |
339 | myData2[iK2] = (DoubleMapNode*) p2->Next2(); |
340 | break; |
341 | } |
342 | q2 = p2; |
343 | p2 = (DoubleMapNode*) p2->Next2(); |
344 | } |
345 | p1->~DoubleMapNode(); |
346 | this->myAllocator->Free(p1); |
347 | Decrement(); |
348 | return Standard_True; |
349 | } |
350 | q1 = p1; |
351 | p1 = (DoubleMapNode*) p1->Next(); |
352 | } |
353 | return Standard_False; |
354 | } |
355 | |
356 | //! UnBind2 |
357 | Standard_Boolean UnBind2 (const TheKey2Type& theKey2) |
358 | { |
359 | if (IsEmpty()) |
360 | return Standard_False; |
9991c9c2 |
361 | Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); |
7fd59977 |
362 | DoubleMapNode * p1, * p2, * q1, *q2; |
363 | q1 = q2 = NULL; |
364 | p2 = (DoubleMapNode *) myData2[iK2]; |
365 | while (p2) |
366 | { |
9991c9c2 |
367 | if (Hasher2::IsEqual (p2->Key2(), theKey2)) |
7fd59977 |
368 | { |
369 | // remove from the data2 |
370 | if (q2) |
371 | q2->Next() = p2->Next(); |
372 | else |
373 | myData2[iK2] = (DoubleMapNode*) p2->Next2(); |
9991c9c2 |
374 | Standard_Integer iK1 = Hasher1::HashCode (p2->Key1(), NbBuckets()); |
7fd59977 |
375 | p1 = (DoubleMapNode *) myData1[iK1]; |
376 | while (p1) |
377 | { |
378 | if (p1 == p2) |
379 | { |
380 | // remove from the data1 |
381 | if (q1) |
382 | q1->Next() = p1->Next(); |
383 | else |
384 | myData1[iK1] = (DoubleMapNode*) p1->Next(); |
385 | break; |
386 | } |
387 | q1 = p1; |
388 | p1 = (DoubleMapNode*) p1->Next(); |
389 | } |
390 | p2->~DoubleMapNode(); |
391 | this->myAllocator->Free(p2); |
392 | Decrement(); |
393 | return Standard_True; |
394 | } |
395 | q2 = p2; |
396 | p2 = (DoubleMapNode*) p2->Next2(); |
397 | } |
398 | return Standard_False; |
399 | } |
400 | |
8f521168 |
401 | //! Find the Key1 and return Key2 value. |
402 | //! Raises an exception if Key1 was not bound. |
7fd59977 |
403 | const TheKey2Type& Find1(const TheKey1Type& theKey1) const |
404 | { |
af2fa459 |
405 | if (const TheKey2Type* aKey2 = Seek1 (theKey1)) |
7fd59977 |
406 | { |
af2fa459 |
407 | return *aKey2; |
7fd59977 |
408 | } |
9775fa61 |
409 | throw Standard_NoSuchObject("NCollection_DoubleMap::Find1"); |
7fd59977 |
410 | } |
411 | |
8f521168 |
412 | //! Find the Key1 and return Key2 value (by copying its value). |
413 | //! @param [in] theKey1 Key1 to find |
414 | //! @param [out] theKey2 Key2 to return |
415 | //! @return TRUE if Key1 has been found |
416 | Standard_Boolean Find1 (const TheKey1Type& theKey1, |
417 | TheKey2Type& theKey2) const |
af2fa459 |
418 | { |
419 | if (const TheKey2Type* aKey2 = Seek1 (theKey1)) |
420 | { |
421 | theKey2 = *aKey2; |
422 | return true; |
423 | } |
424 | return false; |
425 | } |
426 | |
427 | //! Find the Key1 and return pointer to Key2 or NULL if Key1 is not bound. |
428 | //! @param [in] theKey1 Key1 to find |
429 | //! @return pointer to Key2 or NULL if Key1 is not found |
430 | const TheKey2Type* Seek1 (const TheKey1Type& theKey1) const |
8f521168 |
431 | { |
432 | for (DoubleMapNode* aNode1 = !IsEmpty() ? (DoubleMapNode* )myData1[Hasher1::HashCode (theKey1, NbBuckets())] : NULL; |
433 | aNode1 != NULL; aNode1 = (DoubleMapNode* )aNode1->Next()) |
434 | { |
435 | if (Hasher1::IsEqual (aNode1->Key1(), theKey1)) |
436 | { |
af2fa459 |
437 | return &aNode1->Key2(); |
8f521168 |
438 | } |
439 | } |
af2fa459 |
440 | return NULL; |
8f521168 |
441 | } |
442 | |
443 | //! Find the Key2 and return Key1 value. |
444 | //! Raises an exception if Key2 was not bound. |
7fd59977 |
445 | const TheKey1Type& Find2(const TheKey2Type& theKey2) const |
446 | { |
af2fa459 |
447 | if (const TheKey1Type* aVal1 = Seek2 (theKey2)) |
7fd59977 |
448 | { |
af2fa459 |
449 | return *aVal1; |
7fd59977 |
450 | } |
9775fa61 |
451 | throw Standard_NoSuchObject("NCollection_DoubleMap::Find2"); |
7fd59977 |
452 | } |
453 | |
8f521168 |
454 | //! Find the Key2 and return Key1 value (by copying its value). |
455 | //! @param [in] theKey2 Key2 to find |
456 | //! @param [out] theKey1 Key1 to return |
457 | //! @return TRUE if Key2 has been found |
458 | Standard_Boolean Find2 (const TheKey2Type& theKey2, |
459 | TheKey1Type& theKey1) const |
af2fa459 |
460 | { |
461 | if (const TheKey1Type* aVal1 = Seek2 (theKey2)) |
462 | { |
463 | theKey1 = *aVal1; |
464 | return Standard_True; |
465 | } |
466 | return Standard_False; |
467 | } |
468 | |
469 | //! Find the Key2 and return pointer to Key1 or NULL if not bound. |
470 | //! @param [in] theKey2 Key2 to find |
471 | //! @return pointer to Key1 if Key2 has been found |
472 | const TheKey1Type* Seek2 (const TheKey2Type& theKey2) const |
8f521168 |
473 | { |
474 | for (DoubleMapNode* aNode2 = !IsEmpty() ? (DoubleMapNode* )myData2[Hasher2::HashCode (theKey2, NbBuckets())] : NULL; |
475 | aNode2 != NULL; aNode2 = (DoubleMapNode* )aNode2->Next2()) |
476 | { |
477 | if (Hasher2::IsEqual (aNode2->Key2(), theKey2)) |
478 | { |
af2fa459 |
479 | return &aNode2->Key1(); |
8f521168 |
480 | } |
481 | } |
af2fa459 |
482 | return NULL; |
8f521168 |
483 | } |
484 | |
7fd59977 |
485 | //! Clear data. If doReleaseMemory is false then the table of |
486 | //! buckets is not released and will be reused. |
487 | void Clear(const Standard_Boolean doReleaseMemory = Standard_True) |
ddf2fe8e |
488 | { Destroy (DoubleMapNode::delNode, doReleaseMemory); } |
7fd59977 |
489 | |
490 | //! Clear data and reset allocator |
491 | void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) |
492 | { |
493 | Clear(); |
494 | this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : |
495 | NCollection_BaseAllocator::CommonBaseAllocator() ); |
496 | } |
497 | |
498 | //! Destructor |
499 | ~NCollection_DoubleMap (void) |
500 | { Clear(); } |
501 | |
502 | //! Size |
ddf2fe8e |
503 | Standard_Integer Size(void) const |
7fd59977 |
504 | { return Extent(); } |
7fd59977 |
505 | }; |
506 | |
7fd59977 |
507 | #endif |