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
   8 // under the terms of the GNU Lesser General Public 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_BaseCollection.hxx>
  20 #include <NCollection_BaseMap.hxx>
  21 #include <NCollection_TListNode.hxx>
  22 #include <Standard_TypeMismatch.hxx>
  23 #include <Standard_NoSuchObject.hxx>
  24
  25 #include <NCollection_DefaultHasher.hxx>
  26
  27 #if !defined No_Exception && !defined No_Standard_OutOfRange
  28 #include <Standard_OutOfRange.hxx>
  29 #endif
  30
  31 /**
  32  * Purpose:     An indexed map is used  to store keys and to  bind
  33  *              an index to them.  Each  new key stored in the map
  34  *              gets an index.  Index are  incremented as keys are
  35  *              stored in the map. A key can be found by the index
  36  *              and an index by the key.  No  key but the last can
  37  *              be  removed so the  indices   are in the range 1..
  38  *              Extent.  An Item is stored with each key.
  39  *
  40  *              This   class is   similar  to  IndexedMap     from
  41  *              NCollection  with the Item as  a new feature. Note
  42  *              the important difference on  the operator  ().  In
  43  *              the IndexedMap this operator returns  the Key.  In
  44  *              the IndexedDataMap this operator returns the Item.
  45  *
  46  *              See  the  class   Map   from NCollection   for   a
  47  *              discussion about the number of buckets.
  48  */
  49
  50 template < class TheKeyType,
  51            class TheItemType,
  52            class Hasher = NCollection_DefaultHasher<TheKeyType> >
  53   class NCollection_IndexedDataMap
  54   : public NCollection_BaseCollection<TheItemType>,
  55     public NCollection_BaseMap
  56 {
  57   //!    Adaptation of the TListNode to the INDEXEDDatamap
  58  private:
  59   class IndexedDataMapNode : public NCollection_TListNode<TheItemType>
  60   {
  61   public:
  62     //! Constructor with 'Next'
  63     IndexedDataMapNode (const TheKeyType&      theKey1,
  64                         const Standard_Integer theKey2,
  65                         const TheItemType&     theItem,
  66                         NCollection_ListNode*  theNext1,
  67                         NCollection_ListNode*  theNext2) :
  68                           NCollection_TListNode<TheItemType>(theItem,theNext1)
  69     {
  70       myKey1 = theKey1;
  71       myKey2 = theKey2;
  72       myNext2 = (IndexedDataMapNode *) theNext2;
  73     }
  74     //! Key1
  75     TheKeyType& Key1 (void)
  76     { return myKey1; }
  77     //! Key2
  78     const Standard_Integer& Key2 (void)
  79     { return myKey2; }
  80     //! Next2
  81     IndexedDataMapNode*& Next2 (void)
  82     { return myNext2; }
  83
  84     //! Static deleter to be passed to BaseList
  85     static void delNode (NCollection_ListNode * theNode,
  86                          Handle(NCollection_BaseAllocator)& theAl)
  87     {
  88       ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode();
  89       theAl->Free(theNode);
  90     }
  91   private:
  92     TheKeyType           myKey1;
  93     Standard_Integer     myKey2;
  94     IndexedDataMapNode * myNext2;
  95   };
  96
  97  public:
  98   //!   Implementation of the Iterator interface.
  99   class Iterator : public NCollection_BaseCollection<TheItemType>::Iterator
 100   {
 101   public:
 102     //! Empty constructor
 103     Iterator (void) :
 104       myMap(NULL),
 105       myIndex(0) {}
 106     //! Constructor
 107     Iterator (const NCollection_IndexedDataMap& theMap) :
 108       myMap((NCollection_IndexedDataMap *) &theMap),
 109       myIndex(1) {}
 110     //! Query if the end of collection is reached by iterator
 111     virtual Standard_Boolean More(void) const
 112     { return (myIndex <= myMap->Extent()); }
 113     //! Make a step along the collection
 114     virtual void Next(void)
 115     { myIndex++; }
 116     //! Value access
 117     virtual const TheItemType& Value(void) const
 118     {
 119 #if !defined No_Exception && !defined No_Standard_NoSuchObject
 120       if (!More())
 121         Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::Value");
 122 #endif
 123       return myMap->FindFromIndex(myIndex);
 124     }
 125     //! ChangeValue access
 126     virtual TheItemType& ChangeValue(void) const
 127     {
 128 #if !defined No_Exception && !defined No_Standard_NoSuchObject
 129       if (!More())
 130         Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::ChangeValue");
 131 #endif
 132       return myMap->ChangeFromIndex(myIndex);
 133     }
 134
 135   private:
 136     NCollection_IndexedDataMap * myMap;   //!< Pointer to the map being iterated
 137     Standard_Integer             myIndex; //!< Current index
 138   };
 139
 140  public:
 141   // ---------- PUBLIC METHODS ------------
 142
 143   //! Constructor
 144   NCollection_IndexedDataMap (const Standard_Integer NbBuckets=1,
 145                      const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
 146     :  NCollection_BaseCollection<TheItemType>(theAllocator),
 147        NCollection_BaseMap (NbBuckets, Standard_False) {}
 148
 149   //! Copy constructor
 150   NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther)
 151     : NCollection_BaseCollection<TheItemType>(theOther.myAllocator),
 152       NCollection_BaseMap (theOther.NbBuckets(), Standard_False)
 153   { *this = theOther; }
 154
 155   //! Assign another collection
 156   virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther)
 157   {
 158     if (this == &theOther)
 159       return;
 160     Standard_TypeMismatch::Raise("NCollection_IndexedDataMap::Assign");
 161   }
 162
 163   //! Exchange the content of two maps without re-allocations.
 164   //! Notice that allocators will be swapped as well!
 165   void Exchange (NCollection_IndexedDataMap& theOther)
 166   {
 167     this->exchangeAllocators (theOther);
 168     this->exchangeMapsData   (theOther);
 169   }
 170
 171   //! = another map
 172   NCollection_IndexedDataMap& operator=
 173     (const NCollection_IndexedDataMap& theOther)
 174   {
 175     if (this == &theOther)
 176       return *this;
 177
 178     Clear(theOther.myAllocator);
 179     ReSize (theOther.Extent()-1);
 180     Standard_Integer i;
 181     for (i=1; i<=theOther.Extent(); i++)
 182     {
 183       TheKeyType aKey1 = theOther.FindKey(i);
 184       TheItemType anItem = theOther.FindFromIndex(i);
 185       Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
 186       Standard_Integer iK2 = ::HashCode (i, NbBuckets());
 187       IndexedDataMapNode * pNode =
 188         new (this->myAllocator) IndexedDataMapNode (aKey1, i, anItem,
 189                                               myData1[iK1], myData2[iK2]);
 190       myData1[iK1] = pNode;
 191       myData2[iK2] = pNode;
 192       Increment();
 193     }
 194     return *this;
 195   }
 196
 197   //! ReSize
 198   void ReSize (const Standard_Integer N)
 199   {
 200     NCollection_ListNode** ppNewData1 = NULL;
 201     NCollection_ListNode** ppNewData2 = NULL;
 202     Standard_Integer newBuck;
 203     if (BeginResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator))
 204     {
 205       if (myData1)
 206       {
 207         IndexedDataMapNode *p, *q;
 208         Standard_Integer i, iK1, iK2;
 209         for (i = 0; i <= NbBuckets(); i++)
 210         {
 211           if (myData1[i])
 212           {
 213             p = (IndexedDataMapNode *) myData1[i];
 214             while (p)
 215             {
 216               iK1 = Hasher::HashCode (p->Key1(), newBuck);
 217               iK2 = ::HashCode (p->Key2(), newBuck);
 218               q = (IndexedDataMapNode*) p->Next();
 219               p->Next()  = ppNewData1[iK1];
 220               p->Next2() = (IndexedDataMapNode*)ppNewData2[iK2];
 221               ppNewData1[iK1] = p;
 222               ppNewData2[iK2] = p;
 223               p = q;
 224             }
 225           }
 226         }
 227       }
 228       EndResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator);
 229     }
 230   }
 231
 232   //! Add
 233   Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
 234   {
 235     if (Resizable())
 236       ReSize(Extent());
 237     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
 238     IndexedDataMapNode * pNode;
 239     pNode = (IndexedDataMapNode *) myData1[iK1];
 240     while (pNode)
 241     {
 242       if (Hasher::IsEqual (pNode->Key1(), theKey1))
 243         return pNode->Key2();
 244       pNode = (IndexedDataMapNode *) pNode->Next();
 245     }
 246     Increment();
 247     Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
 248     pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, Extent(), theItem,
 249                                                   myData1[iK1], myData2[iK2]);
 250     myData1[iK1] = pNode;
 251     myData2[iK2] = pNode;
 252     return Extent();
 253   }
 254
 255   //! Contains
 256   Standard_Boolean Contains (const TheKeyType& theKey1) const
 257   {
 258     if (IsEmpty())
 259       return Standard_False;
 260     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
 261     IndexedDataMapNode * pNode1;
 262     pNode1 = (IndexedDataMapNode *) myData1[iK1];
 263     while (pNode1)
 264     {
 265       if (Hasher::IsEqual(pNode1->Key1(), theKey1))
 266         return Standard_True;
 267       pNode1 = (IndexedDataMapNode *) pNode1->Next();
 268     }
 269     return Standard_False;
 270   }
 271
 272   //! Substitute
 273   void Substitute (const Standard_Integer theIndex,
 274                    const TheKeyType&      theKey1,
 275                    const TheItemType&     theItem)
 276   {
 277 #if !defined No_Exception && !defined No_Standard_OutOfRange
 278     if (theIndex < 1 || theIndex > Extent())
 279       Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::Substitute");
 280 #endif
 281     IndexedDataMapNode * p;
 282     // check if theKey1 is not already in the map
 283     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
 284     p = (IndexedDataMapNode *) myData1[iK1];
 285     while (p)
 286     {
 287       if (Hasher::IsEqual (p->Key1(), theKey1))
 288         Standard_DomainError::Raise("NCollection_IndexedDataMap::Substitute");
 289       p = (IndexedDataMapNode *) p->Next();
 290     }
 291
 292     // Find the node for the index I
 293     Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
 294     p = (IndexedDataMapNode *) myData2[iK2];
 295     while (p)
 296     {
 297       if (p->Key2() == theIndex)
 298         break;
 299       p = (IndexedDataMapNode*) p->Next2();
 300     }
 301
 302     // remove the old key
 303     Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
 304     IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
 305     if (q == p)
 306       myData1[iK] = (IndexedDataMapNode *) p->Next();
 307     else
 308     {
 309       while (q->Next() != p)
 310         q = (IndexedDataMapNode *) q->Next();
 311       q->Next() = p->Next();
 312     }
 313
 314     // update the node
 315     p->Key1()  = theKey1;
 316     p->ChangeValue() = theItem;
 317     p->Next()  = myData1[iK1];
 318     myData1[iK1] = p;
 319   }
 320
 321   //! RemoveLast
 322   void RemoveLast (void)
 323   {
 324 #if !defined No_Exception && !defined No_Standard_OutOfRange
 325     if (Extent() == 0)
 326       Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::RemoveLast");
 327 #endif
 328     IndexedDataMapNode * p, * q;
 329     // Find the node for the last index and remove it
 330     Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
 331     p = (IndexedDataMapNode *) myData2[iK2];
 332     q = NULL;
 333     while (p)
 334     {
 335       if (p->Key2() == Extent())
 336         break;
 337       q = p;
 338       p = (IndexedDataMapNode*) p->Next2();
 339     }
 340     if (q == NULL)
 341       myData2[iK2] = (IndexedDataMapNode *) p->Next2();
 342     else
 343       q->Next2() = p->Next2();
 344
 345     // remove the key
 346     Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
 347     q = (IndexedDataMapNode *) myData1[iK1];
 348     if (q == p)
 349       myData1[iK1] = (IndexedDataMapNode *) p->Next();
 350     else
 351     {
 352       while (q->Next() != p)
 353         q = (IndexedDataMapNode *) q->Next();
 354       q->Next() = p->Next();
 355     }
 356     p->~IndexedDataMapNode();
 357     this->myAllocator->Free(p);
 358     Decrement();
 359   }
 360
 361   //! FindKey
 362   const TheKeyType& FindKey (const Standard_Integer theKey2) const
 363   {
 364 #if !defined No_Exception && !defined No_Standard_OutOfRange
 365     if (theKey2 < 1 || theKey2 > Extent())
 366       Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindKey");
 367 #endif
 368     IndexedDataMapNode * pNode2 =
 369       (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
 370     while (pNode2)
 371     {
 372       if (pNode2->Key2() == theKey2)
 373         return pNode2->Key1();
 374       pNode2 = (IndexedDataMapNode*) pNode2->Next2();
 375     }
 376     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindKey");
 377     return pNode2->Key1(); // This for compiler
 378   }
 379
 380   //! FindFromIndex
 381   const TheItemType& FindFromIndex (const Standard_Integer theKey2) const
 382   {
 383 #if !defined No_Exception && !defined No_Standard_OutOfRange
 384     if (theKey2 < 1 || theKey2 > Extent())
 385       Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindFromIndex");
 386 #endif
 387     IndexedDataMapNode * pNode2 =
 388       (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
 389     while (pNode2)
 390     {
 391       if (pNode2->Key2() == theKey2)
 392         return pNode2->Value();
 393       pNode2 = (IndexedDataMapNode*) pNode2->Next2();
 394     }
 395     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromIndex");
 396     return pNode2->Value(); // This for compiler
 397   }
 398
 399   //! operator ()
 400   const TheItemType& operator() (const Standard_Integer theKey2) const
 401   { return FindFromIndex (theKey2); }
 402
 403   //! ChangeFromIndex
 404   TheItemType& ChangeFromIndex (const Standard_Integer theKey2)
 405   {
 406 #if !defined No_Exception && !defined No_Standard_OutOfRange
 407     if (theKey2 < 1 || theKey2 > Extent())
 408       Standard_OutOfRange::Raise("NCollection_IndexedDataMap::ChangeFromIndex");
 409 #endif
 410     IndexedDataMapNode * pNode2 =
 411       (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
 412     while (pNode2)
 413     {
 414       if (pNode2->Key2() == theKey2)
 415         return pNode2->ChangeValue();
 416       pNode2 = (IndexedDataMapNode*) pNode2->Next2();
 417     }
 418     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromIndex");
 419     return pNode2->ChangeValue(); // This for compiler
 420   }
 421
 422   //! operator ()
 423   TheItemType& operator() (const Standard_Integer theKey2)
 424   { return ChangeFromIndex (theKey2); }
 425
 426   //! FindIndex
 427   Standard_Integer FindIndex(const TheKeyType& theKey1) const
 428   {
 429     if (IsEmpty()) return 0;
 430     IndexedDataMapNode * pNode1 =
 431       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
 432     while (pNode1)
 433     {
 434       if (Hasher::IsEqual (pNode1->Key1(), theKey1))
 435         return pNode1->Key2();
 436       pNode1 = (IndexedDataMapNode*) pNode1->Next();
 437     }
 438     return 0;
 439   }
 440
 441   //! FindFromKey
 442   const TheItemType& FindFromKey(const TheKeyType& theKey1) const
 443   {
 444 #if !defined No_Exception && !defined No_Standard_NoSuchObject
 445     if (IsEmpty())
 446       Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindFromKey");
 447 #endif
 448     IndexedDataMapNode * pNode1 =
 449       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
 450     while (pNode1)
 451     {
 452       if (Hasher::IsEqual (pNode1->Key1(), theKey1))
 453         return pNode1->Value();
 454       pNode1 = (IndexedDataMapNode*) pNode1->Next();
 455     }
 456     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromKey");
 457     return pNode1->Value();
 458   }
 459
 460   //! ChangeFromKey
 461   TheItemType& ChangeFromKey (const TheKeyType& theKey1)
 462   {
 463 #if !defined No_Exception && !defined No_Standard_NoSuchObject
 464     if (IsEmpty())
 465       Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
 466 #endif
 467     IndexedDataMapNode * pNode1 =
 468       (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
 469     while (pNode1)
 470     {
 471       if (Hasher::IsEqual (pNode1->Key1(), theKey1))
 472         return pNode1->ChangeValue();
 473       pNode1 = (IndexedDataMapNode*) pNode1->Next();
 474     }
 475     Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
 476     return pNode1->ChangeValue();
 477   }
 478
 479   //! Clear data. If doReleaseMemory is false then the table of
 480   //! buckets is not released and will be reused.
 481   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
 482   { Destroy (IndexedDataMapNode::delNode, this->myAllocator, doReleaseMemory); }
 483
 484   //! Clear data and reset allocator
 485   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
 486   {
 487     Clear();
 488     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
 489                     NCollection_BaseAllocator::CommonBaseAllocator() );
 490   }
 491
 492   //! Destructor
 493   ~NCollection_IndexedDataMap (void)
 494   { Clear(); }
 495
 496   //! Size
 497   virtual Standard_Integer Size(void) const
 498   { return Extent(); }
 499
 500  private:
 501   // ----------- PRIVATE METHODS -----------
 502
 503   //! Creates Iterator for use on BaseCollection
 504   virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator&
 505     CreateIterator(void) const
 506   { return *(new (this->IterAllocator()) Iterator(*this)); }
 507
 508 };
 509
 510 #endif