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