0022815: Missing delete operator for placement new
[occt.git] / src / NCollection / NCollection_DataMap.hxx
1 // File:        NCollection_DataMap.hxx
2 // Created:     Thu Apr 24 15:02:53 2002
3 // Author:      Alexander KARTOMIN (akm)
4 //              <akm@opencascade.com>
5
6 #ifndef NCollection_DataMap_HeaderFile
7 #define NCollection_DataMap_HeaderFile
8
9 #include <NCollection_BaseCollection.hxx>
10 #include <NCollection_BaseMap.hxx>
11 #include <NCollection_TListNode.hxx>
12
13 #include <NCollection_DefaultHasher.hxx>
14
15 #include <Standard_TypeMismatch.hxx>
16 #include <Standard_NoSuchObject.hxx>
17
18 /**
19 * Purpose:     The DataMap is a Map to store keys with associated
20 *              Items. See Map  from NCollection for  a discussion
21 *              about the number of buckets.
22 *
23 *              The DataMap can be seen as an extended array where
24 *              the Keys  are the   indices.  For this reason  the
25 *              operator () is defined on DataMap to fetch an Item
26 *              from a Key. So the following syntax can be used :
27 *
28 *              anItem = aMap(aKey);
29 *              aMap(aKey) = anItem;
30 *
31 *              This analogy has its  limit.   aMap(aKey) = anItem
32 *              can  be done only  if aKey was previously bound to
33 *              an item in the map.
34 */              
35
36 template < class TheKeyType, 
37            class TheItemType, 
38            class Hasher = NCollection_DefaultHasher<TheKeyType> >  class NCollection_DataMap 
39   
40   : public NCollection_BaseCollection<TheItemType>,
41     public NCollection_BaseMap
42 {
43   // **************** Adaptation of the TListNode to the DATAmap
44  public:
45   class DataMapNode : public NCollection_TListNode<TheItemType>
46   {
47   public:
48     //! Constructor with 'Next'
49     DataMapNode (const TheKeyType&     theKey, 
50                  const TheItemType&    theItem, 
51                  NCollection_ListNode* theNext) :
52                    NCollection_TListNode<TheItemType> (theItem, theNext) 
53     { myKey = theKey; }
54     //! Key
55     const TheKeyType& Key (void) const
56     { return myKey; }
57     
58     //! Static deleter to be passed to BaseList
59     static void delNode (NCollection_ListNode * theNode, 
60                          Handle(NCollection_BaseAllocator)& theAl)
61     {
62       ((DataMapNode *) theNode)->~DataMapNode();
63       theAl->Free(theNode);
64     }
65
66   private:
67     TheKeyType    myKey;
68   };
69
70  public:
71   // **************** Implementation of the Iterator interface.
72   class Iterator 
73     : public NCollection_BaseCollection<TheItemType>::Iterator,
74       public NCollection_BaseMap::Iterator
75   {
76   public:
77     //! Empty constructor
78     Iterator (void) :
79       NCollection_BaseMap::Iterator() {}
80     //! Constructor
81     Iterator (const NCollection_DataMap& theMap) :
82       NCollection_BaseMap::Iterator(theMap) {}
83     //! Query if the end of collection is reached by iterator
84     virtual Standard_Boolean More(void) const
85     { return PMore(); }
86     //! Make a step along the collection
87     virtual void Next(void)
88     { PNext(); }
89     //! Value inquiry
90     virtual const TheItemType& Value(void) const
91     {  
92 #if !defined No_Exception && !defined No_Standard_NoSuchObject
93       if (!More())
94         Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Value");  
95 #endif
96       return ((DataMapNode *) myNode)->Value();
97     }
98     //! Value change access
99     virtual TheItemType& ChangeValue(void) const
100     {  
101 #if !defined No_Exception && !defined No_Standard_NoSuchObject
102       if (!More())
103         Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::ChangeValue");  
104 #endif
105       return ((DataMapNode *) myNode)->ChangeValue();
106     }
107     //! Key
108     const TheKeyType& Key (void) const
109     { 
110 #if !defined No_Exception && !defined No_Standard_NoSuchObject
111       if (!More())
112         Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Key");  
113 #endif
114       return ((DataMapNode *) myNode)->Key();
115     }
116   };
117
118  public:
119   // ---------- PUBLIC METHODS ------------
120
121   //! Constructor
122   NCollection_DataMap (const Standard_Integer NbBuckets=1,
123                      const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
124     : NCollection_BaseCollection<TheItemType>(theAllocator),
125       NCollection_BaseMap (NbBuckets, Standard_True) {}
126
127   //! Copy constructor
128   NCollection_DataMap (const NCollection_DataMap& theOther)
129     : NCollection_BaseCollection<TheItemType>(theOther.myAllocator),
130       NCollection_BaseMap (theOther.NbBuckets(), Standard_True) 
131   { *this = theOther; }
132
133   //! Assign another collection
134   virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther)
135   { 
136     if (this == &theOther)
137       return;
138     Standard_TypeMismatch::Raise ("NCollection_DataMap::Assign impossible");
139   }
140
141   //! = another map
142   NCollection_DataMap& operator= (const NCollection_DataMap& theOther)
143   { 
144     if (this == &theOther)
145       return *this;
146
147     Clear(theOther.myAllocator);
148     ReSize (theOther.Extent()-1);
149     Iterator anIter(theOther);
150     for (; anIter.More(); anIter.Next())
151       Bind (anIter.Key(), anIter.Value());
152     return *this;
153   }
154
155   //! ReSize
156   void ReSize (const Standard_Integer N)
157   {
158     DataMapNode** newdata = NULL;
159     DataMapNode** dummy   = NULL;
160     Standard_Integer newBuck;
161     if (BeginResize (N, newBuck, 
162                      (NCollection_ListNode**&)newdata, 
163                      (NCollection_ListNode**&)dummy,
164                      this->myAllocator)) 
165     {
166       if (myData1) 
167       {
168         DataMapNode** olddata = (DataMapNode**) myData1;
169         DataMapNode *p, *q;
170         Standard_Integer i,k;
171         for (i = 0; i <= NbBuckets(); i++) 
172         {
173           if (olddata[i]) 
174           {
175             p = olddata[i];
176             while (p) 
177             {
178               k = Hasher::HashCode(p->Key(),newBuck);
179               q = (DataMapNode*) p->Next();
180               p->Next() = newdata[k];
181               newdata[k] = p;
182               p = q;
183             }
184           }
185         }
186       }
187       EndResize(N,newBuck,
188                 (NCollection_ListNode**&)newdata,
189                 (NCollection_ListNode**&)dummy,
190                 this->myAllocator);
191     }
192   }
193
194   //! Bind
195   Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem)
196   {
197     if (Resizable()) 
198       ReSize(Extent());
199     DataMapNode** data = (DataMapNode**)myData1;
200     Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
201     DataMapNode* p = data[k];
202     while (p) 
203     {
204       if (Hasher::IsEqual(p->Key(), theKey))
205       {
206         p->ChangeValue() = theItem;
207         return Standard_False;
208       }
209       p = (DataMapNode *) p->Next();
210     }
211     data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
212     Increment();
213     return Standard_True;
214   }
215
216   //! IsBound
217   Standard_Boolean IsBound(const TheKeyType& K) const
218   {
219     if (IsEmpty()) 
220       return Standard_False;
221     DataMapNode** data = (DataMapNode**) myData1;
222     DataMapNode* p = data[Hasher::HashCode(K,NbBuckets())];
223     while (p) 
224     {
225       if (Hasher::IsEqual(p->Key(),K)) 
226         return Standard_True;
227       p = (DataMapNode *) p->Next();
228     }
229     return Standard_False;
230   }
231
232   //! UnBind
233   Standard_Boolean UnBind(const TheKeyType& K)
234   {
235     if (IsEmpty()) 
236       return Standard_False;
237     DataMapNode** data = (DataMapNode**) myData1;
238     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
239     DataMapNode* p = data[k];
240     DataMapNode* q = NULL;
241     while (p) 
242     {
243       if (Hasher::IsEqual(p->Key(),K)) 
244       {
245         Decrement();
246         if (q) 
247           q->Next() = p->Next();
248         else
249           data[k] = (DataMapNode*) p->Next();
250         p->~DataMapNode();
251         this->myAllocator->Free(p);
252         return Standard_True;
253       }
254       q = p;
255       p = (DataMapNode*) p->Next();
256     }
257     return Standard_False;
258   }
259
260   //! Find
261   const TheItemType& Find(const TheKeyType& theKey) const
262   {
263 #if !defined No_Exception && !defined No_Standard_NoSuchObject
264     if (IsEmpty())
265       Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
266 #endif
267     DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
268     while (p) 
269     {
270       if (Hasher::IsEqual(p->Key(),theKey)) 
271         return p->Value();
272       p = (DataMapNode*) p->Next();
273     }
274     Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
275     return p->Value(); // This for compiler
276   }
277
278   //! operator ()
279   const TheItemType& operator() (const TheKeyType& theKey) const
280   { return Find(theKey); }
281
282   //! ChangeFind
283   TheItemType& ChangeFind (const TheKeyType& theKey)
284   {
285 #if !defined No_Exception && !defined No_Standard_NoSuchObject
286     if (IsEmpty())
287       Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
288 #endif
289     DataMapNode*  p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
290     while (p) 
291     {
292       if (Hasher::IsEqual(p->Key(),theKey)) 
293         return p->ChangeValue();
294       p = (DataMapNode*) p->Next();
295     }
296     Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
297     return p->ChangeValue(); // This for compiler
298   }
299
300   //! operator ()
301   TheItemType& operator() (const TheKeyType& theKey)
302   { return ChangeFind(theKey); }
303
304   //! Clear data. If doReleaseMemory is false then the table of
305   //! buckets is not released and will be reused.
306   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
307   { Destroy (DataMapNode::delNode, this->myAllocator, doReleaseMemory); }
308
309   //! Clear data and reset allocator
310   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
311   { 
312     Clear();
313     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
314                     NCollection_BaseAllocator::CommonBaseAllocator() );
315   }
316
317   //! Destructor
318   ~NCollection_DataMap (void)
319   { Clear(); }
320
321   //! Size
322   virtual Standard_Integer Size(void) const
323   { return Extent(); }
324
325  private:
326   // ----------- PRIVATE METHODS -----------
327
328   //! Creates Iterator for use on BaseCollection
329   virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator& 
330           CreateIterator(void) const
331   { return *(new (this->IterAllocator()) Iterator(*this)); }
332
333 };
334
335 #endif
336