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