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