1 // Created on: 2002-04-24 2 // Created by: Alexander KARTOMIN (akm) 3 // Copyright (c) 2002-2014 OPEN CASCADE SAS 4 // 5 // This file is part of Open CASCADE Technology software library. 6 // 7 // This library is free software; you can redistribute it and/or modify it under 8 // the terms of the GNU Lesser General Public License version 2.1 as published 9 // by the Free Software Foundation, with special exception defined in the file 10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT 11 // distribution for complete text of the license and disclaimer of any warranty. 12 // 13 // Alternatively, this file may be used under the terms of Open CASCADE 14 // commercial license or contractual agreement. 15 16 #ifndef NCollection_IndexedDataMap_HeaderFile 17 #define NCollection_IndexedDataMap_HeaderFile 18 19 #include <NCollection_BaseMap.hxx> 20 #include <NCollection_TListNode.hxx> 21 #include <Standard_TypeMismatch.hxx> 22 #include <Standard_NoSuchObject.hxx> 23 #include <NCollection_StlIterator.hxx> 24 #include <NCollection_DefaultHasher.hxx> 25 26 #include <Standard_OutOfRange.hxx> 27 28 /** 29 * Purpose: An indexed map is used to store keys and to bind 30 * an index to them. Each new key stored in the map 31 * gets an index. Index are incremented as keys are 32 * stored in the map. A key can be found by the index 33 * and an index by the key. No key but the last can 34 * be removed so the indices are in the range 1.. 35 * Extent. An Item is stored with each key. 36 * 37 * This class is similar to IndexedMap from 38 * NCollection with the Item as a new feature. Note 39 * the important difference on the operator (). In 40 * the IndexedMap this operator returns the Key. In 41 * the IndexedDataMap this operator returns the Item. 42 * 43 * See the class Map from NCollection for a 44 * discussion about the number of buckets. 45 */ 46 47 template < class TheKeyType, 48 class TheItemType, 49 class Hasher = NCollection_DefaultHasher<TheKeyType> > 50 class NCollection_IndexedDataMap : public NCollection_BaseMap 51 { 52 public: 53 //! STL-compliant typedef for key type 54 typedef TheKeyType key_type; 55 //! STL-compliant typedef for value type 56 typedef TheItemType value_type; 57 58 private: 59 //! Adaptation of the TListNode to the INDEXEDDatamap 60 class IndexedDataMapNode : public NCollection_TListNode<TheItemType> 61 { 62 public: 63 //! Constructor with 'Next' IndexedDataMapNode(const TheKeyType & theKey1,const Standard_Integer theIndex,const TheItemType & theItem,NCollection_ListNode * theNext1)64 IndexedDataMapNode (const TheKeyType& theKey1, 65 const Standard_Integer theIndex, 66 const TheItemType& theItem, 67 NCollection_ListNode* theNext1) 68 : NCollection_TListNode<TheItemType>(theItem,theNext1), 69 myKey1 (theKey1), 70 myIndex (theIndex) 71 { 72 } 73 //! Key1 Key1()74 TheKeyType& Key1() { return myKey1; } 75 //! Index Index()76 Standard_Integer& Index() { return myIndex; } 77 78 //! Static deleter to be passed to BaseList delNode(NCollection_ListNode * theNode,Handle (NCollection_BaseAllocator)& theAl)79 static void delNode (NCollection_ListNode * theNode, 80 Handle(NCollection_BaseAllocator)& theAl) 81 { 82 ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode(); 83 theAl->Free(theNode); 84 } 85 private: 86 TheKeyType myKey1; 87 Standard_Integer myIndex; 88 }; 89 90 public: 91 //! Implementation of the Iterator interface. 92 class Iterator 93 { 94 public: 95 //! Empty constructor Iterator()96 Iterator() 97 : myMap (NULL), 98 myIndex (0) {} 99 100 //! Constructor Iterator(const NCollection_IndexedDataMap & theMap)101 Iterator (const NCollection_IndexedDataMap& theMap) 102 : myMap ((NCollection_IndexedDataMap*)&theMap), 103 myIndex (1) {} 104 105 //! Query if the end of collection is reached by iterator More(void) const106 Standard_Boolean More(void) const 107 { return (myMap != NULL) && (myIndex <= myMap->Extent()); } 108 109 //! Make a step along the collection Next(void)110 void Next(void) 111 { ++myIndex; } 112 113 //! Value access Value(void) const114 const TheItemType& Value(void) const 115 { 116 Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Value"); 117 return myMap->FindFromIndex(myIndex); 118 } 119 120 //! ChangeValue access ChangeValue(void) const121 TheItemType& ChangeValue(void) const 122 { 123 Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::ChangeValue"); 124 return myMap->ChangeFromIndex(myIndex); 125 } 126 127 //! Key Key() const128 const TheKeyType& Key() const 129 { 130 Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Key"); 131 return myMap->FindKey(myIndex); 132 } 133 134 //! Performs comparison of two iterators. IsEqual(const Iterator & theOther) const135 Standard_Boolean IsEqual (const Iterator& theOther) const 136 { 137 return myMap == theOther.myMap && 138 myIndex == theOther.myIndex; 139 } 140 141 private: 142 NCollection_IndexedDataMap* myMap; //!< Pointer to current node 143 Standard_Integer myIndex; //!< Current index 144 }; 145 146 //! Shorthand for a regular iterator type. 147 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator; 148 149 //! Shorthand for a constant iterator type. 150 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator; 151 152 //! Returns an iterator pointing to the first element in the map. begin() const153 iterator begin() const { return Iterator (*this); } 154 155 //! Returns an iterator referring to the past-the-end element in the map. end() const156 iterator end() const { return Iterator(); } 157 158 //! Returns a const iterator pointing to the first element in the map. cbegin() const159 const_iterator cbegin() const { return Iterator (*this); } 160 161 //! Returns a const iterator referring to the past-the-end element in the map. cend() const162 const_iterator cend() const { return Iterator(); } 163 164 public: 165 // ---------- PUBLIC METHODS ------------ 166 167 //! Empty constructor. NCollection_IndexedDataMap()168 NCollection_IndexedDataMap() : NCollection_BaseMap (1, Standard_False, Handle(NCollection_BaseAllocator)()) {} 169 170 //! Constructor NCollection_IndexedDataMap(const Standard_Integer theNbBuckets,const Handle (NCollection_BaseAllocator)& theAllocator=0L)171 explicit NCollection_IndexedDataMap (const Standard_Integer theNbBuckets, 172 const Handle(NCollection_BaseAllocator)& theAllocator = 0L) 173 : NCollection_BaseMap (theNbBuckets, Standard_False, theAllocator) {} 174 175 //! Copy constructor NCollection_IndexedDataMap(const NCollection_IndexedDataMap & theOther)176 NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther) 177 : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator) 178 { *this = theOther; } 179 180 //! Exchange the content of two maps without re-allocations. 181 //! Notice that allocators will be swapped as well! Exchange(NCollection_IndexedDataMap & theOther)182 void Exchange (NCollection_IndexedDataMap& theOther) 183 { 184 this->exchangeMapsData (theOther); 185 } 186 187 //! Assignment. 188 //! This method does not change the internal allocator. Assign(const NCollection_IndexedDataMap & theOther)189 NCollection_IndexedDataMap& Assign (const NCollection_IndexedDataMap& theOther) 190 { 191 if (this == &theOther) 192 return *this; 193 194 Clear(); 195 Standard_Integer anExt = theOther.Extent(); 196 if (anExt) 197 { 198 ReSize (anExt-1); //mySize is same after resize 199 for (Standard_Integer anIndexIter = 1; anIndexIter <= anExt; ++anIndexIter) 200 { 201 const TheKeyType& aKey1 = theOther.FindKey (anIndexIter); 202 const TheItemType& anItem = theOther.FindFromIndex(anIndexIter); 203 const Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets()); 204 IndexedDataMapNode* pNode = new (this->myAllocator) IndexedDataMapNode (aKey1, anIndexIter, anItem, myData1[iK1]); 205 myData1[iK1] = pNode; 206 myData2[anIndexIter - 1] = pNode; 207 Increment(); 208 } 209 } 210 return *this; 211 } 212 213 //! Assignment operator operator =(const NCollection_IndexedDataMap & theOther)214 NCollection_IndexedDataMap& operator= (const NCollection_IndexedDataMap& theOther) 215 { 216 return Assign (theOther); 217 } 218 219 //! ReSize ReSize(const Standard_Integer N)220 void ReSize (const Standard_Integer N) 221 { 222 NCollection_ListNode** ppNewData1 = NULL; 223 NCollection_ListNode** ppNewData2 = NULL; 224 Standard_Integer newBuck; 225 if (BeginResize (N, newBuck, ppNewData1, ppNewData2)) 226 { 227 if (myData1) 228 { 229 memcpy (ppNewData2, myData2, sizeof(IndexedDataMapNode*) * Extent()); 230 for (Standard_Integer aBucketIter = 0; aBucketIter <= NbBuckets(); ++aBucketIter) 231 { 232 if (myData1[aBucketIter]) 233 { 234 IndexedDataMapNode* p = (IndexedDataMapNode *) myData1[aBucketIter]; 235 while (p) 236 { 237 const Standard_Integer iK1 = Hasher::HashCode (p->Key1(), newBuck); 238 IndexedDataMapNode* q = (IndexedDataMapNode* )p->Next(); 239 p->Next() = ppNewData1[iK1]; 240 ppNewData1[iK1] = p; 241 p = q; 242 } 243 } 244 } 245 } 246 EndResize (N, newBuck, ppNewData1, ppNewData2); 247 } 248 } 249 250 //! Returns the Index of already bound Key or appends new Key with specified Item value. 251 //! @param theKey1 Key to search (and to bind, if it was not bound already) 252 //! @param theItem Item value to set for newly bound Key; ignored if Key was already bound 253 //! @return index of Key Add(const TheKeyType & theKey1,const TheItemType & theItem)254 Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem) 255 { 256 if (Resizable()) 257 { 258 ReSize(Extent()); 259 } 260 261 const Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets()); 262 IndexedDataMapNode* pNode = (IndexedDataMapNode* )myData1[iK1]; 263 while (pNode) 264 { 265 if (Hasher::IsEqual (pNode->Key1(), theKey1)) 266 { 267 return pNode->Index(); 268 } 269 pNode = (IndexedDataMapNode *) pNode->Next(); 270 } 271 272 const Standard_Integer aNewIndex = Increment(); 273 pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, aNewIndex, theItem, myData1[iK1]); 274 myData1[iK1] = pNode; 275 myData2[aNewIndex - 1] = pNode; 276 return aNewIndex; 277 } 278 279 //! Contains Contains(const TheKeyType & theKey1) const280 Standard_Boolean Contains (const TheKeyType& theKey1) const 281 { 282 if (IsEmpty()) 283 return Standard_False; 284 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets()); 285 IndexedDataMapNode * pNode1; 286 pNode1 = (IndexedDataMapNode *) myData1[iK1]; 287 while (pNode1) 288 { 289 if (Hasher::IsEqual(pNode1->Key1(), theKey1)) 290 return Standard_True; 291 pNode1 = (IndexedDataMapNode *) pNode1->Next(); 292 } 293 return Standard_False; 294 } 295 296 //! Substitute Substitute(const Standard_Integer theIndex,const TheKeyType & theKey1,const TheItemType & theItem)297 void Substitute (const Standard_Integer theIndex, 298 const TheKeyType& theKey1, 299 const TheItemType& theItem) 300 { 301 Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), 302 "NCollection_IndexedDataMap::Substitute : " 303 "Index is out of range"); 304 305 // check if theKey1 is not already in the map 306 const Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets()); 307 IndexedDataMapNode* p = (IndexedDataMapNode *) myData1[iK1]; 308 while (p) 309 { 310 if (Hasher::IsEqual (p->Key1(), theKey1)) 311 { 312 if (p->Index() != theIndex) 313 { 314 throw Standard_DomainError ("NCollection_IndexedDataMap::Substitute : " 315 "Attempt to substitute existing key"); 316 } 317 p->Key1() = theKey1; 318 p->ChangeValue() = theItem; 319 return; 320 } 321 p = (IndexedDataMapNode *) p->Next(); 322 } 323 324 // Find the node for the index I 325 p = (IndexedDataMapNode* )myData2[theIndex - 1]; 326 327 // remove the old key 328 const Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets()); 329 IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK]; 330 if (q == p) 331 myData1[iK] = (IndexedDataMapNode *) p->Next(); 332 else 333 { 334 while (q->Next() != p) 335 q = (IndexedDataMapNode *) q->Next(); 336 q->Next() = p->Next(); 337 } 338 339 // update the node 340 p->Key1() = theKey1; 341 p->ChangeValue() = theItem; 342 p->Next() = myData1[iK1]; 343 myData1[iK1] = p; 344 } 345 346 //! Swaps two elements with the given indices. Swap(const Standard_Integer theIndex1,const Standard_Integer theIndex2)347 void Swap (const Standard_Integer theIndex1, 348 const Standard_Integer theIndex2) 349 { 350 Standard_OutOfRange_Raise_if (theIndex1 < 1 || theIndex1 > Extent() 351 || theIndex2 < 1 || theIndex2 > Extent(), "NCollection_IndexedDataMap::Swap"); 352 353 if (theIndex1 == theIndex2) 354 { 355 return; 356 } 357 358 IndexedDataMapNode* aP1 = (IndexedDataMapNode* )myData2[theIndex1 - 1]; 359 IndexedDataMapNode* aP2 = (IndexedDataMapNode* )myData2[theIndex2 - 1]; 360 std::swap (aP1->Index(), aP2->Index()); 361 myData2[theIndex2 - 1] = aP1; 362 myData2[theIndex1 - 1] = aP2; 363 } 364 365 //! RemoveLast RemoveLast(void)366 void RemoveLast (void) 367 { 368 const Standard_Integer aLastIndex = Extent(); 369 Standard_OutOfRange_Raise_if (aLastIndex == 0, "NCollection_IndexedDataMap::RemoveLast"); 370 371 // Find the node for the last index and remove it 372 IndexedDataMapNode* p = (IndexedDataMapNode* )myData2[aLastIndex - 1]; 373 myData2[aLastIndex - 1] = NULL; 374 375 // remove the key 376 const Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets()); 377 IndexedDataMapNode* q = (IndexedDataMapNode *) myData1[iK1]; 378 if (q == p) 379 myData1[iK1] = (IndexedDataMapNode *) p->Next(); 380 else 381 { 382 while (q->Next() != p) 383 q = (IndexedDataMapNode *) q->Next(); 384 q->Next() = p->Next(); 385 } 386 p->~IndexedDataMapNode(); 387 this->myAllocator->Free(p); 388 Decrement(); 389 } 390 391 //! Remove the key of the given index. 392 //! Caution! The index of the last key can be changed. RemoveFromIndex(const Standard_Integer theIndex)393 void RemoveFromIndex(const Standard_Integer theIndex) 394 { 395 const Standard_Integer aLastInd = Extent(); 396 Standard_OutOfRange_Raise_if(theIndex < 1 || theIndex > aLastInd, "NCollection_IndexedDataMap::Remove"); 397 if (theIndex != aLastInd) 398 { 399 Swap (theIndex, aLastInd); 400 } 401 RemoveLast(); 402 } 403 404 //! Remove the given key. 405 //! Caution! The index of the last key can be changed. RemoveKey(const TheKeyType & theKey1)406 void RemoveKey(const TheKeyType& theKey1) 407 { 408 Standard_Integer anIndToRemove = FindIndex(theKey1); 409 if (anIndToRemove > 0) { 410 RemoveFromIndex(anIndToRemove); 411 } 412 } 413 414 //! FindKey FindKey(const Standard_Integer theIndex) const415 const TheKeyType& FindKey (const Standard_Integer theIndex) const 416 { 417 Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::FindKey"); 418 IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1]; 419 return aNode->Key1(); 420 } 421 422 //! FindFromIndex FindFromIndex(const Standard_Integer theIndex) const423 const TheItemType& FindFromIndex (const Standard_Integer theIndex) const 424 { 425 Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::FindFromIndex"); 426 IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1]; 427 return aNode->Value(); 428 } 429 430 //! operator () operator ()(const Standard_Integer theIndex) const431 const TheItemType& operator() (const Standard_Integer theIndex) const { return FindFromIndex (theIndex); } 432 433 //! ChangeFromIndex ChangeFromIndex(const Standard_Integer theIndex)434 TheItemType& ChangeFromIndex (const Standard_Integer theIndex) 435 { 436 Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::ChangeFromIndex"); 437 IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1]; 438 return aNode->ChangeValue(); 439 } 440 441 //! operator () operator ()(const Standard_Integer theIndex)442 TheItemType& operator() (const Standard_Integer theIndex) { return ChangeFromIndex (theIndex); } 443 444 //! FindIndex FindIndex(const TheKeyType & theKey1) const445 Standard_Integer FindIndex(const TheKeyType& theKey1) const 446 { 447 if (IsEmpty()) return 0; 448 IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())]; 449 while (pNode1) 450 { 451 if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 452 { 453 return pNode1->Index(); 454 } 455 pNode1 = (IndexedDataMapNode*) pNode1->Next(); 456 } 457 return 0; 458 } 459 460 //! FindFromKey FindFromKey(const TheKeyType & theKey1) const461 const TheItemType& FindFromKey(const TheKeyType& theKey1) const 462 { 463 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::FindFromKey"); 464 465 IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())]; 466 while (pNode1) 467 { 468 if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 469 { 470 return pNode1->Value(); 471 } 472 pNode1 = (IndexedDataMapNode*) pNode1->Next(); 473 } 474 throw Standard_NoSuchObject("NCollection_IndexedDataMap::FindFromKey"); 475 } 476 477 //! ChangeFromKey ChangeFromKey(const TheKeyType & theKey1)478 TheItemType& ChangeFromKey (const TheKeyType& theKey1) 479 { 480 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::ChangeFromKey"); 481 482 IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())]; 483 while (pNode1) 484 { 485 if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 486 { 487 return pNode1->ChangeValue(); 488 } 489 pNode1 = (IndexedDataMapNode*) pNode1->Next(); 490 } 491 throw Standard_NoSuchObject("NCollection_IndexedDataMap::ChangeFromKey"); 492 } 493 494 //! Seek returns pointer to Item by Key. Returns 495 //! NULL if Key was not found. Seek(const TheKeyType & theKey1) const496 const TheItemType* Seek(const TheKeyType& theKey1) const 497 { 498 return const_cast< NCollection_IndexedDataMap * >( this )->ChangeSeek(theKey1); 499 //NCollection_IndexedDataMap *pMap=(NCollection_IndexedDataMap *)this; 500 //return pMap->ChangeSeek(theKey1); 501 } 502 503 //! ChangeSeek returns modifiable pointer to Item by Key. Returns 504 //! NULL if Key was not found. ChangeSeek(const TheKeyType & theKey1)505 TheItemType* ChangeSeek (const TheKeyType& theKey1) 506 { 507 if (!IsEmpty()) 508 { 509 IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())]; 510 while (pNode1) 511 { 512 if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 513 { 514 return &pNode1->ChangeValue(); 515 } 516 pNode1 = (IndexedDataMapNode*) pNode1->Next(); 517 } 518 } 519 return 0L; 520 } 521 522 //! Find value for key with copying. 523 //! @return true if key was found FindFromKey(const TheKeyType & theKey1,TheItemType & theValue) const524 Standard_Boolean FindFromKey (const TheKeyType& theKey1, 525 TheItemType& theValue) const 526 { 527 if (IsEmpty()) 528 { 529 return Standard_False; 530 } 531 for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData1[Hasher::HashCode (theKey1, NbBuckets())]; 532 aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next()) 533 { 534 if (Hasher::IsEqual (aNode->Key1(), theKey1)) 535 { 536 theValue = aNode->Value(); 537 return Standard_True; 538 } 539 } 540 return Standard_False; 541 } 542 543 //! Clear data. If doReleaseMemory is false then the table of 544 //! buckets is not released and will be reused. Clear(const Standard_Boolean doReleaseMemory=Standard_True)545 void Clear(const Standard_Boolean doReleaseMemory = Standard_True) 546 { Destroy (IndexedDataMapNode::delNode, doReleaseMemory); } 547 548 //! Clear data and reset allocator Clear(const Handle (NCollection_BaseAllocator)& theAllocator)549 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) 550 { 551 Clear(); 552 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : 553 NCollection_BaseAllocator::CommonBaseAllocator() ); 554 } 555 556 //! Destructor ~NCollection_IndexedDataMap(void)557 virtual ~NCollection_IndexedDataMap (void) 558 { Clear(); } 559 560 //! Size Size(void) const561 Standard_Integer Size(void) const 562 { return Extent(); } 563 564 private: 565 // ----------- PRIVATE METHODS ----------- 566 567 }; 568 569 #endif 570