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