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