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