src/NCollection/NCollection_DataMap.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_DataMap_HeaderFile
  17 #define NCollection_DataMap_HeaderFile
  18
  19 #include <NCollection_BaseMap.hxx>
  20 #include <NCollection_TListNode.hxx>
  21 #include <NCollection_StlIterator.hxx>
  22 #include <NCollection_DefaultHasher.hxx>
  23
  24 #include <Standard_TypeMismatch.hxx>
  25 #include <Standard_NoSuchObject.hxx>
  26
  27 /**
  28 * Purpose:     The DataMap is a Map to store keys with associated
  29 *              Items. See Map  from NCollection for  a discussion
  30 *              about the number of buckets.
  31 *
  32 *              The DataMap can be seen as an extended array where
  33 *              the Keys  are the   indices.  For this reason  the
  34 *              operator () is defined on DataMap to fetch an Item
  35 *              from a Key. So the following syntax can be used :
  36 *
  37 *              anItem = aMap(aKey);
  38 *              aMap(aKey) = anItem;
  39 *
  40 *              This analogy has its  limit.   aMap(aKey) = anItem
  41 *              can  be done only  if aKey was previously bound to
  42 *              an item in the map.
  43 */
  44
  45 template < class TheKeyType,
  46            class TheItemType,
  47            class Hasher = NCollection_DefaultHasher<TheKeyType> >
  48 class NCollection_DataMap : public NCollection_BaseMap
  49 {
  50 public:
  51   //! STL-compliant typedef for key type
  52   typedef TheKeyType key_type;
  53   //! STL-compliant typedef for value type
  54   typedef TheItemType value_type;
  55
  56 public:
  57   // **************** Adaptation of the TListNode to the DATAmap
  58   class DataMapNode : public NCollection_TListNode<TheItemType>
  59   {
  60   public:
  61     //! Constructor with 'Next'
  62     DataMapNode (const TheKeyType&     theKey,
  63                  const TheItemType&    theItem,
  64                  NCollection_ListNode* theNext) :
  65       NCollection_TListNode<TheItemType> (theItem, theNext),
  66       myKey(theKey)
  67     {}
  68
  69     //! Key
  70     const TheKeyType& Key (void) const
  71     { return myKey; }
  72
  73     //! Static deleter to be passed to BaseMap
  74     static void delNode (NCollection_ListNode * theNode,
  75                          Handle(NCollection_BaseAllocator)& theAl)
  76     {
  77       ((DataMapNode *) theNode)->~DataMapNode();
  78       theAl->Free(theNode);
  79     }
  80
  81   private:
  82     TheKeyType    myKey;
  83   };
  84
  85  public:
  86   // **************** Implementation of the Iterator interface.
  87   class Iterator : public NCollection_BaseMap::Iterator
  88   {
  89   public:
  90     //! Empty constructor
  91     Iterator (void) :
  92       NCollection_BaseMap::Iterator() {}
  93     //! Constructor
  94     Iterator (const NCollection_DataMap& theMap) :
  95       NCollection_BaseMap::Iterator(theMap) {}
  96     //! Query if the end of collection is reached by iterator
  97     Standard_Boolean More(void) const
  98     { return PMore(); }
  99     //! Make a step along the collection
 100     void Next(void)
 101     { PNext(); }
 102     //! Value inquiry
 103     const TheItemType& Value(void) const
 104     {
 105       Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Value");
 106       return ((DataMapNode *) myNode)->Value();
 107     }
 108     //! Value change access
 109     TheItemType& ChangeValue(void) const
 110     {
 111       Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::ChangeValue");
 112       return ((DataMapNode *) myNode)->ChangeValue();
 113     }
 114     //! Key
 115     const TheKeyType& Key (void) const
 116     {
 117       Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Key");
 118       return ((DataMapNode *) myNode)->Key();
 119     }
 120   };
 121
 122   //! Shorthand for a regular iterator type.
 123   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator;
 124
 125   //! Shorthand for a constant iterator type.
 126   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator;
 127
 128   //! Returns an iterator pointing to the first element in the map.
 129   iterator begin() const { return Iterator (*this); }
 130
 131   //! Returns an iterator referring to the past-the-end element in the map.
 132   iterator end() const { return Iterator(); }
 133
 134   //! Returns a const iterator pointing to the first element in the map.
 135   const_iterator cbegin() const { return Iterator (*this); }
 136
 137   //! Returns a const iterator referring to the past-the-end element in the map.
 138   const_iterator cend() const { return Iterator(); }
 139
 140  public:
 141   // ---------- PUBLIC METHODS ------------
 142
 143   //! Empty Constructor.
 144   NCollection_DataMap() : NCollection_BaseMap (1, Standard_True, Handle(NCollection_BaseAllocator)()) {}
 145
 146   //! Constructor
 147   explicit NCollection_DataMap (const Standard_Integer theNbBuckets,
 148                                 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
 149   : NCollection_BaseMap (theNbBuckets, Standard_True, theAllocator) {}
 150
 151   //! Copy constructor
 152   NCollection_DataMap (const NCollection_DataMap& theOther)
 153     : NCollection_BaseMap (theOther.NbBuckets(), Standard_True, theOther.myAllocator)
 154   { *this = theOther; }
 155
 156   //! Exchange the content of two maps without re-allocations.
 157   //! Notice that allocators will be swapped as well!
 158   void Exchange (NCollection_DataMap& theOther)
 159   {
 160     this->exchangeMapsData (theOther);
 161   }
 162
 163   //! Assignment.
 164   //! This method does not change the internal allocator.
 165   NCollection_DataMap& Assign (const NCollection_DataMap& theOther)
 166   {
 167     if (this == &theOther)
 168       return *this;
 169
 170     Clear();
 171     Standard_Integer anExt = theOther.Extent();
 172     if (anExt)
 173     {
 174       ReSize (anExt-1);
 175       Iterator anIter(theOther);
 176       for (; anIter.More(); anIter.Next())
 177         Bind (anIter.Key(), anIter.Value());
 178     }
 179     return *this;
 180   }
 181
 182   //! Assignment operator
 183   NCollection_DataMap& operator= (const NCollection_DataMap& theOther)
 184   {
 185     return Assign (theOther);
 186   }
 187
 188   //! ReSize
 189   void ReSize (const Standard_Integer N)
 190   {
 191     NCollection_ListNode** newdata = NULL;
 192     NCollection_ListNode** dummy   = NULL;
 193     Standard_Integer newBuck;
 194     if (BeginResize (N, newBuck, newdata, dummy))
 195     {
 196       if (myData1)
 197       {
 198         DataMapNode** olddata = (DataMapNode**) myData1;
 199         DataMapNode *p, *q;
 200         Standard_Integer i,k;
 201         for (i = 0; i <= NbBuckets(); i++)
 202         {
 203           if (olddata[i])
 204           {
 205             p = olddata[i];
 206             while (p)
 207             {
 208               k = Hasher::HashCode(p->Key(),newBuck);
 209               q = (DataMapNode*) p->Next();
 210               p->Next() = newdata[k];
 211               newdata[k] = p;
 212               p = q;
 213             }
 214           }
 215         }
 216       }
 217       EndResize (N, newBuck, newdata, dummy);
 218     }
 219   }
 220
 221   //! Bind binds Item to Key in map.
 222   //! @param theKey  key to add/update
 223   //! @param theItem new item; overrides value previously bound to the key, if any
 224   //! @return Standard_True if Key was not bound already
 225   Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem)
 226   {
 227     if (Resizable())
 228       ReSize(Extent());
 229     DataMapNode** data = (DataMapNode**)myData1;
 230     Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
 231     DataMapNode* p = data[k];
 232     while (p)
 233     {
 234       if (Hasher::IsEqual(p->Key(), theKey))
 235       {
 236         p->ChangeValue() = theItem;
 237         return Standard_False;
 238       }
 239       p = (DataMapNode *) p->Next();
 240     }
 241     data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
 242     Increment();
 243     return Standard_True;
 244   }
 245
 246   //! Bound binds Item to Key in map. Returns modifiable Item
 247   TheItemType* Bound (const TheKeyType& theKey, const TheItemType& theItem)
 248   {
 249     if (Resizable())
 250       ReSize(Extent());
 251     DataMapNode** data = (DataMapNode**)myData1;
 252     Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
 253     DataMapNode* p = data[k];
 254     while (p)
 255     {
 256       if (Hasher::IsEqual(p->Key(), theKey))
 257       {
 258         p->ChangeValue() = theItem;
 259         return &p->ChangeValue();
 260       }
 261       p = (DataMapNode*)p->Next();
 262     }
 263     data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
 264     Increment();
 265     return &data[k]->ChangeValue();
 266   }
 267
 268   //! IsBound
 269   Standard_Boolean IsBound(const TheKeyType& theKey) const
 270   {
 271     DataMapNode* p;
 272     return lookup(theKey, p);
 273   }
 274
 275   //! UnBind removes Item Key pair from map
 276   Standard_Boolean UnBind(const TheKeyType& theKey)
 277   {
 278     if (IsEmpty())
 279       return Standard_False;
 280     DataMapNode** data = (DataMapNode**) myData1;
 281     Standard_Integer k = Hasher::HashCode(theKey,NbBuckets());
 282     DataMapNode* p = data[k];
 283     DataMapNode* q = NULL;
 284     while (p)
 285     {
 286       if (Hasher::IsEqual(p->Key(), theKey))
 287       {
 288         Decrement();
 289         if (q)
 290           q->Next() = p->Next();
 291         else
 292           data[k] = (DataMapNode*) p->Next();
 293         p->~DataMapNode();
 294         this->myAllocator->Free(p);
 295         return Standard_True;
 296       }
 297       q = p;
 298       p = (DataMapNode*) p->Next();
 299     }
 300     return Standard_False;
 301   }
 302
 303   //! Seek returns pointer to Item by Key. Returns
 304   //! NULL is Key was not bound.
 305   const TheItemType* Seek(const TheKeyType& theKey) const
 306   {
 307     DataMapNode* p = 0;
 308     if (!lookup(theKey, p))
 309       return 0L;
 310     return &p->Value();
 311   }
 312
 313   //! Find returns the Item for Key. Raises if Key was not bound
 314   const TheItemType& Find(const TheKeyType& theKey) const
 315   {
 316     DataMapNode* p = 0;
 317     if (!lookup(theKey, p))
 318       throw Standard_NoSuchObject("NCollection_DataMap::Find");
 319     return p->Value();
 320   }
 321
 322   //! Find Item for key with copying.
 323   //! @return true if key was found
 324   Standard_Boolean Find (const TheKeyType& theKey,
 325                          TheItemType&      theValue) const
 326   {
 327     DataMapNode* p = 0;
 328     if (!lookup(theKey, p))
 329       return Standard_False;
 330
 331     theValue = p->Value();
 332     return Standard_True;
 333   }
 334
 335   //! operator ()
 336   const TheItemType& operator() (const TheKeyType& theKey) const
 337   { return Find(theKey); }
 338
 339   //! ChangeSeek returns modifiable pointer to Item by Key. Returns
 340   //! NULL is Key was not bound.
 341   TheItemType* ChangeSeek(const TheKeyType& theKey)
 342   {
 343     DataMapNode* p = 0;
 344     if (!lookup(theKey, p))
 345       return 0L;
 346     return &p->ChangeValue();
 347   }
 348
 349   //! ChangeFind returns mofifiable Item by Key. Raises if Key was not bound
 350   TheItemType& ChangeFind (const TheKeyType& theKey)
 351   {
 352     DataMapNode* p = 0;
 353     if (!lookup(theKey, p))
 354       throw Standard_NoSuchObject("NCollection_DataMap::Find");
 355     return p->ChangeValue();
 356   }
 357
 358   //! operator ()
 359   TheItemType& operator() (const TheKeyType& theKey)
 360   { return ChangeFind(theKey); }
 361
 362   //! Clear data. If doReleaseMemory is false then the table of
 363   //! buckets is not released and will be reused.
 364   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
 365   { Destroy (DataMapNode::delNode, doReleaseMemory); }
 366
 367   //! Clear data and reset allocator
 368   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
 369   {
 370     Clear();
 371     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
 372                     NCollection_BaseAllocator::CommonBaseAllocator() );
 373   }
 374
 375   //! Destructor
 376   virtual ~NCollection_DataMap (void)
 377   { Clear(); }
 378
 379   //! Size
 380   Standard_Integer Size(void) const
 381   { return Extent(); }
 382
 383
 384  protected:
 385   // ---------- PROTECTED METHODS ----------
 386   //! Lookup for particular key in map. Returns true if key is found and
 387   //! thepNode points to binded node. Returns false if key is not found,
 388   //! thehNode value is this case is not usable.
 389   Standard_Boolean lookup(const TheKeyType& theKey,DataMapNode*& thepNode) const
 390   {
 391     if (IsEmpty())
 392       return Standard_False; // Not found
 393     for (thepNode = (DataMapNode*)myData1[Hasher::HashCode(theKey, NbBuckets())];
 394          thepNode; thepNode = (DataMapNode*)thepNode->Next())
 395     {
 396       if (Hasher::IsEqual(thepNode->Key(), theKey))
 397         return Standard_True;
 398     }
 399     return Standard_False; // Not found
 400   }
 401
 402 };
 403
 404 #endif
 405