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     //! Constructor with 'Next'
  60     IndexedMapNode (TheKeyType&&           theKey1,
  61                     const Standard_Integer theIndex,
  62                     NCollection_ListNode*  theNext1)
  63     : NCollection_TListNode<TheKeyType> (std::forward<TheKeyType>(theKey1), theNext1),
  64       myIndex (theIndex)
  65     {}
  66     //! Key1
  67     TheKeyType& Key1() { return this->ChangeValue(); }
  68
  69     //! Index
  70     Standard_Integer& Index() { return myIndex; }
  71
  72     //! Static deleter to be passed to BaseList
  73     static void delNode (NCollection_ListNode * theNode,
  74                          Handle(NCollection_BaseAllocator)& theAl)
  75     {
  76       ((IndexedMapNode *) theNode)->~IndexedMapNode();
  77       theAl->Free(theNode);
  78     }
  79
  80   private:
  81     Standard_Integer myIndex;
  82   };
  83
  84  public:
  85   // **************** Implementation of the Iterator interface.
  86   class Iterator
  87   {
  88   public:
  89     //! Empty constructor
  90     Iterator (void) :
  91       myMap(NULL),
  92       myIndex(0) {}
  93     //! Constructor
  94     Iterator (const NCollection_IndexedMap& theMap) :
  95       myMap((NCollection_IndexedMap *) &theMap),
  96       myIndex(1) {}
  97     //! Query if the end of collection is reached by iterator
  98     Standard_Boolean More(void) const
  99     { return (myMap != NULL) && (myIndex <= myMap->Extent()); }
 100     //! Make a step along the collection
 101     void Next(void)
 102     { myIndex++; }
 103     //! Value access
 104     const TheKeyType& Value(void) const
 105     {
 106       Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedMap::Iterator::Value");
 107       return myMap->FindKey(myIndex);
 108     }
 109
 110     //! Performs comparison of two iterators.
 111     Standard_Boolean IsEqual (const Iterator& theOther) const
 112     {
 113       return myMap == theOther.myMap && myIndex == theOther.myIndex;
 114     }
 115
 116   private:
 117     NCollection_IndexedMap * myMap;   // Pointer to the map being iterated
 118     Standard_Integer         myIndex; // Current index
 119   };
 120
 121   //! Shorthand for a constant iterator type.
 122   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheKeyType, true> const_iterator;
 123
 124   //! Returns a const iterator pointing to the first element in the map.
 125   const_iterator cbegin() const { return Iterator (*this); }
 126
 127   //! Returns a const iterator referring to the past-the-end element in the map.
 128   const_iterator cend() const { return Iterator(); }
 129
 130  public:
 131   // ---------- PUBLIC METHODS ------------
 132
 133   //! Empty constructor.
 134   NCollection_IndexedMap() : NCollection_BaseMap (1, true, Handle(NCollection_BaseAllocator)()) {}
 135
 136   //! Constructor
 137   explicit NCollection_IndexedMap (const Standard_Integer theNbBuckets,
 138                                    const Handle(NCollection_BaseAllocator)& theAllocator=0L)
 139   : NCollection_BaseMap (theNbBuckets, true, theAllocator) {}
 140
 141   //! Copy constructor
 142   NCollection_IndexedMap (const NCollection_IndexedMap& theOther)
 143   : NCollection_BaseMap (theOther.NbBuckets(), true, theOther.myAllocator)
 144   { *this = theOther; }
 145
 146   //! Move constructor
 147   NCollection_IndexedMap(NCollection_IndexedMap&& theOther) noexcept :
 148     NCollection_BaseMap(std::forward<NCollection_BaseMap>(theOther))
 149   {}
 150
 151   //! Exchange the content of two maps without re-allocations.
 152   //! Notice that allocators will be swapped as well!
 153   void Exchange (NCollection_IndexedMap& theOther)
 154   {
 155     this->exchangeMapsData (theOther);
 156   }
 157
 158   //! Assign.
 159   //! This method does not change the internal allocator.
 160   NCollection_IndexedMap& Assign (const NCollection_IndexedMap& theOther)
 161   {
 162     if (this == &theOther)
 163       return *this;
 164
 165     Clear();
 166     Standard_Integer anExt = theOther.Extent();
 167     if (anExt)
 168     {
 169       ReSize (anExt-1); //mySize is same after resize
 170       for (Standard_Integer anIndexIter = 1; anIndexIter <= anExt; ++anIndexIter)
 171       {
 172         const TheKeyType& aKey1 = theOther.FindKey (anIndexIter);
 173         const size_t iK1 = HashCode (aKey1, NbBuckets());
 174         IndexedMapNode* pNode = new (this->myAllocator) IndexedMapNode (aKey1, anIndexIter, myData1[iK1]);
 175         myData1[iK1]             = pNode;
 176         myData2[anIndexIter - 1] = pNode;
 177         Increment();
 178       }
 179     }
 180     return *this;
 181   }
 182
 183   //! Assignment operator
 184   NCollection_IndexedMap& operator= (const NCollection_IndexedMap& theOther)
 185   {
 186     return Assign (theOther);
 187   }
 188
 189   //! Move operator
 190   NCollection_IndexedMap& operator= (NCollection_IndexedMap&& theOther) noexcept
 191   {
 192     if (this == &theOther)
 193       return *this;
 194     exchangeMapsData(theOther);
 195     return *this;
 196   }
 197
 198   //! ReSize
 199   void ReSize (const Standard_Integer theExtent)
 200   {
 201     NCollection_ListNode** ppNewData1 = NULL;
 202     NCollection_ListNode** ppNewData2 = NULL;
 203     Standard_Integer newBuck;
 204     if (BeginResize (theExtent, newBuck, ppNewData1, ppNewData2))
 205     {
 206       if (myData1)
 207       {
 208         for (Standard_Integer aBucketIter = 0; aBucketIter <= NbBuckets(); ++aBucketIter)
 209         {
 210           if (myData1[aBucketIter])
 211           {
 212             IndexedMapNode* p = (IndexedMapNode* )myData1[aBucketIter];
 213             while (p)
 214             {
 215               const size_t iK1 = HashCode (p->Key1(), newBuck);
 216               IndexedMapNode* q = (IndexedMapNode* )p->Next();
 217               p->Next() = ppNewData1[iK1];
 218               ppNewData1[iK1] = p;
 219               p = q;
 220             }
 221           }
 222         }
 223       }
 224       EndResize (theExtent, newBuck, ppNewData1, (NCollection_ListNode**)
 225         Standard::Reallocate(myData2, (newBuck + 1) * sizeof(NCollection_ListNode*)));
 226     }
 227   }
 228
 229   //! Add
 230   Standard_Integer Add (const TheKeyType& theKey1)
 231   {
 232     if (Resizable())
 233     {
 234       ReSize (Extent());
 235     }
 236     IndexedMapNode* aNode;
 237     size_t aHash;
 238     if (lookup(theKey1, aNode, aHash))
 239     {
 240       return aNode->Index();
 241     }
 242     const Standard_Integer aNewIndex = Increment();
 243     aNode = new (this->myAllocator) IndexedMapNode (theKey1, aNewIndex, myData1[aHash]);
 244     myData1[aHash]         = aNode;
 245     myData2[aNewIndex - 1] = aNode;
 246     return aNewIndex;
 247   }
 248
 249   //! Add
 250   Standard_Integer Add (TheKeyType&& theKey1)
 251   {
 252     if (Resizable())
 253     {
 254       ReSize(Extent());
 255     }
 256     size_t aHash;
 257     IndexedMapNode* aNode;
 258     if (lookup(theKey1, aNode, aHash))
 259     {
 260       return aNode->Index();
 261     }
 262     const Standard_Integer aNewIndex = Increment();
 263     aNode = new (this->myAllocator) IndexedMapNode(std::forward<TheKeyType>(theKey1),
 264                                                    aNewIndex, myData1[aHash]);
 265     myData1[aHash] = aNode;
 266     myData2[aNewIndex - 1] = aNode;
 267     return aNewIndex;
 268   }
 269
 270   //! Contains
 271   Standard_Boolean Contains (const TheKeyType& theKey1) const
 272   {
 273     IndexedMapNode* p;
 274     return lookup(theKey1, p);
 275   }
 276
 277   //! Substitute
 278   void Substitute (const Standard_Integer theIndex,
 279                    const TheKeyType& theKey1)
 280   {
 281     Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(),
 282                                   "NCollection_IndexedMap::Substitute : "
 283                                   "Index is out of range");
 284
 285     // check if theKey1 is not already in the map
 286     IndexedMapNode* aNode;
 287     size_t aHash;
 288     if (lookup(theKey1, aNode, aHash))
 289     {
 290       if (aNode->Index() != theIndex)
 291       {
 292         throw Standard_DomainError ("NCollection_IndexedMap::Substitute : "
 293                                     "Attempt to substitute existing key");
 294       }
 295       aNode->Key1() = theKey1;
 296       return;
 297     }
 298     // Find the node for the index I
 299     aNode = (IndexedMapNode* )myData2[theIndex - 1];
 300
 301     // remove the old key
 302     const size_t iK = HashCode (aNode->Key1(), NbBuckets());
 303     IndexedMapNode * q = (IndexedMapNode *) myData1[iK];
 304     if (q == aNode)
 305       myData1[iK] = (IndexedMapNode *) aNode->Next();
 306     else
 307     {
 308       while (q->Next() != aNode)
 309         q = (IndexedMapNode *) q->Next();
 310       q->Next() = aNode->Next();
 311     }
 312
 313     // update the node
 314     aNode->Key1() = theKey1;
 315     aNode->Next() = myData1[aHash];
 316     myData1[aHash] = aNode;
 317   }
 318
 319   //! Swaps two elements with the given indices.
 320   void Swap (const Standard_Integer theIndex1,
 321              const Standard_Integer theIndex2)
 322   {
 323     Standard_OutOfRange_Raise_if (theIndex1 < 1 || theIndex1 > Extent()
 324                                || theIndex2 < 1 || theIndex2 > Extent(), "NCollection_IndexedMap::Swap");
 325
 326     if (theIndex1 == theIndex2)
 327     {
 328       return;
 329     }
 330
 331     IndexedMapNode* aP1 = (IndexedMapNode* )myData2[theIndex1 - 1];
 332     IndexedMapNode* aP2 = (IndexedMapNode* )myData2[theIndex2 - 1];
 333     std::swap (aP1->Index(), aP2->Index());
 334     myData2[theIndex2 - 1] = aP1;
 335     myData2[theIndex1 - 1] = aP2;
 336   }
 337
 338   //! RemoveLast
 339   void RemoveLast (void)
 340   {
 341     const Standard_Integer aLastIndex = Extent();
 342     Standard_OutOfRange_Raise_if (aLastIndex == 0, "NCollection_IndexedMap::RemoveLast");
 343
 344     // Find the node for the last index and remove it
 345     IndexedMapNode* p = (IndexedMapNode* )myData2[aLastIndex - 1];
 346     myData2[aLastIndex - 1] = NULL;
 347
 348     // remove the key
 349     const size_t iK1 = HashCode (p->Key1(), NbBuckets());
 350     IndexedMapNode* q = (IndexedMapNode *) myData1[iK1];
 351     if (q == p)
 352       myData1[iK1] = (IndexedMapNode *) p->Next();
 353     else
 354     {
 355       while (q->Next() != p)
 356         q = (IndexedMapNode *) q->Next();
 357       q->Next() = p->Next();
 358     }
 359     p->~IndexedMapNode();
 360     this->myAllocator->Free(p);
 361     Decrement();
 362   }
 363
 364   //! Remove the key of the given index.
 365   //! Caution! The index of the last key can be changed.
 366   void RemoveFromIndex(const Standard_Integer theIndex)
 367   {
 368     Standard_OutOfRange_Raise_if(theIndex < 1 || theIndex > Extent(), "NCollection_IndexedMap::RemoveFromIndex");
 369     const Standard_Integer aLastInd = Extent();
 370     if (theIndex != aLastInd)
 371     {
 372       Swap(theIndex, aLastInd);
 373     }
 374     RemoveLast();
 375   }
 376
 377   //! Remove the given key.
 378   //! Caution! The index of the last key can be changed.
 379   Standard_Boolean RemoveKey (const TheKeyType& theKey1)
 380   {
 381     Standard_Integer anIndToRemove = FindIndex(theKey1);
 382     if (anIndToRemove < 1)
 383     {
 384       return Standard_False;
 385     }
 386
 387     RemoveFromIndex (anIndToRemove);
 388     return Standard_True;
 389   }
 390
 391   //! FindKey
 392   const TheKeyType& FindKey (const Standard_Integer theIndex) const
 393   {
 394     Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedMap::FindKey");
 395     IndexedMapNode* pNode2 = (IndexedMapNode* )myData2[theIndex - 1];
 396     return pNode2->Key1();
 397   }
 398
 399   //! operator ()
 400   const TheKeyType& operator() (const Standard_Integer theIndex) const
 401   { return FindKey (theIndex); }
 402
 403   //! FindIndex
 404   Standard_Integer FindIndex(const TheKeyType& theKey1) const
 405   {
 406     IndexedMapNode* aNode;
 407     if (lookup(theKey1, aNode))
 408     {
 409       return aNode->Index();
 410     }
 411     return 0;
 412   }
 413
 414   //! Clear data. If doReleaseMemory is false then the table of
 415   //! buckets is not released and will be reused.
 416   void Clear(const Standard_Boolean doReleaseMemory = Standard_False)
 417   { Destroy (IndexedMapNode::delNode, doReleaseMemory); }
 418
 419   //! Clear data and reset allocator
 420   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
 421   {
 422     Clear(theAllocator != this->myAllocator);
 423     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
 424                     NCollection_BaseAllocator::CommonBaseAllocator() );
 425   }
 426
 427   //! Destructor
 428   virtual ~NCollection_IndexedMap (void)
 429   { Clear(true); }
 430
 431   //! Size
 432   Standard_Integer Size(void) const
 433   { return Extent(); }
 434
 435 protected:
 436
 437   //! Lookup for particular key in map.
 438   //! @param[in] theKey key to compute hash
 439   //! @param[out] theNode the detected node with equal key. Can be null.
 440   //! @param[out] theHash computed bounded hash code for current key.
 441   //! @return true if key is found
 442   Standard_Boolean lookup(const TheKeyType& theKey, IndexedMapNode*& theNode, size_t& theHash) const
 443   {
 444     theHash = HashCode(theKey, NbBuckets());
 445     if (IsEmpty())
 446       return Standard_False; // Not found
 447     for (theNode = (IndexedMapNode*)myData1[theHash];
 448          theNode; theNode = (IndexedMapNode*)theNode->Next())
 449     {
 450       if (IsEqual(theNode->Key1(), theKey))
 451         return Standard_True;
 452     }
 453     return Standard_False; // Not found
 454   }
 455
 456   //! Lookup for particular key in map.
 457   //! @param[in] theKey key to compute hash
 458   //! @param[out] theNode the detected node with equal key. Can be null.
 459   //! @return true if key is found
 460   Standard_Boolean lookup(const TheKeyType& theKey, IndexedMapNode*& theNode) const
 461   {
 462     if (IsEmpty())
 463       return Standard_False; // Not found
 464     for (theNode = (IndexedMapNode*)myData1[HashCode(theKey, NbBuckets())];
 465          theNode; theNode = (IndexedMapNode*)theNode->Next())
 466     {
 467       if (IsEqual(theNode->Key1(), theKey))
 468       {
 469         return Standard_True;
 470       }
 471     }
 472     return Standard_False; // Not found
 473   }
 474
 475   bool IsEqual(const TheKeyType& theKey1,
 476                const TheKeyType& theKey2) const
 477   {
 478     return myHasher(theKey1, theKey2);
 479   }
 480
 481   size_t HashCode(const TheKeyType& theKey,
 482                   const int theUpperBound) const
 483   {
 484     return myHasher(theKey) % theUpperBound + 1;
 485   }
 486
 487 protected:
 488
 489   Hasher myHasher;
 490 };
 491
 492 #endif