src/NCollection/NCollection_IndexedDataMap.hxx

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