src/NCollection/NCollection_Map.hxx

   1 // Created on: 2002-04-23
   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_Map_HeaderFile
  17 #define NCollection_Map_HeaderFile
  18
  19 #include <NCollection_BaseMap.hxx>
  20 #include <NCollection_DataMap.hxx>
  21 #include <NCollection_TListNode.hxx>
  22 #include <NCollection_StlIterator.hxx>
  23 #include <NCollection_DefaultHasher.hxx>
  24
  25 #include <Standard_NoSuchObject.hxx>
  26
  27 /**
  28  * Purpose:     Single hashed Map. This  Map is used  to store and
  29  *              retrieve keys in linear time.
  30  *
  31  *              The ::Iterator class can be  used to explore  the
  32  *              content of the map. It is not  wise to iterate and
  33  *              modify a map in parallel.
  34  *
  35  *              To compute  the hashcode of  the key the  function
  36  *              ::HashCode must be defined in the global namespace
  37  *
  38  *              To compare two keys the function ::IsEqual must be
  39  *              defined in the global namespace.
  40  *
  41  *              The performance of  a Map is conditionned  by  its
  42  *              number of buckets that  should be kept greater  to
  43  *              the number   of keys.  This  map has  an automatic
  44  *              management of the number of buckets. It is resized
  45  *              when  the number of Keys  becomes greater than the
  46  *              number of buckets.
  47  *
  48  *              If you have a fair  idea of the number of  objects
  49  *              you  can save on automatic   resizing by giving  a
  50  *              number of buckets  at creation or using the ReSize
  51  *              method. This should be  consider only for  crucial
  52  *              optimisation issues.
  53  */
  54
  55 template < class TheKeyType,
  56            class Hasher = NCollection_DefaultHasher<TheKeyType> >
  57 class NCollection_Map : public NCollection_BaseMap
  58 {
  59   //!   Adaptation of the TListNode to the map notations
  60  public:
  61
  62   class MapNode : public NCollection_TListNode<TheKeyType>
  63   {
  64   public:
  65     //! Constructor with 'Next'
  66     MapNode (const TheKeyType& theKey,
  67              NCollection_ListNode* theNext) :
  68       NCollection_TListNode<TheKeyType> (theKey, theNext) {}
  69     //! Key
  70     const TheKeyType& Key (void)
  71     { return this->Value(); }
  72
  73   };
  74
  75  public:
  76   //!   Implementation of the Iterator interface.
  77   class Iterator : public NCollection_BaseMap::Iterator
  78   {
  79   public:
  80     //! Empty constructor
  81     Iterator (void) :
  82       NCollection_BaseMap::Iterator() {}
  83     //! Constructor
  84     Iterator (const NCollection_Map& theMap) :
  85       NCollection_BaseMap::Iterator(theMap) {}
  86     //! Query if the end of collection is reached by iterator
  87     Standard_Boolean More(void) const
  88     { return PMore(); }
  89     //! Make a step along the collection
  90     void Next(void)
  91     { PNext(); }
  92     //! Value inquiry
  93     const TheKeyType& Value(void) const
  94     {
  95       Standard_NoSuchObject_Raise_if (!More(), "NCollection_Map::Iterator::Value");
  96       return ((MapNode *) myNode)->Value();
  97     }
  98
  99     //! Key
 100     const TheKeyType& Key (void) const
 101     {
 102       Standard_NoSuchObject_Raise_if (!More(), "NCollection_Map::Iterator::Key");
 103       return ((MapNode *) myNode)->Value();
 104     }
 105   };
 106
 107   //! Shorthand for a constant iterator type.
 108   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheKeyType, true> const_iterator;
 109
 110   //! Returns a const iterator pointing to the first element in the map.
 111   const_iterator cbegin() const { return Iterator (*this); }
 112
 113   //! Returns a const iterator referring to the past-the-end element in the map.
 114   const_iterator cend() const { return Iterator(); }
 115
 116  public:
 117   // ---------- PUBLIC METHODS ------------
 118
 119   //! Constructor
 120   NCollection_Map (const Standard_Integer NbBuckets = 1,
 121                    const Handle(NCollection_BaseAllocator)& theAllocator = 0L) :
 122     NCollection_BaseMap (NbBuckets, Standard_True, theAllocator) {}
 123
 124   //! Copy constructor
 125   NCollection_Map (const NCollection_Map& theOther) :
 126     NCollection_BaseMap (theOther.NbBuckets(), Standard_True, theOther.myAllocator)
 127   { *this = theOther; }
 128
 129   //! Exchange the content of two maps without re-allocations.
 130   //! Notice that allocators will be swapped as well!
 131   void Exchange (NCollection_Map& theOther)
 132   {
 133     this->exchangeMapsData (theOther);
 134   }
 135
 136   //! Assign.
 137   //! This method does not change the internal allocator.
 138   NCollection_Map& Assign (const NCollection_Map& theOther)
 139   {
 140     if (this == &theOther)
 141       return *this;
 142
 143     Clear();
 144     ReSize (theOther.Extent()-1);
 145     Iterator anIter(theOther);
 146     for (; anIter.More(); anIter.Next())
 147       Add (anIter.Key());
 148     return *this;
 149   }
 150
 151   //! Assign operator
 152   NCollection_Map& operator= (const NCollection_Map& theOther)
 153   {
 154     return Assign(theOther);
 155   }
 156
 157   //! ReSize
 158   void ReSize (const Standard_Integer N)
 159   {
 160     NCollection_ListNode** newdata = 0L;
 161     NCollection_ListNode** dummy = 0L;
 162     Standard_Integer newBuck;
 163     if (BeginResize (N, newBuck, newdata, dummy))
 164     {
 165       if (myData1)
 166       {
 167         MapNode** olddata = (MapNode**) myData1;
 168         MapNode *p, *q;
 169         Standard_Integer i,k;
 170         for (i = 0; i <= NbBuckets(); i++)
 171         {
 172           if (olddata[i])
 173           {
 174             p = olddata[i];
 175             while (p)
 176             {
 177               k = Hasher::HashCode(p->Key(),newBuck);
 178               q = (MapNode*) p->Next();
 179               p->Next() = newdata[k];
 180               newdata[k] = p;
 181               p = q;
 182             }
 183           }
 184         }
 185       }
 186       EndResize (N, newBuck, newdata, dummy);
 187     }
 188   }
 189
 190   //! Add
 191   Standard_Boolean Add(const TheKeyType& K)
 192   {
 193     if (Resizable())
 194       ReSize(Extent());
 195     MapNode** data = (MapNode**)myData1;
 196     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
 197     MapNode* p = data[k];
 198     while (p)
 199     {
 200       if (Hasher::IsEqual(p->Key(),K))
 201         return Standard_False;
 202       p = (MapNode *) p->Next();
 203     }
 204     data[k] = new (this->myAllocator) MapNode(K,data[k]);
 205     Increment();
 206     return Standard_True;
 207   }
 208
 209   //! Added: add a new key if not yet in the map, and return
 210   //! reference to either newly added or previously existing object
 211   const TheKeyType& Added(const TheKeyType& K)
 212   {
 213     if (Resizable())
 214       ReSize(Extent());
 215     MapNode** data = (MapNode**)myData1;
 216     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
 217     MapNode* p = data[k];
 218     while (p)
 219     {
 220       if (Hasher::IsEqual(p->Key(),K))
 221         return p->Key();
 222       p = (MapNode *) p->Next();
 223     }
 224     data[k] = new (this->myAllocator) MapNode(K,data[k]);
 225     Increment();
 226     return data[k]->Key();
 227   }
 228
 229   //! Contains
 230   Standard_Boolean Contains(const TheKeyType& K) const
 231   {
 232     if (IsEmpty())
 233       return Standard_False;
 234     MapNode** data = (MapNode**) myData1;
 235     MapNode*  p = data[Hasher::HashCode(K,NbBuckets())];
 236     while (p)
 237     {
 238       if (Hasher::IsEqual(p->Key(),K))
 239         return Standard_True;
 240       p = (MapNode *) p->Next();
 241     }
 242     return Standard_False;
 243   }
 244
 245   //! Remove
 246   Standard_Boolean Remove(const TheKeyType& K)
 247   {
 248     if (IsEmpty())
 249       return Standard_False;
 250     MapNode** data = (MapNode**) myData1;
 251     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
 252     MapNode* p = data[k];
 253     MapNode* q = NULL;
 254     while (p)
 255     {
 256       if (Hasher::IsEqual(p->Key(),K))
 257       {
 258         Decrement();
 259         if (q)
 260           q->Next() = p->Next();
 261         else
 262           data[k] = (MapNode*) p->Next();
 263         p->~MapNode();
 264         this->myAllocator->Free(p);
 265         return Standard_True;
 266       }
 267       q = p;
 268       p = (MapNode*) p->Next();
 269     }
 270     return Standard_False;
 271   }
 272
 273   //! Clear data. If doReleaseMemory is false then the table of
 274   //! buckets is not released and will be reused.
 275   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
 276   { Destroy (MapNode::delNode, doReleaseMemory); }
 277
 278   //! Clear data and reset allocator
 279   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
 280   {
 281     Clear();
 282     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
 283                     NCollection_BaseAllocator::CommonBaseAllocator() );
 284   }
 285
 286   //! Destructor
 287   virtual ~NCollection_Map (void)
 288   { Clear(); }
 289
 290   //! Size
 291   Standard_Integer Size(void) const
 292   { return Extent(); }
 293
 294  public:
 295   //!@name Boolean operations with maps as sets of keys
 296   //!@{
 297
 298   //! @return true if two maps contains exactly the same keys
 299   Standard_Boolean IsEqual (const NCollection_Map& theOther) const
 300   {
 301     return Extent() == theOther.Extent()
 302         && Contains (theOther);
 303   }
 304
 305   //! @return true if this map contains ALL keys of another map.
 306   Standard_Boolean Contains (const NCollection_Map& theOther) const
 307   {
 308     if (this == &theOther
 309      || theOther.IsEmpty())
 310     {
 311       return Standard_True;
 312     }
 313     else if (Extent() < theOther.Extent())
 314     {
 315       return Standard_False;
 316     }
 317
 318     for (Iterator anIter (theOther); anIter.More(); anIter.Next())
 319     {
 320       if (!Contains (anIter.Key()))
 321       {
 322         return Standard_False;
 323       }
 324     }
 325
 326     return Standard_True;
 327   }
 328
 329   //! Sets this Map to be the result of union (aka addition, fuse, merge, boolean OR) operation between two given Maps
 330   //! The new Map contains the values that are contained either in the first map or in the second map or in both.
 331   //! All previous content of this Map is cleared.
 332   //! This map (result of the boolean operation) can also be passed as one of operands.
 333   void Union (const NCollection_Map& theLeft,
 334               const NCollection_Map& theRight)
 335   {
 336     if (&theLeft == &theRight)
 337     {
 338       Assign (theLeft);
 339       return;
 340     }
 341
 342     if (this != &theLeft
 343      && this != &theRight)
 344     {
 345       Clear();
 346     }
 347
 348     if (this != &theLeft)
 349     {
 350       for (Iterator anIter (theLeft); anIter.More(); anIter.Next())
 351       {
 352         Add (anIter.Key());
 353       }
 354     }
 355     if (this != &theRight)
 356     {
 357       for (Iterator anIter (theRight); anIter.More(); anIter.Next())
 358       {
 359         Add (anIter.Key());
 360       }
 361     }
 362   }
 363
 364   //! Apply to this Map the boolean operation union (aka addition, fuse, merge, boolean OR) with another (given) Map.
 365   //! The result contains the values that were previously contained in this map or contained in the given (operand) map.
 366   //! This algorithm is similar to method Union().
 367   //! Returns True if contents of this map is changed.
 368   Standard_Boolean Unite (const NCollection_Map& theOther)
 369   {
 370     if (this == &theOther)
 371     {
 372       return Standard_False;
 373     }
 374
 375     const Standard_Integer anOldExtent = Extent();
 376     Union (*this, theOther);
 377     return anOldExtent != Extent();
 378   }
 379
 380   //! Returns true if this and theMap have common elements.
 381   Standard_Boolean HasIntersection (const NCollection_Map& theMap) const
 382   {
 383     const NCollection_Map* aMap1 = this;
 384     const NCollection_Map* aMap2 = &theMap;
 385     if (theMap.Size() < Size())
 386     {
 387       aMap1 = &theMap;
 388       aMap2 = this;
 389     }
 390
 391     for (NCollection_Map::Iterator aIt(*aMap1); aIt.More(); aIt.Next())
 392     {
 393       if (aMap2->Contains(aIt.Value()))
 394       {
 395         return Standard_True;
 396       }
 397     }
 398
 399     return Standard_False;
 400   }
 401
 402   //! Sets this Map to be the result of intersection (aka multiplication, common, boolean AND) operation between two given Maps.
 403   //! The new Map contains only the values that are contained in both map operands.
 404   //! All previous content of this Map is cleared.
 405   //! This same map (result of the boolean operation) can also be used as one of operands.
 406   void Intersection (const NCollection_Map& theLeft,
 407                      const NCollection_Map& theRight)
 408   {
 409     if (&theLeft == &theRight)
 410     {
 411       Assign (theLeft);
 412       return;
 413     }
 414
 415     if (this == &theLeft)
 416     {
 417       NCollection_Map aCopy (1, this->myAllocator);
 418       Exchange     (aCopy);
 419       Intersection (aCopy, theRight);
 420       return;
 421     }
 422     else if (this == &theRight)
 423     {
 424       NCollection_Map aCopy (1, this->myAllocator);
 425       Exchange     (aCopy);
 426       Intersection (theLeft, aCopy);
 427       return;
 428     }
 429
 430     Clear();
 431     if (theLeft.Extent() < theRight.Extent())
 432     {
 433       for (Iterator anIter (theLeft); anIter.More(); anIter.Next())
 434       {
 435         if (theRight.Contains (anIter.Key()))
 436         {
 437           Add (anIter.Key());
 438         }
 439       }
 440     }
 441     else
 442     {
 443       for (Iterator anIter (theRight); anIter.More(); anIter.Next())
 444       {
 445         if (theLeft.Contains (anIter.Key()))
 446         {
 447           Add (anIter.Key());
 448         }
 449       }
 450     }
 451   }
 452
 453   //! Apply to this Map the intersection operation (aka multiplication, common, boolean AND) with another (given) Map.
 454   //! The result contains only the values that are contained in both this and the given maps.
 455   //! This algorithm is similar to method Intersection().
 456   //! Returns True if contents of this map is changed.
 457   Standard_Boolean Intersect (const NCollection_Map& theOther)
 458   {
 459     if (this == &theOther
 460      || IsEmpty())
 461     {
 462       return Standard_False;
 463     }
 464
 465     const Standard_Integer anOldExtent = Extent();
 466     Intersection (*this, theOther);
 467     return anOldExtent != Extent();
 468   }
 469
 470   //! Sets this Map to be the result of subtraction (aka set-theoretic difference, relative complement,
 471   //! exclude, cut, boolean NOT) operation between two given Maps.
 472   //! The new Map contains only the values that are contained in the first map operands and not contained in the second one.
 473   //! All previous content of this Map is cleared.
 474   void Subtraction (const NCollection_Map& theLeft,
 475                     const NCollection_Map& theRight)
 476   {
 477     if (this == &theLeft)
 478     {
 479       Subtract (theRight);
 480       return;
 481     }
 482     else if (this == &theRight)
 483     {
 484       NCollection_Map aCopy (1, this->myAllocator);
 485       Exchange    (aCopy);
 486       Subtraction (theLeft, aCopy);
 487       return;
 488     }
 489
 490     Assign   (theLeft);
 491     Subtract (theRight);
 492   }
 493
 494   //! Apply to this Map the subtraction (aka set-theoretic difference, relative complement,
 495   //! exclude, cut, boolean NOT) operation with another (given) Map.
 496   //! The result contains only the values that were previously contained in this map and not contained in this map.
 497   //! This algorithm is similar to method Subtract() with two operands.
 498   //! Returns True if contents of this map is changed.
 499   Standard_Boolean Subtract (const NCollection_Map& theOther)
 500   {
 501     if (this == &theOther)
 502     {
 503       if (IsEmpty())
 504       {
 505         return Standard_False;
 506       }
 507
 508       Clear();
 509       return Standard_True;
 510     }
 511
 512     const Standard_Integer anOldExtent = Extent();
 513     for (Iterator anIter (theOther); anIter.More(); anIter.Next())
 514     {
 515       Remove (anIter.Key());
 516     }
 517     return anOldExtent != Extent();
 518   }
 519
 520   //! Sets this Map to be the result of symmetric difference (aka exclusive disjunction, boolean XOR) operation between two given Maps.
 521   //! The new Map contains the values that are contained only in the first or the second operand maps but not in both.
 522   //! All previous content of this Map is cleared. This map (result of the boolean operation) can also be used as one of operands.
 523   void Difference (const NCollection_Map& theLeft,
 524                    const NCollection_Map& theRight)
 525   {
 526     if (&theLeft == &theRight)
 527     {
 528       Clear();
 529       return;
 530     }
 531     else if (this == &theLeft)
 532     {
 533       NCollection_Map aCopy (1, this->myAllocator);
 534       Exchange   (aCopy);
 535       Difference (aCopy, theRight);
 536       return;
 537     }
 538     else if (this == &theRight)
 539     {
 540       NCollection_Map aCopy (1, this->myAllocator);
 541       Exchange   (aCopy);
 542       Difference (theLeft, aCopy);
 543       return;
 544     }
 545
 546     Clear();
 547     for (Iterator anIter (theLeft); anIter.More(); anIter.Next())
 548     {
 549       if (!theRight.Contains (anIter.Key()))
 550       {
 551         Add (anIter.Key());
 552       }
 553     }
 554     for (Iterator anIter (theRight); anIter.More(); anIter.Next())
 555     {
 556       if (!theLeft.Contains (anIter.Key()))
 557       {
 558         Add (anIter.Key());
 559       }
 560     }
 561   }
 562
 563   //! Apply to this Map the symmetric difference (aka exclusive disjunction, boolean XOR) operation with another (given) Map.
 564   //! The result contains the values that are contained only in this or the operand map, but not in both.
 565   //! This algorithm is similar to method Difference().
 566   //! Returns True if contents of this map is changed.
 567   Standard_Boolean Differ (const NCollection_Map& theOther)
 568   {
 569     if (this == &theOther)
 570     {
 571       if (IsEmpty())
 572       {
 573         return Standard_False;
 574       }
 575       Clear();
 576       return Standard_True;
 577     }
 578
 579     const Standard_Integer anOldExtent = Extent();
 580     Difference (*this, theOther);
 581     return anOldExtent != Extent();
 582   }
 583
 584   //!@}
 585 };
 586
 587 #endif