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