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