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