0030518: Foundation Classes - NCollection_IndexedDataMap array out of bounds
[occt.git] / src / NCollection / NCollection_IndexedDataMap.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_IndexedDataMap_HeaderFile
17 #define NCollection_IndexedDataMap_HeaderFile
18
19 #include <NCollection_BaseMap.hxx>
20 #include <NCollection_TListNode.hxx>
21 #include <Standard_TypeMismatch.hxx>
22 #include <Standard_NoSuchObject.hxx>
23 #include <NCollection_StlIterator.hxx>
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..
35  *              Extent.  An Item is stored with each key.
36  *              
37  *              This   class is   similar  to  IndexedMap     from
38  *              NCollection  with the Item as  a new feature. Note
39  *              the important difference on  the operator  ().  In
40  *              the IndexedMap this operator returns  the Key.  In
41  *              the IndexedDataMap this operator returns the Item.
42  *               
43  *              See  the  class   Map   from NCollection   for   a
44  *              discussion about the number of buckets.
45  */            
46
47 template < class TheKeyType, 
48            class TheItemType, 
49            class Hasher = NCollection_DefaultHasher<TheKeyType> > 
50 class NCollection_IndexedDataMap : public NCollection_BaseMap
51 {
52 public:
53   //! STL-compliant typedef for key type
54   typedef TheKeyType key_type;
55   //! STL-compliant typedef for value type
56   typedef TheItemType value_type;
57
58 private:
59   //!    Adaptation of the TListNode to the INDEXEDDatamap
60   class IndexedDataMapNode : public NCollection_TListNode<TheItemType>
61   {
62   public:
63     //! Constructor with 'Next'
64     IndexedDataMapNode (const TheKeyType&      theKey1, 
65                         const Standard_Integer theIndex,
66                         const TheItemType&     theItem,
67                         NCollection_ListNode*  theNext1)
68     : NCollection_TListNode<TheItemType>(theItem,theNext1),
69       myKey1  (theKey1),
70       myIndex (theIndex)
71     { 
72     }
73     //! Key1
74     TheKeyType& Key1() { return myKey1; }
75     //! Index
76     Standard_Integer& Index() { return myIndex; }
77
78     //! Static deleter to be passed to BaseList
79     static void delNode (NCollection_ListNode * theNode, 
80                          Handle(NCollection_BaseAllocator)& theAl)
81     {
82       ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode();
83       theAl->Free(theNode);
84     }
85   private:
86     TheKeyType       myKey1;
87     Standard_Integer myIndex;
88   };
89
90  public:
91   //!   Implementation of the Iterator interface.
92   class Iterator
93   {
94   public:
95     //! Empty constructor
96     Iterator()
97     : myMap (NULL),
98       myIndex (0) {}
99
100     //! Constructor
101     Iterator (const NCollection_IndexedDataMap& theMap)
102     : myMap ((NCollection_IndexedDataMap*)&theMap),
103       myIndex (1) {}
104
105     //! Query if the end of collection is reached by iterator
106     Standard_Boolean More(void) const
107     { return (myMap != NULL) && (myIndex <= myMap->Extent()); }
108
109     //! Make a step along the collection
110     void Next(void)
111     { ++myIndex; }
112
113     //! Value access
114     const TheItemType& Value(void) const
115     {  
116       Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Value");
117       return myMap->FindFromIndex(myIndex);
118     }
119
120     //! ChangeValue access
121     TheItemType& ChangeValue(void) const
122     {  
123       Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::ChangeValue");
124       return myMap->ChangeFromIndex(myIndex);
125     }
126
127     //! Key
128     const TheKeyType& Key() const
129     {
130       Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Key");
131       return myMap->FindKey(myIndex);
132     }
133
134     //! Performs comparison of two iterators.
135     Standard_Boolean IsEqual (const Iterator& theOther) const
136     {
137       return myMap == theOther.myMap &&
138              myIndex == theOther.myIndex;
139     }
140
141   private:
142     NCollection_IndexedDataMap* myMap;   //!< Pointer to current node
143     Standard_Integer            myIndex; //!< Current index
144   };
145   
146   //! Shorthand for a regular iterator type.
147   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator;
148
149   //! Shorthand for a constant iterator type.
150   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator;
151
152   //! Returns an iterator pointing to the first element in the map.
153   iterator begin() const { return Iterator (*this); }
154
155   //! Returns an iterator referring to the past-the-end element in the map.
156   iterator end() const { return Iterator(); }
157
158   //! Returns a const iterator pointing to the first element in the map.
159   const_iterator cbegin() const { return Iterator (*this); }
160
161   //! Returns a const iterator referring to the past-the-end element in the map.
162   const_iterator cend() const { return Iterator(); }
163   
164  public:
165   // ---------- PUBLIC METHODS ------------
166
167   //! Empty constructor.
168   NCollection_IndexedDataMap() : NCollection_BaseMap (1, Standard_False, Handle(NCollection_BaseAllocator)()) {}
169
170   //! Constructor
171   explicit NCollection_IndexedDataMap (const Standard_Integer theNbBuckets,
172                                        const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
173   : NCollection_BaseMap (theNbBuckets, Standard_False, theAllocator) {}
174
175   //! Copy constructor
176   NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther) 
177     : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator) 
178   { *this = theOther; }
179
180   //! Exchange the content of two maps without re-allocations.
181   //! Notice that allocators will be swapped as well!
182   void Exchange (NCollection_IndexedDataMap& theOther)
183   {
184     this->exchangeMapsData (theOther);
185   }
186
187   //! Assignment.
188   //! This method does not change the internal allocator.
189   NCollection_IndexedDataMap& Assign (const NCollection_IndexedDataMap& theOther)
190   { 
191     if (this == &theOther)
192       return *this;
193
194     Clear();
195     Standard_Integer anExt = theOther.Extent();
196     if (anExt)
197     {
198       ReSize (anExt-1); //mySize is same after resize
199       for (Standard_Integer anIndexIter = 1; anIndexIter <= anExt; ++anIndexIter)
200       {
201         const TheKeyType&  aKey1  = theOther.FindKey      (anIndexIter);
202         const TheItemType& anItem = theOther.FindFromIndex(anIndexIter);
203         const Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
204         IndexedDataMapNode* pNode = new (this->myAllocator) IndexedDataMapNode (aKey1, anIndexIter, anItem, myData1[iK1]);
205         myData1[iK1]             = pNode;
206         myData2[anIndexIter - 1] = pNode;
207         Increment();
208       }
209     }
210     return *this;
211   }
212
213   //! Assignment operator
214   NCollection_IndexedDataMap& operator= (const NCollection_IndexedDataMap& theOther)
215   {
216     return Assign (theOther);
217   }
218
219   //! ReSize
220   void ReSize (const Standard_Integer N)
221   {
222     NCollection_ListNode** ppNewData1 = NULL;
223     NCollection_ListNode** ppNewData2 = NULL;
224     Standard_Integer newBuck;
225     if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
226     {
227       if (myData1) 
228       {
229         memcpy (ppNewData2, myData2, sizeof(IndexedDataMapNode*) * Extent());
230         for (Standard_Integer aBucketIter = 0; aBucketIter <= NbBuckets(); ++aBucketIter)
231         {
232           if (myData1[aBucketIter])
233           {
234             IndexedDataMapNode* p = (IndexedDataMapNode *) myData1[aBucketIter];
235             while (p) 
236             {
237               const Standard_Integer iK1 = Hasher::HashCode (p->Key1(), newBuck);
238               IndexedDataMapNode* q = (IndexedDataMapNode* )p->Next();
239               p->Next() = ppNewData1[iK1];
240               ppNewData1[iK1] = p;
241               p = q;
242             }
243           }
244         }
245       }
246       EndResize (N, newBuck, ppNewData1, ppNewData2);
247     }
248   }
249
250   //! Returns the Index of already bound Key or appends new Key with specified Item value.
251   //! @param theKey1 Key to search (and to bind, if it was not bound already)
252   //! @param theItem Item value to set for newly bound Key; ignored if Key was already bound
253   //! @return index of Key
254   Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
255   {
256     if (Resizable())
257     {
258       ReSize(Extent());
259     }
260
261     const Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
262     IndexedDataMapNode* pNode = (IndexedDataMapNode* )myData1[iK1];
263     while (pNode)
264     {
265       if (Hasher::IsEqual (pNode->Key1(), theKey1))
266       {
267         return pNode->Index();
268       }
269       pNode = (IndexedDataMapNode *) pNode->Next();
270     }
271
272     const Standard_Integer aNewIndex = Increment();
273     pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, aNewIndex, theItem, myData1[iK1]);
274     myData1[iK1]           = pNode;
275     myData2[aNewIndex - 1] = pNode;
276     return aNewIndex;
277   }
278
279   //! Contains
280   Standard_Boolean Contains (const TheKeyType& theKey1) const
281   {
282     if (IsEmpty()) 
283       return Standard_False;
284     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
285     IndexedDataMapNode * pNode1;
286     pNode1 = (IndexedDataMapNode *) myData1[iK1];
287     while (pNode1) 
288     {
289       if (Hasher::IsEqual(pNode1->Key1(), theKey1)) 
290         return Standard_True;
291       pNode1 = (IndexedDataMapNode *) pNode1->Next();
292     }
293     return Standard_False;
294   }
295
296   //! Substitute
297   void Substitute (const Standard_Integer theIndex,
298                    const TheKeyType&      theKey1,
299                    const TheItemType&     theItem)
300   {
301     Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(),
302                                   "NCollection_IndexedDataMap::Substitute : "
303                                   "Index is out of range");
304
305     // check if theKey1 is not already in the map
306     const Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
307     IndexedDataMapNode* p = (IndexedDataMapNode *) myData1[iK1];
308     while (p)
309     {
310       if (Hasher::IsEqual (p->Key1(), theKey1))
311       {
312         if (p->Index() != theIndex)
313         {
314           throw Standard_DomainError ("NCollection_IndexedDataMap::Substitute : "
315                                       "Attempt to substitute existing key");
316         }
317         p->Key1() = theKey1;
318         p->ChangeValue() = theItem;
319         return;
320       }
321       p = (IndexedDataMapNode *) p->Next();
322     }
323
324     // Find the node for the index I
325     p = (IndexedDataMapNode* )myData2[theIndex - 1];
326     
327     // remove the old key
328     const Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
329     IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
330     if (q == p)
331       myData1[iK] = (IndexedDataMapNode *) p->Next();
332     else 
333     {
334       while (q->Next() != p) 
335         q = (IndexedDataMapNode *) q->Next();
336       q->Next() = p->Next();
337     }
338
339     // update the node
340     p->Key1()  = theKey1;
341     p->ChangeValue() = theItem;
342     p->Next()  = myData1[iK1];
343     myData1[iK1] = p;
344   }
345
346   //! Swaps two elements with the given indices.
347   void Swap (const Standard_Integer theIndex1,
348              const Standard_Integer theIndex2)
349   {
350     Standard_OutOfRange_Raise_if (theIndex1 < 1 || theIndex1 > Extent()
351                                || theIndex2 < 1 || theIndex2 > Extent(), "NCollection_IndexedDataMap::Swap");
352
353     if (theIndex1 == theIndex2)
354     {
355       return;
356     }
357
358     IndexedDataMapNode* aP1 = (IndexedDataMapNode* )myData2[theIndex1 - 1];
359     IndexedDataMapNode* aP2 = (IndexedDataMapNode* )myData2[theIndex2 - 1];
360     std::swap (aP1->Index(), aP2->Index());
361     myData2[theIndex2 - 1] = aP1;
362     myData2[theIndex1 - 1] = aP2;
363   }
364
365   //! RemoveLast
366   void RemoveLast (void)
367   {
368     const Standard_Integer aLastIndex = Extent();
369     Standard_OutOfRange_Raise_if (aLastIndex == 0, "NCollection_IndexedDataMap::RemoveLast");
370
371     // Find the node for the last index and remove it
372     IndexedDataMapNode* p = (IndexedDataMapNode* )myData2[aLastIndex - 1];
373     myData2[aLastIndex - 1] = NULL;
374     
375     // remove the key
376     const Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
377     IndexedDataMapNode* q = (IndexedDataMapNode *) myData1[iK1];
378     if (q == p)
379       myData1[iK1] = (IndexedDataMapNode *) p->Next();
380     else 
381     {
382       while (q->Next() != p) 
383         q = (IndexedDataMapNode *) q->Next();
384       q->Next() = p->Next();
385     }
386     p->~IndexedDataMapNode();
387     this->myAllocator->Free(p);
388     Decrement();
389   }
390
391   //! Remove the key of the given index.
392   //! Caution! The index of the last key can be changed.
393   void RemoveFromIndex(const Standard_Integer theIndex)
394   {
395     const Standard_Integer aLastInd = Extent();
396     Standard_OutOfRange_Raise_if(theIndex < 1 || theIndex > aLastInd, "NCollection_IndexedDataMap::Remove");
397     if (theIndex != aLastInd)
398     {
399       Swap (theIndex, aLastInd);
400     }
401     RemoveLast();
402   }
403
404   //! Remove the given key.
405   //! Caution! The index of the last key can be changed.
406   void RemoveKey(const TheKeyType& theKey1)
407   {
408     Standard_Integer anIndToRemove = FindIndex(theKey1);
409     if (anIndToRemove > 0) {
410       RemoveFromIndex(anIndToRemove);
411     }
412   }
413
414   //! FindKey
415   const TheKeyType& FindKey (const Standard_Integer theIndex) const
416   {
417     Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::FindKey");
418     IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1];
419     return aNode->Key1();
420   }
421
422   //! FindFromIndex
423   const TheItemType& FindFromIndex (const Standard_Integer theIndex) const
424   {
425     Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::FindFromIndex");
426     IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1];
427     return aNode->Value();
428   }
429
430   //! operator ()
431   const TheItemType& operator() (const Standard_Integer theIndex) const { return FindFromIndex (theIndex); }
432
433   //! ChangeFromIndex
434   TheItemType& ChangeFromIndex (const Standard_Integer theIndex)
435   {
436     Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::ChangeFromIndex");
437     IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1];
438     return aNode->ChangeValue();
439   }
440
441   //! operator ()
442   TheItemType& operator() (const Standard_Integer theIndex) { return ChangeFromIndex (theIndex); }
443
444   //! FindIndex
445   Standard_Integer FindIndex(const TheKeyType& theKey1) const
446   {
447     if (IsEmpty()) return 0;
448     IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())];
449     while (pNode1)
450     {
451       if (Hasher::IsEqual (pNode1->Key1(), theKey1))
452       {
453         return pNode1->Index();
454       }
455       pNode1 = (IndexedDataMapNode*) pNode1->Next();
456     }
457     return 0;
458   }
459
460   //! FindFromKey
461   const TheItemType& FindFromKey(const TheKeyType& theKey1) const
462   {
463     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::FindFromKey");
464
465     IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())];
466     while (pNode1)
467     {
468       if (Hasher::IsEqual (pNode1->Key1(), theKey1))
469       {
470         return pNode1->Value();
471       }
472       pNode1 = (IndexedDataMapNode*) pNode1->Next();
473     }
474     throw Standard_NoSuchObject("NCollection_IndexedDataMap::FindFromKey");
475   }
476
477   //! ChangeFromKey
478   TheItemType& ChangeFromKey (const TheKeyType& theKey1)
479   {
480     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::ChangeFromKey");
481
482     IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())];
483     while (pNode1)
484     {
485       if (Hasher::IsEqual (pNode1->Key1(), theKey1))
486       {
487         return pNode1->ChangeValue();
488       }
489       pNode1 = (IndexedDataMapNode*) pNode1->Next();
490     }
491     throw Standard_NoSuchObject("NCollection_IndexedDataMap::ChangeFromKey");
492   }
493
494   //! Seek returns pointer to Item by Key. Returns
495   //! NULL if Key was not found.
496   const TheItemType* Seek(const TheKeyType& theKey1) const
497   {
498     return const_cast< NCollection_IndexedDataMap * >( this )->ChangeSeek(theKey1);
499     //NCollection_IndexedDataMap *pMap=(NCollection_IndexedDataMap *)this;
500     //return pMap->ChangeSeek(theKey1);
501   }
502
503   //! ChangeSeek returns modifiable pointer to Item by Key. Returns
504   //! NULL if Key was not found.
505   TheItemType* ChangeSeek (const TheKeyType& theKey1)
506   {
507     if (!IsEmpty()) 
508     {
509       IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())];
510       while (pNode1)
511       {
512         if (Hasher::IsEqual (pNode1->Key1(), theKey1))
513         {
514           return &pNode1->ChangeValue();
515         }
516         pNode1 = (IndexedDataMapNode*) pNode1->Next();
517       }
518     }
519     return 0L;
520   }
521
522   //! Find value for key with copying.
523   //! @return true if key was found
524   Standard_Boolean FindFromKey (const TheKeyType& theKey1,
525                                 TheItemType&      theValue) const
526   {
527     if (IsEmpty())
528     {
529       return Standard_False;
530     }
531     for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData1[Hasher::HashCode (theKey1, NbBuckets())];
532          aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next())
533     {
534       if (Hasher::IsEqual (aNode->Key1(), theKey1))
535       {
536         theValue = aNode->Value();
537         return Standard_True;
538       }
539     }
540     return Standard_False;
541   }
542
543   //! Clear data. If doReleaseMemory is false then the table of
544   //! buckets is not released and will be reused.
545   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
546   { Destroy (IndexedDataMapNode::delNode, doReleaseMemory); }
547
548   //! Clear data and reset allocator
549   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
550   { 
551     Clear();
552     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
553                     NCollection_BaseAllocator::CommonBaseAllocator() );
554   }
555
556   //! Destructor
557   virtual ~NCollection_IndexedDataMap (void)
558   { Clear(); }
559
560   //! Size
561   Standard_Integer Size(void) const
562   { return Extent(); }
563
564  private:
565   // ----------- PRIVATE METHODS -----------
566
567 };
568
569 #endif