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