0024911: Avoid using virtual functions in NCollection classes
[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   // **************** Adaptation of the TListNode to the DOUBLEmap
44  public:
45   class DoubleMapNode : public NCollection_TListNode<TheKey2Type>
46   {
47   public:
48     //! Constructor with 'Next'
49     DoubleMapNode (const TheKey1Type&    theKey1, 
50                    const TheKey2Type&    theKey2, 
51                    NCollection_ListNode* theNext1, 
52                    NCollection_ListNode* theNext2) :
53                    NCollection_TListNode<TheKey2Type> (theKey2, theNext1)
54     { 
55       myKey1 = theKey1;
56       myNext2 = (DoubleMapNode *) theNext2;
57     }
58     //! Key1
59     const TheKey1Type& Key1 (void)
60     { return myKey1; }
61     //! Key2
62     const TheKey2Type& Key2 (void)
63     { return this->myValue; }
64     //! Next2
65     DoubleMapNode*& Next2 (void)
66     { return myNext2; }
67     
68     //! Static deleter to be passed to BaseList
69     static void delNode (NCollection_ListNode * theNode, 
70                          Handle(NCollection_BaseAllocator)& theAl)
71     {
72       ((DoubleMapNode *) theNode)->~DoubleMapNode();
73       theAl->Free(theNode);
74     }
75
76   private:
77     TheKey1Type    myKey1;
78     DoubleMapNode *myNext2;
79   };
80
81  public:
82   // **************** Implementation of the Iterator interface.
83   class Iterator : public NCollection_BaseMap::Iterator
84   {
85   public:
86     //! Empty constructor
87     Iterator (void) {}
88     //! Constructor
89     Iterator (const NCollection_DoubleMap& theMap) :
90       NCollection_BaseMap::Iterator(theMap) {}
91     //! Query if the end of collection is reached by iterator
92     Standard_Boolean More(void) const
93     { return PMore(); }
94     //! Make a step along the collection
95     void Next(void)
96     { PNext(); }
97     //! Key1 inquiry
98     const TheKey1Type& Key1(void) const
99     {
100 #if !defined No_Exception && !defined No_Standard_NoSuchObject
101       if (!More())
102          Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Key1");
103 #endif
104       return ((DoubleMapNode *) myNode)->Key1();
105     }
106     //! Key2 inquiry
107     const TheKey2Type& Key2(void) const
108     {  
109 #if !defined No_Exception && !defined No_Standard_NoSuchObject
110       if (!More())
111          Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Key2");
112 #endif
113       return ((DoubleMapNode *) myNode)->Key2();
114     }
115     //! Value access
116     const TheKey2Type& Value(void) const
117     {  
118 #if !defined No_Exception && !defined No_Standard_NoSuchObject
119       if (!More())
120          Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Value");
121 #endif
122       return ((DoubleMapNode *) myNode)->Value();
123     }
124     //! Value change access - denied
125     TheKey2Type& ChangeValue(void) const
126     {  
127       Standard_ImmutableObject::Raise("NCollection_DoubleMap::Iterator::ChangeValue");
128       return * (TheKey2Type *) NULL; // For compiler
129     }
130   };
131
132  public:
133   // ---------- PUBLIC METHODS ------------
134
135   //! Constructor
136   NCollection_DoubleMap (const Standard_Integer NbBuckets=1,
137                      const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
138     : NCollection_BaseMap (NbBuckets, Standard_False, theAllocator) {}
139
140   //! Copy constructor
141   NCollection_DoubleMap (const NCollection_DoubleMap& theOther)
142     : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator) 
143   { *this = theOther; }
144
145   //! Exchange the content of two maps without re-allocations.
146   //! Notice that allocators will be swapped as well!
147   void Exchange (NCollection_DoubleMap& theOther)
148   {
149     this->exchangeMapsData (theOther);
150   }
151
152   //! Assignment
153   NCollection_DoubleMap& Assign (const NCollection_DoubleMap& theOther)
154   { 
155     if (this == &theOther)
156       return *this;
157
158     Clear(theOther.myAllocator);
159     ReSize (theOther.Extent()-1);
160     Iterator anIter(theOther);
161     for (; anIter.More(); anIter.Next())
162     {
163       TheKey1Type aKey1 = anIter.Key1();
164       TheKey2Type aKey2 = anIter.Key2();
165       Standard_Integer iK1 = Hasher1::HashCode (aKey1, NbBuckets());
166       Standard_Integer iK2 = Hasher2::HashCode (aKey2, NbBuckets());
167       DoubleMapNode * pNode = new (this->myAllocator) DoubleMapNode (aKey1, aKey2, 
168                                                                      myData1[iK1], 
169                                                                      myData2[iK2]);
170       myData1[iK1] = pNode;
171       myData2[iK2] = pNode;
172       Increment();
173     }
174     return *this;
175   }
176
177   //! Assignment operator
178   NCollection_DoubleMap& operator= (const NCollection_DoubleMap& theOther)
179   { 
180     return Assign (theOther);
181   }
182
183   //! ReSize
184   void ReSize (const Standard_Integer N)
185   {
186     NCollection_ListNode** ppNewData1 = NULL;
187     NCollection_ListNode** ppNewData2 = NULL;
188     Standard_Integer newBuck;
189     if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
190     {
191       if (myData1) 
192       {
193         DoubleMapNode *p, *q;
194         Standard_Integer i, iK1, iK2;
195         for (i = 0; i <= NbBuckets(); i++) 
196         {
197           if (myData1[i]) 
198           {
199             p = (DoubleMapNode *) myData1[i];
200             while (p) 
201             {
202               iK1 = Hasher1::HashCode (p->Key1(), newBuck);
203               iK2 = Hasher2::HashCode (p->Key2(), newBuck);
204               q = (DoubleMapNode*) p->Next();
205               p->Next()  = ppNewData1[iK1];
206               p->Next2() = (DoubleMapNode*)ppNewData2[iK2];
207               ppNewData1[iK1] = p;
208               ppNewData2[iK2] = p;
209               p = q;
210             }
211           }
212         }
213       }
214       EndResize (N, newBuck, ppNewData1, ppNewData2);
215     }
216   }
217
218   //! Bind
219   void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2)
220   {
221     if (Resizable()) 
222       ReSize(Extent());
223     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
224     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
225     DoubleMapNode * pNode;
226     pNode = (DoubleMapNode *) myData1[iK1];
227     while (pNode) 
228     {
229       if (Hasher1::IsEqual (pNode->Key1(), theKey1))
230         Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind");
231       pNode = (DoubleMapNode *) pNode->Next();
232     }
233     pNode = (DoubleMapNode *) myData2[iK2];
234     while (pNode) 
235     {
236       if (Hasher2::IsEqual (pNode->Key2(), theKey2))
237         Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind");
238       pNode = (DoubleMapNode *) pNode->Next();
239     }
240     pNode = new (this->myAllocator) DoubleMapNode (theKey1, theKey2, 
241                                                    myData1[iK1], myData2[iK2]);
242     myData1[iK1] = pNode;
243     myData2[iK2] = pNode;
244     Increment();
245   }
246
247   //!* AreBound
248   Standard_Boolean AreBound (const TheKey1Type& theKey1,
249                              const TheKey2Type& theKey2) const
250   {
251     if (IsEmpty()) 
252       return Standard_False;
253     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
254     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
255     DoubleMapNode * pNode1, * pNode2;
256     pNode1 = (DoubleMapNode *) myData1[iK1];
257     while (pNode1) 
258     {
259       if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) 
260         break;
261       pNode1 = (DoubleMapNode *) pNode1->Next();
262     }
263     if (pNode1 == NULL)
264       return Standard_False;
265     pNode2 = (DoubleMapNode *) myData2[iK2];
266     while (pNode2) 
267     {
268       if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) 
269         break;
270       pNode2 = (DoubleMapNode *) pNode2->Next();
271     }
272     if (pNode2 == NULL)
273       return Standard_False;
274
275     return (pNode1 == pNode2);
276   }
277
278   //! IsBound1
279   Standard_Boolean IsBound1 (const TheKey1Type& theKey1) const
280   {
281     if (IsEmpty()) 
282       return Standard_False;
283     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
284     DoubleMapNode * pNode1;
285     pNode1 = (DoubleMapNode *) myData1[iK1];
286     while (pNode1) 
287     {
288       if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) 
289         return Standard_True;
290       pNode1 = (DoubleMapNode *) pNode1->Next();
291     }
292     return Standard_False;
293   }
294
295   //! IsBound2
296   Standard_Boolean IsBound2 (const TheKey2Type& theKey2) const
297   {
298     if (IsEmpty()) 
299       return Standard_False;
300     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
301     DoubleMapNode * pNode2;
302     pNode2 = (DoubleMapNode *) myData2[iK2];
303     while (pNode2) 
304     {
305       if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) 
306         return Standard_True;
307       pNode2 = (DoubleMapNode *) pNode2->Next2();
308     }
309     return Standard_False;
310   }
311
312   //! UnBind1
313   Standard_Boolean UnBind1 (const TheKey1Type& theKey1)
314   {
315     if (IsEmpty()) 
316       return Standard_False;
317     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
318     DoubleMapNode * p1, * p2, * q1, *q2;
319     q1 = q2 = NULL;
320     p1 = (DoubleMapNode *) myData1[iK1];
321     while (p1) 
322     {
323       if (Hasher1::IsEqual (p1->Key1(), theKey1)) 
324       {
325         // remove from the data1
326         if (q1) 
327           q1->Next() = p1->Next();
328         else
329           myData1[iK1] = (DoubleMapNode*) p1->Next();
330         Standard_Integer iK2 = Hasher2::HashCode (p1->Key2(), NbBuckets());
331         p2 = (DoubleMapNode *) myData2[iK2];
332         while (p2)
333         {
334           if (p2 == p1) 
335           {
336             // remove from the data2
337             if (q2) 
338               q2->Next2() = p2->Next2();
339             else
340               myData2[iK2] = (DoubleMapNode*) p2->Next2();
341             break;
342           }
343           q2 = p2;
344           p2 = (DoubleMapNode*) p2->Next2();
345         }
346         p1->~DoubleMapNode();
347         this->myAllocator->Free(p1);
348         Decrement();
349         return Standard_True;
350       }
351       q1 = p1;
352       p1 = (DoubleMapNode*) p1->Next();
353     }
354     return Standard_False;
355   }
356
357   //! UnBind2
358   Standard_Boolean UnBind2 (const TheKey2Type& theKey2)
359   {
360     if (IsEmpty()) 
361       return Standard_False;
362     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
363     DoubleMapNode * p1, * p2, * q1, *q2;
364     q1 = q2 = NULL;
365     p2 = (DoubleMapNode *) myData2[iK2];
366     while (p2) 
367     {
368       if (Hasher2::IsEqual (p2->Key2(), theKey2)) 
369       {
370         // remove from the data2
371         if (q2)
372           q2->Next() = p2->Next();
373         else
374           myData2[iK2] = (DoubleMapNode*) p2->Next2();
375         Standard_Integer iK1 = Hasher1::HashCode (p2->Key1(), NbBuckets());
376         p1 = (DoubleMapNode *) myData1[iK1];
377         while (p1)
378         {
379           if (p1 == p2) 
380           {
381             // remove from the data1
382             if (q1)
383               q1->Next() = p1->Next();
384             else
385               myData1[iK1] = (DoubleMapNode*) p1->Next();
386             break;
387           }
388           q1 = p1;
389           p1 = (DoubleMapNode*) p1->Next();
390         }
391         p2->~DoubleMapNode();
392         this->myAllocator->Free(p2);
393         Decrement();
394         return Standard_True;
395       }
396       q2 = p2;
397       p2 = (DoubleMapNode*) p2->Next2();
398     }
399     return Standard_False;
400   }
401
402   //! Find1
403   const TheKey2Type& Find1(const TheKey1Type& theKey1) const
404   {
405 #if !defined No_Exception && !defined No_Standard_NoSuchObject
406     if (IsEmpty())
407       Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Find1");
408 #endif
409     DoubleMapNode * pNode1 = 
410       (DoubleMapNode *) myData1[Hasher1::HashCode(theKey1,NbBuckets())];
411     while (pNode1)
412     {
413       if (Hasher1::IsEqual (pNode1->Key1(), theKey1)) 
414         return pNode1->Key2();
415       pNode1 = (DoubleMapNode*) pNode1->Next();
416     }
417     Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find1");
418     return pNode1->Key2(); // This for compiler
419   }
420
421   //! Find2
422   const TheKey1Type& Find2(const TheKey2Type& theKey2) const
423   {
424 #if !defined No_Exception && !defined No_Standard_NoSuchObject
425     if (IsEmpty())
426       Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Find2");
427 #endif
428     DoubleMapNode * pNode2 = 
429       (DoubleMapNode *) myData2[Hasher2::HashCode(theKey2,NbBuckets())];
430     while (pNode2)
431     {
432       if (Hasher2::IsEqual (pNode2->Key2(), theKey2)) 
433         return pNode2->Key1();
434       pNode2 = (DoubleMapNode*) pNode2->Next2();
435     }
436     Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find2");
437     return pNode2->Key1(); // This for compiler
438   }
439
440   //! Clear data. If doReleaseMemory is false then the table of
441   //! buckets is not released and will be reused.
442   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
443   { Destroy (DoubleMapNode::delNode, doReleaseMemory); }
444
445   //! Clear data and reset allocator
446   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
447   { 
448     Clear();
449     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
450                     NCollection_BaseAllocator::CommonBaseAllocator() );
451   }
452
453   //! Destructor
454   ~NCollection_DoubleMap (void)
455   { Clear(); }
456
457   //! Size
458   Standard_Integer Size(void) const
459   { return Extent(); }
460 };
461
462 #endif