1 // Created on: 2002-04-24
2 // Created by: Alexander KARTOMIN (akm)
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef NCollection_DoubleMap_HeaderFile
17 #define NCollection_DoubleMap_HeaderFile
19 #include <NCollection_TypeDef.hxx>
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>
27 #include <NCollection_DefaultHasher.hxx>
30 * Purpose: The DoubleMap is used to bind pairs (Key1,Key2)
31 * and retrieve them in linear time.
33 * See Map from NCollection for a discussion about the number
37 template < class TheKey1Type,
39 class Hasher1 = NCollection_DefaultHasher<TheKey1Type>,
40 class Hasher2 = NCollection_DefaultHasher<TheKey2Type> >
41 class NCollection_DoubleMap : public NCollection_BaseMap
44 //! STL-compliant typedef for key1 type
45 typedef TheKey1Type key1_type;
46 //! STL-compliant typedef for key2 type
47 typedef TheKey2Type key2_type;
50 // **************** Adaptation of the TListNode to the DOUBLEmap
51 class DoubleMapNode : public NCollection_TListNode<TheKey2Type>
54 //! Constructor with 'Next'
55 DoubleMapNode (const TheKey1Type& theKey1,
56 const TheKey2Type& theKey2,
57 NCollection_ListNode* theNext1,
58 NCollection_ListNode* theNext2) :
59 NCollection_TListNode<TheKey2Type> (theKey2, theNext1),
61 myNext2((DoubleMapNode*)theNext2)
65 const TheKey1Type& Key1 (void)
68 const TheKey2Type& Key2 (void)
69 { return this->myValue; }
71 DoubleMapNode*& Next2 (void)
74 //! Static deleter to be passed to BaseList
75 static void delNode (NCollection_ListNode * theNode,
76 Handle(NCollection_BaseAllocator)& theAl)
78 ((DoubleMapNode *) theNode)->~DoubleMapNode();
84 DoubleMapNode *myNext2;
88 // **************** Implementation of the Iterator interface.
89 class Iterator : public NCollection_BaseMap::Iterator
95 Iterator (const NCollection_DoubleMap& theMap) :
96 NCollection_BaseMap::Iterator(theMap) {}
97 //! Query if the end of collection is reached by iterator
98 Standard_Boolean More(void) const
100 //! Make a step along the collection
104 const TheKey1Type& Key1(void) const
106 Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key1");
107 return ((DoubleMapNode *) myNode)->Key1();
110 const TheKey2Type& Key2(void) const
112 Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key2");
113 return ((DoubleMapNode *) myNode)->Key2();
116 const TheKey2Type& Value(void) const
118 Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Value");
119 return ((DoubleMapNode *) myNode)->Value();
124 // ---------- PUBLIC METHODS ------------
126 //! Empty constructor.
127 NCollection_DoubleMap() : NCollection_BaseMap (1, Standard_False, Handle(NCollection_BaseAllocator)()) {}
130 explicit NCollection_DoubleMap (const Standard_Integer theNbBuckets,
131 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
132 : NCollection_BaseMap (theNbBuckets, Standard_False, theAllocator) {}
135 NCollection_DoubleMap (const NCollection_DoubleMap& theOther)
136 : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator)
137 { *this = theOther; }
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)
143 this->exchangeMapsData (theOther);
147 //! This method does not change the internal allocator.
148 NCollection_DoubleMap& Assign (const NCollection_DoubleMap& theOther)
150 if (this == &theOther)
154 Standard_Integer anExt = theOther.Extent();
158 Iterator anIter(theOther);
159 for (; anIter.More(); anIter.Next())
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,
168 myData1[iK1] = pNode;
169 myData2[iK2] = pNode;
176 //! Assignment operator
177 NCollection_DoubleMap& operator= (const NCollection_DoubleMap& theOther)
179 return Assign (theOther);
183 void ReSize (const Standard_Integer N)
185 NCollection_ListNode** ppNewData1 = NULL;
186 NCollection_ListNode** ppNewData2 = NULL;
187 Standard_Integer newBuck;
188 if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
192 DoubleMapNode *p, *q;
193 Standard_Integer i, iK1, iK2;
194 for (i = 0; i <= NbBuckets(); i++)
198 p = (DoubleMapNode *) myData1[i];
201 iK1 = Hasher1::HashCode (p->Key1(), newBuck);
202 iK2 = Hasher2::HashCode (p->Key2(), newBuck);
203 q = (DoubleMapNode*) p->Next();
204 p->Next() = ppNewData1[iK1];
205 p->Next2() = (DoubleMapNode*)ppNewData2[iK2];
213 EndResize (N, newBuck, ppNewData1, ppNewData2);
218 void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2)
222 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
223 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
224 DoubleMapNode * pNode;
225 pNode = (DoubleMapNode *) myData1[iK1];
228 if (Hasher1::IsEqual (pNode->Key1(), theKey1))
229 throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind");
230 pNode = (DoubleMapNode *) pNode->Next();
232 pNode = (DoubleMapNode *) myData2[iK2];
235 if (Hasher2::IsEqual (pNode->Key2(), theKey2))
236 throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind");
237 pNode = (DoubleMapNode *) pNode->Next();
239 pNode = new (this->myAllocator) DoubleMapNode (theKey1, theKey2,
240 myData1[iK1], myData2[iK2]);
241 myData1[iK1] = pNode;
242 myData2[iK2] = pNode;
247 Standard_Boolean AreBound (const TheKey1Type& theKey1,
248 const TheKey2Type& theKey2) const
251 return Standard_False;
252 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
253 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
254 DoubleMapNode * pNode1, * pNode2;
255 pNode1 = (DoubleMapNode *) myData1[iK1];
258 if (Hasher1::IsEqual(pNode1->Key1(), theKey1))
260 pNode1 = (DoubleMapNode *) pNode1->Next();
263 return Standard_False;
264 pNode2 = (DoubleMapNode *) myData2[iK2];
267 if (Hasher2::IsEqual(pNode2->Key2(), theKey2))
269 pNode2 = (DoubleMapNode *) pNode2->Next();
272 return Standard_False;
274 return (pNode1 == pNode2);
278 Standard_Boolean IsBound1 (const TheKey1Type& theKey1) const
281 return Standard_False;
282 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
283 DoubleMapNode * pNode1;
284 pNode1 = (DoubleMapNode *) myData1[iK1];
287 if (Hasher1::IsEqual(pNode1->Key1(), theKey1))
288 return Standard_True;
289 pNode1 = (DoubleMapNode *) pNode1->Next();
291 return Standard_False;
295 Standard_Boolean IsBound2 (const TheKey2Type& theKey2) const
298 return Standard_False;
299 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
300 DoubleMapNode * pNode2;
301 pNode2 = (DoubleMapNode *) myData2[iK2];
304 if (Hasher2::IsEqual(pNode2->Key2(), theKey2))
305 return Standard_True;
306 pNode2 = (DoubleMapNode *) pNode2->Next2();
308 return Standard_False;
312 Standard_Boolean UnBind1 (const TheKey1Type& theKey1)
315 return Standard_False;
316 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
317 DoubleMapNode * p1, * p2, * q1, *q2;
319 p1 = (DoubleMapNode *) myData1[iK1];
322 if (Hasher1::IsEqual (p1->Key1(), theKey1))
324 // remove from the data1
326 q1->Next() = p1->Next();
328 myData1[iK1] = (DoubleMapNode*) p1->Next();
329 Standard_Integer iK2 = Hasher2::HashCode (p1->Key2(), NbBuckets());
330 p2 = (DoubleMapNode *) myData2[iK2];
335 // remove from the data2
337 q2->Next2() = p2->Next2();
339 myData2[iK2] = (DoubleMapNode*) p2->Next2();
343 p2 = (DoubleMapNode*) p2->Next2();
345 p1->~DoubleMapNode();
346 this->myAllocator->Free(p1);
348 return Standard_True;
351 p1 = (DoubleMapNode*) p1->Next();
353 return Standard_False;
357 Standard_Boolean UnBind2 (const TheKey2Type& theKey2)
360 return Standard_False;
361 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
362 DoubleMapNode * p1, * p2, * q1, *q2;
364 p2 = (DoubleMapNode *) myData2[iK2];
367 if (Hasher2::IsEqual (p2->Key2(), theKey2))
369 // remove from the data2
371 q2->Next() = p2->Next();
373 myData2[iK2] = (DoubleMapNode*) p2->Next2();
374 Standard_Integer iK1 = Hasher1::HashCode (p2->Key1(), NbBuckets());
375 p1 = (DoubleMapNode *) myData1[iK1];
380 // remove from the data1
382 q1->Next() = p1->Next();
384 myData1[iK1] = (DoubleMapNode*) p1->Next();
388 p1 = (DoubleMapNode*) p1->Next();
390 p2->~DoubleMapNode();
391 this->myAllocator->Free(p2);
393 return Standard_True;
396 p2 = (DoubleMapNode*) p2->Next2();
398 return Standard_False;
401 //! Find the Key1 and return Key2 value.
402 //! Raises an exception if Key1 was not bound.
403 const TheKey2Type& Find1(const TheKey1Type& theKey1) const
405 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_DoubleMap::Find1");
406 DoubleMapNode * pNode1 =
407 (DoubleMapNode *) myData1[Hasher1::HashCode(theKey1,NbBuckets())];
410 if (Hasher1::IsEqual (pNode1->Key1(), theKey1))
411 return pNode1->Key2();
412 pNode1 = (DoubleMapNode*) pNode1->Next();
414 throw Standard_NoSuchObject("NCollection_DoubleMap::Find1");
417 //! Find the Key1 and return Key2 value (by copying its value).
418 //! @param [in] theKey1 Key1 to find
419 //! @param [out] theKey2 Key2 to return
420 //! @return TRUE if Key1 has been found
421 Standard_Boolean Find1 (const TheKey1Type& theKey1,
422 TheKey2Type& theKey2) const
424 for (DoubleMapNode* aNode1 = !IsEmpty() ? (DoubleMapNode* )myData1[Hasher1::HashCode (theKey1, NbBuckets())] : NULL;
425 aNode1 != NULL; aNode1 = (DoubleMapNode* )aNode1->Next())
427 if (Hasher1::IsEqual (aNode1->Key1(), theKey1))
429 theKey2 = aNode1->Key2();
430 return Standard_True;
433 return Standard_False;
436 //! Find the Key2 and return Key1 value.
437 //! Raises an exception if Key2 was not bound.
438 const TheKey1Type& Find2(const TheKey2Type& theKey2) const
440 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_DoubleMap::Find2");
441 DoubleMapNode * pNode2 =
442 (DoubleMapNode *) myData2[Hasher2::HashCode(theKey2,NbBuckets())];
445 if (Hasher2::IsEqual (pNode2->Key2(), theKey2))
446 return pNode2->Key1();
447 pNode2 = (DoubleMapNode*) pNode2->Next2();
449 throw Standard_NoSuchObject("NCollection_DoubleMap::Find2");
452 //! Find the Key2 and return Key1 value (by copying its value).
453 //! @param [in] theKey2 Key2 to find
454 //! @param [out] theKey1 Key1 to return
455 //! @return TRUE if Key2 has been found
456 Standard_Boolean Find2 (const TheKey2Type& theKey2,
457 TheKey1Type& theKey1) const
459 for (DoubleMapNode* aNode2 = !IsEmpty() ? (DoubleMapNode* )myData2[Hasher2::HashCode (theKey2, NbBuckets())] : NULL;
460 aNode2 != NULL; aNode2 = (DoubleMapNode* )aNode2->Next2())
462 if (Hasher2::IsEqual (aNode2->Key2(), theKey2))
464 theKey1 = aNode2->Key1();
465 return Standard_True;
468 return Standard_False;
471 //! Clear data. If doReleaseMemory is false then the table of
472 //! buckets is not released and will be reused.
473 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
474 { Destroy (DoubleMapNode::delNode, doReleaseMemory); }
476 //! Clear data and reset allocator
477 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
480 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
481 NCollection_BaseAllocator::CommonBaseAllocator() );
485 ~NCollection_DoubleMap (void)
489 Standard_Integer Size(void) const