0022815: Missing delete operator for placement new
[occt.git] / src / NCollection / NCollection_Map.hxx
1 // File:        NCollection_Map.hxx
2 // Created:     Thu Apr 23 15:02:53 2002
3 // Author:      Alexander KARTOMIN (akm)
4 //              <a-kartomin@opencascade.com>
5
6 #ifndef NCollection_Map_HeaderFile
7 #define NCollection_Map_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_ImmutableObject.hxx>
16
17 #if !defined No_Exception && !defined No_Standard_NoSuchObject
18 #include <Standard_NoSuchObject.hxx>
19 #endif
20
21 /**
22  * Purpose:     Single hashed Map. This  Map is used  to store and
23  *              retrieve keys in linear time.
24  *              
25  *              The ::Iterator class can be  used to explore  the
26  *              content of the map. It is not  wise to iterate and
27  *              modify a map in parallel.
28  *               
29  *              To compute  the hashcode of  the key the  function
30  *              ::HashCode must be defined in the global namespace
31  *               
32  *              To compare two keys the function ::IsEqual must be
33  *              defined in the global namespace.
34  *               
35  *              The performance of  a Map is conditionned  by  its
36  *              number of buckets that  should be kept greater  to
37  *              the number   of keys.  This  map has  an automatic
38  *              management of the number of buckets. It is resized
39  *              when  the number of Keys  becomes greater than the
40  *              number of buckets.
41  *              
42  *              If you have a fair  idea of the number of  objects
43  *              you  can save on automatic   resizing by giving  a
44  *              number of buckets  at creation or using the ReSize
45  *              method. This should be  consider only for  crucial
46  *              optimisation issues.
47  */            
48
49 template < class TheKeyType, 
50            class Hasher = NCollection_DefaultHasher<TheKeyType> > class NCollection_Map 
51   : public NCollection_BaseCollection<TheKeyType>,
52     public NCollection_BaseMap
53 {
54   //!   Adaptation of the TListNode to the map notations
55  public:
56
57   class MapNode : public NCollection_TListNode<TheKeyType>
58   {
59   public:
60     //! Constructor with 'Next'
61     MapNode (const TheKeyType& theKey, 
62              NCollection_ListNode* theNext) :
63       NCollection_TListNode<TheKeyType> (theKey, theNext) {}
64     //! Key
65     const TheKeyType& Key (void)
66     { return this->Value(); }
67
68   };
69
70  public:
71   //!   Implementation of the Iterator interface.
72   class Iterator 
73     : public NCollection_BaseCollection<TheKeyType>::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_Map& 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 TheKeyType& Value(void) const
91     {
92 #if !defined No_Exception && !defined No_Standard_NoSuchObject
93       if (!More())
94         Standard_NoSuchObject::Raise ("NCollection_Map::Iterator::Value");  
95 #endif
96       return ((MapNode *) myNode)->Value();
97     }
98     //! Value change access - denied
99     virtual TheKeyType& ChangeValue(void) const
100     {  
101       Standard_ImmutableObject::Raise("NCollection_Map::Iterator::ChangeValue");
102       return * (TheKeyType *) NULL; // For compiler
103     }
104     //! Key
105     const TheKeyType& Key (void)
106     { 
107 #if !defined No_Exception && !defined No_Standard_NoSuchObject
108       if (!More())
109         Standard_NoSuchObject::Raise ("NCollection_Map::Iterator::Key");  
110 #endif
111       return ((MapNode *) myNode)->Value();
112     }
113   };
114
115  public:
116   // ---------- PUBLIC METHODS ------------
117
118   //! Constructor
119   NCollection_Map (const Standard_Integer NbBuckets = 1,
120                    const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
121     : NCollection_BaseCollection<TheKeyType>(theAllocator),
122       NCollection_BaseMap (NbBuckets, Standard_True) {}
123
124   //! Copy constructor
125   NCollection_Map (const NCollection_Map& theOther)
126     : NCollection_BaseCollection<TheKeyType>(theOther.myAllocator),
127       NCollection_BaseMap (theOther.NbBuckets(), Standard_True) 
128   { *this = theOther; }
129
130   //! Assign another collection
131   virtual void Assign (const NCollection_BaseCollection<TheKeyType>& theOther)
132   { 
133     if (this == &theOther)
134       return;
135
136     Clear();
137     ReSize (theOther.Size()-1);
138     TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& anIter = 
139       theOther.CreateIterator();
140     for (; anIter.More(); anIter.Next())
141       Add (anIter.Value());
142   }
143
144   //! = another map
145   NCollection_Map& operator= (const NCollection_Map& theOther)
146   { 
147     if (this == &theOther)
148       return *this;
149
150     Clear(theOther.myAllocator);
151     ReSize (theOther.Extent()-1);
152     Iterator anIter(theOther);
153     for (; anIter.More(); anIter.Next())
154       Add (anIter.Key());
155     return *this;
156   }
157
158   //! ReSize
159   void ReSize (const Standard_Integer N)
160   {
161     MapNode** newdata = 0L;
162     MapNode** dummy = 0L;
163     Standard_Integer newBuck;
164     if (BeginResize (N, newBuck, 
165                      (NCollection_ListNode**&)newdata, 
166                      (NCollection_ListNode**&)dummy,
167                      this->myAllocator)) 
168     {
169       if (myData1) 
170       {
171         MapNode** olddata = (MapNode**) myData1;
172         MapNode *p, *q;
173         Standard_Integer i,k;
174         for (i = 0; i <= NbBuckets(); i++) 
175         {
176           if (olddata[i]) 
177           {
178             p = olddata[i];
179             while (p) 
180             {
181               k = Hasher::HashCode(p->Key(),newBuck);
182               q = (MapNode*) p->Next();
183               p->Next() = newdata[k];
184               newdata[k] = p;
185               p = q;
186             }
187           }
188         }
189       }
190       EndResize(N,newBuck,
191                 (NCollection_ListNode**&)newdata,
192                 (NCollection_ListNode**&)dummy,
193                 this->myAllocator);
194     }
195   }
196
197   //! Add
198   Standard_Boolean Add(const TheKeyType& K)
199   {
200     if (Resizable()) 
201       ReSize(Extent());
202     MapNode** data = (MapNode**)myData1;
203     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
204     MapNode* p = data[k];
205     while (p) 
206     {
207       if (Hasher::IsEqual(p->Key(),K))
208         return Standard_False;
209       p = (MapNode *) p->Next();
210     }
211     data[k] = new (this->myAllocator) MapNode(K,data[k]);
212     Increment();
213     return Standard_True;
214   }
215
216   //! Added: add a new key if not yet in the map, and return 
217   //! reference to either newly added or previously existing object
218   const TheKeyType& Added(const TheKeyType& K)
219   {
220     if (Resizable()) 
221       ReSize(Extent());
222     MapNode** data = (MapNode**)myData1;
223     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
224     MapNode* p = data[k];
225     while (p) 
226     {
227       if (Hasher::IsEqual(p->Key(),K))
228         return p->Key();
229       p = (MapNode *) p->Next();
230     }
231     data[k] = new (this->myAllocator) MapNode(K,data[k]);
232     Increment();
233     return data[k]->Key();
234   }
235
236   //! Contains
237   Standard_Boolean Contains(const TheKeyType& K) const
238   {
239     if (IsEmpty()) 
240       return Standard_False;
241     MapNode** data = (MapNode**) myData1;
242     MapNode*  p = data[Hasher::HashCode(K,NbBuckets())];
243     while (p) 
244     {
245       if (Hasher::IsEqual(p->Key(),K)) 
246         return Standard_True;
247       p = (MapNode *) p->Next();
248     }
249     return Standard_False;
250   }
251
252   //! Remove
253   Standard_Boolean Remove(const TheKeyType& K)
254   {
255     if (IsEmpty()) 
256       return Standard_False;
257     MapNode** data = (MapNode**) myData1;
258     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
259     MapNode* p = data[k];
260     MapNode* q = NULL;
261     while (p) 
262     {
263       if (Hasher::IsEqual(p->Key(),K)) 
264       {
265         Decrement();
266         if (q) 
267           q->Next() = p->Next();
268         else
269           data[k] = (MapNode*) p->Next();
270         p->~MapNode();
271         this->myAllocator->Free(p);
272         return Standard_True;
273       }
274       q = p;
275       p = (MapNode*) p->Next();
276     }
277     return Standard_False;
278   }
279
280   //! Clear data. If doReleaseMemory is false then the table of
281   //! buckets is not released and will be reused.
282   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
283   { Destroy (MapNode::delNode, this->myAllocator, doReleaseMemory); }
284
285   //! Clear data and reset allocator
286   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
287   { 
288     Clear();
289     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
290                     NCollection_BaseAllocator::CommonBaseAllocator() );
291   }
292
293   //! Destructor
294   ~NCollection_Map (void)
295   { Clear(); }
296
297   //! Size
298   virtual Standard_Integer Size(void) const
299   { return Extent(); }
300
301  private:
302   // ----------- PRIVATE METHODS -----------
303
304   //! Creates Iterator for use on BaseCollection
305   virtual TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& 
306     CreateIterator(void) const
307   { return *(new (this->IterAllocator()) Iterator(*this)); }
308
309 };
310
311 #endif