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