SALOME - SMESH
SMESH_IndexedMap.hxx
Go to the documentation of this file.
00001 // File:        NCollection_IndexedMap.hxx
00002 // Created:     Thu Apr 24 15:02:53 2002
00003 // Author:      Alexander KARTOMIN (akm)
00004 //              <akm@opencascade.com>
00005 
00006 #ifndef SMESH_IndexedMap_HeaderFile
00007 #define SMESH_IndexedMap_HeaderFile
00008 
00009 #include <NCollection_BaseCollection.hxx>
00010 #include <NCollection_BaseMap.hxx>
00011 #include <NCollection_TListNode.hxx>
00012 #include <Standard_NoSuchObject.hxx>
00013 #include <Standard_ImmutableObject.hxx>
00014 
00015 #if !defined No_Exception && !defined No_Standard_OutOfRange
00016 #include <Standard_OutOfRange.hxx>
00017 #endif
00018 
00019 #ifdef WNT
00020 // Disable the warning "operator new unmatched by delete"
00021 #pragma warning (push)
00022 #pragma warning (disable:4291)
00023 #endif
00024 
00035 template <class TheKeyType> class SMESH_IndexedMap 
00036   : public NCollection_BaseCollection<TheKeyType>,
00037     public NCollection_BaseMap
00038 {
00039   // **************** Adaptation of the TListNode to the INDEXEDmap
00040  private:
00041   class IndexedMapNode : public NCollection_TListNode<TheKeyType>
00042   {
00043   public:
00045     IndexedMapNode (const TheKeyType&      theKey1, 
00046                     const Standard_Integer theKey2, 
00047                     NCollection_ListNode*  theNext1, 
00048                     NCollection_ListNode*  theNext2) :
00049                       NCollection_TListNode<TheKeyType> (theKey1, theNext1)
00050     { 
00051       myKey2 = theKey2;
00052       myNext2 = (IndexedMapNode *) theNext2;
00053     }
00055     TheKeyType& Key1 (void)
00056     { return this->ChangeValue(); }
00058     const Standard_Integer& Key2 (void)
00059     { return myKey2; }
00061     IndexedMapNode*& Next2 (void)
00062     { return myNext2; }
00063     
00065     static void delNode (NCollection_ListNode * theNode, 
00066                          Handle(NCollection_BaseAllocator)& theAl)
00067     {
00068       ((IndexedMapNode *) theNode)->~IndexedMapNode();
00069       theAl->Free(theNode);
00070     }
00071 
00072   private:
00073     Standard_Integer myKey2;
00074     IndexedMapNode * myNext2;
00075   };
00076 
00077  public:
00078   // **************** Implementation of the Iterator interface.
00079   class Iterator 
00080      : public NCollection_BaseCollection<TheKeyType>::Iterator
00081   {
00082   public:
00084     Iterator (void) :
00085       myMap(NULL),
00086       myIndex(0) {}
00088     Iterator (const SMESH_IndexedMap& theMap) :
00089        myMap(const_cast<SMESH_IndexedMap<TheKeyType>*>(&theMap) /*(SMESH_IndexedMap *) &theMap*/),
00090        myIndex(1) {}
00092     virtual Standard_Boolean More(void) const
00093     { return (myIndex <= myMap->Extent()); }
00095     virtual void Next(void)
00096     { myIndex++; }
00098     virtual const TheKeyType& Value(void) const
00099     {
00100 #if !defined No_Exception && !defined No_Standard_NoSuchObject
00101       if (!More())
00102         Standard_NoSuchObject::Raise("SMESH_IndexedMap::Iterator::Value");
00103 #endif
00104       return myMap->FindKey(myIndex);
00105     }
00107     virtual TheKeyType& ChangeValue(void) const
00108     {  
00109       Standard_ImmutableObject::Raise ("impossible to ChangeValue");
00110       return * (TheKeyType *) NULL; // This for compiler
00111     }
00112     
00114     void* operator new(size_t theSize,
00115                        const Handle(NCollection_BaseAllocator)& theAllocator) 
00116     { return theAllocator->Allocate(theSize); }
00117     
00118   private:
00119     SMESH_IndexedMap * myMap;   // Pointer to the map being iterated
00120     Standard_Integer         myIndex; // Current index
00121   };
00122   
00123  public:
00124   // ---------- PUBLIC METHODS ------------
00125 
00127   SMESH_IndexedMap (const Standard_Integer NbBuckets=1,
00128                           const Handle(NCollection_BaseAllocator)& theAllocator=0L) :
00129     NCollection_BaseCollection<TheKeyType>(theAllocator),
00130     NCollection_BaseMap (NbBuckets, Standard_False) {}
00131 
00133   SMESH_IndexedMap (const SMESH_IndexedMap& theOther) :
00134     NCollection_BaseCollection<TheKeyType>(theOther.myAllocator),
00135     NCollection_BaseMap (theOther.NbBuckets(), Standard_False) 
00136   { *this = theOther; }
00137 
00139   virtual void Assign (const NCollection_BaseCollection<TheKeyType>& theOther)
00140   { 
00141     if (this == &theOther)
00142       return;
00143     Clear();
00144     ReSize (theOther.Size());
00145     TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& anIter = 
00146       theOther.CreateIterator();
00147     for (; anIter.More(); anIter.Next())
00148       Add(anIter.Value());
00149   }
00150 
00152   SMESH_IndexedMap& operator= (const SMESH_IndexedMap& theOther)
00153   { 
00154     if (this == &theOther)
00155       return *this;
00156 
00157     Clear();
00158     ReSize (theOther.NbBuckets());
00159     Standard_Integer i, iLength=theOther.Extent();
00160     for (i=1; i<=iLength; i++)
00161     {
00162       TheKeyType aKey1 = theOther(i);
00163       Standard_Integer iK1 = HashCode (aKey1, NbBuckets());
00164       Standard_Integer iK2 = HashCode (i, NbBuckets());
00165       IndexedMapNode * pNode = new (this->myAllocator) IndexedMapNode (aKey1, i, 
00166                                                                        myData1[iK1], 
00167                                                                        myData2[iK2]);
00168       myData1[iK1] = pNode;
00169       myData2[iK2] = pNode;
00170       Increment();
00171     }
00172     return *this;
00173   }
00174 
00176   void ReSize (const Standard_Integer N)
00177   {
00178     IndexedMapNode** ppNewData1 = NULL;
00179     IndexedMapNode** ppNewData2 = NULL;
00180     Standard_Integer newBuck;
00181     if (BeginResize (N, newBuck, 
00182                      (NCollection_ListNode**&)ppNewData1, 
00183                      (NCollection_ListNode**&)ppNewData2,
00184                      this->myAllocator)) 
00185     {
00186       if (myData1) 
00187       {
00188         IndexedMapNode *p, *q;
00189         Standard_Integer i, iK1, iK2;
00190         for (i = 0; i <= NbBuckets(); i++) 
00191         {
00192           if (myData1[i]) 
00193           {
00194             p = (IndexedMapNode *) myData1[i];
00195             while (p) 
00196             {
00197               iK1 = HashCode (p->Key1(), newBuck);
00198               q = (IndexedMapNode*) p->Next();
00199               p->Next()  = ppNewData1[iK1];
00200               ppNewData1[iK1] = p;
00201               if (p->Key2() > 0) 
00202               {
00203                 iK2 = HashCode (p->Key2(), newBuck);
00204                 p->Next2() = ppNewData2[iK2];
00205                 ppNewData2[iK2] = p;
00206               }
00207               p = q;
00208             }
00209           }
00210         }
00211       }
00212       EndResize(N,newBuck,
00213                 (NCollection_ListNode**&)ppNewData1,
00214                 (NCollection_ListNode**&)ppNewData2,
00215                 this->myAllocator);
00216     }
00217   }
00218 
00220   Standard_Integer Add (const TheKeyType& theKey1)
00221   {
00222     if (Resizable()) 
00223       ReSize(Extent());
00224     Standard_Integer iK1 = HashCode (theKey1, NbBuckets());
00225     IndexedMapNode * pNode;
00226     pNode = (IndexedMapNode *) myData1[iK1];
00227     while (pNode)
00228     {
00229       if (IsEqual (pNode->Key1(), theKey1))
00230         return pNode->Key2();
00231       pNode = (IndexedMapNode *) pNode->Next();
00232     }
00233     Increment();
00234     Standard_Integer iK2 = HashCode(Extent(),NbBuckets());
00235     pNode = new (this->myAllocator) IndexedMapNode (theKey1, Extent(), 
00236                                                     myData1[iK1], myData2[iK2]);
00237     myData1[iK1] = pNode;
00238     myData2[iK2] = pNode;
00239     return Extent();
00240   }
00241 
00243   Standard_Boolean Contains (const TheKeyType& theKey1) const
00244   {
00245     if (IsEmpty()) 
00246       return Standard_False;
00247     Standard_Integer iK1 = HashCode (theKey1, NbBuckets());
00248     IndexedMapNode * pNode1;
00249     pNode1 = (IndexedMapNode *) myData1[iK1];
00250     while (pNode1) 
00251     {
00252       if (IsEqual(pNode1->Key1(), theKey1)) 
00253         return Standard_True;
00254       pNode1 = (IndexedMapNode *) pNode1->Next();
00255     }
00256     return Standard_False;
00257   }
00258 
00260   void Substitute (const Standard_Integer theIndex,
00261                    const TheKeyType& theKey1)
00262   {
00263 #if !defined No_Exception && !defined No_Standard_OutOfRange
00264     if (theIndex < 1 || theIndex > Extent())
00265       Standard_OutOfRange::Raise ("SMESH_IndexedMap::Substitute");
00266 #endif
00267     IndexedMapNode * p;
00268     // check if theKey1 is not already in the map
00269     Standard_Integer iK1 = HashCode (theKey1, NbBuckets());
00270     p = (IndexedMapNode *) myData1[iK1];
00271     while (p) 
00272     {
00273       if (IsEqual (p->Key1(), theKey1)) 
00274         Standard_DomainError::Raise("SMESH_IndexedMap::Substitute");
00275       p = (IndexedMapNode *) p->Next();
00276     }
00277 
00278     // Find the node for the index I
00279     Standard_Integer iK2 = HashCode (theIndex, NbBuckets());
00280     p = (IndexedMapNode *) myData2[iK2];
00281     while (p) 
00282     {
00283       if (p->Key2() == theIndex) 
00284         break;
00285       p = (IndexedMapNode*) p->Next2();
00286     }
00287     
00288     // remove the old key
00289     Standard_Integer iK = HashCode (p->Key1(), NbBuckets());
00290     IndexedMapNode * q = (IndexedMapNode *) myData1[iK];
00291     if (q == p)
00292       myData1[iK] = (IndexedMapNode *) p->Next();
00293     else 
00294     {
00295       while (q->Next() != p) 
00296         q = (IndexedMapNode *) q->Next();
00297       q->Next() = p->Next();
00298     }
00299 
00300     // update the node
00301     p->Key1() = theKey1;
00302     p->Next() = myData1[iK1];
00303     myData1[iK1] = p;
00304   }
00305 
00307   void RemoveLast (void)
00308   {
00309 #if !defined No_Exception && !defined No_Standard_OutOfRange
00310     if (Extent() == 0)
00311       Standard_OutOfRange::Raise ("SMESH_IndexedMap::RemoveLast");
00312 #endif
00313     IndexedMapNode * p, * q;
00314     // Find the node for the last index and remove it
00315     Standard_Integer iK2 = HashCode (Extent(), NbBuckets());
00316     p = (IndexedMapNode *) myData2[iK2];
00317     q = NULL;
00318     while (p) 
00319     {
00320       if (p->Key2() == Extent()) 
00321         break;
00322       q = p;
00323       p = (IndexedMapNode*) p->Next2();
00324     }
00325     if (q == NULL) 
00326       myData2[iK2] = (IndexedMapNode *) p->Next2();
00327     else 
00328       q->Next2() = p->Next2();
00329     
00330     // remove the key
00331     Standard_Integer iK1 = HashCode (p->Key1(), NbBuckets());
00332     q = (IndexedMapNode *) myData1[iK1];
00333     if (q == p)
00334       myData1[iK1] = (IndexedMapNode *) p->Next();
00335     else 
00336     {
00337       while (q->Next() != p) 
00338         q = (IndexedMapNode *) q->Next();
00339       q->Next() = p->Next();
00340     }
00341     p->~IndexedMapNode();
00342     this->myAllocator->Free(p);
00343     Decrement();
00344   }
00345 
00347   const TheKeyType& FindKey (const Standard_Integer theKey2) const
00348   {
00349 #if !defined No_Exception && !defined No_Standard_OutOfRange
00350     if (theKey2 < 1 || theKey2 > Extent())
00351       Standard_OutOfRange::Raise ("SMESH_IndexedMap::FindKey");
00352 #endif
00353     IndexedMapNode * pNode2 =
00354       (IndexedMapNode *) myData2[HashCode(theKey2,NbBuckets())];
00355     while (pNode2)
00356     {
00357       if (pNode2->Key2() == theKey2) 
00358         return pNode2->Key1();
00359       pNode2 = (IndexedMapNode*) pNode2->Next2();
00360     }
00361     Standard_NoSuchObject::Raise("SMESH_IndexedMap::FindKey");
00362     return pNode2->Key1(); // This for compiler
00363   }
00364 
00366   const TheKeyType& operator() (const Standard_Integer theKey2) const
00367   { return FindKey (theKey2); }
00368 
00370   Standard_Integer FindIndex(const TheKeyType& theKey1) const
00371   {
00372     if (IsEmpty()) return 0;
00373     IndexedMapNode * pNode1 = 
00374       (IndexedMapNode *) myData1[HashCode(theKey1,NbBuckets())];
00375     while (pNode1)
00376     {
00377       if (IsEqual (pNode1->Key1(), theKey1)) 
00378         return pNode1->Key2();
00379       pNode1 = (IndexedMapNode*) pNode1->Next();
00380     }
00381     return 0;
00382   }
00383 
00386   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
00387   { Destroy (IndexedMapNode::delNode, this->myAllocator, doReleaseMemory); }
00388 
00390   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
00391   { 
00392     Clear();
00393     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
00394                     NCollection_BaseAllocator::CommonBaseAllocator() );
00395   }
00396 
00398   ~SMESH_IndexedMap (void)
00399   { Clear(); }
00400 
00402   virtual Standard_Integer Size(void) const
00403   { return Extent(); }
00404 
00405  private:
00406   // ----------- PRIVATE METHODS -----------
00407 
00409   virtual TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& 
00410     CreateIterator(void) const
00411   { return *(new (this->IterAllocator()) Iterator(*this)); }
00412 
00413 };
00414 
00415 #ifdef WNT
00416 #pragma warning (pop)
00417 #endif
00418 
00419 #endif