0022815: Missing delete operator for placement new
[occt.git] / src / NCollection / NCollection_IndexedMap.hxx
1 // File:        NCollection_IndexedMap.hxx
2 // Created:     Thu Apr 24 15:02:53 2002
3 // Author:      Alexander KARTOMIN (akm)
4 //              <akm@opencascade.com>
5
6 #ifndef NCollection_IndexedMap_HeaderFile
7 #define NCollection_IndexedMap_HeaderFile
8
9 #include <NCollection_BaseCollection.hxx>
10 #include <NCollection_BaseMap.hxx>
11 #include <NCollection_TListNode.hxx>
12 #include <Standard_NoSuchObject.hxx>
13 #include <Standard_ImmutableObject.hxx>
14
15 #include <NCollection_DefaultHasher.hxx>
16
17 #if !defined No_Exception && !defined No_Standard_OutOfRange
18 #include <Standard_OutOfRange.hxx>
19 #endif
20
21 /**
22  * Purpose:     An indexed map is used to  store  keys and to bind
23  *              an index to them.  Each new key stored in  the map
24  *              gets an index.  Index are incremented  as keys are
25  *              stored in the map. A key can be found by the index
26  *              and an index by the  key. No key  but the last can
27  *              be removed so the indices are in the range 1..Extent.
28  *              See  the  class   Map   from NCollection   for   a
29  *              discussion about the number of buckets.
30  */            
31
32 template < class TheKeyType, 
33            class Hasher = NCollection_DefaultHasher<TheKeyType> > 
34   class NCollection_IndexedMap 
35   : public NCollection_BaseCollection<TheKeyType>,
36     public NCollection_BaseMap
37 {
38   // **************** Adaptation of the TListNode to the INDEXEDmap
39  private:
40   class IndexedMapNode : public NCollection_TListNode<TheKeyType>
41   {
42   public:
43     //! Constructor with 'Next'
44     IndexedMapNode (const TheKeyType&      theKey1, 
45                     const Standard_Integer theKey2, 
46                     NCollection_ListNode*  theNext1, 
47                     NCollection_ListNode*  theNext2) :
48                       NCollection_TListNode<TheKeyType> (theKey1, theNext1)
49     { 
50       myKey2 = theKey2;
51       myNext2 = (IndexedMapNode *) theNext2;
52     }
53     //! Key1
54     TheKeyType& Key1 (void)
55     { return this->ChangeValue(); }
56     //! Key2
57     const Standard_Integer& Key2 (void)
58     { return myKey2; }
59     //! Next2
60     IndexedMapNode*& Next2 (void)
61     { return myNext2; }
62     
63     //! Static deleter to be passed to BaseList
64     static void delNode (NCollection_ListNode * theNode, 
65                          Handle(NCollection_BaseAllocator)& theAl)
66     {
67       ((IndexedMapNode *) theNode)->~IndexedMapNode();
68       theAl->Free(theNode);
69     }
70
71   private:
72     Standard_Integer myKey2;
73     IndexedMapNode * myNext2;
74   };
75
76  public:
77   // **************** Implementation of the Iterator interface.
78   class Iterator 
79     : public NCollection_BaseCollection<TheKeyType>::Iterator
80   {
81   public:
82     //! Empty constructor
83     Iterator (void) :
84       myMap(NULL),
85       myIndex(0) {}
86     //! Constructor
87     Iterator (const NCollection_IndexedMap& theMap) :
88       myMap((NCollection_IndexedMap *) &theMap),
89       myIndex(1) {}
90     //! Query if the end of collection is reached by iterator
91     virtual Standard_Boolean More(void) const
92     { return (myIndex <= myMap->Extent()); }
93     //! Make a step along the collection
94     virtual void Next(void)
95     { myIndex++; }
96     //! Value access
97     virtual const TheKeyType& Value(void) const
98     {
99 #if !defined No_Exception && !defined No_Standard_NoSuchObject
100       if (!More())
101         Standard_NoSuchObject::Raise("NCollection_IndexedMap::Iterator::Value");
102 #endif
103       return myMap->FindKey(myIndex);
104     }
105     //! Value change access denied - use Substitute
106     virtual TheKeyType& ChangeValue(void) const
107     {  
108       Standard_ImmutableObject::Raise ("impossible to ChangeValue");
109       return * (TheKeyType *) NULL; // This for compiler
110     }
111     
112   private:
113     NCollection_IndexedMap * myMap;   // Pointer to the map being iterated
114     Standard_Integer         myIndex; // Current index
115   };
116   
117  public:
118   // ---------- PUBLIC METHODS ------------
119
120   //! Constructor
121   NCollection_IndexedMap (const Standard_Integer NbBuckets=1,
122                           const Handle(NCollection_BaseAllocator)& theAllocator=0L) :
123     NCollection_BaseCollection<TheKeyType>(theAllocator),
124     NCollection_BaseMap (NbBuckets, Standard_False) {}
125
126   //! Copy constructor
127   NCollection_IndexedMap (const NCollection_IndexedMap& theOther) :
128     NCollection_BaseCollection<TheKeyType>(theOther.myAllocator),
129     NCollection_BaseMap (theOther.NbBuckets(), Standard_False) 
130   { *this = theOther; }
131
132   //! Assign another collection
133   virtual void Assign (const NCollection_BaseCollection<TheKeyType>& theOther)
134   { 
135     if (this == &theOther)
136       return;
137     Clear();
138     ReSize (theOther.Size()-1);
139     TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& anIter = 
140       theOther.CreateIterator();
141     for (; anIter.More(); anIter.Next())
142       Add(anIter.Value());
143   }
144
145   //! = another map
146   NCollection_IndexedMap& operator= (const NCollection_IndexedMap& theOther)
147   { 
148     if (this == &theOther)
149       return *this;
150
151     Clear(theOther.myAllocator);
152     ReSize (theOther.Extent()-1);
153     Standard_Integer i, iLength=theOther.Extent();
154     for (i=1; i<=iLength; i++)
155     {
156       TheKeyType aKey1 = theOther(i);
157       Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
158       Standard_Integer iK2 = ::HashCode (i, NbBuckets());
159       IndexedMapNode * pNode = new (this->myAllocator) IndexedMapNode (aKey1, i, 
160                                                                        myData1[iK1], 
161                                                                        myData2[iK2]);
162       myData1[iK1] = pNode;
163       myData2[iK2] = pNode;
164       Increment();
165     }
166     return *this;
167   }
168
169   //! ReSize
170   void ReSize (const Standard_Integer N)
171   {
172     IndexedMapNode** ppNewData1 = NULL;
173     IndexedMapNode** ppNewData2 = NULL;
174     Standard_Integer newBuck;
175     if (BeginResize (N, newBuck, 
176                      (NCollection_ListNode**&)ppNewData1, 
177                      (NCollection_ListNode**&)ppNewData2,
178                      this->myAllocator)) 
179     {
180       if (myData1) 
181       {
182         IndexedMapNode *p, *q;
183         Standard_Integer i, iK1, iK2;
184         for (i = 0; i <= NbBuckets(); i++) 
185         {
186           if (myData1[i]) 
187           {
188             p = (IndexedMapNode *) myData1[i];
189             while (p) 
190             {
191               iK1 =Hasher::HashCode(p->Key1(), newBuck);
192               q = (IndexedMapNode*) p->Next();
193               p->Next()  = ppNewData1[iK1];
194               ppNewData1[iK1] = p;
195               if (p->Key2() > 0) 
196               {
197                 iK2 = ::HashCode (p->Key2(), newBuck);
198                 p->Next2() = ppNewData2[iK2];
199                 ppNewData2[iK2] = p;
200               }
201               p = q;
202             }
203           }
204         }
205       }
206       EndResize(N,newBuck,
207                 (NCollection_ListNode**&)ppNewData1,
208                 (NCollection_ListNode**&)ppNewData2,
209                 this->myAllocator);
210     }
211   }
212
213   //! Add
214   Standard_Integer Add (const TheKeyType& theKey1)
215   {
216     if (Resizable()) 
217       ReSize(Extent());
218     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
219     IndexedMapNode * pNode;
220     pNode = (IndexedMapNode *) myData1[iK1];
221     while (pNode)
222     {
223       if (Hasher::IsEqual (pNode->Key1(), theKey1))
224         return pNode->Key2();
225       pNode = (IndexedMapNode *) pNode->Next();
226     }
227     Increment();
228     Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
229     pNode = new (this->myAllocator) IndexedMapNode (theKey1, Extent(), 
230                                                     myData1[iK1], myData2[iK2]);
231     myData1[iK1] = pNode;
232     myData2[iK2] = pNode;
233     return Extent();
234   }
235
236   //! Contains
237   Standard_Boolean Contains (const TheKeyType& theKey1) const
238   {
239     if (IsEmpty()) 
240       return Standard_False;
241     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
242     IndexedMapNode * pNode1;
243     pNode1 = (IndexedMapNode *) myData1[iK1];
244     while (pNode1) 
245     {
246       if (Hasher::IsEqual(pNode1->Key1(), theKey1)) 
247         return Standard_True;
248       pNode1 = (IndexedMapNode *) pNode1->Next();
249     }
250     return Standard_False;
251   }
252
253   //! Substitute
254   void Substitute (const Standard_Integer theIndex,
255                    const TheKeyType& theKey1)
256   {
257 #if !defined No_Exception && !defined No_Standard_OutOfRange
258     if (theIndex < 1 || theIndex > Extent())
259       Standard_OutOfRange::Raise ("NCollection_IndexedMap::Substitute");
260 #endif
261     IndexedMapNode * p;
262     // check if theKey1 is not already in the map
263     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
264     p = (IndexedMapNode *) myData1[iK1];
265     while (p) 
266     {
267       if (Hasher::IsEqual (p->Key1(), theKey1)) 
268         Standard_DomainError::Raise("NCollection_IndexedMap::Substitute");
269       p = (IndexedMapNode *) p->Next();
270     }
271
272     // Find the node for the index I
273     Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
274     p = (IndexedMapNode *) myData2[iK2];
275     while (p) 
276     {
277       if (p->Key2() == theIndex) 
278         break;
279       p = (IndexedMapNode*) p->Next2();
280     }
281     
282     // remove the old key
283     Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
284     IndexedMapNode * q = (IndexedMapNode *) myData1[iK];
285     if (q == p)
286       myData1[iK] = (IndexedMapNode *) p->Next();
287     else 
288     {
289       while (q->Next() != p) 
290         q = (IndexedMapNode *) q->Next();
291       q->Next() = p->Next();
292     }
293
294     // update the node
295     p->Key1() = theKey1;
296     p->Next() = myData1[iK1];
297     myData1[iK1] = p;
298   }
299
300   //! RemoveLast
301   void RemoveLast (void)
302   {
303 #if !defined No_Exception && !defined No_Standard_OutOfRange
304     if (Extent() == 0)
305       Standard_OutOfRange::Raise ("NCollection_IndexedMap::RemoveLast");
306 #endif
307     IndexedMapNode * p, * q;
308     // Find the node for the last index and remove it
309     Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
310     p = (IndexedMapNode *) myData2[iK2];
311     q = NULL;
312     while (p) 
313     {
314       if (p->Key2() == Extent()) 
315         break;
316       q = p;
317       p = (IndexedMapNode*) p->Next2();
318     }
319     if (q == NULL) 
320       myData2[iK2] = (IndexedMapNode *) p->Next2();
321     else 
322       q->Next2() = p->Next2();
323     
324     // remove the key
325     Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
326     q = (IndexedMapNode *) myData1[iK1];
327     if (q == p)
328       myData1[iK1] = (IndexedMapNode *) p->Next();
329     else 
330     {
331       while (q->Next() != p) 
332         q = (IndexedMapNode *) q->Next();
333       q->Next() = p->Next();
334     }
335     p->~IndexedMapNode();
336     this->myAllocator->Free(p);
337     Decrement();
338   }
339
340   //! FindKey
341   const TheKeyType& FindKey (const Standard_Integer theKey2) const
342   {
343 #if !defined No_Exception && !defined No_Standard_OutOfRange
344     if (theKey2 < 1 || theKey2 > Extent())
345       Standard_OutOfRange::Raise ("NCollection_IndexedMap::FindKey");
346 #endif
347     IndexedMapNode * pNode2 =
348       (IndexedMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
349     while (pNode2)
350     {
351       if (pNode2->Key2() == theKey2) 
352         return pNode2->Key1();
353       pNode2 = (IndexedMapNode*) pNode2->Next2();
354     }
355     Standard_NoSuchObject::Raise("NCollection_IndexedMap::FindKey");
356     return pNode2->Key1(); // This for compiler
357   }
358
359   //! operator ()
360   const TheKeyType& operator() (const Standard_Integer theKey2) const
361   { return FindKey (theKey2); }
362
363   //! FindIndex
364   Standard_Integer FindIndex(const TheKeyType& theKey1) const
365   {
366     if (IsEmpty()) return 0;
367     IndexedMapNode * pNode1 = 
368       (IndexedMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
369     while (pNode1)
370     {
371       if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
372         return pNode1->Key2();
373       pNode1 = (IndexedMapNode*) pNode1->Next();
374     }
375     return 0;
376   }
377
378   //! Clear data. If doReleaseMemory is false then the table of
379   //! buckets is not released and will be reused.
380   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
381   { Destroy (IndexedMapNode::delNode, this->myAllocator, doReleaseMemory); }
382
383   //! Clear data and reset allocator
384   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
385   { 
386     Clear();
387     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
388                     NCollection_BaseAllocator::CommonBaseAllocator() );
389   }
390
391   //! Destructor
392   ~NCollection_IndexedMap (void)
393   { Clear(); }
394
395   //! Size
396   virtual Standard_Integer Size(void) const
397   { return Extent(); }
398
399  private:
400   // ----------- PRIVATE METHODS -----------
401
402   //! Creates Iterator for use on BaseCollection
403   virtual TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& 
404     CreateIterator(void) const
405   { return *(new (this->IterAllocator()) Iterator(*this)); }
406
407 };
408
409 #endif