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   //! This method does not change the internal allocator.
 185   NCollection_IndexedDataMap& Assign (const NCollection_IndexedDataMap& theOther)
 186   {
 187     if (this == &theOther)
 188       return *this;
 189
 190     Clear();
 191     ReSize (theOther.Extent()-1);
 192     Standard_Integer i;
 193     for (i=1; i<=theOther.Extent(); i++)
 194     {
 195       TheKeyType aKey1 = theOther.FindKey(i);
 196       TheItemType anItem = theOther.FindFromIndex(i);
 197       Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
 198       Standard_Integer iK2 = ::HashCode (i, NbBuckets());
 199       IndexedDataMapNode * pNode =
 200         new (this->myAllocator) IndexedDataMapNode (aKey1, i, anItem,
 201                                               myData1[iK1], myData2[iK2]);
 202       myData1[iK1] = pNode;
 203       myData2[iK2] = pNode;
 204       Increment();
 205     }
 206     return *this;
 207   }
 208
 209   //! Assignment operator
 210   NCollection_IndexedDataMap& operator= (const NCollection_IndexedDataMap& theOther)
 211   {
 212     return Assign (theOther);
 213   }
 214
 215   //! ReSize
 216   void ReSize (const Standard_Integer N)
 217   {
 218     NCollection_ListNode** ppNewData1 = NULL;
 219     NCollection_ListNode** ppNewData2 = NULL;
 220     Standard_Integer newBuck;
 221     if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
 222     {
 223       if (myData1)
 224       {
 225         IndexedDataMapNode *p, *q;
 226         Standard_Integer i, iK1, iK2;
 227         for (i = 0; i <= NbBuckets(); i++)
 228         {
 229           if (myData1[i])
 230           {
 231             p = (IndexedDataMapNode *) myData1[i];
 232             while (p)
 233             {
 234               iK1 = Hasher::HashCode (p->Key1(), newBuck);
 235               iK2 = ::HashCode (p->Key2(), newBuck);
 236               q = (IndexedDataMapNode*) p->Next();
 237               p->Next()  = ppNewData1[iK1];
 238               p->Next2() = (IndexedDataMapNode*)ppNewData2[iK2];
 239               ppNewData1[iK1] = p;
 240               ppNewData2[iK2] = p;
 241               p = q;
 242             }
 243           }
 244         }
 245       }
 246       EndResize (N, newBuck, ppNewData1, ppNewData2);
 247     }
 248   }
 249
 250   //! Add
 251   Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
 252   {
 253     if (Resizable())
 254       ReSize(Extent());
 255     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
 256     IndexedDataMapNode * pNode;
 257     pNode = (IndexedDataMapNode *) myData1[iK1];
 258     while (pNode)
 259     {
 260       if (Hasher::IsEqual (pNode->Key1(), theKey1))
 261         return pNode->Key2();
 262       pNode = (IndexedDataMapNode *) pNode->Next();
 263     }
 264     Increment();
 265     Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
 266     pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, Extent(), theItem,
 267                                                   myData1[iK1], myData2[iK2]);
 268     myData1[iK1] = pNode;
 269     myData2[iK2] = pNode;
 270     return Extent();
 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     IndexedDataMapNode * p;
 300     // check if theKey1 is not already in the map
 301     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
 302     p = (IndexedDataMapNode *) myData1[iK1];
 303     while (p)
 304     {
 305       if (Hasher::IsEqual (p->Key1(), theKey1))
 306       {
 307         if (p->Key2() != theIndex)
 308         {
 309           Standard_DomainError::Raise ("NCollection_IndexedDataMap::Substitute : "
 310                                        "Attempt to substitute existing key");
 311         }
 312         p->Key1() = theKey1;
 313         p->ChangeValue() = theItem;
 314         return;
 315       }
 316       p = (IndexedDataMapNode *) p->Next();
 317     }
 318
 319     // Find the node for the index I
 320     Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
 321     p = (IndexedDataMapNode *) myData2[iK2];
 322     while (p)
 323     {
 324       if (p->Key2() == theIndex)
 325         break;
 326       p = (IndexedDataMapNode*) p->Next2();
 327     }
 328
 329     // remove the old key
 330     Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
 331     IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
 332     if (q == p)
 333       myData1[iK] = (IndexedDataMapNode *) p->Next();
 334     else
 335     {
 336       while (q->Next() != p)
 337         q = (IndexedDataMapNode *) q->Next();
 338       q->Next() = p->Next();
 339     }
 340
 341     // update the node
 342     p->Key1()  = theKey1;
 343     p->ChangeValue() = theItem;
 344     p->Next()  = myData1[iK1];
 345     myData1[iK1] = p;
 346   }
 347
 348   //! RemoveLast
 349   void RemoveLast (void)
 350   {
 351     Standard_OutOfRange_Raise_if (Extent() == 0, "NCollection_IndexedDataMap::RemoveLast");
 352
 353     IndexedDataMapNode * p, * q;
 354     // Find the node for the last index and remove it
 355     Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
 356     p = (IndexedDataMapNode *) myData2[iK2];
 357     q = NULL;
 358     while (p)
 359     {
 360       if (p->Key2() == Extent())
 361         break;
 362       q = p;
 363       p = (IndexedDataMapNode*) p->Next2();
 364     }
 365     if (q == NULL)
 366       myData2[iK2] = (IndexedDataMapNode *) p->Next2();
 367     else
 368       q->Next2() = p->Next2();
 369
 370     // remove the key
 371     Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
 372     q = (IndexedDataMapNode *) myData1[iK1];
 373     if (q == p)
 374       myData1[iK1] = (IndexedDataMapNode *) p->Next();
 375     else
 376     {
 377       while (q->Next() != p)
 378         q = (IndexedDataMapNode *) q->Next();
 379       q->Next() = p->Next();
 380     }
 381     p->~IndexedDataMapNode();
 382     this->myAllocator->Free(p);
 383     Decrement();
 384   }
 385
 386   //! FindKey
 387   const TheKeyType& FindKey (const Standard_Integer theKey2) const
 388   {
 389     Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::FindKey");
 390
 391     IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
 392     if (aNode == NULL)
 393     {
 394       Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindKey");
 395     }
 396     return aNode->Key1();
 397   }
 398
 399   //! FindFromIndex
 400   const TheItemType& FindFromIndex (const Standard_Integer theKey2) const
 401   {
 402     Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::FindFromIndex");
 403
 404     IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
 405     if (aNode == NULL)
 406     {
 407       Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindFromIndex");
 408     }
 409     return aNode->Value();
 410   }
 411
 412   //! operator ()
 413   const TheItemType& operator() (const Standard_Integer theKey2) const
 414   { return FindFromIndex (theKey2); }
 415
 416   //! ChangeFromIndex
 417   TheItemType& ChangeFromIndex (const Standard_Integer theKey2)
 418   {
 419     Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::ChangeFromIndex");
 420
 421     IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
 422     if (aNode == NULL)
 423     {
 424       Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::ChangeFromIndex");
 425     }
 426     return aNode->ChangeValue();
 427   }
 428
 429   //! operator ()
 430   TheItemType& operator() (const Standard_Integer theKey2)
 431   { return ChangeFromIndex (theKey2); }
 432
 433   //! FindIndex
 434   Standard_Integer FindIndex(const TheKeyType& theKey1) const
 435   {
 436     if (IsEmpty()) return 0;
 437     IndexedDataMapNode * pNode1 =
 438       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
 439     while (pNode1)
 440     {
 441       if (Hasher::IsEqual (pNode1->Key1(), theKey1))
 442         return pNode1->Key2();
 443       pNode1 = (IndexedDataMapNode*) pNode1->Next();
 444     }
 445     return 0;
 446   }
 447
 448   //! FindFromKey
 449   const TheItemType& FindFromKey(const TheKeyType& theKey1) const
 450   {
 451     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::FindFromKey");
 452
 453     IndexedDataMapNode * pNode1 =
 454       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
 455     while (pNode1)
 456     {
 457       if (Hasher::IsEqual (pNode1->Key1(), theKey1))
 458         return pNode1->Value();
 459       pNode1 = (IndexedDataMapNode*) pNode1->Next();
 460     }
 461     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromKey");
 462     return pNode1->Value();
 463   }
 464
 465   //! ChangeFromKey
 466   TheItemType& ChangeFromKey (const TheKeyType& theKey1)
 467   {
 468     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::ChangeFromKey");
 469
 470     IndexedDataMapNode * pNode1 =
 471       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
 472     while (pNode1)
 473     {
 474       if (Hasher::IsEqual (pNode1->Key1(), theKey1))
 475         return pNode1->ChangeValue();
 476       pNode1 = (IndexedDataMapNode*) pNode1->Next();
 477     }
 478     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
 479     return pNode1->ChangeValue();
 480   }
 481
 482   //! Find value for key with copying.
 483   //! @return true if key was found
 484   Standard_Boolean FindFromKey (const TheKeyType& theKey1,
 485                                 TheItemType&      theValue) const
 486   {
 487     if (IsEmpty())
 488     {
 489       return Standard_False;
 490     }
 491     for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData1[Hasher::HashCode (theKey1, NbBuckets())];
 492          aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next())
 493     {
 494       if (Hasher::IsEqual (aNode->Key1(), theKey1))
 495       {
 496         theValue = aNode->Value();
 497         return Standard_True;
 498       }
 499     }
 500     return Standard_False;
 501   }
 502
 503   //! Clear data. If doReleaseMemory is false then the table of
 504   //! buckets is not released and will be reused.
 505   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
 506   { Destroy (IndexedDataMapNode::delNode, doReleaseMemory); }
 507
 508   //! Clear data and reset allocator
 509   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
 510   {
 511     Clear();
 512     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
 513                     NCollection_BaseAllocator::CommonBaseAllocator() );
 514   }
 515
 516   //! Destructor
 517   ~NCollection_IndexedDataMap (void)
 518   { Clear(); }
 519
 520   //! Size
 521   Standard_Integer Size(void) const
 522   { return Extent(); }
 523
 524  private:
 525   // ----------- PRIVATE METHODS -----------
 526
 527   //! Find map node associated with specified index.
 528   //! Return NULL if not found (exception-free internal implementation).
 529   IndexedDataMapNode* nodeFromIndex (const Standard_Integer theKey2) const
 530   {
 531     if (Extent() == 0)
 532     {
 533       return NULL;
 534     }
 535     for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[::HashCode (theKey2, NbBuckets())];
 536          aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next2())
 537     {
 538       if (aNode->Key2() == theKey2)
 539       {
 540         return aNode;
 541       }
 542     }
 543     return NULL;
 544   }
 545
 546 };
 547
 548 #endif