0024271: Provide Boolean operations for NCollection_Map
[occt.git] / src / NCollection / NCollection_DoubleMap.hxx
1 // Created on: 2002-04-24
2 // Created by: Alexander KARTOMIN (akm)
3 // Copyright (c) 2002-2012 OPEN CASCADE SAS
4 //
5 // The content of this file is subject to the Open CASCADE Technology Public
6 // License Version 6.5 (the "License"). You may not use the content of this file
7 // except in compliance with the License. Please obtain a copy of the License
8 // at http://www.opencascade.org and read it completely before using this file.
9 //
10 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
11 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
12 //
13 // The Original Code and all software distributed under the License is
14 // distributed on an "AS IS" basis, without warranty of any kind, and the
15 // Initial Developer hereby disclaims all such warranties, including without
16 // limitation, any warranties of merchantability, fitness for a particular
17 // purpose or non-infringement. Please see the License for the specific terms
18 // and conditions governing the rights and limitations under the License.
19
20 #ifndef NCollection_DoubleMap_HeaderFile
21 #define NCollection_DoubleMap_HeaderFile
22
23 #include <NCollection_TypeDef.hxx>
24 #include <NCollection_BaseCollection.hxx>
25 #include <NCollection_BaseMap.hxx>
26 #include <NCollection_TListNode.hxx>
27 #include <Standard_TypeMismatch.hxx>
28 #include <Standard_MultiplyDefined.hxx>
29 #include <Standard_ImmutableObject.hxx>
30 #include <Standard_NoSuchObject.hxx>
31
32 #include <NCollection_DefaultHasher.hxx>
33
34 /**
35 * Purpose:     The DoubleMap  is used to  bind  pairs (Key1,Key2)
36 *              and retrieve them in linear time.
37 *              
38 *              See Map from NCollection for a discussion about the number
39 *              of buckets
40 */              
41
42 template < class TheKey1Type, 
43            class TheKey2Type, 
44            class Hasher1 = NCollection_DefaultHasher<TheKey1Type>, 
45            class Hasher2 = NCollection_DefaultHasher<TheKey2Type> > class NCollection_DoubleMap 
46   : public NCollection_BaseCollection<TheKey2Type>,
47     public NCollection_BaseMap
48 {
49   // **************** Adaptation of the TListNode to the DOUBLEmap
50  public:
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     { 
61       myKey1 = theKey1;
62       myNext2 = (DoubleMapNode *) theNext2;
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 
90     : public NCollection_BaseCollection<TheKey2Type>::Iterator,
91       public NCollection_BaseMap::Iterator
92   {
93   public:
94     //! Empty constructor
95     Iterator (void) :
96       NCollection_BaseMap::Iterator() {}
97     //! Constructor
98     Iterator (const NCollection_DoubleMap& theMap) :
99       NCollection_BaseMap::Iterator(theMap) {}
100     //! Query if the end of collection is reached by iterator
101     virtual Standard_Boolean More(void) const
102     { return PMore(); }
103     //! Make a step along the collection
104     virtual void Next(void)
105     { PNext(); }
106     //! Key1 inquiry
107     const TheKey1Type& Key1(void) const
108     {
109 #if !defined No_Exception && !defined No_Standard_NoSuchObject
110       if (!More())
111          Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Key1");
112 #endif
113       return ((DoubleMapNode *) myNode)->Key1();
114     }
115     //! Key2 inquiry
116     const TheKey2Type& Key2(void) const
117     {  
118 #if !defined No_Exception && !defined No_Standard_NoSuchObject
119       if (!More())
120          Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Key2");
121 #endif
122       return ((DoubleMapNode *) myNode)->Key2();
123     }
124     //! Value access
125     virtual const TheKey2Type& Value(void) const
126     {  
127 #if !defined No_Exception && !defined No_Standard_NoSuchObject
128       if (!More())
129          Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Iterator::Value");
130 #endif
131       return ((DoubleMapNode *) myNode)->Value();
132     }
133     //! Value change access - denied
134     virtual TheKey2Type& ChangeValue(void) const
135     {  
136       Standard_ImmutableObject::Raise("NCollection_DoubleMap::Iterator::ChangeValue");
137       return * (TheKey2Type *) NULL; // For compiler
138     }
139   };
140
141  public:
142   // ---------- PUBLIC METHODS ------------
143
144   //! Constructor
145   NCollection_DoubleMap (const Standard_Integer NbBuckets=1,
146                      const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
147     : NCollection_BaseCollection<TheKey2Type>(theAllocator),
148       NCollection_BaseMap (NbBuckets, Standard_False) {}
149
150   //! Copy constructor
151   NCollection_DoubleMap (const NCollection_DoubleMap& theOther)
152     : NCollection_BaseCollection<TheKey2Type>(theOther.myAllocator),
153       NCollection_BaseMap (theOther.NbBuckets(), Standard_False) 
154   { *this = theOther; }
155
156   //! Assign another collection
157   virtual void Assign(const NCollection_BaseCollection<TheKey2Type>& theOther)
158   { 
159     if (this == &theOther)
160       return;
161     Standard_TypeMismatch::Raise ("NCollection_DoubleMap::Assign impossible");
162   }
163
164   //! Exchange the content of two maps without re-allocations.
165   //! Notice that allocators will be swapped as well!
166   void Exchange (NCollection_DoubleMap& theOther)
167   {
168     this->exchangeAllocators (theOther);
169     this->exchangeMapsData   (theOther);
170   }
171
172   //! = another map
173   NCollection_DoubleMap& operator=(const NCollection_DoubleMap& theOther)
174   { 
175     if (this == &theOther)
176       return *this;
177
178     Clear(theOther.myAllocator);
179     ReSize (theOther.Extent()-1);
180     Iterator anIter(theOther);
181     for (; anIter.More(); anIter.Next())
182     {
183       TheKey1Type aKey1 = anIter.Key1();
184       TheKey2Type aKey2 = anIter.Key2();
185       Standard_Integer iK1 = Hasher1::HashCode (aKey1, NbBuckets());
186       Standard_Integer iK2 = Hasher2::HashCode (aKey2, NbBuckets());
187       DoubleMapNode * pNode = new (this->myAllocator) DoubleMapNode (aKey1, aKey2, 
188                                                                      myData1[iK1], 
189                                                                      myData2[iK2]);
190       myData1[iK1] = pNode;
191       myData2[iK2] = pNode;
192       Increment();
193     }
194     return *this;
195   }
196
197   //! ReSize
198   void ReSize (const Standard_Integer N)
199   {
200     DoubleMapNode** ppNewData1 = NULL;
201     DoubleMapNode** ppNewData2 = NULL;
202     Standard_Integer newBuck;
203     if (BeginResize (N, newBuck, 
204                      (NCollection_ListNode**&)ppNewData1, 
205                      (NCollection_ListNode**&)ppNewData2,
206                      this->myAllocator)) 
207     {
208       if (myData1) 
209       {
210         DoubleMapNode *p, *q;
211         Standard_Integer i, iK1, iK2;
212         for (i = 0; i <= NbBuckets(); i++) 
213         {
214           if (myData1[i]) 
215           {
216             p = (DoubleMapNode *) myData1[i];
217             while (p) 
218             {
219               iK1 = Hasher1::HashCode (p->Key1(), newBuck);
220               iK2 = Hasher2::HashCode (p->Key2(), newBuck);
221               q = (DoubleMapNode*) p->Next();
222               p->Next()  = ppNewData1[iK1];
223               p->Next2() = ppNewData2[iK2];
224               ppNewData1[iK1] = p;
225               ppNewData2[iK2] = p;
226               p = q;
227             }
228           }
229         }
230       }
231       EndResize(N,newBuck,
232                 (NCollection_ListNode**&)ppNewData1,
233                 (NCollection_ListNode**&)ppNewData2,
234                 this->myAllocator);
235     }
236   }
237
238   //! Bind
239   void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2)
240   {
241     if (Resizable()) 
242       ReSize(Extent());
243     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
244     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
245     DoubleMapNode * pNode;
246     pNode = (DoubleMapNode *) myData1[iK1];
247     while (pNode) 
248     {
249       if (Hasher1::IsEqual (pNode->Key1(), theKey1))
250         Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind");
251       pNode = (DoubleMapNode *) pNode->Next();
252     }
253     pNode = (DoubleMapNode *) myData2[iK2];
254     while (pNode) 
255     {
256       if (Hasher2::IsEqual (pNode->Key2(), theKey2))
257         Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind");
258       pNode = (DoubleMapNode *) pNode->Next();
259     }
260     pNode = new (this->myAllocator) DoubleMapNode (theKey1, theKey2, 
261                                                    myData1[iK1], myData2[iK2]);
262     myData1[iK1] = pNode;
263     myData2[iK2] = pNode;
264     Increment();
265   }
266
267   //!* AreBound
268   Standard_Boolean AreBound (const TheKey1Type& theKey1,
269                              const TheKey2Type& theKey2) const
270   {
271     if (IsEmpty()) 
272       return Standard_False;
273     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
274     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
275     DoubleMapNode * pNode1, * pNode2;
276     pNode1 = (DoubleMapNode *) myData1[iK1];
277     while (pNode1) 
278     {
279       if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) 
280         break;
281       pNode1 = (DoubleMapNode *) pNode1->Next();
282     }
283     if (pNode1 == NULL)
284       return Standard_False;
285     pNode2 = (DoubleMapNode *) myData2[iK2];
286     while (pNode2) 
287     {
288       if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) 
289         break;
290       pNode2 = (DoubleMapNode *) pNode2->Next();
291     }
292     if (pNode2 == NULL)
293       return Standard_False;
294
295     return (pNode1 == pNode2);
296   }
297
298   //! IsBound1
299   Standard_Boolean IsBound1 (const TheKey1Type& theKey1) const
300   {
301     if (IsEmpty()) 
302       return Standard_False;
303     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
304     DoubleMapNode * pNode1;
305     pNode1 = (DoubleMapNode *) myData1[iK1];
306     while (pNode1) 
307     {
308       if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) 
309         return Standard_True;
310       pNode1 = (DoubleMapNode *) pNode1->Next();
311     }
312     return Standard_False;
313   }
314
315   //! IsBound2
316   Standard_Boolean IsBound2 (const TheKey2Type& theKey2) const
317   {
318     if (IsEmpty()) 
319       return Standard_False;
320     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
321     DoubleMapNode * pNode2;
322     pNode2 = (DoubleMapNode *) myData2[iK2];
323     while (pNode2) 
324     {
325       if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) 
326         return Standard_True;
327       pNode2 = (DoubleMapNode *) pNode2->Next2();
328     }
329     return Standard_False;
330   }
331
332   //! UnBind1
333   Standard_Boolean UnBind1 (const TheKey1Type& theKey1)
334   {
335     if (IsEmpty()) 
336       return Standard_False;
337     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
338     DoubleMapNode * p1, * p2, * q1, *q2;
339     q1 = q2 = NULL;
340     p1 = (DoubleMapNode *) myData1[iK1];
341     while (p1) 
342     {
343       if (Hasher1::IsEqual (p1->Key1(), theKey1)) 
344       {
345         // remove from the data1
346         if (q1) 
347           q1->Next() = p1->Next();
348         else
349           myData1[iK1] = (DoubleMapNode*) p1->Next();
350         Standard_Integer iK2 = Hasher2::HashCode (p1->Key2(), NbBuckets());
351         p2 = (DoubleMapNode *) myData2[iK2];
352         while (p2)
353         {
354           if (p2 == p1) 
355           {
356             // remove from the data2
357             if (q2) 
358               q2->Next2() = p2->Next2();
359             else
360               myData2[iK2] = (DoubleMapNode*) p2->Next2();
361             break;
362           }
363           q2 = p2;
364           p2 = (DoubleMapNode*) p2->Next2();
365         }
366         p1->~DoubleMapNode();
367         this->myAllocator->Free(p1);
368         Decrement();
369         return Standard_True;
370       }
371       q1 = p1;
372       p1 = (DoubleMapNode*) p1->Next();
373     }
374     return Standard_False;
375   }
376
377   //! UnBind2
378   Standard_Boolean UnBind2 (const TheKey2Type& theKey2)
379   {
380     if (IsEmpty()) 
381       return Standard_False;
382     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
383     DoubleMapNode * p1, * p2, * q1, *q2;
384     q1 = q2 = NULL;
385     p2 = (DoubleMapNode *) myData2[iK2];
386     while (p2) 
387     {
388       if (Hasher2::IsEqual (p2->Key2(), theKey2)) 
389       {
390         // remove from the data2
391         if (q2)
392           q2->Next() = p2->Next();
393         else
394           myData2[iK2] = (DoubleMapNode*) p2->Next2();
395         Standard_Integer iK1 = Hasher1::HashCode (p2->Key1(), NbBuckets());
396         p1 = (DoubleMapNode *) myData1[iK1];
397         while (p1)
398         {
399           if (p1 == p2) 
400           {
401             // remove from the data1
402             if (q1)
403               q1->Next() = p1->Next();
404             else
405               myData1[iK1] = (DoubleMapNode*) p1->Next();
406             break;
407           }
408           q1 = p1;
409           p1 = (DoubleMapNode*) p1->Next();
410         }
411         p2->~DoubleMapNode();
412         this->myAllocator->Free(p2);
413         Decrement();
414         return Standard_True;
415       }
416       q2 = p2;
417       p2 = (DoubleMapNode*) p2->Next2();
418     }
419     return Standard_False;
420   }
421
422   //! Find1
423   const TheKey2Type& Find1(const TheKey1Type& theKey1) const
424   {
425 #if !defined No_Exception && !defined No_Standard_NoSuchObject
426     if (IsEmpty())
427       Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Find1");
428 #endif
429     DoubleMapNode * pNode1 = 
430       (DoubleMapNode *) myData1[Hasher1::HashCode(theKey1,NbBuckets())];
431     while (pNode1)
432     {
433       if (Hasher1::IsEqual (pNode1->Key1(), theKey1)) 
434         return pNode1->Key2();
435       pNode1 = (DoubleMapNode*) pNode1->Next();
436     }
437     Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find1");
438     return pNode1->Key2(); // This for compiler
439   }
440
441   //! Find2
442   const TheKey1Type& Find2(const TheKey2Type& theKey2) const
443   {
444 #if !defined No_Exception && !defined No_Standard_NoSuchObject
445     if (IsEmpty())
446       Standard_NoSuchObject::Raise ("NCollection_DoubleMap::Find2");
447 #endif
448     DoubleMapNode * pNode2 = 
449       (DoubleMapNode *) myData2[Hasher2::HashCode(theKey2,NbBuckets())];
450     while (pNode2)
451     {
452       if (Hasher2::IsEqual (pNode2->Key2(), theKey2)) 
453         return pNode2->Key1();
454       pNode2 = (DoubleMapNode*) pNode2->Next2();
455     }
456     Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find2");
457     return pNode2->Key1(); // This for compiler
458   }
459
460   //! Clear data. If doReleaseMemory is false then the table of
461   //! buckets is not released and will be reused.
462   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
463   { Destroy (DoubleMapNode::delNode, this->myAllocator, doReleaseMemory); }
464
465   //! Clear data and reset allocator
466   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
467   { 
468     Clear();
469     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
470                     NCollection_BaseAllocator::CommonBaseAllocator() );
471   }
472
473   //! Destructor
474   ~NCollection_DoubleMap (void)
475   { Clear(); }
476
477   //! Size
478   virtual Standard_Integer Size(void) const
479   { return Extent(); }
480
481  private:
482   // ----------- PRIVATE METHODS -----------
483
484   //! Creates Iterator for use on BaseCollection
485   virtual TYPENAME NCollection_BaseCollection<TheKey2Type>::Iterator& 
486     CreateIterator(void) const
487   { return *(new (this->IterAllocator()) Iterator(*this)); }
488
489 };
490
491 #endif