0025348: Method Assign of NCollection containers must not change own allocator of...
[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   //!    Adaptation of the TListNode to the INDEXEDDatamap
53  private:
54   class IndexedDataMapNode : public NCollection_TListNode<TheItemType>
55   {
56   public:
57     //! Constructor with 'Next'
58     IndexedDataMapNode (const TheKeyType&      theKey1, 
59                         const Standard_Integer theKey2,
60                         const TheItemType&     theItem,
61                         NCollection_ListNode*  theNext1, 
62                         NCollection_ListNode*  theNext2) :
63       NCollection_TListNode<TheItemType>(theItem,theNext1),
64       myKey1(theKey1),
65       myKey2(theKey2),
66       myNext2((IndexedDataMapNode*)theNext2)
67     { 
68     }
69     //! Key1
70     TheKeyType& Key1 (void)
71     { return myKey1; }
72     //! Key2
73     const Standard_Integer& Key2 (void)
74     { return myKey2; }
75     //! Next2
76     IndexedDataMapNode*& Next2 (void)
77     { return myNext2; }
78     
79     //! Static deleter to be passed to BaseList
80     static void delNode (NCollection_ListNode * theNode, 
81                          Handle(NCollection_BaseAllocator)& theAl)
82     {
83       ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode();
84       theAl->Free(theNode);
85     }
86   private:
87     TheKeyType           myKey1;
88     Standard_Integer     myKey2;
89     IndexedDataMapNode * myNext2;
90   };
91
92  public:
93   //!   Implementation of the Iterator interface.
94   class Iterator
95   {
96   public:
97     //! Empty constructor
98     Iterator (void) :
99       myMap(NULL),
100       myIndex(0) {}
101     //! Constructor
102     Iterator (const NCollection_IndexedDataMap& theMap)
103     : myMap  ((NCollection_IndexedDataMap* )&theMap),
104       myNode (myMap->nodeFromIndex (1)),
105       myIndex (1) {}
106     //! Query if the end of collection is reached by iterator
107     Standard_Boolean More(void) const
108     { return (myMap != NULL) && (myIndex <= myMap->Extent()); }
109     //! Make a step along the collection
110     void Next(void)
111     {
112       myNode = myMap->nodeFromIndex (++myIndex);
113     }
114     //! Value access
115     const TheItemType& Value(void) const
116     {  
117       Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Value");
118       return myNode->Value();
119     }
120     //! ChangeValue access
121     TheItemType& ChangeValue(void) const
122     {  
123       Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::ChangeValue");
124       return myNode->ChangeValue();
125     }
126     //! Key
127     const TheKeyType& Key() const
128     {
129       Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Key");
130       return myNode->Key1();
131     }
132     //! Performs comparison of two iterators.
133     Standard_Boolean IsEqual (const Iterator& theOther) const
134     {
135       return myMap == theOther.myMap &&
136              myNode == theOther.myNode &&
137              myIndex == theOther.myIndex;
138     }
139   private:
140     NCollection_IndexedDataMap* myMap;   //!< Pointer to the map being iterated
141     IndexedDataMapNode*         myNode;  //!< Current node
142     Standard_Integer            myIndex; //!< Current index
143   };
144   
145   //! Shorthand for a regular iterator type.
146   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator;
147
148   //! Shorthand for a constant iterator type.
149   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator;
150
151   //! Returns an iterator pointing to the first element in the map.
152   iterator begin() const { return Iterator (*this); }
153
154   //! Returns an iterator referring to the past-the-end element in the map.
155   iterator end() const { return Iterator(); }
156
157   //! Returns a const iterator pointing to the first element in the map.
158   const_iterator cbegin() const { return Iterator (*this); }
159
160   //! Returns a const iterator referring to the past-the-end element in the map.
161   const_iterator cend() const { return Iterator(); }
162   
163  public:
164   // ---------- PUBLIC METHODS ------------
165
166   //! Constructor
167   NCollection_IndexedDataMap (const Standard_Integer NbBuckets=1,
168                      const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
169     :  NCollection_BaseMap (NbBuckets, Standard_False, theAllocator) {}
170
171   //! Copy constructor
172   NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther) 
173     : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator) 
174   { *this = theOther; }
175
176   //! Exchange the content of two maps without re-allocations.
177   //! Notice that allocators will be swapped as well!
178   void Exchange (NCollection_IndexedDataMap& theOther)
179   {
180     this->exchangeMapsData (theOther);
181   }
182
183   //! Assignment.
184   //! This method does not change the internal allocator.
185   NCollection_IndexedDataMap& Assign (const NCollection_IndexedDataMap& theOther)
186   { 
187     if (this == &theOther)
188       return *this;
189
190     Clear();
191     ReSize (theOther.Extent()-1);
192     Standard_Integer i;
193     for (i=1; i<=theOther.Extent(); i++)
194     {
195       TheKeyType aKey1 = theOther.FindKey(i);
196       TheItemType anItem = theOther.FindFromIndex(i);
197       Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
198       Standard_Integer iK2 = ::HashCode (i, NbBuckets());
199       IndexedDataMapNode * pNode = 
200         new (this->myAllocator) IndexedDataMapNode (aKey1, i, anItem,
201                                               myData1[iK1], myData2[iK2]);
202       myData1[iK1] = pNode;
203       myData2[iK2] = pNode;
204       Increment();
205     }
206     return *this;
207   }
208
209   //! Assignment operator
210   NCollection_IndexedDataMap& operator= (const NCollection_IndexedDataMap& theOther)
211   {
212     return Assign (theOther);
213   }
214
215   //! ReSize
216   void ReSize (const Standard_Integer N)
217   {
218     NCollection_ListNode** ppNewData1 = NULL;
219     NCollection_ListNode** ppNewData2 = NULL;
220     Standard_Integer newBuck;
221     if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
222     {
223       if (myData1) 
224       {
225         IndexedDataMapNode *p, *q;
226         Standard_Integer i, iK1, iK2;
227         for (i = 0; i <= NbBuckets(); i++) 
228         {
229           if (myData1[i]) 
230           {
231             p = (IndexedDataMapNode *) myData1[i];
232             while (p) 
233             {
234               iK1 = Hasher::HashCode (p->Key1(), newBuck);
235               iK2 = ::HashCode (p->Key2(), newBuck);
236               q = (IndexedDataMapNode*) p->Next();
237               p->Next()  = ppNewData1[iK1];
238               p->Next2() = (IndexedDataMapNode*)ppNewData2[iK2];
239               ppNewData1[iK1] = p;
240               ppNewData2[iK2] = p;
241               p = q;
242             }
243           }
244         }
245       }
246       EndResize (N, newBuck, ppNewData1, ppNewData2);
247     }
248   }
249
250   //! Add
251   Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
252   {
253     if (Resizable()) 
254       ReSize(Extent());
255     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
256     IndexedDataMapNode * pNode;
257     pNode = (IndexedDataMapNode *) myData1[iK1];
258     while (pNode)
259     {
260       if (Hasher::IsEqual (pNode->Key1(), theKey1))
261         return pNode->Key2();
262       pNode = (IndexedDataMapNode *) pNode->Next();
263     }
264     Increment();
265     Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
266     pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, Extent(), theItem,
267                                                   myData1[iK1], myData2[iK2]);
268     myData1[iK1] = pNode;
269     myData2[iK2] = pNode;
270     return Extent();
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(), "NCollection_IndexedDataMap::Substitute");
296
297     IndexedDataMapNode * p;
298     // check if theKey1 is not already in the map
299     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
300     p = (IndexedDataMapNode *) myData1[iK1];
301     while (p) 
302     {
303       if (Hasher::IsEqual (p->Key1(), theKey1)) 
304         Standard_DomainError::Raise("NCollection_IndexedDataMap::Substitute");
305       p = (IndexedDataMapNode *) p->Next();
306     }
307
308     // Find the node for the index I
309     Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
310     p = (IndexedDataMapNode *) myData2[iK2];
311     while (p) 
312     {
313       if (p->Key2() == theIndex) 
314         break;
315       p = (IndexedDataMapNode*) p->Next2();
316     }
317     
318     // remove the old key
319     Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
320     IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
321     if (q == p)
322       myData1[iK] = (IndexedDataMapNode *) p->Next();
323     else 
324     {
325       while (q->Next() != p) 
326         q = (IndexedDataMapNode *) q->Next();
327       q->Next() = p->Next();
328     }
329
330     // update the node
331     p->Key1()  = theKey1;
332     p->ChangeValue() = theItem;
333     p->Next()  = myData1[iK1];
334     myData1[iK1] = p;
335   }
336
337   //! RemoveLast
338   void RemoveLast (void)
339   {
340     Standard_OutOfRange_Raise_if (Extent() == 0, "NCollection_IndexedDataMap::RemoveLast");
341
342     IndexedDataMapNode * p, * q;
343     // Find the node for the last index and remove it
344     Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
345     p = (IndexedDataMapNode *) myData2[iK2];
346     q = NULL;
347     while (p) 
348     {
349       if (p->Key2() == Extent()) 
350         break;
351       q = p;
352       p = (IndexedDataMapNode*) p->Next2();
353     }
354     if (q == NULL) 
355       myData2[iK2] = (IndexedDataMapNode *) p->Next2();
356     else 
357       q->Next2() = p->Next2();
358     
359     // remove the key
360     Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
361     q = (IndexedDataMapNode *) myData1[iK1];
362     if (q == p)
363       myData1[iK1] = (IndexedDataMapNode *) p->Next();
364     else 
365     {
366       while (q->Next() != p) 
367         q = (IndexedDataMapNode *) q->Next();
368       q->Next() = p->Next();
369     }
370     p->~IndexedDataMapNode();
371     this->myAllocator->Free(p);
372     Decrement();
373   }
374
375   //! FindKey
376   const TheKeyType& FindKey (const Standard_Integer theKey2) const
377   {
378     Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::FindKey");
379
380     IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
381     if (aNode == NULL)
382     {
383       Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindKey");
384     }
385     return aNode->Key1();
386   }
387
388   //! FindFromIndex
389   const TheItemType& FindFromIndex (const Standard_Integer theKey2) const
390   {
391     Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::FindFromIndex");
392
393     IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
394     if (aNode == NULL)
395     {
396       Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindFromIndex");
397     }
398     return aNode->Value();
399   }
400
401   //! operator ()
402   const TheItemType& operator() (const Standard_Integer theKey2) const
403   { return FindFromIndex (theKey2); }
404
405   //! ChangeFromIndex
406   TheItemType& ChangeFromIndex (const Standard_Integer theKey2)
407   {
408     Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::ChangeFromIndex");
409
410     IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
411     if (aNode == NULL)
412     {
413       Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::ChangeFromIndex");
414     }
415     return aNode->ChangeValue();
416   }
417
418   //! operator ()
419   TheItemType& operator() (const Standard_Integer theKey2)
420   { return ChangeFromIndex (theKey2); }
421
422   //! FindIndex
423   Standard_Integer FindIndex(const TheKeyType& theKey1) const
424   {
425     if (IsEmpty()) return 0;
426     IndexedDataMapNode * pNode1 = 
427       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
428     while (pNode1)
429     {
430       if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
431         return pNode1->Key2();
432       pNode1 = (IndexedDataMapNode*) pNode1->Next();
433     }
434     return 0;
435   }
436
437   //! FindFromKey
438   const TheItemType& FindFromKey(const TheKeyType& theKey1) const
439   {
440     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::FindFromKey");
441
442     IndexedDataMapNode * pNode1 = 
443       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
444     while (pNode1)
445     {
446       if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
447         return pNode1->Value();
448       pNode1 = (IndexedDataMapNode*) pNode1->Next();
449     }
450     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromKey");
451     return pNode1->Value();
452   }
453
454   //! ChangeFromKey
455   TheItemType& ChangeFromKey (const TheKeyType& theKey1)
456   {
457     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::ChangeFromKey");
458
459     IndexedDataMapNode * pNode1 = 
460       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
461     while (pNode1)
462     {
463       if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
464         return pNode1->ChangeValue();
465       pNode1 = (IndexedDataMapNode*) pNode1->Next();
466     }
467     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
468     return pNode1->ChangeValue();
469   }
470
471   //! Find value for key with copying.
472   //! @return true if key was found
473   Standard_Boolean FindFromKey (const TheKeyType& theKey1,
474                                 TheItemType&      theValue) const
475   {
476     if (IsEmpty())
477     {
478       return Standard_False;
479     }
480     for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData1[Hasher::HashCode (theKey1, NbBuckets())];
481          aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next())
482     {
483       if (Hasher::IsEqual (aNode->Key1(), theKey1))
484       {
485         theValue = aNode->Value();
486         return Standard_True;
487       }
488     }
489     return Standard_False;
490   }
491
492   //! Clear data. If doReleaseMemory is false then the table of
493   //! buckets is not released and will be reused.
494   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
495   { Destroy (IndexedDataMapNode::delNode, doReleaseMemory); }
496
497   //! Clear data and reset allocator
498   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
499   { 
500     Clear();
501     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
502                     NCollection_BaseAllocator::CommonBaseAllocator() );
503   }
504
505   //! Destructor
506   ~NCollection_IndexedDataMap (void)
507   { Clear(); }
508
509   //! Size
510   Standard_Integer Size(void) const
511   { return Extent(); }
512
513  private:
514   // ----------- PRIVATE METHODS -----------
515
516   //! Find map node associated with specified index.
517   //! Return NULL if not found (exception-free internal implementation).
518   IndexedDataMapNode* nodeFromIndex (const Standard_Integer theKey2) const
519   {
520     if (Extent() == 0)
521     {
522       return NULL;
523     }
524     for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[::HashCode (theKey2, NbBuckets())];
525          aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next2())
526     {
527       if (aNode->Key2() == theKey2)
528       {
529         return aNode;
530       }
531     }
532     return NULL;
533   }
534
535 };
536
537 #endif