SALOME - SMESH
|
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