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