0024831: Make iterators of NCollection classes STL-compatible
[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_BaseCollection.hxx>
20 #include <NCollection_BaseMap.hxx>
21 #include <NCollection_TListNode.hxx>
22 #include <NCollection_StlIterator.hxx>
23 #include <Standard_NoSuchObject.hxx>
24 #include <Standard_ImmutableObject.hxx>
25
26 #include <NCollection_DefaultHasher.hxx>
27
28 #if !defined No_Exception && !defined No_Standard_OutOfRange
29 #include <Standard_OutOfRange.hxx>
30 #endif
31
32 /**
33  * Purpose:     An indexed map is used to  store  keys and to bind
34  *              an index to them.  Each new key stored in  the map
35  *              gets an index.  Index are incremented  as keys are
36  *              stored in the map. A key can be found by the index
37  *              and an index by the  key. No key  but the last can
38  *              be removed so the indices are in the range 1..Extent.
39  *              See  the  class   Map   from NCollection   for   a
40  *              discussion about the number of buckets.
41  */            
42
43 template < class TheKeyType, 
44            class Hasher = NCollection_DefaultHasher<TheKeyType> > 
45   class NCollection_IndexedMap 
46   : public NCollection_BaseCollection<TheKeyType>,
47     public NCollection_BaseMap
48 {
49   // **************** Adaptation of the TListNode to the INDEXEDmap
50  private:
51   class IndexedMapNode : public NCollection_TListNode<TheKeyType>
52   {
53   public:
54     //! Constructor with 'Next'
55     IndexedMapNode (const TheKeyType&      theKey1, 
56                     const Standard_Integer theKey2, 
57                     NCollection_ListNode*  theNext1, 
58                     NCollection_ListNode*  theNext2) :
59                       NCollection_TListNode<TheKeyType> (theKey1, theNext1)
60     { 
61       myKey2 = theKey2;
62       myNext2 = (IndexedMapNode *) theNext2;
63     }
64     //! Key1
65     TheKeyType& Key1 (void)
66     { return this->ChangeValue(); }
67     //! Key2
68     const Standard_Integer& Key2 (void)
69     { return myKey2; }
70     //! Next2
71     IndexedMapNode*& Next2 (void)
72     { return myNext2; }
73     
74     //! Static deleter to be passed to BaseList
75     static void delNode (NCollection_ListNode * theNode, 
76                          Handle(NCollection_BaseAllocator)& theAl)
77     {
78       ((IndexedMapNode *) theNode)->~IndexedMapNode();
79       theAl->Free(theNode);
80     }
81
82   private:
83     Standard_Integer myKey2;
84     IndexedMapNode * myNext2;
85   };
86
87  public:
88   // **************** Implementation of the Iterator interface.
89   class Iterator 
90     : public NCollection_BaseCollection<TheKeyType>::Iterator
91   {
92   public:
93     //! Empty constructor
94     Iterator (void) :
95       myMap(NULL),
96       myIndex(0) {}
97     //! Constructor
98     Iterator (const NCollection_IndexedMap& theMap) :
99       myMap((NCollection_IndexedMap *) &theMap),
100       myIndex(1) {}
101     //! Query if the end of collection is reached by iterator
102     virtual Standard_Boolean More(void) const
103     { return (myMap != NULL) && (myIndex <= myMap->Extent()); }
104     //! Make a step along the collection
105     virtual void Next(void)
106     { myIndex++; }
107     //! Value access
108     virtual const TheKeyType& Value(void) const
109     {
110 #if !defined No_Exception && !defined No_Standard_NoSuchObject
111       if (!More())
112         Standard_NoSuchObject::Raise("NCollection_IndexedMap::Iterator::Value");
113 #endif
114       return myMap->FindKey(myIndex);
115     }
116     //! Value change access denied - use Substitute
117     virtual TheKeyType& ChangeValue(void) const
118     {  
119       Standard_ImmutableObject::Raise ("impossible to ChangeValue");
120       return * (TheKeyType *) NULL; // This for compiler
121     }
122     //! Performs comparison of two iterators.
123     virtual Standard_Boolean IsEqual (const Iterator& theOther) const
124     {
125       return myMap == theOther.myMap && myIndex == theOther.myIndex;
126     }
127     
128   private:
129     NCollection_IndexedMap * myMap;   // Pointer to the map being iterated
130     Standard_Integer         myIndex; // Current index
131   };
132   
133   //! Shorthand for a constant iterator type.
134   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheKeyType, true> const_iterator;
135
136   //! Returns a const iterator pointing to the first element in the map.
137   const_iterator cbegin() const { return Iterator (*this); }
138
139   //! Returns a const iterator referring to the past-the-end element in the map.
140   const_iterator cend() const { return Iterator(); }
141   
142  public:
143   // ---------- PUBLIC METHODS ------------
144
145   //! Constructor
146   NCollection_IndexedMap (const Standard_Integer NbBuckets=1,
147                           const Handle(NCollection_BaseAllocator)& theAllocator=0L) :
148     NCollection_BaseCollection<TheKeyType>(theAllocator),
149     NCollection_BaseMap (NbBuckets, Standard_False) {}
150
151   //! Copy constructor
152   NCollection_IndexedMap (const NCollection_IndexedMap& theOther) :
153     NCollection_BaseCollection<TheKeyType>(theOther.myAllocator),
154     NCollection_BaseMap (theOther.NbBuckets(), Standard_False) 
155   { *this = theOther; }
156
157   //! Assign another collection
158   virtual void Assign (const NCollection_BaseCollection<TheKeyType>& theOther)
159   { 
160     if (this == &theOther)
161       return;
162     Clear();
163     ReSize (theOther.Size()-1);
164     TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& anIter = 
165       theOther.CreateIterator();
166     for (; anIter.More(); anIter.Next())
167       Add(anIter.Value());
168   }
169
170   //! Exchange the content of two maps without re-allocations.
171   //! Notice that allocators will be swapped as well!
172   void Exchange (NCollection_IndexedMap& theOther)
173   {
174     this->exchangeAllocators (theOther);
175     this->exchangeMapsData   (theOther);
176   }
177
178   //! = another map
179   NCollection_IndexedMap& operator= (const NCollection_IndexedMap& theOther)
180   { 
181     if (this == &theOther)
182       return *this;
183
184     Clear(theOther.myAllocator);
185     ReSize (theOther.Extent()-1);
186     Standard_Integer i, iLength=theOther.Extent();
187     for (i=1; i<=iLength; i++)
188     {
189       TheKeyType aKey1 = theOther(i);
190       Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
191       Standard_Integer iK2 = ::HashCode (i, NbBuckets());
192       IndexedMapNode * pNode = new (this->myAllocator) IndexedMapNode (aKey1, i, 
193                                                                        myData1[iK1], 
194                                                                        myData2[iK2]);
195       myData1[iK1] = pNode;
196       myData2[iK2] = pNode;
197       Increment();
198     }
199     return *this;
200   }
201
202   //! ReSize
203   void ReSize (const Standard_Integer N)
204   {
205     NCollection_ListNode** ppNewData1 = NULL;
206     NCollection_ListNode** ppNewData2 = NULL;
207     Standard_Integer newBuck;
208     if (BeginResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator)) 
209     {
210       if (myData1) 
211       {
212         IndexedMapNode *p, *q;
213         Standard_Integer i, iK1, iK2;
214         for (i = 0; i <= NbBuckets(); i++) 
215         {
216           if (myData1[i]) 
217           {
218             p = (IndexedMapNode *) myData1[i];
219             while (p) 
220             {
221               iK1 =Hasher::HashCode(p->Key1(), newBuck);
222               q = (IndexedMapNode*) p->Next();
223               p->Next()  = ppNewData1[iK1];
224               ppNewData1[iK1] = p;
225               if (p->Key2() > 0) 
226               {
227                 iK2 = ::HashCode (p->Key2(), newBuck);
228                 p->Next2() = (IndexedMapNode*)ppNewData2[iK2];
229                 ppNewData2[iK2] = p;
230               }
231               p = q;
232             }
233           }
234         }
235       }
236       EndResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator);
237     }
238   }
239
240   //! Add
241   Standard_Integer Add (const TheKeyType& theKey1)
242   {
243     if (Resizable()) 
244       ReSize(Extent());
245     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
246     IndexedMapNode * pNode;
247     pNode = (IndexedMapNode *) myData1[iK1];
248     while (pNode)
249     {
250       if (Hasher::IsEqual (pNode->Key1(), theKey1))
251         return pNode->Key2();
252       pNode = (IndexedMapNode *) pNode->Next();
253     }
254     Increment();
255     Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
256     pNode = new (this->myAllocator) IndexedMapNode (theKey1, Extent(), 
257                                                     myData1[iK1], myData2[iK2]);
258     myData1[iK1] = pNode;
259     myData2[iK2] = pNode;
260     return Extent();
261   }
262
263   //! Contains
264   Standard_Boolean Contains (const TheKeyType& theKey1) const
265   {
266     if (IsEmpty()) 
267       return Standard_False;
268     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
269     IndexedMapNode * pNode1;
270     pNode1 = (IndexedMapNode *) myData1[iK1];
271     while (pNode1) 
272     {
273       if (Hasher::IsEqual(pNode1->Key1(), theKey1)) 
274         return Standard_True;
275       pNode1 = (IndexedMapNode *) pNode1->Next();
276     }
277     return Standard_False;
278   }
279
280   //! Substitute
281   void Substitute (const Standard_Integer theIndex,
282                    const TheKeyType& theKey1)
283   {
284 #if !defined No_Exception && !defined No_Standard_OutOfRange
285     if (theIndex < 1 || theIndex > Extent())
286       Standard_OutOfRange::Raise ("NCollection_IndexedMap::Substitute");
287 #endif
288     IndexedMapNode * p;
289     // check if theKey1 is not already in the map
290     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
291     p = (IndexedMapNode *) myData1[iK1];
292     while (p) 
293     {
294       if (Hasher::IsEqual (p->Key1(), theKey1)) 
295         Standard_DomainError::Raise("NCollection_IndexedMap::Substitute");
296       p = (IndexedMapNode *) p->Next();
297     }
298
299     // Find the node for the index I
300     Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
301     p = (IndexedMapNode *) myData2[iK2];
302     while (p) 
303     {
304       if (p->Key2() == theIndex) 
305         break;
306       p = (IndexedMapNode*) p->Next2();
307     }
308     
309     // remove the old key
310     Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
311     IndexedMapNode * q = (IndexedMapNode *) myData1[iK];
312     if (q == p)
313       myData1[iK] = (IndexedMapNode *) p->Next();
314     else 
315     {
316       while (q->Next() != p) 
317         q = (IndexedMapNode *) q->Next();
318       q->Next() = p->Next();
319     }
320
321     // update the node
322     p->Key1() = theKey1;
323     p->Next() = myData1[iK1];
324     myData1[iK1] = p;
325   }
326
327   //! RemoveLast
328   void RemoveLast (void)
329   {
330 #if !defined No_Exception && !defined No_Standard_OutOfRange
331     if (Extent() == 0)
332       Standard_OutOfRange::Raise ("NCollection_IndexedMap::RemoveLast");
333 #endif
334     IndexedMapNode * p, * q;
335     // Find the node for the last index and remove it
336     Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
337     p = (IndexedMapNode *) myData2[iK2];
338     q = NULL;
339     while (p) 
340     {
341       if (p->Key2() == Extent()) 
342         break;
343       q = p;
344       p = (IndexedMapNode*) p->Next2();
345     }
346     if (q == NULL) 
347       myData2[iK2] = (IndexedMapNode *) p->Next2();
348     else 
349       q->Next2() = p->Next2();
350     
351     // remove the key
352     Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
353     q = (IndexedMapNode *) myData1[iK1];
354     if (q == p)
355       myData1[iK1] = (IndexedMapNode *) p->Next();
356     else 
357     {
358       while (q->Next() != p) 
359         q = (IndexedMapNode *) q->Next();
360       q->Next() = p->Next();
361     }
362     p->~IndexedMapNode();
363     this->myAllocator->Free(p);
364     Decrement();
365   }
366
367   //! FindKey
368   const TheKeyType& FindKey (const Standard_Integer theKey2) const
369   {
370 #if !defined No_Exception && !defined No_Standard_OutOfRange
371     if (theKey2 < 1 || theKey2 > Extent())
372       Standard_OutOfRange::Raise ("NCollection_IndexedMap::FindKey");
373 #endif
374     IndexedMapNode * pNode2 =
375       (IndexedMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
376     while (pNode2)
377     {
378       if (pNode2->Key2() == theKey2) 
379         return pNode2->Key1();
380       pNode2 = (IndexedMapNode*) pNode2->Next2();
381     }
382     Standard_NoSuchObject::Raise("NCollection_IndexedMap::FindKey");
383     return pNode2->Key1(); // This for compiler
384   }
385
386   //! operator ()
387   const TheKeyType& operator() (const Standard_Integer theKey2) const
388   { return FindKey (theKey2); }
389
390   //! FindIndex
391   Standard_Integer FindIndex(const TheKeyType& theKey1) const
392   {
393     if (IsEmpty()) return 0;
394     IndexedMapNode * pNode1 = 
395       (IndexedMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
396     while (pNode1)
397     {
398       if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
399         return pNode1->Key2();
400       pNode1 = (IndexedMapNode*) pNode1->Next();
401     }
402     return 0;
403   }
404
405   //! Clear data. If doReleaseMemory is false then the table of
406   //! buckets is not released and will be reused.
407   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
408   { Destroy (IndexedMapNode::delNode, this->myAllocator, doReleaseMemory); }
409
410   //! Clear data and reset allocator
411   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
412   { 
413     Clear();
414     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
415                     NCollection_BaseAllocator::CommonBaseAllocator() );
416   }
417
418   //! Destructor
419   ~NCollection_IndexedMap (void)
420   { Clear(); }
421
422   //! Size
423   virtual Standard_Integer Size(void) const
424   { return Extent(); }
425
426  private:
427   // ----------- PRIVATE METHODS -----------
428
429   //! Creates Iterator for use on BaseCollection
430   virtual TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& 
431     CreateIterator(void) const
432   { return *(new (this->IterAllocator()) Iterator(*this)); }
433
434 };
435
436 #endif