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