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     ReSize (theOther.Extent()-1);
 155     Iterator anIter(theOther);
 156     for (; anIter.More(); anIter.Next())
 157     {
 158       TheKey1Type aKey1 = anIter.Key1();
 159       TheKey2Type aKey2 = anIter.Key2();
 160       Standard_Integer iK1 = Hasher1::HashCode (aKey1, NbBuckets());
 161       Standard_Integer iK2 = Hasher2::HashCode (aKey2, NbBuckets());
 162       DoubleMapNode * pNode = new (this->myAllocator) DoubleMapNode (aKey1, aKey2,
 163                                                                      myData1[iK1],
 164                                                                      myData2[iK2]);
 165       myData1[iK1] = pNode;
 166       myData2[iK2] = pNode;
 167       Increment();
 168     }
 169     return *this;
 170   }
 171
 172   //! Assignment operator
 173   NCollection_DoubleMap& operator= (const NCollection_DoubleMap& theOther)
 174   {
 175     return Assign (theOther);
 176   }
 177
 178   //! ReSize
 179   void ReSize (const Standard_Integer N)
 180   {
 181     NCollection_ListNode** ppNewData1 = NULL;
 182     NCollection_ListNode** ppNewData2 = NULL;
 183     Standard_Integer newBuck;
 184     if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
 185     {
 186       if (myData1)
 187       {
 188         DoubleMapNode *p, *q;
 189         Standard_Integer i, iK1, iK2;
 190         for (i = 0; i <= NbBuckets(); i++)
 191         {
 192           if (myData1[i])
 193           {
 194             p = (DoubleMapNode *) myData1[i];
 195             while (p)
 196             {
 197               iK1 = Hasher1::HashCode (p->Key1(), newBuck);
 198               iK2 = Hasher2::HashCode (p->Key2(), newBuck);
 199               q = (DoubleMapNode*) p->Next();
 200               p->Next()  = ppNewData1[iK1];
 201               p->Next2() = (DoubleMapNode*)ppNewData2[iK2];
 202               ppNewData1[iK1] = p;
 203               ppNewData2[iK2] = p;
 204               p = q;
 205             }
 206           }
 207         }
 208       }
 209       EndResize (N, newBuck, ppNewData1, ppNewData2);
 210     }
 211   }
 212
 213   //! Bind
 214   void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2)
 215   {
 216     if (Resizable())
 217       ReSize(Extent());
 218     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
 219     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
 220     DoubleMapNode * pNode;
 221     pNode = (DoubleMapNode *) myData1[iK1];
 222     while (pNode)
 223     {
 224       if (Hasher1::IsEqual (pNode->Key1(), theKey1))
 225         throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind");
 226       pNode = (DoubleMapNode *) pNode->Next();
 227     }
 228     pNode = (DoubleMapNode *) myData2[iK2];
 229     while (pNode)
 230     {
 231       if (Hasher2::IsEqual (pNode->Key2(), theKey2))
 232         throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind");
 233       pNode = (DoubleMapNode *) pNode->Next();
 234     }
 235     pNode = new (this->myAllocator) DoubleMapNode (theKey1, theKey2,
 236                                                    myData1[iK1], myData2[iK2]);
 237     myData1[iK1] = pNode;
 238     myData2[iK2] = pNode;
 239     Increment();
 240   }
 241
 242   //!* AreBound
 243   Standard_Boolean AreBound (const TheKey1Type& theKey1,
 244                              const TheKey2Type& theKey2) const
 245   {
 246     if (IsEmpty())
 247       return Standard_False;
 248     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
 249     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
 250     DoubleMapNode * pNode1, * pNode2;
 251     pNode1 = (DoubleMapNode *) myData1[iK1];
 252     while (pNode1)
 253     {
 254       if (Hasher1::IsEqual(pNode1->Key1(), theKey1))
 255         break;
 256       pNode1 = (DoubleMapNode *) pNode1->Next();
 257     }
 258     if (pNode1 == NULL)
 259       return Standard_False;
 260     pNode2 = (DoubleMapNode *) myData2[iK2];
 261     while (pNode2)
 262     {
 263       if (Hasher2::IsEqual(pNode2->Key2(), theKey2))
 264         break;
 265       pNode2 = (DoubleMapNode *) pNode2->Next();
 266     }
 267     if (pNode2 == NULL)
 268       return Standard_False;
 269
 270     return (pNode1 == pNode2);
 271   }
 272
 273   //! IsBound1
 274   Standard_Boolean IsBound1 (const TheKey1Type& theKey1) const
 275   {
 276     if (IsEmpty())
 277       return Standard_False;
 278     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
 279     DoubleMapNode * pNode1;
 280     pNode1 = (DoubleMapNode *) myData1[iK1];
 281     while (pNode1)
 282     {
 283       if (Hasher1::IsEqual(pNode1->Key1(), theKey1))
 284         return Standard_True;
 285       pNode1 = (DoubleMapNode *) pNode1->Next();
 286     }
 287     return Standard_False;
 288   }
 289
 290   //! IsBound2
 291   Standard_Boolean IsBound2 (const TheKey2Type& theKey2) const
 292   {
 293     if (IsEmpty())
 294       return Standard_False;
 295     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
 296     DoubleMapNode * pNode2;
 297     pNode2 = (DoubleMapNode *) myData2[iK2];
 298     while (pNode2)
 299     {
 300       if (Hasher2::IsEqual(pNode2->Key2(), theKey2))
 301         return Standard_True;
 302       pNode2 = (DoubleMapNode *) pNode2->Next2();
 303     }
 304     return Standard_False;
 305   }
 306
 307   //! UnBind1
 308   Standard_Boolean UnBind1 (const TheKey1Type& theKey1)
 309   {
 310     if (IsEmpty())
 311       return Standard_False;
 312     Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets());
 313     DoubleMapNode * p1, * p2, * q1, *q2;
 314     q1 = q2 = NULL;
 315     p1 = (DoubleMapNode *) myData1[iK1];
 316     while (p1)
 317     {
 318       if (Hasher1::IsEqual (p1->Key1(), theKey1))
 319       {
 320         // remove from the data1
 321         if (q1)
 322           q1->Next() = p1->Next();
 323         else
 324           myData1[iK1] = (DoubleMapNode*) p1->Next();
 325         Standard_Integer iK2 = Hasher2::HashCode (p1->Key2(), NbBuckets());
 326         p2 = (DoubleMapNode *) myData2[iK2];
 327         while (p2)
 328         {
 329           if (p2 == p1)
 330           {
 331             // remove from the data2
 332             if (q2)
 333               q2->Next2() = p2->Next2();
 334             else
 335               myData2[iK2] = (DoubleMapNode*) p2->Next2();
 336             break;
 337           }
 338           q2 = p2;
 339           p2 = (DoubleMapNode*) p2->Next2();
 340         }
 341         p1->~DoubleMapNode();
 342         this->myAllocator->Free(p1);
 343         Decrement();
 344         return Standard_True;
 345       }
 346       q1 = p1;
 347       p1 = (DoubleMapNode*) p1->Next();
 348     }
 349     return Standard_False;
 350   }
 351
 352   //! UnBind2
 353   Standard_Boolean UnBind2 (const TheKey2Type& theKey2)
 354   {
 355     if (IsEmpty())
 356       return Standard_False;
 357     Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets());
 358     DoubleMapNode * p1, * p2, * q1, *q2;
 359     q1 = q2 = NULL;
 360     p2 = (DoubleMapNode *) myData2[iK2];
 361     while (p2)
 362     {
 363       if (Hasher2::IsEqual (p2->Key2(), theKey2))
 364       {
 365         // remove from the data2
 366         if (q2)
 367           q2->Next() = p2->Next();
 368         else
 369           myData2[iK2] = (DoubleMapNode*) p2->Next2();
 370         Standard_Integer iK1 = Hasher1::HashCode (p2->Key1(), NbBuckets());
 371         p1 = (DoubleMapNode *) myData1[iK1];
 372         while (p1)
 373         {
 374           if (p1 == p2)
 375           {
 376             // remove from the data1
 377             if (q1)
 378               q1->Next() = p1->Next();
 379             else
 380               myData1[iK1] = (DoubleMapNode*) p1->Next();
 381             break;
 382           }
 383           q1 = p1;
 384           p1 = (DoubleMapNode*) p1->Next();
 385         }
 386         p2->~DoubleMapNode();
 387         this->myAllocator->Free(p2);
 388         Decrement();
 389         return Standard_True;
 390       }
 391       q2 = p2;
 392       p2 = (DoubleMapNode*) p2->Next2();
 393     }
 394     return Standard_False;
 395   }
 396
 397   //! Find1
 398   const TheKey2Type& Find1(const TheKey1Type& theKey1) const
 399   {
 400     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_DoubleMap::Find1");
 401     DoubleMapNode * pNode1 =
 402       (DoubleMapNode *) myData1[Hasher1::HashCode(theKey1,NbBuckets())];
 403     while (pNode1)
 404     {
 405       if (Hasher1::IsEqual (pNode1->Key1(), theKey1))
 406         return pNode1->Key2();
 407       pNode1 = (DoubleMapNode*) pNode1->Next();
 408     }
 409     throw Standard_NoSuchObject("NCollection_DoubleMap::Find1");
 410   }
 411
 412   //! Find2
 413   const TheKey1Type& Find2(const TheKey2Type& theKey2) const
 414   {
 415     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_DoubleMap::Find2");
 416     DoubleMapNode * pNode2 =
 417       (DoubleMapNode *) myData2[Hasher2::HashCode(theKey2,NbBuckets())];
 418     while (pNode2)
 419     {
 420       if (Hasher2::IsEqual (pNode2->Key2(), theKey2))
 421         return pNode2->Key1();
 422       pNode2 = (DoubleMapNode*) pNode2->Next2();
 423     }
 424     throw Standard_NoSuchObject("NCollection_DoubleMap::Find2");
 425   }
 426
 427   //! Clear data. If doReleaseMemory is false then the table of
 428   //! buckets is not released and will be reused.
 429   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
 430   { Destroy (DoubleMapNode::delNode, doReleaseMemory); }
 431
 432   //! Clear data and reset allocator
 433   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
 434   {
 435     Clear();
 436     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
 437                     NCollection_BaseAllocator::CommonBaseAllocator() );
 438   }
 439
 440   //! Destructor
 441   ~NCollection_DoubleMap (void)
 442   { Clear(); }
 443
 444   //! Size
 445   Standard_Integer Size(void) const
 446   { return Extent(); }
 447 };
 448
 449 #endif