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