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   //! = another map
 156   NCollection_DataMap& operator= (const NCollection_DataMap& theOther)
 157   {
 158     if (this == &theOther)
 159       return *this;
 160
 161     Clear(theOther.myAllocator);
 162     ReSize (theOther.Extent()-1);
 163     Iterator anIter(theOther);
 164     for (; anIter.More(); anIter.Next())
 165       Bind (anIter.Key(), anIter.Value());
 166     return *this;
 167   }
 168
 169   //! ReSize
 170   void ReSize (const Standard_Integer N)
 171   {
 172     DataMapNode** newdata = NULL;
 173     DataMapNode** dummy   = NULL;
 174     Standard_Integer newBuck;
 175     if (BeginResize (N, newBuck,
 176                      (NCollection_ListNode**&)newdata,
 177                      (NCollection_ListNode**&)dummy,
 178                      this->myAllocator))
 179     {
 180       if (myData1)
 181       {
 182         DataMapNode** olddata = (DataMapNode**) myData1;
 183         DataMapNode *p, *q;
 184         Standard_Integer i,k;
 185         for (i = 0; i <= NbBuckets(); i++)
 186         {
 187           if (olddata[i])
 188           {
 189             p = olddata[i];
 190             while (p)
 191             {
 192               k = Hasher::HashCode(p->Key(),newBuck);
 193               q = (DataMapNode*) p->Next();
 194               p->Next() = newdata[k];
 195               newdata[k] = p;
 196               p = q;
 197             }
 198           }
 199         }
 200       }
 201       EndResize(N,newBuck,
 202                 (NCollection_ListNode**&)newdata,
 203                 (NCollection_ListNode**&)dummy,
 204                 this->myAllocator);
 205     }
 206   }
 207
 208   //! Bind
 209   Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem)
 210   {
 211     if (Resizable())
 212       ReSize(Extent());
 213     DataMapNode** data = (DataMapNode**)myData1;
 214     Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
 215     DataMapNode* p = data[k];
 216     while (p)
 217     {
 218       if (Hasher::IsEqual(p->Key(), theKey))
 219       {
 220         p->ChangeValue() = theItem;
 221         return Standard_False;
 222       }
 223       p = (DataMapNode *) p->Next();
 224     }
 225     data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
 226     Increment();
 227     return Standard_True;
 228   }
 229
 230   //! IsBound
 231   Standard_Boolean IsBound(const TheKeyType& K) const
 232   {
 233     if (IsEmpty())
 234       return Standard_False;
 235     DataMapNode** data = (DataMapNode**) myData1;
 236     DataMapNode* p = data[Hasher::HashCode(K,NbBuckets())];
 237     while (p)
 238     {
 239       if (Hasher::IsEqual(p->Key(),K))
 240         return Standard_True;
 241       p = (DataMapNode *) p->Next();
 242     }
 243     return Standard_False;
 244   }
 245
 246   //! UnBind
 247   Standard_Boolean UnBind(const TheKeyType& K)
 248   {
 249     if (IsEmpty())
 250       return Standard_False;
 251     DataMapNode** data = (DataMapNode**) myData1;
 252     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
 253     DataMapNode* p = data[k];
 254     DataMapNode* q = NULL;
 255     while (p)
 256     {
 257       if (Hasher::IsEqual(p->Key(),K))
 258       {
 259         Decrement();
 260         if (q)
 261           q->Next() = p->Next();
 262         else
 263           data[k] = (DataMapNode*) p->Next();
 264         p->~DataMapNode();
 265         this->myAllocator->Free(p);
 266         return Standard_True;
 267       }
 268       q = p;
 269       p = (DataMapNode*) p->Next();
 270     }
 271     return Standard_False;
 272   }
 273
 274   //! Find
 275   const TheItemType& Find(const TheKeyType& theKey) const
 276   {
 277 #if !defined No_Exception && !defined No_Standard_NoSuchObject
 278     if (IsEmpty())
 279       Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
 280 #endif
 281     DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
 282     while (p)
 283     {
 284       if (Hasher::IsEqual(p->Key(),theKey))
 285         return p->Value();
 286       p = (DataMapNode*) p->Next();
 287     }
 288     Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
 289     return p->Value(); // This for compiler
 290   }
 291
 292   //! Find value for key with copying.
 293   //! @return true if key was found
 294   Standard_Boolean Find (const TheKeyType& theKey,
 295                          TheItemType&      theValue) const
 296   {
 297     if (IsEmpty())
 298     {
 299       return Standard_False;
 300     }
 301
 302     for (DataMapNode* aNodeIter = (DataMapNode* )myData1[Hasher::HashCode (theKey, NbBuckets())];
 303          aNodeIter != NULL;
 304          aNodeIter = (DataMapNode* )aNodeIter->Next())
 305     {
 306       if (Hasher::IsEqual (aNodeIter->Key(), theKey))
 307       {
 308         theValue = aNodeIter->Value();
 309         return Standard_True;
 310       }
 311     }
 312     return Standard_False;
 313   }
 314
 315   //! operator ()
 316   const TheItemType& operator() (const TheKeyType& theKey) const
 317   { return Find(theKey); }
 318
 319   //! ChangeFind
 320   TheItemType& ChangeFind (const TheKeyType& theKey)
 321   {
 322 #if !defined No_Exception && !defined No_Standard_NoSuchObject
 323     if (IsEmpty())
 324       Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
 325 #endif
 326     DataMapNode*  p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
 327     while (p)
 328     {
 329       if (Hasher::IsEqual(p->Key(),theKey))
 330         return p->ChangeValue();
 331       p = (DataMapNode*) p->Next();
 332     }
 333     Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
 334     return p->ChangeValue(); // This for compiler
 335   }
 336
 337   //! operator ()
 338   TheItemType& operator() (const TheKeyType& theKey)
 339   { return ChangeFind(theKey); }
 340
 341   //! Clear data. If doReleaseMemory is false then the table of
 342   //! buckets is not released and will be reused.
 343   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
 344   { Destroy (DataMapNode::delNode, this->myAllocator, doReleaseMemory); }
 345
 346   //! Clear data and reset allocator
 347   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
 348   {
 349     Clear();
 350     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
 351                     NCollection_BaseAllocator::CommonBaseAllocator() );
 352   }
 353
 354   //! Destructor
 355   ~NCollection_DataMap (void)
 356   { Clear(); }
 357
 358   //! Size
 359   virtual Standard_Integer Size(void) const
 360   { return Extent(); }
 361
 362  private:
 363   // ----------- PRIVATE METHODS -----------
 364
 365   //! Creates Iterator for use on BaseCollection
 366   virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator&
 367           CreateIterator(void) const
 368   { return *(new (this->IterAllocator()) Iterator(*this)); }
 369
 370 };
 371
 372 #endif
 373