src/NCollection/NCollection_DataMap.hxx

   1 // Created on: 2002-04-24
   2 // Created by: Alexander KARTOMIN (akm)
   3 // Copyright (c) 2002-2012 OPEN CASCADE SAS
   4 //
   5 // The content of this file is subject to the Open CASCADE Technology Public
   6 // License Version 6.5 (the "License"). You may not use the content of this file
   7 // except in compliance with the License. Please obtain a copy of the License
   8 // at http://www.opencascade.org and read it completely before using this file.
   9 //
  10 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
  11 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  12 //
  13 // The Original Code and all software distributed under the License is
  14 // distributed on an "AS IS" basis, without warranty of any kind, and the
  15 // Initial Developer hereby disclaims all such warranties, including without
  16 // limitation, any warranties of merchantability, fitness for a particular
  17 // purpose or non-infringement. Please see the License for the specific terms
  18 // and conditions governing the rights and limitations under the License.
  19
  20 #ifndef NCollection_DataMap_HeaderFile
  21 #define NCollection_DataMap_HeaderFile
  22
  23 #include <NCollection_BaseCollection.hxx>
  24 #include <NCollection_BaseMap.hxx>
  25 #include <NCollection_TListNode.hxx>
  26
  27 #include <NCollection_DefaultHasher.hxx>
  28
  29 #include <Standard_TypeMismatch.hxx>
  30 #include <Standard_NoSuchObject.hxx>
  31
  32 /**
  33 * Purpose:     The DataMap is a Map to store keys with associated
  34 *              Items. See Map  from NCollection for  a discussion
  35 *              about the number of buckets.
  36 *
  37 *              The DataMap can be seen as an extended array where
  38 *              the Keys  are the   indices.  For this reason  the
  39 *              operator () is defined on DataMap to fetch an Item
  40 *              from a Key. So the following syntax can be used :
  41 *
  42 *              anItem = aMap(aKey);
  43 *              aMap(aKey) = anItem;
  44 *
  45 *              This analogy has its  limit.   aMap(aKey) = anItem
  46 *              can  be done only  if aKey was previously bound to
  47 *              an item in the map.
  48 */
  49
  50 template < class TheKeyType,
  51            class TheItemType,
  52            class Hasher = NCollection_DefaultHasher<TheKeyType> >  class NCollection_DataMap
  53
  54   : public NCollection_BaseCollection<TheItemType>,
  55     public NCollection_BaseMap
  56 {
  57   // **************** Adaptation of the TListNode to the DATAmap
  58  public:
  59   class DataMapNode : public NCollection_TListNode<TheItemType>
  60   {
  61   public:
  62     //! Constructor with 'Next'
  63     DataMapNode (const TheKeyType&     theKey,
  64                  const TheItemType&    theItem,
  65                  NCollection_ListNode* theNext) :
  66                    NCollection_TListNode<TheItemType> (theItem, theNext)
  67     { myKey = theKey; }
  68     //! Key
  69     const TheKeyType& Key (void) const
  70     { return myKey; }
  71
  72     //! Static deleter to be passed to BaseList
  73     static void delNode (NCollection_ListNode * theNode,
  74                          Handle(NCollection_BaseAllocator)& theAl)
  75     {
  76       ((DataMapNode *) theNode)->~DataMapNode();
  77       theAl->Free(theNode);
  78     }
  79
  80   private:
  81     TheKeyType    myKey;
  82   };
  83
  84  public:
  85   // **************** Implementation of the Iterator interface.
  86   class Iterator
  87     : public NCollection_BaseCollection<TheItemType>::Iterator,
  88       public NCollection_BaseMap::Iterator
  89   {
  90   public:
  91     //! Empty constructor
  92     Iterator (void) :
  93       NCollection_BaseMap::Iterator() {}
  94     //! Constructor
  95     Iterator (const NCollection_DataMap& theMap) :
  96       NCollection_BaseMap::Iterator(theMap) {}
  97     //! Query if the end of collection is reached by iterator
  98     virtual Standard_Boolean More(void) const
  99     { return PMore(); }
 100     //! Make a step along the collection
 101     virtual void Next(void)
 102     { PNext(); }
 103     //! Value inquiry
 104     virtual const TheItemType& Value(void) const
 105     {
 106 #if !defined No_Exception && !defined No_Standard_NoSuchObject
 107       if (!More())
 108         Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Value");
 109 #endif
 110       return ((DataMapNode *) myNode)->Value();
 111     }
 112     //! Value change access
 113     virtual TheItemType& ChangeValue(void) const
 114     {
 115 #if !defined No_Exception && !defined No_Standard_NoSuchObject
 116       if (!More())
 117         Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::ChangeValue");
 118 #endif
 119       return ((DataMapNode *) myNode)->ChangeValue();
 120     }
 121     //! Key
 122     const TheKeyType& Key (void) const
 123     {
 124 #if !defined No_Exception && !defined No_Standard_NoSuchObject
 125       if (!More())
 126         Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Key");
 127 #endif
 128       return ((DataMapNode *) myNode)->Key();
 129     }
 130   };
 131
 132  public:
 133   // ---------- PUBLIC METHODS ------------
 134
 135   //! Constructor
 136   NCollection_DataMap (const Standard_Integer NbBuckets=1,
 137                      const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
 138     : NCollection_BaseCollection<TheItemType>(theAllocator),
 139       NCollection_BaseMap (NbBuckets, Standard_True) {}
 140
 141   //! Copy constructor
 142   NCollection_DataMap (const NCollection_DataMap& theOther)
 143     : NCollection_BaseCollection<TheItemType>(theOther.myAllocator),
 144       NCollection_BaseMap (theOther.NbBuckets(), Standard_True)
 145   { *this = theOther; }
 146
 147   //! Assign another collection
 148   virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther)
 149   {
 150     if (this == &theOther)
 151       return;
 152     Standard_TypeMismatch::Raise ("NCollection_DataMap::Assign impossible");
 153   }
 154
 155   //! Exchange the content of two maps without re-allocations.
 156   //! Notice that allocators will be swapped as well!
 157   void Exchange (NCollection_DataMap& theOther)
 158   {
 159     this->exchangeAllocators (theOther);
 160     this->exchangeMapsData   (theOther);
 161   }
 162
 163   //! = another map
 164   NCollection_DataMap& operator= (const NCollection_DataMap& theOther)
 165   {
 166     if (this == &theOther)
 167       return *this;
 168
 169     Clear(theOther.myAllocator);
 170     ReSize (theOther.Extent()-1);
 171     Iterator anIter(theOther);
 172     for (; anIter.More(); anIter.Next())
 173       Bind (anIter.Key(), anIter.Value());
 174     return *this;
 175   }
 176
 177   //! ReSize
 178   void ReSize (const Standard_Integer N)
 179   {
 180     DataMapNode** newdata = NULL;
 181     DataMapNode** dummy   = NULL;
 182     Standard_Integer newBuck;
 183     if (BeginResize (N, newBuck,
 184                      (NCollection_ListNode**&)newdata,
 185                      (NCollection_ListNode**&)dummy,
 186                      this->myAllocator))
 187     {
 188       if (myData1)
 189       {
 190         DataMapNode** olddata = (DataMapNode**) myData1;
 191         DataMapNode *p, *q;
 192         Standard_Integer i,k;
 193         for (i = 0; i <= NbBuckets(); i++)
 194         {
 195           if (olddata[i])
 196           {
 197             p = olddata[i];
 198             while (p)
 199             {
 200               k = Hasher::HashCode(p->Key(),newBuck);
 201               q = (DataMapNode*) p->Next();
 202               p->Next() = newdata[k];
 203               newdata[k] = p;
 204               p = q;
 205             }
 206           }
 207         }
 208       }
 209       EndResize(N,newBuck,
 210                 (NCollection_ListNode**&)newdata,
 211                 (NCollection_ListNode**&)dummy,
 212                 this->myAllocator);
 213     }
 214   }
 215
 216   //! Bind
 217   Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem)
 218   {
 219     if (Resizable())
 220       ReSize(Extent());
 221     DataMapNode** data = (DataMapNode**)myData1;
 222     Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
 223     DataMapNode* p = data[k];
 224     while (p)
 225     {
 226       if (Hasher::IsEqual(p->Key(), theKey))
 227       {
 228         p->ChangeValue() = theItem;
 229         return Standard_False;
 230       }
 231       p = (DataMapNode *) p->Next();
 232     }
 233     data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
 234     Increment();
 235     return Standard_True;
 236   }
 237
 238   //! IsBound
 239   Standard_Boolean IsBound(const TheKeyType& K) const
 240   {
 241     if (IsEmpty())
 242       return Standard_False;
 243     DataMapNode** data = (DataMapNode**) myData1;
 244     DataMapNode* p = data[Hasher::HashCode(K,NbBuckets())];
 245     while (p)
 246     {
 247       if (Hasher::IsEqual(p->Key(),K))
 248         return Standard_True;
 249       p = (DataMapNode *) p->Next();
 250     }
 251     return Standard_False;
 252   }
 253
 254   //! UnBind
 255   Standard_Boolean UnBind(const TheKeyType& K)
 256   {
 257     if (IsEmpty())
 258       return Standard_False;
 259     DataMapNode** data = (DataMapNode**) myData1;
 260     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
 261     DataMapNode* p = data[k];
 262     DataMapNode* q = NULL;
 263     while (p)
 264     {
 265       if (Hasher::IsEqual(p->Key(),K))
 266       {
 267         Decrement();
 268         if (q)
 269           q->Next() = p->Next();
 270         else
 271           data[k] = (DataMapNode*) p->Next();
 272         p->~DataMapNode();
 273         this->myAllocator->Free(p);
 274         return Standard_True;
 275       }
 276       q = p;
 277       p = (DataMapNode*) p->Next();
 278     }
 279     return Standard_False;
 280   }
 281
 282   //! Find
 283   const TheItemType& Find(const TheKeyType& theKey) const
 284   {
 285 #if !defined No_Exception && !defined No_Standard_NoSuchObject
 286     if (IsEmpty())
 287       Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
 288 #endif
 289     DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
 290     while (p)
 291     {
 292       if (Hasher::IsEqual(p->Key(),theKey))
 293         return p->Value();
 294       p = (DataMapNode*) p->Next();
 295     }
 296     Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
 297     return p->Value(); // This for compiler
 298   }
 299
 300   //! Find value for key with copying.
 301   //! @return true if key was found
 302   Standard_Boolean Find (const TheKeyType& theKey,
 303                          TheItemType&      theValue) const
 304   {
 305     if (IsEmpty())
 306     {
 307       return Standard_False;
 308     }
 309
 310     for (DataMapNode* aNodeIter = (DataMapNode* )myData1[Hasher::HashCode (theKey, NbBuckets())];
 311          aNodeIter != NULL;
 312          aNodeIter = (DataMapNode* )aNodeIter->Next())
 313     {
 314       if (Hasher::IsEqual (aNodeIter->Key(), theKey))
 315       {
 316         theValue = aNodeIter->Value();
 317         return Standard_True;
 318       }
 319     }
 320     return Standard_False;
 321   }
 322
 323   //! operator ()
 324   const TheItemType& operator() (const TheKeyType& theKey) const
 325   { return Find(theKey); }
 326
 327   //! ChangeFind
 328   TheItemType& ChangeFind (const TheKeyType& theKey)
 329   {
 330 #if !defined No_Exception && !defined No_Standard_NoSuchObject
 331     if (IsEmpty())
 332       Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
 333 #endif
 334     DataMapNode*  p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
 335     while (p)
 336     {
 337       if (Hasher::IsEqual(p->Key(),theKey))
 338         return p->ChangeValue();
 339       p = (DataMapNode*) p->Next();
 340     }
 341     Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
 342     return p->ChangeValue(); // This for compiler
 343   }
 344
 345   //! operator ()
 346   TheItemType& operator() (const TheKeyType& theKey)
 347   { return ChangeFind(theKey); }
 348
 349   //! Clear data. If doReleaseMemory is false then the table of
 350   //! buckets is not released and will be reused.
 351   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
 352   { Destroy (DataMapNode::delNode, this->myAllocator, doReleaseMemory); }
 353
 354   //! Clear data and reset allocator
 355   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
 356   {
 357     Clear();
 358     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
 359                     NCollection_BaseAllocator::CommonBaseAllocator() );
 360   }
 361
 362   //! Destructor
 363   ~NCollection_DataMap (void)
 364   { Clear(); }
 365
 366   //! Size
 367   virtual Standard_Integer Size(void) const
 368   { return Extent(); }
 369
 370  private:
 371   // ----------- PRIVATE METHODS -----------
 372
 373   //! Creates Iterator for use on BaseCollection
 374   virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator&
 375           CreateIterator(void) const
 376   { return *(new (this->IterAllocator()) Iterator(*this)); }
 377
 378 };
 379
 380 #endif
 381