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