00001
00002
00003
00004
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
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
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
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) ),
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;
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;
00120 Standard_Integer myIndex;
00121 };
00122
00123 public:
00124
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
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
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
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
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
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
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();
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
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