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