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 protected:
  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     Standard_Integer anExt = theOther.Extent();
 156     if (anExt)
 157     {
 158       ReSize (anExt-1); //mySize is same after resize
 159       for (Standard_Integer anIndexIter = 1; anIndexIter <= anExt; ++anIndexIter)
 160       {
 161         const TheKeyType& aKey1 = theOther.FindKey (anIndexIter);
 162         const Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
 163         IndexedMapNode* pNode = new (this->myAllocator) IndexedMapNode (aKey1, anIndexIter, myData1[iK1]);
 164         myData1[iK1]             = pNode;
 165         myData2[anIndexIter - 1] = pNode;
 166         Increment();
 167       }
 168     }
 169     return *this;
 170   }
 171
 172   //! Assignment operator
 173   NCollection_IndexedMap& operator= (const NCollection_IndexedMap& theOther)
 174   {
 175     return Assign (theOther);
 176   }
 177
 178   //! ReSize
 179   void ReSize (const Standard_Integer theExtent)
 180   {
 181     NCollection_ListNode** ppNewData1 = NULL;
 182     NCollection_ListNode** ppNewData2 = NULL;
 183     Standard_Integer newBuck;
 184     if (BeginResize (theExtent, newBuck, ppNewData1, ppNewData2))
 185     {
 186       if (myData1)
 187       {
 188         memcpy (ppNewData2, myData2, sizeof(IndexedMapNode*) * Extent());
 189         for (Standard_Integer aBucketIter = 0; aBucketIter <= NbBuckets(); ++aBucketIter)
 190         {
 191           if (myData1[aBucketIter])
 192           {
 193             IndexedMapNode* p = (IndexedMapNode* )myData1[aBucketIter];
 194             while (p)
 195             {
 196               const Standard_Integer iK1 = Hasher::HashCode (p->Key1(), newBuck);
 197               IndexedMapNode* q = (IndexedMapNode* )p->Next();
 198               p->Next() = ppNewData1[iK1];
 199               ppNewData1[iK1] = p;
 200               p = q;
 201             }
 202           }
 203         }
 204       }
 205       EndResize (theExtent, newBuck, ppNewData1, ppNewData2);
 206     }
 207   }
 208
 209   //! Add
 210   Standard_Integer Add (const TheKeyType& theKey1)
 211   {
 212     if (Resizable())
 213     {
 214       ReSize (Extent());
 215     }
 216
 217     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
 218     IndexedMapNode* pNode = (IndexedMapNode* )myData1[iK1];
 219     while (pNode)
 220     {
 221       if (Hasher::IsEqual (pNode->Key1(), theKey1))
 222       {
 223         return pNode->Index();
 224       }
 225       pNode = (IndexedMapNode *) pNode->Next();
 226     }
 227
 228     const Standard_Integer aNewIndex = Increment();
 229     pNode = new (this->myAllocator) IndexedMapNode (theKey1, aNewIndex, myData1[iK1]);
 230     myData1[iK1]           = pNode;
 231     myData2[aNewIndex - 1] = pNode;
 232     return aNewIndex;
 233   }
 234
 235   //! Contains
 236   Standard_Boolean Contains (const TheKeyType& theKey1) const
 237   {
 238     if (IsEmpty())
 239       return Standard_False;
 240     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
 241     IndexedMapNode * pNode1;
 242     pNode1 = (IndexedMapNode *) myData1[iK1];
 243     while (pNode1)
 244     {
 245       if (Hasher::IsEqual(pNode1->Key1(), theKey1))
 246         return Standard_True;
 247       pNode1 = (IndexedMapNode *) pNode1->Next();
 248     }
 249     return Standard_False;
 250   }
 251
 252   //! Substitute
 253   void Substitute (const Standard_Integer theIndex,
 254                    const TheKeyType& theKey1)
 255   {
 256     Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(),
 257                                   "NCollection_IndexedMap::Substitute : "
 258                                   "Index is out of range");
 259
 260     // check if theKey1 is not already in the map
 261     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
 262     IndexedMapNode* p = (IndexedMapNode *) myData1[iK1];
 263     while (p)
 264     {
 265       if (Hasher::IsEqual (p->Key1(), theKey1))
 266       {
 267         if (p->Index() != theIndex)
 268         {
 269           throw Standard_DomainError ("NCollection_IndexedMap::Substitute : "
 270                                       "Attempt to substitute existing key");
 271         }
 272         p->Key1() = theKey1;
 273         return;
 274       }
 275       p = (IndexedMapNode *) p->Next();
 276     }
 277
 278     // Find the node for the index I
 279     p = (IndexedMapNode* )myData2[theIndex - 1];
 280
 281     // remove the old key
 282     Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
 283     IndexedMapNode * q = (IndexedMapNode *) myData1[iK];
 284     if (q == p)
 285       myData1[iK] = (IndexedMapNode *) p->Next();
 286     else
 287     {
 288       while (q->Next() != p)
 289         q = (IndexedMapNode *) q->Next();
 290       q->Next() = p->Next();
 291     }
 292
 293     // update the node
 294     p->Key1() = theKey1;
 295     p->Next() = myData1[iK1];
 296     myData1[iK1] = p;
 297   }
 298
 299   //! Swaps two elements with the given indices.
 300   void Swap (const Standard_Integer theIndex1,
 301              const Standard_Integer theIndex2)
 302   {
 303     Standard_OutOfRange_Raise_if (theIndex1 < 1 || theIndex1 > Extent()
 304                                || theIndex2 < 1 || theIndex2 > Extent(), "NCollection_IndexedMap::Swap");
 305
 306     if (theIndex1 == theIndex2)
 307     {
 308       return;
 309     }
 310
 311     IndexedMapNode* aP1 = (IndexedMapNode* )myData2[theIndex1 - 1];
 312     IndexedMapNode* aP2 = (IndexedMapNode* )myData2[theIndex2 - 1];
 313     std::swap (aP1->Index(), aP2->Index());
 314     myData2[theIndex2 - 1] = aP1;
 315     myData2[theIndex1 - 1] = aP2;
 316   }
 317
 318   //! RemoveLast
 319   void RemoveLast (void)
 320   {
 321     const Standard_Integer aLastIndex = Extent();
 322     Standard_OutOfRange_Raise_if (aLastIndex == 0, "NCollection_IndexedMap::RemoveLast");
 323
 324     // Find the node for the last index and remove it
 325     IndexedMapNode* p = (IndexedMapNode* )myData2[aLastIndex - 1];
 326     myData2[aLastIndex - 1] = NULL;
 327
 328     // remove the key
 329     Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
 330     IndexedMapNode* q = (IndexedMapNode *) myData1[iK1];
 331     if (q == p)
 332       myData1[iK1] = (IndexedMapNode *) p->Next();
 333     else
 334     {
 335       while (q->Next() != p)
 336         q = (IndexedMapNode *) q->Next();
 337       q->Next() = p->Next();
 338     }
 339     p->~IndexedMapNode();
 340     this->myAllocator->Free(p);
 341     Decrement();
 342   }
 343
 344   //! Remove the key of the given index.
 345   //! Caution! The index of the last key can be changed.
 346   void RemoveFromIndex(const Standard_Integer theIndex)
 347   {
 348     Standard_OutOfRange_Raise_if(theIndex < 1 || theIndex > Extent(), "NCollection_IndexedMap::RemoveFromIndex");
 349     const Standard_Integer aLastInd = Extent();
 350     if (theIndex != aLastInd)
 351     {
 352       Swap(theIndex, aLastInd);
 353     }
 354     RemoveLast();
 355   }
 356
 357   //! Remove the given key.
 358   //! Caution! The index of the last key can be changed.
 359   Standard_Boolean RemoveKey (const TheKeyType& theKey1)
 360   {
 361     Standard_Integer anIndToRemove = FindIndex(theKey1);
 362     if (anIndToRemove < 1)
 363     {
 364       return Standard_False;
 365     }
 366
 367     RemoveFromIndex (anIndToRemove);
 368     return Standard_True;
 369   }
 370
 371   //! FindKey
 372   const TheKeyType& FindKey (const Standard_Integer theIndex) const
 373   {
 374     Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedMap::FindKey");
 375     IndexedMapNode* pNode2 = (IndexedMapNode* )myData2[theIndex - 1];
 376     return pNode2->Key1();
 377   }
 378
 379   //! operator ()
 380   const TheKeyType& operator() (const Standard_Integer theIndex) const
 381   { return FindKey (theIndex); }
 382
 383   //! FindIndex
 384   Standard_Integer FindIndex(const TheKeyType& theKey1) const
 385   {
 386     if (IsEmpty()) return 0;
 387     IndexedMapNode* pNode1 = (IndexedMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())];
 388     while (pNode1)
 389     {
 390       if (Hasher::IsEqual (pNode1->Key1(), theKey1))
 391       {
 392         return pNode1->Index();
 393       }
 394       pNode1 = (IndexedMapNode*) pNode1->Next();
 395     }
 396     return 0;
 397   }
 398
 399   //! Clear data. If doReleaseMemory is false then the table of
 400   //! buckets is not released and will be reused.
 401   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
 402   { Destroy (IndexedMapNode::delNode, doReleaseMemory); }
 403
 404   //! Clear data and reset allocator
 405   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
 406   {
 407     Clear();
 408     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
 409                     NCollection_BaseAllocator::CommonBaseAllocator() );
 410   }
 411
 412   //! Destructor
 413   virtual ~NCollection_IndexedMap (void)
 414   { Clear(); }
 415
 416   //! Size
 417   Standard_Integer Size(void) const
 418   { return Extent(); }
 419 };
 420
 421 #endif