0030547: Foundation Classes - NCollection_DoubleMap lacks Seek() method
[occt.git] / src / NCollection / NCollection_DoubleMap.hxx
1 // Created on: 2002-04-24
2 // Created by: Alexander KARTOMIN (akm)
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
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.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #ifndef NCollection_DoubleMap_HeaderFile
17 #define NCollection_DoubleMap_HeaderFile
18
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>
26
27 #include <NCollection_DefaultHasher.hxx>
28
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 */              
36
37 template < class TheKey1Type, 
38            class TheKey2Type, 
39            class Hasher1 = NCollection_DefaultHasher<TheKey1Type>, 
40            class Hasher2 = NCollection_DefaultHasher<TheKey2Type> >
41 class NCollection_DoubleMap : public NCollection_BaseMap
42 {
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:
50   // **************** Adaptation of the TListNode to the DOUBLEmap
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) :
59       NCollection_TListNode<TheKey2Type> (theKey2, theNext1),
60       myKey1(theKey1),
61       myNext2((DoubleMapNode*)theNext2)
62     { 
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.
89   class Iterator : public NCollection_BaseMap::Iterator
90   {
91   public:
92     //! Empty constructor
93     Iterator (void) {}
94     //! Constructor
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
99     { return PMore(); }
100     //! Make a step along the collection
101     void Next(void)
102     { PNext(); }
103     //! Key1 inquiry
104     const TheKey1Type& Key1(void) const
105     {
106       Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key1");
107       return ((DoubleMapNode *) myNode)->Key1();
108     }
109     //! Key2 inquiry
110     const TheKey2Type& Key2(void) const
111     {  
112       Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key2");
113       return ((DoubleMapNode *) myNode)->Key2();
114     }
115     //! Value access
116     const TheKey2Type& Value(void) const
117     {  
118       Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Value");
119       return ((DoubleMapNode *) myNode)->Value();
120     }
121   };
122
123  public:
124   // ---------- PUBLIC METHODS ------------
125
126   //! Empty constructor.
127   NCollection_DoubleMap() : NCollection_BaseMap (1, Standard_False, Handle(NCollection_BaseAllocator)()) {}
128
129   //! Constructor
130   explicit NCollection_DoubleMap (const Standard_Integer theNbBuckets,
131                                   const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
132   : NCollection_BaseMap (theNbBuckets, Standard_False, theAllocator) {}
133
134   //! Copy constructor
135   NCollection_DoubleMap (const NCollection_DoubleMap& theOther)
136     : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator) 
137   { *this = theOther; }
138
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   {
143     this->exchangeMapsData (theOther);
144   }
145
146   //! Assignment.
147   //! This method does not change the internal allocator.
148   NCollection_DoubleMap& Assign (const NCollection_DoubleMap& theOther)
149   { 
150     if (this == &theOther)
151       return *this;
152
153     Clear();
154     Standard_Integer anExt = theOther.Extent();
155     if (anExt)
156     {
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       }
172     }
173     return *this;
174   }
175
176   //! Assignment operator
177   NCollection_DoubleMap& operator= (const NCollection_DoubleMap& theOther)
178   {
179     return Assign (theOther);
180   }
181
182   //! ReSize
183   void ReSize (const Standard_Integer N)
184   {
185     NCollection_ListNode** ppNewData1 = NULL;
186     NCollection_ListNode** ppNewData2 = NULL;
187     Standard_Integer newBuck;
188     if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
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 = 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];
206               ppNewData1[iK1] = p;
207               ppNewData2[iK2] = p;
208               p = q;
209             }
210           }
211         }
212       }
213       EndResize (N, newBuck, ppNewData1, ppNewData2);
214     }
215   }
216
217   //! Bind
218   void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2)
219   {
220     if (Resizable()) 
221       ReSize(Extent());
222     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
223     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
224     DoubleMapNode * pNode;
225     pNode = (DoubleMapNode *) myData1[iK1];
226     while (pNode) 
227     {
228       if (Hasher1::IsEqual (pNode->Key1(), theKey1))
229         throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind");
230       pNode = (DoubleMapNode *) pNode->Next();
231     }
232     pNode = (DoubleMapNode *) myData2[iK2];
233     while (pNode) 
234     {
235       if (Hasher2::IsEqual (pNode->Key2(), theKey2))
236         throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind");
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;
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];
256     while (pNode1) 
257     {
258       if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) 
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     {
267       if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) 
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;
282     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
283     DoubleMapNode * pNode1;
284     pNode1 = (DoubleMapNode *) myData1[iK1];
285     while (pNode1) 
286     {
287       if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) 
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;
299     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
300     DoubleMapNode * pNode2;
301     pNode2 = (DoubleMapNode *) myData2[iK2];
302     while (pNode2) 
303     {
304       if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) 
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;
316     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
317     DoubleMapNode * p1, * p2, * q1, *q2;
318     q1 = q2 = NULL;
319     p1 = (DoubleMapNode *) myData1[iK1];
320     while (p1) 
321     {
322       if (Hasher1::IsEqual (p1->Key1(), theKey1)) 
323       {
324         // remove from the data1
325         if (q1) 
326           q1->Next() = p1->Next();
327         else
328           myData1[iK1] = (DoubleMapNode*) p1->Next();
329         Standard_Integer iK2 = Hasher2::HashCode (p1->Key2(), NbBuckets());
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;
361     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
362     DoubleMapNode * p1, * p2, * q1, *q2;
363     q1 = q2 = NULL;
364     p2 = (DoubleMapNode *) myData2[iK2];
365     while (p2) 
366     {
367       if (Hasher2::IsEqual (p2->Key2(), theKey2)) 
368       {
369         // remove from the data2
370         if (q2)
371           q2->Next() = p2->Next();
372         else
373           myData2[iK2] = (DoubleMapNode*) p2->Next2();
374         Standard_Integer iK1 = Hasher1::HashCode (p2->Key1(), NbBuckets());
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
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
404   {
405     if (const TheKey2Type* aKey2 = Seek1 (theKey1))
406     {
407       return *aKey2;
408     }
409     throw Standard_NoSuchObject("NCollection_DoubleMap::Find1");
410   }
411
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
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
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       {
437         return &aNode1->Key2();
438       }
439     }
440     return NULL;
441   }
442
443   //! Find the Key2 and return Key1 value.
444   //! Raises an exception if Key2 was not bound.
445   const TheKey1Type& Find2(const TheKey2Type& theKey2) const
446   {
447     if (const TheKey1Type* aVal1 = Seek2 (theKey2))
448     {
449       return *aVal1;
450     }
451     throw Standard_NoSuchObject("NCollection_DoubleMap::Find2");
452   }
453
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
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
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       {
479         return &aNode2->Key1();
480       }
481     }
482     return NULL;
483   }
484
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)
488   { Destroy (DoubleMapNode::delNode, doReleaseMemory); }
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
503   Standard_Integer Size(void) const
504   { return Extent(); }
505 };
506
507 #endif