0029064: Copying of empty NCollection map takes excessive memory
[occt.git] / src / NCollection / NCollection_IndexedMap.hxx
1 // Created on: 2002-04-24
2 // Created by: Alexander KARTOMIN (akm)
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #ifndef NCollection_IndexedMap_HeaderFile
17 #define NCollection_IndexedMap_HeaderFile
18
19 #include <NCollection_BaseMap.hxx>
20 #include <NCollection_TListNode.hxx>
21 #include <NCollection_StlIterator.hxx>
22 #include <Standard_NoSuchObject.hxx>
23
24 #include <NCollection_DefaultHasher.hxx>
25
26 #include <Standard_OutOfRange.hxx>
27
28 /**
29  * Purpose:     An indexed map is used to  store  keys and to bind
30  *              an index to them.  Each new key stored in  the map
31  *              gets an index.  Index are incremented  as keys are
32  *              stored in the map. A key can be found by the index
33  *              and an index by the  key. No key  but the last can
34  *              be removed so the indices are in the range 1..Extent.
35  *              See  the  class   Map   from NCollection   for   a
36  *              discussion about the number of buckets.
37  */            
38
39 template < class TheKeyType, 
40            class Hasher = NCollection_DefaultHasher<TheKeyType> > 
41 class NCollection_IndexedMap : public NCollection_BaseMap
42 {
43 public:
44   //! STL-compliant typedef for key type
45   typedef TheKeyType key_type;
46
47 private:
48   //! Adaptation of the TListNode to the INDEXEDmap
49   class IndexedMapNode : public NCollection_TListNode<TheKeyType>
50   {
51   public:
52     //! Constructor with 'Next'
53     IndexedMapNode (const TheKeyType&      theKey1, 
54                     const Standard_Integer theIndex,
55                     NCollection_ListNode*  theNext1)
56     : NCollection_TListNode<TheKeyType> (theKey1, theNext1),
57       myIndex (theIndex)
58     {
59     }
60     //! Key1
61     TheKeyType& Key1() { return this->ChangeValue(); }
62
63     //! Index
64     Standard_Integer& Index() { return myIndex; }
65     
66     //! Static deleter to be passed to BaseList
67     static void delNode (NCollection_ListNode * theNode, 
68                          Handle(NCollection_BaseAllocator)& theAl)
69     {
70       ((IndexedMapNode *) theNode)->~IndexedMapNode();
71       theAl->Free(theNode);
72     }
73
74   private:
75     Standard_Integer myIndex;
76   };
77
78  public:
79   // **************** Implementation of the Iterator interface.
80   class Iterator
81   {
82   public:
83     //! Empty constructor
84     Iterator (void) :
85       myMap(NULL),
86       myIndex(0) {}
87     //! Constructor
88     Iterator (const NCollection_IndexedMap& theMap) :
89       myMap((NCollection_IndexedMap *) &theMap),
90       myIndex(1) {}
91     //! Query if the end of collection is reached by iterator
92     Standard_Boolean More(void) const
93     { return (myMap != NULL) && (myIndex <= myMap->Extent()); }
94     //! Make a step along the collection
95     void Next(void)
96     { myIndex++; }
97     //! Value access
98     const TheKeyType& Value(void) const
99     {
100       Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedMap::Iterator::Value");
101       return myMap->FindKey(myIndex);
102     }
103
104     //! Performs comparison of two iterators.
105     Standard_Boolean IsEqual (const Iterator& theOther) const
106     {
107       return myMap == theOther.myMap && myIndex == theOther.myIndex;
108     }
109     
110   private:
111     NCollection_IndexedMap * myMap;   // Pointer to the map being iterated
112     Standard_Integer         myIndex; // Current index
113   };
114   
115   //! Shorthand for a constant iterator type.
116   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheKeyType, true> const_iterator;
117
118   //! Returns a const iterator pointing to the first element in the map.
119   const_iterator cbegin() const { return Iterator (*this); }
120
121   //! Returns a const iterator referring to the past-the-end element in the map.
122   const_iterator cend() const { return Iterator(); }
123   
124  public:
125   // ---------- PUBLIC METHODS ------------
126
127   //! Empty constructor.
128   NCollection_IndexedMap() : NCollection_BaseMap (1, Standard_False, Handle(NCollection_BaseAllocator)()) {}
129
130   //! Constructor
131   explicit NCollection_IndexedMap (const Standard_Integer theNbBuckets,
132                                    const Handle(NCollection_BaseAllocator)& theAllocator=0L)
133   : NCollection_BaseMap (theNbBuckets, Standard_False, theAllocator) {}
134
135   //! Copy constructor
136   NCollection_IndexedMap (const NCollection_IndexedMap& theOther)
137   : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator)
138   { *this = theOther; }
139
140   //! Exchange the content of two maps without re-allocations.
141   //! Notice that allocators will be swapped as well!
142   void Exchange (NCollection_IndexedMap& theOther)
143   {
144     this->exchangeMapsData (theOther);
145   }
146
147   //! Assign.
148   //! This method does not change the internal allocator.
149   NCollection_IndexedMap& Assign (const NCollection_IndexedMap& theOther)
150   { 
151     if (this == &theOther)
152       return *this;
153
154     Clear();
155     Standard_Integer anExt = theOther.Extent();
156     if (anExt)
157     {
158       ReSize (anExt-1); //mySize is same after resize
159       for (Standard_Integer anIndexIter = 1; anIndexIter <= anExt; ++anIndexIter)
160       {
161         const TheKeyType& aKey1 = theOther.FindKey (anIndexIter);
162         const Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
163         IndexedMapNode* pNode = new (this->myAllocator) IndexedMapNode (aKey1, anIndexIter, myData1[iK1]);
164         myData1[iK1]             = pNode;
165         myData2[anIndexIter - 1] = pNode;
166         Increment();
167       }
168     }
169     return *this;
170   }
171
172   //! Assignment operator
173   NCollection_IndexedMap& operator= (const NCollection_IndexedMap& theOther)
174   {
175     return Assign (theOther);
176   }
177
178   //! ReSize
179   void ReSize (const Standard_Integer theExtent)
180   {
181     NCollection_ListNode** ppNewData1 = NULL;
182     NCollection_ListNode** ppNewData2 = NULL;
183     Standard_Integer newBuck;
184     if (BeginResize (theExtent, newBuck, ppNewData1, ppNewData2))
185     {
186       if (myData1) 
187       {
188         memcpy (ppNewData2, myData2, sizeof(IndexedMapNode*) * Extent());
189         for (Standard_Integer aBucketIter = 0; aBucketIter <= NbBuckets(); ++aBucketIter)
190         {
191           if (myData1[aBucketIter])
192           {
193             IndexedMapNode* p = (IndexedMapNode* )myData1[aBucketIter];
194             while (p) 
195             {
196               const Standard_Integer iK1 = Hasher::HashCode (p->Key1(), newBuck);
197               IndexedMapNode* q = (IndexedMapNode* )p->Next();
198               p->Next() = ppNewData1[iK1];
199               ppNewData1[iK1] = p;
200               p = q;
201             }
202           }
203         }
204       }
205       EndResize (theExtent, newBuck, ppNewData1, ppNewData2);
206     }
207   }
208
209   //! Add
210   Standard_Integer Add (const TheKeyType& theKey1)
211   {
212     if (Resizable())
213     {
214       ReSize (Extent());
215     }
216
217     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
218     IndexedMapNode* pNode = (IndexedMapNode* )myData1[iK1];
219     while (pNode)
220     {
221       if (Hasher::IsEqual (pNode->Key1(), theKey1))
222       {
223         return pNode->Index();
224       }
225       pNode = (IndexedMapNode *) pNode->Next();
226     }
227
228     const Standard_Integer aNewIndex = Increment();
229     pNode = new (this->myAllocator) IndexedMapNode (theKey1, aNewIndex, myData1[iK1]);
230     myData1[iK1]           = pNode;
231     myData2[aNewIndex - 1] = pNode;
232     return aNewIndex;
233   }
234
235   //! Contains
236   Standard_Boolean Contains (const TheKeyType& theKey1) const
237   {
238     if (IsEmpty()) 
239       return Standard_False;
240     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
241     IndexedMapNode * pNode1;
242     pNode1 = (IndexedMapNode *) myData1[iK1];
243     while (pNode1) 
244     {
245       if (Hasher::IsEqual(pNode1->Key1(), theKey1)) 
246         return Standard_True;
247       pNode1 = (IndexedMapNode *) pNode1->Next();
248     }
249     return Standard_False;
250   }
251
252   //! Substitute
253   void Substitute (const Standard_Integer theIndex,
254                    const TheKeyType& theKey1)
255   {
256     Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(),
257                                   "NCollection_IndexedMap::Substitute : "
258                                   "Index is out of range");
259
260     // check if theKey1 is not already in the map
261     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
262     IndexedMapNode* p = (IndexedMapNode *) myData1[iK1];
263     while (p)
264     {
265       if (Hasher::IsEqual (p->Key1(), theKey1))
266       {
267         if (p->Index() != theIndex)
268         {
269           throw Standard_DomainError ("NCollection_IndexedMap::Substitute : "
270                                       "Attempt to substitute existing key");
271         }
272         p->Key1() = theKey1;
273         return;
274       }
275       p = (IndexedMapNode *) p->Next();
276     }
277
278     // Find the node for the index I
279     p = (IndexedMapNode* )myData2[theIndex - 1];
280     
281     // remove the old key
282     Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
283     IndexedMapNode * q = (IndexedMapNode *) myData1[iK];
284     if (q == p)
285       myData1[iK] = (IndexedMapNode *) p->Next();
286     else 
287     {
288       while (q->Next() != p) 
289         q = (IndexedMapNode *) q->Next();
290       q->Next() = p->Next();
291     }
292
293     // update the node
294     p->Key1() = theKey1;
295     p->Next() = myData1[iK1];
296     myData1[iK1] = p;
297   }
298
299   //! Swaps two elements with the given indices.
300   void Swap (const Standard_Integer theIndex1,
301              const Standard_Integer theIndex2)
302   {
303     Standard_OutOfRange_Raise_if (theIndex1 < 1 || theIndex1 > Extent()
304                                || theIndex2 < 1 || theIndex2 > Extent(), "NCollection_IndexedMap::Swap");
305
306     if (theIndex1 == theIndex2)
307     {
308       return;
309     }
310
311     IndexedMapNode* aP1 = (IndexedMapNode* )myData2[theIndex1 - 1];
312     IndexedMapNode* aP2 = (IndexedMapNode* )myData2[theIndex2 - 1];
313     std::swap (aP1->Index(), aP2->Index());
314     myData2[theIndex2 - 1] = aP1;
315     myData2[theIndex1 - 1] = aP2;
316   }
317
318   //! RemoveLast
319   void RemoveLast (void)
320   {
321     const Standard_Integer aLastIndex = Extent();
322     Standard_OutOfRange_Raise_if (aLastIndex == 0, "NCollection_IndexedMap::RemoveLast");
323
324     // Find the node for the last index and remove it
325     IndexedMapNode* p = (IndexedMapNode* )myData2[aLastIndex - 1];
326     myData2[aLastIndex - 1] = NULL;
327
328     // remove the key
329     Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
330     IndexedMapNode* q = (IndexedMapNode *) myData1[iK1];
331     if (q == p)
332       myData1[iK1] = (IndexedMapNode *) p->Next();
333     else 
334     {
335       while (q->Next() != p) 
336         q = (IndexedMapNode *) q->Next();
337       q->Next() = p->Next();
338     }
339     p->~IndexedMapNode();
340     this->myAllocator->Free(p);
341     Decrement();
342   }
343
344   //! Remove the key of the given index.
345   //! Caution! The index of the last key can be changed.
346   void RemoveFromIndex(const Standard_Integer theIndex)
347   {
348     Standard_OutOfRange_Raise_if(theIndex < 1 || theIndex > Extent(), "NCollection_IndexedMap::RemoveFromIndex");
349     const Standard_Integer aLastInd = Extent();
350     if (theIndex != aLastInd)
351     {
352       Swap(theIndex, aLastInd);
353     }
354     RemoveLast();
355   }
356
357   //! Remove the given key.
358   //! Caution! The index of the last key can be changed.
359   Standard_Boolean RemoveKey (const TheKeyType& theKey1)
360   {
361     Standard_Integer anIndToRemove = FindIndex(theKey1);
362     if (anIndToRemove < 1)
363     {
364       return Standard_False;
365     }
366
367     RemoveFromIndex (anIndToRemove);
368     return Standard_True;
369   }
370
371   //! FindKey
372   const TheKeyType& FindKey (const Standard_Integer theIndex) const
373   {
374     Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedMap::FindKey");
375     IndexedMapNode* pNode2 = (IndexedMapNode* )myData2[theIndex - 1];
376     return pNode2->Key1();
377   }
378
379   //! operator ()
380   const TheKeyType& operator() (const Standard_Integer theIndex) const
381   { return FindKey (theIndex); }
382
383   //! FindIndex
384   Standard_Integer FindIndex(const TheKeyType& theKey1) const
385   {
386     if (IsEmpty()) return 0;
387     IndexedMapNode* pNode1 = (IndexedMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())];
388     while (pNode1)
389     {
390       if (Hasher::IsEqual (pNode1->Key1(), theKey1))
391       {
392         return pNode1->Index();
393       }
394       pNode1 = (IndexedMapNode*) pNode1->Next();
395     }
396     return 0;
397   }
398
399   //! Clear data. If doReleaseMemory is false then the table of
400   //! buckets is not released and will be reused.
401   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
402   { Destroy (IndexedMapNode::delNode, doReleaseMemory); }
403
404   //! Clear data and reset allocator
405   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
406   { 
407     Clear();
408     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
409                     NCollection_BaseAllocator::CommonBaseAllocator() );
410   }
411
412   //! Destructor
413   virtual ~NCollection_IndexedMap (void)
414   { Clear(); }
415
416   //! Size
417   Standard_Integer Size(void) const
418   { return Extent(); }
419 };
420
421 #endif