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
8 // under the terms of the GNU Lesser General Public 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_BaseCollection.hxx>
21 #include <NCollection_BaseMap.hxx>
22 #include <NCollection_TListNode.hxx>
23 #include <Standard_TypeMismatch.hxx>
24 #include <Standard_MultiplyDefined.hxx>
25 #include <Standard_ImmutableObject.hxx>
26 #include <Standard_NoSuchObject.hxx>
28 #include <NCollection_DefaultHasher.hxx>
31 * Purpose: The DoubleMap is used to bind pairs (Key1,Key2)
32 * and retrieve them in linear time.
34 * See Map from NCollection for a discussion about the number
38 template < class TheKey1Type,
40 class Hasher1 = NCollection_DefaultHasher<TheKey1Type>,
41 class Hasher2 = NCollection_DefaultHasher<TheKey2Type> > class NCollection_DoubleMap
42 : public NCollection_BaseCollection<TheKey2Type>,
43 public NCollection_BaseMap
45 // **************** Adaptation of the TListNode to the DOUBLEmap
47 class DoubleMapNode : public NCollection_TListNode<TheKey2Type>
50 //! Constructor with 'Next'
51 DoubleMapNode (const TheKey1Type& theKey1,
52 const TheKey2Type& theKey2,
53 NCollection_ListNode* theNext1,
54 NCollection_ListNode* theNext2) :
55 NCollection_TListNode<TheKey2Type> (theKey2, theNext1)
58 myNext2 = (DoubleMapNode *) theNext2;
61 const TheKey1Type& Key1 (void)
64 const TheKey2Type& Key2 (void)
65 { return this->myValue; }
67 DoubleMapNode*& Next2 (void)
70 //! Static deleter to be passed to BaseList
71 static void delNode (NCollection_ListNode * theNode,
72 Handle(NCollection_BaseAllocator)& theAl)
74 ((DoubleMapNode *) theNode)->~DoubleMapNode();
80 DoubleMapNode *myNext2;
84 // **************** Implementation of the Iterator interface.
86 : public NCollection_BaseCollection<TheKey2Type>::Iterator,
87 public NCollection_BaseMap::Iterator
92 NCollection_BaseMap::Iterator() {}
94 Iterator (const NCollection_DoubleMap& theMap) :
95 NCollection_BaseMap::Iterator(theMap) {}
96 //! Query if the end of collection is reached by iterator
97 virtual Standard_Boolean More(void) const
99 //! Make a step along the collection
100 virtual void Next(void)
103 const TheKey1Type& Key1(void) const
105 #if !defined No_Exception && !defined No_Standard_NoSuchObject
107 Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Key1");
109 return ((DoubleMapNode *) myNode)->Key1();
112 const TheKey2Type& Key2(void) const
114 #if !defined No_Exception && !defined No_Standard_NoSuchObject
116 Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Key2");
118 return ((DoubleMapNode *) myNode)->Key2();
121 virtual const TheKey2Type& Value(void) const
123 #if !defined No_Exception && !defined No_Standard_NoSuchObject
125 Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Value");
127 return ((DoubleMapNode *) myNode)->Value();
129 //! Value change access - denied
130 virtual TheKey2Type& ChangeValue(void) const
132 Standard_ImmutableObject::Raise("NCollection_DoubleMap::Iterator::ChangeValue");
133 return * (TheKey2Type *) NULL; // For compiler
138 // ---------- PUBLIC METHODS ------------
141 NCollection_DoubleMap (const Standard_Integer NbBuckets=1,
142 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
143 : NCollection_BaseCollection<TheKey2Type>(theAllocator),
144 NCollection_BaseMap (NbBuckets, Standard_False) {}
147 NCollection_DoubleMap (const NCollection_DoubleMap& theOther)
148 : NCollection_BaseCollection<TheKey2Type>(theOther.myAllocator),
149 NCollection_BaseMap (theOther.NbBuckets(), Standard_False)
150 { *this = theOther; }
152 //! Assign another collection
153 virtual void Assign(const NCollection_BaseCollection<TheKey2Type>& theOther)
155 if (this == &theOther)
157 Standard_TypeMismatch::Raise ("NCollection_DoubleMap::Assign impossible");
160 //! Exchange the content of two maps without re-allocations.
161 //! Notice that allocators will be swapped as well!
162 void Exchange (NCollection_DoubleMap& theOther)
164 this->exchangeAllocators (theOther);
165 this->exchangeMapsData (theOther);
169 NCollection_DoubleMap& operator=(const NCollection_DoubleMap& theOther)
171 if (this == &theOther)
174 Clear(theOther.myAllocator);
175 ReSize (theOther.Extent()-1);
176 Iterator anIter(theOther);
177 for (; anIter.More(); anIter.Next())
179 TheKey1Type aKey1 = anIter.Key1();
180 TheKey2Type aKey2 = anIter.Key2();
181 Standard_Integer iK1 = Hasher1::HashCode (aKey1, NbBuckets());
182 Standard_Integer iK2 = Hasher2::HashCode (aKey2, NbBuckets());
183 DoubleMapNode * pNode = new (this->myAllocator) DoubleMapNode (aKey1, aKey2,
186 myData1[iK1] = pNode;
187 myData2[iK2] = pNode;
194 void ReSize (const Standard_Integer N)
196 DoubleMapNode** ppNewData1 = NULL;
197 DoubleMapNode** ppNewData2 = NULL;
198 Standard_Integer newBuck;
199 if (BeginResize (N, newBuck,
200 (NCollection_ListNode**&)ppNewData1,
201 (NCollection_ListNode**&)ppNewData2,
206 DoubleMapNode *p, *q;
207 Standard_Integer i, iK1, iK2;
208 for (i = 0; i <= NbBuckets(); i++)
212 p = (DoubleMapNode *) myData1[i];
215 iK1 = Hasher1::HashCode (p->Key1(), newBuck);
216 iK2 = Hasher2::HashCode (p->Key2(), newBuck);
217 q = (DoubleMapNode*) p->Next();
218 p->Next() = ppNewData1[iK1];
219 p->Next2() = ppNewData2[iK2];
228 (NCollection_ListNode**&)ppNewData1,
229 (NCollection_ListNode**&)ppNewData2,
235 void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2)
239 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
240 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
241 DoubleMapNode * pNode;
242 pNode = (DoubleMapNode *) myData1[iK1];
245 if (Hasher1::IsEqual (pNode->Key1(), theKey1))
246 Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind");
247 pNode = (DoubleMapNode *) pNode->Next();
249 pNode = (DoubleMapNode *) myData2[iK2];
252 if (Hasher2::IsEqual (pNode->Key2(), theKey2))
253 Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind");
254 pNode = (DoubleMapNode *) pNode->Next();
256 pNode = new (this->myAllocator) DoubleMapNode (theKey1, theKey2,
257 myData1[iK1], myData2[iK2]);
258 myData1[iK1] = pNode;
259 myData2[iK2] = pNode;
264 Standard_Boolean AreBound (const TheKey1Type& theKey1,
265 const TheKey2Type& theKey2) const
268 return Standard_False;
269 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
270 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
271 DoubleMapNode * pNode1, * pNode2;
272 pNode1 = (DoubleMapNode *) myData1[iK1];
275 if (Hasher1::IsEqual(pNode1->Key1(), theKey1))
277 pNode1 = (DoubleMapNode *) pNode1->Next();
280 return Standard_False;
281 pNode2 = (DoubleMapNode *) myData2[iK2];
284 if (Hasher2::IsEqual(pNode2->Key2(), theKey2))
286 pNode2 = (DoubleMapNode *) pNode2->Next();
289 return Standard_False;
291 return (pNode1 == pNode2);
295 Standard_Boolean IsBound1 (const TheKey1Type& theKey1) const
298 return Standard_False;
299 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
300 DoubleMapNode * pNode1;
301 pNode1 = (DoubleMapNode *) myData1[iK1];
304 if (Hasher1::IsEqual(pNode1->Key1(), theKey1))
305 return Standard_True;
306 pNode1 = (DoubleMapNode *) pNode1->Next();
308 return Standard_False;
312 Standard_Boolean IsBound2 (const TheKey2Type& theKey2) const
315 return Standard_False;
316 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
317 DoubleMapNode * pNode2;
318 pNode2 = (DoubleMapNode *) myData2[iK2];
321 if (Hasher2::IsEqual(pNode2->Key2(), theKey2))
322 return Standard_True;
323 pNode2 = (DoubleMapNode *) pNode2->Next2();
325 return Standard_False;
329 Standard_Boolean UnBind1 (const TheKey1Type& theKey1)
332 return Standard_False;
333 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
334 DoubleMapNode * p1, * p2, * q1, *q2;
336 p1 = (DoubleMapNode *) myData1[iK1];
339 if (Hasher1::IsEqual (p1->Key1(), theKey1))
341 // remove from the data1
343 q1->Next() = p1->Next();
345 myData1[iK1] = (DoubleMapNode*) p1->Next();
346 Standard_Integer iK2 = Hasher2::HashCode (p1->Key2(), NbBuckets());
347 p2 = (DoubleMapNode *) myData2[iK2];
352 // remove from the data2
354 q2->Next2() = p2->Next2();
356 myData2[iK2] = (DoubleMapNode*) p2->Next2();
360 p2 = (DoubleMapNode*) p2->Next2();
362 p1->~DoubleMapNode();
363 this->myAllocator->Free(p1);
365 return Standard_True;
368 p1 = (DoubleMapNode*) p1->Next();
370 return Standard_False;
374 Standard_Boolean UnBind2 (const TheKey2Type& theKey2)
377 return Standard_False;
378 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
379 DoubleMapNode * p1, * p2, * q1, *q2;
381 p2 = (DoubleMapNode *) myData2[iK2];
384 if (Hasher2::IsEqual (p2->Key2(), theKey2))
386 // remove from the data2
388 q2->Next() = p2->Next();
390 myData2[iK2] = (DoubleMapNode*) p2->Next2();
391 Standard_Integer iK1 = Hasher1::HashCode (p2->Key1(), NbBuckets());
392 p1 = (DoubleMapNode *) myData1[iK1];
397 // remove from the data1
399 q1->Next() = p1->Next();
401 myData1[iK1] = (DoubleMapNode*) p1->Next();
405 p1 = (DoubleMapNode*) p1->Next();
407 p2->~DoubleMapNode();
408 this->myAllocator->Free(p2);
410 return Standard_True;
413 p2 = (DoubleMapNode*) p2->Next2();
415 return Standard_False;
419 const TheKey2Type& Find1(const TheKey1Type& theKey1) const
421 #if !defined No_Exception && !defined No_Standard_NoSuchObject
423 Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Find1");
425 DoubleMapNode * pNode1 =
426 (DoubleMapNode *) myData1[Hasher1::HashCode(theKey1,NbBuckets())];
429 if (Hasher1::IsEqual (pNode1->Key1(), theKey1))
430 return pNode1->Key2();
431 pNode1 = (DoubleMapNode*) pNode1->Next();
433 Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find1");
434 return pNode1->Key2(); // This for compiler
438 const TheKey1Type& Find2(const TheKey2Type& theKey2) const
440 #if !defined No_Exception && !defined No_Standard_NoSuchObject
442 Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Find2");
444 DoubleMapNode * pNode2 =
445 (DoubleMapNode *) myData2[Hasher2::HashCode(theKey2,NbBuckets())];
448 if (Hasher2::IsEqual (pNode2->Key2(), theKey2))
449 return pNode2->Key1();
450 pNode2 = (DoubleMapNode*) pNode2->Next2();
452 Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find2");
453 return pNode2->Key1(); // This for compiler
456 //! Clear data. If doReleaseMemory is false then the table of
457 //! buckets is not released and will be reused.
458 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
459 { Destroy (DoubleMapNode::delNode, this->myAllocator, doReleaseMemory); }
461 //! Clear data and reset allocator
462 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
465 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
466 NCollection_BaseAllocator::CommonBaseAllocator() );
470 ~NCollection_DoubleMap (void)
474 virtual Standard_Integer Size(void) const
478 // ----------- PRIVATE METHODS -----------
480 //! Creates Iterator for use on BaseCollection
481 virtual TYPENAME NCollection_BaseCollection<TheKey2Type>::Iterator&
482 CreateIterator(void) const
483 { return *(new (this->IterAllocator()) Iterator(*this)); }