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