0022815: Missing delete operator for placement new
[occt.git] / src / NCollection / NCollection_IndexedDataMap.hxx
1 // File:        NCollection_IndexedDataMap.hxx
2 // Created:     Thu Apr 24 15:02:53 2002
3 // Author:      Alexander KARTOMIN (akm)
4 //              <akm@opencascade.com>
5
6 #ifndef NCollection_IndexedDataMap_HeaderFile
7 #define NCollection_IndexedDataMap_HeaderFile
8
9 #include <NCollection_BaseCollection.hxx>
10 #include <NCollection_BaseMap.hxx>
11 #include <NCollection_TListNode.hxx>
12 #include <Standard_TypeMismatch.hxx>
13 #include <Standard_NoSuchObject.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..
28  *              Extent.  An Item is stored with each key.
29  *              
30  *              This   class is   similar  to  IndexedMap     from
31  *              NCollection  with the Item as  a new feature. Note
32  *              the important difference on  the operator  ().  In
33  *              the IndexedMap this operator returns  the Key.  In
34  *              the IndexedDataMap this operator returns the Item.
35  *               
36  *              See  the  class   Map   from NCollection   for   a
37  *              discussion about the number of buckets.
38  */            
39
40 template < class TheKeyType, 
41            class TheItemType, 
42            class Hasher = NCollection_DefaultHasher<TheKeyType> > 
43   class NCollection_IndexedDataMap 
44   : public NCollection_BaseCollection<TheItemType>,
45     public NCollection_BaseMap
46 {
47   //!    Adaptation of the TListNode to the INDEXEDDatamap
48  private:
49   class IndexedDataMapNode : public NCollection_TListNode<TheItemType>
50   {
51   public:
52     //! Constructor with 'Next'
53     IndexedDataMapNode (const TheKeyType&      theKey1, 
54                         const Standard_Integer theKey2,
55                         const TheItemType&     theItem,
56                         NCollection_ListNode*  theNext1, 
57                         NCollection_ListNode*  theNext2) :
58                           NCollection_TListNode<TheItemType>(theItem,theNext1)
59     { 
60       myKey1 = theKey1;
61       myKey2 = theKey2;
62       myNext2 = (IndexedDataMapNode *) theNext2;
63     }
64     //! Key1
65     TheKeyType& Key1 (void)
66     { return myKey1; }
67     //! Key2
68     const Standard_Integer& Key2 (void)
69     { return myKey2; }
70     //! Next2
71     IndexedDataMapNode*& 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       ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode();
79       theAl->Free(theNode);
80     }
81   private:
82     TheKeyType           myKey1;
83     Standard_Integer     myKey2;
84     IndexedDataMapNode * myNext2;
85   };
86
87  public:
88   //!   Implementation of the Iterator interface.
89   class Iterator : public NCollection_BaseCollection<TheItemType>::Iterator
90   {
91   public:
92     //! Empty constructor
93     Iterator (void) :
94       myMap(NULL),
95       myIndex(0) {}
96     //! Constructor
97     Iterator (const NCollection_IndexedDataMap& theMap) :
98       myMap((NCollection_IndexedDataMap *) &theMap),
99       myIndex(1) {}
100     //! Query if the end of collection is reached by iterator
101     virtual Standard_Boolean More(void) const
102     { return (myIndex <= myMap->Extent()); }
103     //! Make a step along the collection
104     virtual void Next(void)
105     { myIndex++; }
106     //! Value access
107     virtual const TheItemType& Value(void) const
108     {  
109 #if !defined No_Exception && !defined No_Standard_NoSuchObject
110       if (!More())
111         Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::Value");
112 #endif
113       return myMap->FindFromIndex(myIndex);
114     }
115     //! ChangeValue access
116     virtual TheItemType& ChangeValue(void) const
117     {  
118 #if !defined No_Exception && !defined No_Standard_NoSuchObject
119       if (!More())
120         Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::ChangeValue");
121 #endif
122       return myMap->ChangeFromIndex(myIndex);
123     }
124     
125   private:
126     NCollection_IndexedDataMap * myMap;   //!< Pointer to the map being iterated
127     Standard_Integer             myIndex; //!< Current index
128   };
129   
130  public:
131   // ---------- PUBLIC METHODS ------------
132
133   //! Constructor
134   NCollection_IndexedDataMap (const Standard_Integer NbBuckets=1,
135                      const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
136     :  NCollection_BaseCollection<TheItemType>(theAllocator),
137        NCollection_BaseMap (NbBuckets, Standard_False) {}
138
139   //! Copy constructor
140   NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther) 
141     : NCollection_BaseCollection<TheItemType>(theOther.myAllocator),
142       NCollection_BaseMap (theOther.NbBuckets(), Standard_False) 
143   { *this = theOther; }
144
145   //! Assign another collection
146   virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther)
147   { 
148     if (this == &theOther)
149       return;
150     Standard_TypeMismatch::Raise("NCollection_IndexedDataMap::Assign");
151   }
152
153   //! = another map
154   NCollection_IndexedDataMap& operator= 
155     (const NCollection_IndexedDataMap& theOther)
156   { 
157     if (this == &theOther)
158       return *this;
159
160     Clear(theOther.myAllocator);
161     ReSize (theOther.Extent()-1);
162     Standard_Integer i;
163     for (i=1; i<=theOther.Extent(); i++)
164     {
165       TheKeyType aKey1 = theOther.FindKey(i);
166       TheItemType anItem = theOther.FindFromIndex(i);
167       Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
168       Standard_Integer iK2 = ::HashCode (i, NbBuckets());
169       IndexedDataMapNode * pNode = 
170         new (this->myAllocator) IndexedDataMapNode (aKey1, i, anItem,
171                                               myData1[iK1], myData2[iK2]);
172       myData1[iK1] = pNode;
173       myData2[iK2] = pNode;
174       Increment();
175     }
176     return *this;
177   }
178
179   //! ReSize
180   void ReSize (const Standard_Integer N)
181   {
182     IndexedDataMapNode** ppNewData1 = NULL;
183     IndexedDataMapNode** ppNewData2 = NULL;
184     Standard_Integer newBuck;
185     if (BeginResize (N, newBuck, 
186                      (NCollection_ListNode**&)ppNewData1, 
187                      (NCollection_ListNode**&)ppNewData2,
188                      this->myAllocator)) 
189     {
190       if (myData1) 
191       {
192         IndexedDataMapNode *p, *q;
193         Standard_Integer i, iK1, iK2;
194         for (i = 0; i <= NbBuckets(); i++) 
195         {
196           if (myData1[i]) 
197           {
198             p = (IndexedDataMapNode *) myData1[i];
199             while (p) 
200             {
201               iK1 = Hasher::HashCode (p->Key1(), newBuck);
202               iK2 = ::HashCode (p->Key2(), newBuck);
203               q = (IndexedDataMapNode*) p->Next();
204               p->Next()  = ppNewData1[iK1];
205               p->Next2() = ppNewData2[iK2];
206               ppNewData1[iK1] = p;
207               ppNewData2[iK2] = p;
208               p = q;
209             }
210           }
211         }
212       }
213       EndResize(N,newBuck,
214                 (NCollection_ListNode**&)ppNewData1,
215                 (NCollection_ListNode**&)ppNewData2,
216                 this->myAllocator);
217     }
218   }
219
220   //! Add
221   Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
222   {
223     if (Resizable()) 
224       ReSize(Extent());
225     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
226     IndexedDataMapNode * pNode;
227     pNode = (IndexedDataMapNode *) myData1[iK1];
228     while (pNode)
229     {
230       if (Hasher::IsEqual (pNode->Key1(), theKey1))
231         return pNode->Key2();
232       pNode = (IndexedDataMapNode *) pNode->Next();
233     }
234     Increment();
235     Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
236     pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, Extent(), theItem,
237                                                   myData1[iK1], myData2[iK2]);
238     myData1[iK1] = pNode;
239     myData2[iK2] = pNode;
240     return Extent();
241   }
242
243   //! Contains
244   Standard_Boolean Contains (const TheKeyType& theKey1) const
245   {
246     if (IsEmpty()) 
247       return Standard_False;
248     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
249     IndexedDataMapNode * pNode1;
250     pNode1 = (IndexedDataMapNode *) myData1[iK1];
251     while (pNode1) 
252     {
253       if (Hasher::IsEqual(pNode1->Key1(), theKey1)) 
254         return Standard_True;
255       pNode1 = (IndexedDataMapNode *) pNode1->Next();
256     }
257     return Standard_False;
258   }
259
260   //! Substitute
261   void Substitute (const Standard_Integer theIndex,
262                    const TheKeyType&      theKey1,
263                    const TheItemType&     theItem)
264   {
265 #if !defined No_Exception && !defined No_Standard_OutOfRange
266     if (theIndex < 1 || theIndex > Extent())
267       Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::Substitute");
268 #endif
269     IndexedDataMapNode * p;
270     // check if theKey1 is not already in the map
271     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
272     p = (IndexedDataMapNode *) myData1[iK1];
273     while (p) 
274     {
275       if (Hasher::IsEqual (p->Key1(), theKey1)) 
276         Standard_DomainError::Raise("NCollection_IndexedDataMap::Substitute");
277       p = (IndexedDataMapNode *) p->Next();
278     }
279
280     // Find the node for the index I
281     Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
282     p = (IndexedDataMapNode *) myData2[iK2];
283     while (p) 
284     {
285       if (p->Key2() == theIndex) 
286         break;
287       p = (IndexedDataMapNode*) p->Next2();
288     }
289     
290     // remove the old key
291     Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
292     IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
293     if (q == p)
294       myData1[iK] = (IndexedDataMapNode *) p->Next();
295     else 
296     {
297       while (q->Next() != p) 
298         q = (IndexedDataMapNode *) q->Next();
299       q->Next() = p->Next();
300     }
301
302     // update the node
303     p->Key1()  = theKey1;
304     p->ChangeValue() = theItem;
305     p->Next()  = myData1[iK1];
306     myData1[iK1] = p;
307   }
308
309   //! RemoveLast
310   void RemoveLast (void)
311   {
312 #if !defined No_Exception && !defined No_Standard_OutOfRange
313     if (Extent() == 0)
314       Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::RemoveLast");
315 #endif
316     IndexedDataMapNode * p, * q;
317     // Find the node for the last index and remove it
318     Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
319     p = (IndexedDataMapNode *) myData2[iK2];
320     q = NULL;
321     while (p) 
322     {
323       if (p->Key2() == Extent()) 
324         break;
325       q = p;
326       p = (IndexedDataMapNode*) p->Next2();
327     }
328     if (q == NULL) 
329       myData2[iK2] = (IndexedDataMapNode *) p->Next2();
330     else 
331       q->Next2() = p->Next2();
332     
333     // remove the key
334     Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
335     q = (IndexedDataMapNode *) myData1[iK1];
336     if (q == p)
337       myData1[iK1] = (IndexedDataMapNode *) p->Next();
338     else 
339     {
340       while (q->Next() != p) 
341         q = (IndexedDataMapNode *) q->Next();
342       q->Next() = p->Next();
343     }
344     p->~IndexedDataMapNode();
345     this->myAllocator->Free(p);
346     Decrement();
347   }
348
349   //! FindKey
350   const TheKeyType& FindKey (const Standard_Integer theKey2) const
351   {
352 #if !defined No_Exception && !defined No_Standard_OutOfRange
353     if (theKey2 < 1 || theKey2 > Extent())
354       Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindKey");
355 #endif
356     IndexedDataMapNode * pNode2 =
357       (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
358     while (pNode2)
359     {
360       if (pNode2->Key2() == theKey2)
361         return pNode2->Key1();
362       pNode2 = (IndexedDataMapNode*) pNode2->Next2();
363     }
364     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindKey");
365     return pNode2->Key1(); // This for compiler
366   }
367
368   //! FindFromIndex
369   const TheItemType& FindFromIndex (const Standard_Integer theKey2) const
370   {
371 #if !defined No_Exception && !defined No_Standard_OutOfRange
372     if (theKey2 < 1 || theKey2 > Extent())
373       Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindFromIndex");
374 #endif
375     IndexedDataMapNode * pNode2 =
376       (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
377     while (pNode2)
378     {
379       if (pNode2->Key2() == theKey2)
380         return pNode2->Value();
381       pNode2 = (IndexedDataMapNode*) pNode2->Next2();
382     }
383     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromIndex");
384     return pNode2->Value(); // This for compiler
385   }
386
387   //! operator ()
388   const TheItemType& operator() (const Standard_Integer theKey2) const
389   { return FindFromIndex (theKey2); }
390
391   //! ChangeFromIndex
392   TheItemType& ChangeFromIndex (const Standard_Integer theKey2)
393   {
394 #if !defined No_Exception && !defined No_Standard_OutOfRange
395     if (theKey2 < 1 || theKey2 > Extent())
396       Standard_OutOfRange::Raise("NCollection_IndexedDataMap::ChangeFromIndex");
397 #endif
398     IndexedDataMapNode * pNode2 =
399       (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
400     while (pNode2)
401     {
402       if (pNode2->Key2() == theKey2)
403         return pNode2->ChangeValue();
404       pNode2 = (IndexedDataMapNode*) pNode2->Next2();
405     }
406     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromIndex");
407     return pNode2->ChangeValue(); // This for compiler
408   }
409
410   //! operator ()
411   TheItemType& operator() (const Standard_Integer theKey2)
412   { return ChangeFromIndex (theKey2); }
413
414   //! FindIndex
415   Standard_Integer FindIndex(const TheKeyType& theKey1) const
416   {
417     if (IsEmpty()) return 0;
418     IndexedDataMapNode * pNode1 = 
419       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
420     while (pNode1)
421     {
422       if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
423         return pNode1->Key2();
424       pNode1 = (IndexedDataMapNode*) pNode1->Next();
425     }
426     return 0;
427   }
428
429   //! FindFromKey
430   const TheItemType& FindFromKey(const TheKeyType& theKey1) const
431   {
432 #if !defined No_Exception && !defined No_Standard_NoSuchObject
433     if (IsEmpty())
434       Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindFromKey");
435 #endif
436     IndexedDataMapNode * pNode1 = 
437       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
438     while (pNode1)
439     {
440       if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
441         return pNode1->Value();
442       pNode1 = (IndexedDataMapNode*) pNode1->Next();
443     }
444     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromKey");
445     return pNode1->Value();
446   }
447
448   //! ChangeFromKey
449   TheItemType& ChangeFromKey (const TheKeyType& theKey1)
450   {
451 #if !defined No_Exception && !defined No_Standard_NoSuchObject
452     if (IsEmpty())
453       Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
454 #endif
455     IndexedDataMapNode * pNode1 = 
456       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
457     while (pNode1)
458     {
459       if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
460         return pNode1->ChangeValue();
461       pNode1 = (IndexedDataMapNode*) pNode1->Next();
462     }
463     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
464     return pNode1->ChangeValue();
465   }
466
467   //! Clear data. If doReleaseMemory is false then the table of
468   //! buckets is not released and will be reused.
469   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
470   { Destroy (IndexedDataMapNode::delNode, this->myAllocator, doReleaseMemory); }
471
472   //! Clear data and reset allocator
473   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
474   { 
475     Clear();
476     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
477                     NCollection_BaseAllocator::CommonBaseAllocator() );
478   }
479
480   //! Destructor
481   ~NCollection_IndexedDataMap (void)
482   { Clear(); }
483
484   //! Size
485   virtual Standard_Integer Size(void) const
486   { return Extent(); }
487
488  private:
489   // ----------- PRIVATE METHODS -----------
490
491   //! Creates Iterator for use on BaseCollection
492   virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator& 
493     CreateIterator(void) const
494   { return *(new (this->IterAllocator()) Iterator(*this)); }
495
496 };
497
498 #endif