src/NCollection/NCollection_DoubleMap.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_DoubleMap_HeaderFile
  17 #define NCollection_DoubleMap_HeaderFile
  18
  19 #include <NCollection_TypeDef.hxx>
  20 #include <NCollection_BaseMap.hxx>
  21 #include <NCollection_TListNode.hxx>
  22 #include <Standard_TypeMismatch.hxx>
  23 #include <Standard_MultiplyDefined.hxx>
  24 #include <Standard_ImmutableObject.hxx>
  25 #include <Standard_NoSuchObject.hxx>
  26
  27 #include <NCollection_DefaultHasher.hxx>
  28
  29 /**
  30 * Purpose:     The DoubleMap  is used to  bind  pairs (Key1,Key2)
  31 *              and retrieve them in linear time.
  32 *
  33 *              See Map from NCollection for a discussion about the number
  34 *              of buckets
  35 */
  36
  37 template < class TheKey1Type,
  38            class TheKey2Type,
  39            class Hasher1 = NCollection_DefaultHasher<TheKey1Type>,
  40            class Hasher2 = NCollection_DefaultHasher<TheKey2Type> >
  41 class NCollection_DoubleMap : public NCollection_BaseMap
  42 {
  43 public:
  44   //! STL-compliant typedef for key1 type
  45   typedef TheKey1Type key1_type;
  46   //! STL-compliant typedef for key2 type
  47   typedef TheKey2Type key2_type;
  48
  49 public:
  50   // **************** Adaptation of the TListNode to the DOUBLEmap
  51   class DoubleMapNode : public NCollection_TListNode<TheKey2Type>
  52   {
  53   public:
  54     //! Constructor with 'Next'
  55     DoubleMapNode (const TheKey1Type&    theKey1,
  56                    const TheKey2Type&    theKey2,
  57                    NCollection_ListNode* theNext1,
  58                    NCollection_ListNode* theNext2) :
  59       NCollection_TListNode<TheKey2Type> (theKey2, theNext1),
  60       myKey1(theKey1),
  61       myNext2((DoubleMapNode*)theNext2)
  62     {
  63     }
  64     //! Key1
  65     const TheKey1Type& Key1 (void)
  66     { return myKey1; }
  67     //! Key2
  68     const TheKey2Type& Key2 (void)
  69     { return this->myValue; }
  70     //! Next2
  71     DoubleMapNode*& Next2 (void)
  72     { return myNext2; }
  73
  74     //! Static deleter to be passed to BaseList
  75     static void delNode (NCollection_ListNode * theNode,
  76                          Handle(NCollection_BaseAllocator)& theAl)
  77     {
  78       ((DoubleMapNode *) theNode)->~DoubleMapNode();
  79       theAl->Free(theNode);
  80     }
  81
  82   private:
  83     TheKey1Type    myKey1;
  84     DoubleMapNode *myNext2;
  85   };
  86
  87  public:
  88   // **************** Implementation of the Iterator interface.
  89   class Iterator : public NCollection_BaseMap::Iterator
  90   {
  91   public:
  92     //! Empty constructor
  93     Iterator (void) {}
  94     //! Constructor
  95     Iterator (const NCollection_DoubleMap& theMap) :
  96       NCollection_BaseMap::Iterator(theMap) {}
  97     //! Query if the end of collection is reached by iterator
  98     Standard_Boolean More(void) const
  99     { return PMore(); }
 100     //! Make a step along the collection
 101     void Next(void)
 102     { PNext(); }
 103     //! Key1 inquiry
 104     const TheKey1Type& Key1(void) const
 105     {
 106       Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key1");
 107       return ((DoubleMapNode *) myNode)->Key1();
 108     }
 109     //! Key2 inquiry
 110     const TheKey2Type& Key2(void) const
 111     {
 112       Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key2");
 113       return ((DoubleMapNode *) myNode)->Key2();
 114     }
 115     //! Value access
 116     const TheKey2Type& Value(void) const
 117     {
 118       Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Value");
 119       return ((DoubleMapNode *) myNode)->Value();
 120     }
 121   };
 122
 123  public:
 124   // ---------- PUBLIC METHODS ------------
 125
 126   //! Empty constructor.
 127   NCollection_DoubleMap() : NCollection_BaseMap (1, Standard_False, Handle(NCollection_BaseAllocator)()) {}
 128
 129   //! Constructor
 130   explicit NCollection_DoubleMap (const Standard_Integer theNbBuckets,
 131                                   const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
 132   : NCollection_BaseMap (theNbBuckets, Standard_False, theAllocator) {}
 133
 134   //! Copy constructor
 135   NCollection_DoubleMap (const NCollection_DoubleMap& theOther)
 136     : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator)
 137   { *this = theOther; }
 138
 139   //! Exchange the content of two maps without re-allocations.
 140   //! Notice that allocators will be swapped as well!
 141   void Exchange (NCollection_DoubleMap& theOther)
 142   {
 143     this->exchangeMapsData (theOther);
 144   }
 145
 146   //! Assignment.
 147   //! This method does not change the internal allocator.
 148   NCollection_DoubleMap& Assign (const NCollection_DoubleMap& theOther)
 149   {
 150     if (this == &theOther)
 151       return *this;
 152
 153     Clear();
 154     Standard_Integer anExt = theOther.Extent();
 155     if (anExt)
 156     {
 157       ReSize (anExt-1);
 158       Iterator anIter(theOther);
 159       for (; anIter.More(); anIter.Next())
 160       {
 161         TheKey1Type aKey1 = anIter.Key1();
 162         TheKey2Type aKey2 = anIter.Key2();
 163         Standard_Integer iK1 = Hasher1::HashCode (aKey1, NbBuckets());
 164         Standard_Integer iK2 = Hasher2::HashCode (aKey2, NbBuckets());
 165         DoubleMapNode * pNode = new (this->myAllocator) DoubleMapNode (aKey1, aKey2,
 166           myData1[iK1],
 167           myData2[iK2]);
 168         myData1[iK1] = pNode;
 169         myData2[iK2] = pNode;
 170         Increment();
 171       }
 172     }
 173     return *this;
 174   }
 175
 176   //! Assignment operator
 177   NCollection_DoubleMap& operator= (const NCollection_DoubleMap& theOther)
 178   {
 179     return Assign (theOther);
 180   }
 181
 182   //! ReSize
 183   void ReSize (const Standard_Integer N)
 184   {
 185     NCollection_ListNode** ppNewData1 = NULL;
 186     NCollection_ListNode** ppNewData2 = NULL;
 187     Standard_Integer newBuck;
 188     if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
 189     {
 190       if (myData1)
 191       {
 192         DoubleMapNode *p, *q;
 193         Standard_Integer i, iK1, iK2;
 194         for (i = 0; i <= NbBuckets(); i++)
 195         {
 196           if (myData1[i])
 197           {
 198             p = (DoubleMapNode *) myData1[i];
 199             while (p)
 200             {
 201               iK1 = Hasher1::HashCode (p->Key1(), newBuck);
 202               iK2 = Hasher2::HashCode (p->Key2(), newBuck);
 203               q = (DoubleMapNode*) p->Next();
 204               p->Next()  = ppNewData1[iK1];
 205               p->Next2() = (DoubleMapNode*)ppNewData2[iK2];
 206               ppNewData1[iK1] = p;
 207               ppNewData2[iK2] = p;
 208               p = q;
 209             }
 210           }
 211         }
 212       }
 213       EndResize (N, newBuck, ppNewData1, ppNewData2);
 214     }
 215   }
 216
 217   //! Bind
 218   void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2)
 219   {
 220     if (Resizable())
 221       ReSize(Extent());
 222     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
 223     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
 224     DoubleMapNode * pNode;
 225     pNode = (DoubleMapNode *) myData1[iK1];
 226     while (pNode)
 227     {
 228       if (Hasher1::IsEqual (pNode->Key1(), theKey1))
 229         throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind");
 230       pNode = (DoubleMapNode *) pNode->Next();
 231     }
 232     pNode = (DoubleMapNode *) myData2[iK2];
 233     while (pNode)
 234     {
 235       if (Hasher2::IsEqual (pNode->Key2(), theKey2))
 236         throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind");
 237       pNode = (DoubleMapNode *) pNode->Next();
 238     }
 239     pNode = new (this->myAllocator) DoubleMapNode (theKey1, theKey2,
 240                                                    myData1[iK1], myData2[iK2]);
 241     myData1[iK1] = pNode;
 242     myData2[iK2] = pNode;
 243     Increment();
 244   }
 245
 246   //!* AreBound
 247   Standard_Boolean AreBound (const TheKey1Type& theKey1,
 248                              const TheKey2Type& theKey2) const
 249   {
 250     if (IsEmpty())
 251       return Standard_False;
 252     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
 253     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
 254     DoubleMapNode * pNode1, * pNode2;
 255     pNode1 = (DoubleMapNode *) myData1[iK1];
 256     while (pNode1)
 257     {
 258       if (Hasher1::IsEqual(pNode1->Key1(), theKey1))
 259         break;
 260       pNode1 = (DoubleMapNode *) pNode1->Next();
 261     }
 262     if (pNode1 == NULL)
 263       return Standard_False;
 264     pNode2 = (DoubleMapNode *) myData2[iK2];
 265     while (pNode2)
 266     {
 267       if (Hasher2::IsEqual(pNode2->Key2(), theKey2))
 268         break;
 269       pNode2 = (DoubleMapNode *) pNode2->Next();
 270     }
 271     if (pNode2 == NULL)
 272       return Standard_False;
 273
 274     return (pNode1 == pNode2);
 275   }
 276
 277   //! IsBound1
 278   Standard_Boolean IsBound1 (const TheKey1Type& theKey1) const
 279   {
 280     if (IsEmpty())
 281       return Standard_False;
 282     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
 283     DoubleMapNode * pNode1;
 284     pNode1 = (DoubleMapNode *) myData1[iK1];
 285     while (pNode1)
 286     {
 287       if (Hasher1::IsEqual(pNode1->Key1(), theKey1))
 288         return Standard_True;
 289       pNode1 = (DoubleMapNode *) pNode1->Next();
 290     }
 291     return Standard_False;
 292   }
 293
 294   //! IsBound2
 295   Standard_Boolean IsBound2 (const TheKey2Type& theKey2) const
 296   {
 297     if (IsEmpty())
 298       return Standard_False;
 299     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
 300     DoubleMapNode * pNode2;
 301     pNode2 = (DoubleMapNode *) myData2[iK2];
 302     while (pNode2)
 303     {
 304       if (Hasher2::IsEqual(pNode2->Key2(), theKey2))
 305         return Standard_True;
 306       pNode2 = (DoubleMapNode *) pNode2->Next2();
 307     }
 308     return Standard_False;
 309   }
 310
 311   //! UnBind1
 312   Standard_Boolean UnBind1 (const TheKey1Type& theKey1)
 313   {
 314     if (IsEmpty())
 315       return Standard_False;
 316     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
 317     DoubleMapNode * p1, * p2, * q1, *q2;
 318     q1 = q2 = NULL;
 319     p1 = (DoubleMapNode *) myData1[iK1];
 320     while (p1)
 321     {
 322       if (Hasher1::IsEqual (p1->Key1(), theKey1))
 323       {
 324         // remove from the data1
 325         if (q1)
 326           q1->Next() = p1->Next();
 327         else
 328           myData1[iK1] = (DoubleMapNode*) p1->Next();
 329         Standard_Integer iK2 = Hasher2::HashCode (p1->Key2(), NbBuckets());
 330         p2 = (DoubleMapNode *) myData2[iK2];
 331         while (p2)
 332         {
 333           if (p2 == p1)
 334           {
 335             // remove from the data2
 336             if (q2)
 337               q2->Next2() = p2->Next2();
 338             else
 339               myData2[iK2] = (DoubleMapNode*) p2->Next2();
 340             break;
 341           }
 342           q2 = p2;
 343           p2 = (DoubleMapNode*) p2->Next2();
 344         }
 345         p1->~DoubleMapNode();
 346         this->myAllocator->Free(p1);
 347         Decrement();
 348         return Standard_True;
 349       }
 350       q1 = p1;
 351       p1 = (DoubleMapNode*) p1->Next();
 352     }
 353     return Standard_False;
 354   }
 355
 356   //! UnBind2
 357   Standard_Boolean UnBind2 (const TheKey2Type& theKey2)
 358   {
 359     if (IsEmpty())
 360       return Standard_False;
 361     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
 362     DoubleMapNode * p1, * p2, * q1, *q2;
 363     q1 = q2 = NULL;
 364     p2 = (DoubleMapNode *) myData2[iK2];
 365     while (p2)
 366     {
 367       if (Hasher2::IsEqual (p2->Key2(), theKey2))
 368       {
 369         // remove from the data2
 370         if (q2)
 371           q2->Next() = p2->Next();
 372         else
 373           myData2[iK2] = (DoubleMapNode*) p2->Next2();
 374         Standard_Integer iK1 = Hasher1::HashCode (p2->Key1(), NbBuckets());
 375         p1 = (DoubleMapNode *) myData1[iK1];
 376         while (p1)
 377         {
 378           if (p1 == p2)
 379           {
 380             // remove from the data1
 381             if (q1)
 382               q1->Next() = p1->Next();
 383             else
 384               myData1[iK1] = (DoubleMapNode*) p1->Next();
 385             break;
 386           }
 387           q1 = p1;
 388           p1 = (DoubleMapNode*) p1->Next();
 389         }
 390         p2->~DoubleMapNode();
 391         this->myAllocator->Free(p2);
 392         Decrement();
 393         return Standard_True;
 394       }
 395       q2 = p2;
 396       p2 = (DoubleMapNode*) p2->Next2();
 397     }
 398     return Standard_False;
 399   }
 400
 401   //! Find the Key1 and return Key2 value.
 402   //! Raises an exception if Key1 was not bound.
 403   const TheKey2Type& Find1(const TheKey1Type& theKey1) const
 404   {
 405     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_DoubleMap::Find1");
 406     DoubleMapNode * pNode1 =
 407       (DoubleMapNode *) myData1[Hasher1::HashCode(theKey1,NbBuckets())];
 408     while (pNode1)
 409     {
 410       if (Hasher1::IsEqual (pNode1->Key1(), theKey1))
 411         return pNode1->Key2();
 412       pNode1 = (DoubleMapNode*) pNode1->Next();
 413     }
 414     throw Standard_NoSuchObject("NCollection_DoubleMap::Find1");
 415   }
 416
 417   //! Find the Key1 and return Key2 value (by copying its value).
 418   //! @param [in]  theKey1 Key1 to find
 419   //! @param [out] theKey2 Key2 to return
 420   //! @return TRUE if Key1 has been found
 421   Standard_Boolean Find1 (const TheKey1Type& theKey1,
 422                           TheKey2Type& theKey2) const
 423   {
 424     for (DoubleMapNode* aNode1 = !IsEmpty() ? (DoubleMapNode* )myData1[Hasher1::HashCode (theKey1, NbBuckets())] : NULL;
 425          aNode1 != NULL; aNode1 = (DoubleMapNode* )aNode1->Next())
 426     {
 427       if (Hasher1::IsEqual (aNode1->Key1(), theKey1))
 428       {
 429         theKey2 = aNode1->Key2();
 430         return Standard_True;
 431       }
 432     }
 433     return Standard_False;
 434   }
 435
 436   //! Find the Key2 and return Key1 value.
 437   //! Raises an exception if Key2 was not bound.
 438   const TheKey1Type& Find2(const TheKey2Type& theKey2) const
 439   {
 440     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_DoubleMap::Find2");
 441     DoubleMapNode * pNode2 =
 442       (DoubleMapNode *) myData2[Hasher2::HashCode(theKey2,NbBuckets())];
 443     while (pNode2)
 444     {
 445       if (Hasher2::IsEqual (pNode2->Key2(), theKey2))
 446         return pNode2->Key1();
 447       pNode2 = (DoubleMapNode*) pNode2->Next2();
 448     }
 449     throw Standard_NoSuchObject("NCollection_DoubleMap::Find2");
 450   }
 451
 452   //! Find the Key2 and return Key1 value (by copying its value).
 453   //! @param [in]  theKey2 Key2 to find
 454   //! @param [out] theKey1 Key1 to return
 455   //! @return TRUE if Key2 has been found
 456   Standard_Boolean Find2 (const TheKey2Type& theKey2,
 457                           TheKey1Type& theKey1) const
 458   {
 459     for (DoubleMapNode* aNode2 = !IsEmpty() ? (DoubleMapNode* )myData2[Hasher2::HashCode (theKey2, NbBuckets())] : NULL;
 460          aNode2 != NULL; aNode2 = (DoubleMapNode* )aNode2->Next2())
 461     {
 462       if (Hasher2::IsEqual (aNode2->Key2(), theKey2))
 463       {
 464         theKey1 = aNode2->Key1();
 465         return Standard_True;
 466       }
 467     }
 468     return Standard_False;
 469   }
 470
 471   //! Clear data. If doReleaseMemory is false then the table of
 472   //! buckets is not released and will be reused.
 473   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
 474   { Destroy (DoubleMapNode::delNode, doReleaseMemory); }
 475
 476   //! Clear data and reset allocator
 477   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
 478   {
 479     Clear();
 480     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
 481                     NCollection_BaseAllocator::CommonBaseAllocator() );
 482   }
 483
 484   //! Destructor
 485   ~NCollection_DoubleMap (void)
 486   { Clear(); }
 487
 488   //! Size
 489   Standard_Integer Size(void) const
 490   { return Extent(); }
 491 };
 492
 493 #endif