1 // File: NCollection_DoubleMap.hxx
2 // Created: Thu Apr 24 15:02:53 2002
3 // Author: Alexander KARTOMIN (akm)
4 // <akm@opencascade.com>
6 #ifndef NCollection_DoubleMap_HeaderFile
7 #define NCollection_DoubleMap_HeaderFile
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>
18 #include <NCollection_DefaultHasher.hxx>
21 * Purpose: The DoubleMap is used to bind pairs (Key1,Key2)
22 * and retrieve them in linear time.
24 * See Map from NCollection for a discussion about the number
28 template < class TheKey1Type,
30 class Hasher1 = NCollection_DefaultHasher<TheKey1Type>,
31 class Hasher2 = NCollection_DefaultHasher<TheKey2Type> > class NCollection_DoubleMap
32 : public NCollection_BaseCollection<TheKey2Type>,
33 public NCollection_BaseMap
35 // **************** Adaptation of the TListNode to the DOUBLEmap
37 class DoubleMapNode : public NCollection_TListNode<TheKey2Type>
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)
48 myNext2 = (DoubleMapNode *) theNext2;
51 const TheKey1Type& Key1 (void)
54 const TheKey2Type& Key2 (void)
55 { return this->myValue; }
57 DoubleMapNode*& Next2 (void)
60 //! Static deleter to be passed to BaseList
61 static void delNode (NCollection_ListNode * theNode,
62 Handle(NCollection_BaseAllocator)& theAl)
64 ((DoubleMapNode *) theNode)->~DoubleMapNode();
70 DoubleMapNode *myNext2;
74 // **************** Implementation of the Iterator interface.
76 : public NCollection_BaseCollection<TheKey2Type>::Iterator,
77 public NCollection_BaseMap::Iterator
82 NCollection_BaseMap::Iterator() {}
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
89 //! Make a step along the collection
90 virtual void Next(void)
93 const TheKey1Type& Key1(void) const
95 #if !defined No_Exception && !defined No_Standard_NoSuchObject
97 Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Key1");
99 return ((DoubleMapNode *) myNode)->Key1();
102 const TheKey2Type& Key2(void) const
104 #if !defined No_Exception && !defined No_Standard_NoSuchObject
106 Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Key2");
108 return ((DoubleMapNode *) myNode)->Key2();
111 virtual const TheKey2Type& Value(void) const
113 #if !defined No_Exception && !defined No_Standard_NoSuchObject
115 Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Value");
117 return ((DoubleMapNode *) myNode)->Value();
119 //! Value change access - denied
120 virtual TheKey2Type& ChangeValue(void) const
122 Standard_ImmutableObject::Raise("NCollection_DoubleMap::Iterator::ChangeValue");
123 return * (TheKey2Type *) NULL; // For compiler
128 // ---------- PUBLIC METHODS ------------
131 NCollection_DoubleMap (const Standard_Integer NbBuckets=1,
132 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
133 : NCollection_BaseCollection<TheKey2Type>(theAllocator),
134 NCollection_BaseMap (NbBuckets, Standard_False) {}
137 NCollection_DoubleMap (const NCollection_DoubleMap& theOther)
138 : NCollection_BaseCollection<TheKey2Type>(theOther.myAllocator),
139 NCollection_BaseMap (theOther.NbBuckets(), Standard_False)
140 { *this = theOther; }
142 //! Assign another collection
143 virtual void Assign(const NCollection_BaseCollection<TheKey2Type>& theOther)
145 if (this == &theOther)
147 Standard_TypeMismatch::Raise ("NCollection_DoubleMap::Assign impossible");
151 NCollection_DoubleMap& operator=(const NCollection_DoubleMap& theOther)
153 if (this == &theOther)
156 Clear(theOther.myAllocator);
157 ReSize (theOther.Extent()-1);
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 void ReSize (const Standard_Integer N)
178 DoubleMapNode** ppNewData1 = NULL;
179 DoubleMapNode** ppNewData2 = NULL;
180 Standard_Integer newBuck;
181 if (BeginResize (N, newBuck,
182 (NCollection_ListNode**&)ppNewData1,
183 (NCollection_ListNode**&)ppNewData2,
188 DoubleMapNode *p, *q;
189 Standard_Integer i, iK1, iK2;
190 for (i = 0; i <= NbBuckets(); i++)
194 p = (DoubleMapNode *) myData1[i];
197 iK1 = Hasher1::HashCode (p->Key1(), newBuck);
198 iK2 = Hasher2::HashCode (p->Key2(), newBuck);
199 q = (DoubleMapNode*) p->Next();
200 p->Next() = ppNewData1[iK1];
201 p->Next2() = ppNewData2[iK2];
210 (NCollection_ListNode**&)ppNewData1,
211 (NCollection_ListNode**&)ppNewData2,
217 void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2)
221 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
222 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
223 DoubleMapNode * pNode;
224 pNode = (DoubleMapNode *) myData1[iK1];
227 if (Hasher1::IsEqual (pNode->Key1(), theKey1))
228 Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind");
229 pNode = (DoubleMapNode *) pNode->Next();
231 pNode = (DoubleMapNode *) myData2[iK2];
234 if (Hasher2::IsEqual (pNode->Key2(), theKey2))
235 Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind");
236 pNode = (DoubleMapNode *) pNode->Next();
238 pNode = new (this->myAllocator) DoubleMapNode (theKey1, theKey2,
239 myData1[iK1], myData2[iK2]);
240 myData1[iK1] = pNode;
241 myData2[iK2] = pNode;
246 Standard_Boolean AreBound (const TheKey1Type& theKey1,
247 const TheKey2Type& theKey2) const
250 return Standard_False;
251 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
252 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
253 DoubleMapNode * pNode1, * pNode2;
254 pNode1 = (DoubleMapNode *) myData1[iK1];
257 if (Hasher1::IsEqual(pNode1->Key1(), theKey1))
259 pNode1 = (DoubleMapNode *) pNode1->Next();
262 return Standard_False;
263 pNode2 = (DoubleMapNode *) myData2[iK2];
266 if (Hasher2::IsEqual(pNode2->Key2(), theKey2))
268 pNode2 = (DoubleMapNode *) pNode2->Next();
271 return Standard_False;
273 return (pNode1 == pNode2);
277 Standard_Boolean IsBound1 (const TheKey1Type& theKey1) const
280 return Standard_False;
281 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
282 DoubleMapNode * pNode1;
283 pNode1 = (DoubleMapNode *) myData1[iK1];
286 if (Hasher1::IsEqual(pNode1->Key1(), theKey1))
287 return Standard_True;
288 pNode1 = (DoubleMapNode *) pNode1->Next();
290 return Standard_False;
294 Standard_Boolean IsBound2 (const TheKey2Type& theKey2) const
297 return Standard_False;
298 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
299 DoubleMapNode * pNode2;
300 pNode2 = (DoubleMapNode *) myData2[iK2];
303 if (Hasher2::IsEqual(pNode2->Key2(), theKey2))
304 return Standard_True;
305 pNode2 = (DoubleMapNode *) pNode2->Next2();
307 return Standard_False;
311 Standard_Boolean UnBind1 (const TheKey1Type& theKey1)
314 return Standard_False;
315 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
316 DoubleMapNode * p1, * p2, * q1, *q2;
318 p1 = (DoubleMapNode *) myData1[iK1];
321 if (Hasher1::IsEqual (p1->Key1(), theKey1))
323 // remove from the data1
325 q1->Next() = p1->Next();
327 myData1[iK1] = (DoubleMapNode*) p1->Next();
328 Standard_Integer iK2 = Hasher2::HashCode (p1->Key2(), NbBuckets());
329 p2 = (DoubleMapNode *) myData2[iK2];
334 // remove from the data2
336 q2->Next2() = p2->Next2();
338 myData2[iK2] = (DoubleMapNode*) p2->Next2();
342 p2 = (DoubleMapNode*) p2->Next2();
344 p1->~DoubleMapNode();
345 this->myAllocator->Free(p1);
347 return Standard_True;
350 p1 = (DoubleMapNode*) p1->Next();
352 return Standard_False;
356 Standard_Boolean UnBind2 (const TheKey2Type& theKey2)
359 return Standard_False;
360 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
361 DoubleMapNode * p1, * p2, * q1, *q2;
363 p2 = (DoubleMapNode *) myData2[iK2];
366 if (Hasher2::IsEqual (p2->Key2(), theKey2))
368 // remove from the data2
370 q2->Next() = p2->Next();
372 myData2[iK2] = (DoubleMapNode*) p2->Next2();
373 Standard_Integer iK1 = Hasher1::HashCode (p2->Key1(), NbBuckets());
374 p1 = (DoubleMapNode *) myData1[iK1];
379 // remove from the data1
381 q1->Next() = p1->Next();
383 myData1[iK1] = (DoubleMapNode*) p1->Next();
387 p1 = (DoubleMapNode*) p1->Next();
389 p2->~DoubleMapNode();
390 this->myAllocator->Free(p2);
392 return Standard_True;
395 p2 = (DoubleMapNode*) p2->Next2();
397 return Standard_False;
401 const TheKey2Type& Find1(const TheKey1Type& theKey1) const
403 #if !defined No_Exception && !defined No_Standard_NoSuchObject
405 Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Find1");
407 DoubleMapNode * pNode1 =
408 (DoubleMapNode *) myData1[Hasher1::HashCode(theKey1,NbBuckets())];
411 if (Hasher1::IsEqual (pNode1->Key1(), theKey1))
412 return pNode1->Key2();
413 pNode1 = (DoubleMapNode*) pNode1->Next();
415 Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find1");
416 return pNode1->Key2(); // This for compiler
420 const TheKey1Type& Find2(const TheKey2Type& theKey2) const
422 #if !defined No_Exception && !defined No_Standard_NoSuchObject
424 Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Find2");
426 DoubleMapNode * pNode2 =
427 (DoubleMapNode *) myData2[Hasher2::HashCode(theKey2,NbBuckets())];
430 if (Hasher2::IsEqual (pNode2->Key2(), theKey2))
431 return pNode2->Key1();
432 pNode2 = (DoubleMapNode*) pNode2->Next2();
434 Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find2");
435 return pNode2->Key1(); // This for compiler
438 //! Clear data. If doReleaseMemory is false then the table of
439 //! buckets is not released and will be reused.
440 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
441 { Destroy (DoubleMapNode::delNode, this->myAllocator, doReleaseMemory); }
443 //! Clear data and reset allocator
444 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
447 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
448 NCollection_BaseAllocator::CommonBaseAllocator() );
452 ~NCollection_DoubleMap (void)
456 virtual Standard_Integer Size(void) const
460 // ----------- PRIVATE METHODS -----------
462 //! Creates Iterator for use on BaseCollection
463 virtual TYPENAME NCollection_BaseCollection<TheKey2Type>::Iterator&
464 CreateIterator(void) const
465 { return *(new (this->IterAllocator()) Iterator(*this)); }