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_DoubleMap_HeaderFile 17 #define NCollection_DoubleMap_HeaderFile 18 19 #include <NCollection_TypeDef.hxx> 20 #include <NCollection_BaseMap.hxx> 21 #include <NCollection_TListNode.hxx> 22 #include <Standard_TypeMismatch.hxx> 23 #include <Standard_MultiplyDefined.hxx> 24 #include <Standard_ImmutableObject.hxx> 25 #include <Standard_NoSuchObject.hxx> 26 27 #include <NCollection_DefaultHasher.hxx> 28 29 /** 30 * Purpose: The DoubleMap is used to bind pairs (Key1,Key2) 31 * and retrieve them in linear time. 32 * 33 * See Map from NCollection for a discussion about the number 34 * of buckets 35 */ 36 37 template < class TheKey1Type, 38 class TheKey2Type, 39 class Hasher1 = NCollection_DefaultHasher<TheKey1Type>, 40 class Hasher2 = NCollection_DefaultHasher<TheKey2Type> > 41 class NCollection_DoubleMap : public NCollection_BaseMap 42 { 43 public: 44 //! STL-compliant typedef for key1 type 45 typedef TheKey1Type key1_type; 46 //! STL-compliant typedef for key2 type 47 typedef TheKey2Type key2_type; 48 49 public: 50 // **************** Adaptation of the TListNode to the DOUBLEmap 51 class DoubleMapNode : public NCollection_TListNode<TheKey2Type> 52 { 53 public: 54 //! Constructor with 'Next' DoubleMapNode(const TheKey1Type & theKey1,const TheKey2Type & theKey2,NCollection_ListNode * theNext1,NCollection_ListNode * theNext2)55 DoubleMapNode (const TheKey1Type& theKey1, 56 const TheKey2Type& theKey2, 57 NCollection_ListNode* theNext1, 58 NCollection_ListNode* theNext2) : 59 NCollection_TListNode<TheKey2Type> (theKey2, theNext1), 60 myKey1(theKey1), 61 myNext2((DoubleMapNode*)theNext2) 62 { 63 } 64 //! Key1 Key1(void)65 const TheKey1Type& Key1 (void) 66 { return myKey1; } 67 //! Key2 Key2(void)68 const TheKey2Type& Key2 (void) 69 { return this->myValue; } 70 //! Next2 Next2(void)71 DoubleMapNode*& Next2 (void) 72 { return myNext2; } 73 74 //! Static deleter to be passed to BaseList delNode(NCollection_ListNode * theNode,Handle (NCollection_BaseAllocator)& theAl)75 static void delNode (NCollection_ListNode * theNode, 76 Handle(NCollection_BaseAllocator)& theAl) 77 { 78 ((DoubleMapNode *) theNode)->~DoubleMapNode(); 79 theAl->Free(theNode); 80 } 81 82 private: 83 TheKey1Type myKey1; 84 DoubleMapNode *myNext2; 85 }; 86 87 public: 88 // **************** Implementation of the Iterator interface. 89 class Iterator : public NCollection_BaseMap::Iterator 90 { 91 public: 92 //! Empty constructor Iterator(void)93 Iterator (void) {} 94 //! Constructor Iterator(const NCollection_DoubleMap & theMap)95 Iterator (const NCollection_DoubleMap& theMap) : 96 NCollection_BaseMap::Iterator(theMap) {} 97 //! Query if the end of collection is reached by iterator More(void) const98 Standard_Boolean More(void) const 99 { return PMore(); } 100 //! Make a step along the collection Next(void)101 void Next(void) 102 { PNext(); } 103 //! Key1 inquiry Key1(void) const104 const TheKey1Type& Key1(void) const 105 { 106 Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key1"); 107 return ((DoubleMapNode *) myNode)->Key1(); 108 } 109 //! Key2 inquiry Key2(void) const110 const TheKey2Type& Key2(void) const 111 { 112 Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key2"); 113 return ((DoubleMapNode *) myNode)->Key2(); 114 } 115 //! Value access Value(void) const116 const TheKey2Type& Value(void) const 117 { 118 Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Value"); 119 return ((DoubleMapNode *) myNode)->Value(); 120 } 121 }; 122 123 public: 124 // ---------- PUBLIC METHODS ------------ 125 126 //! Empty constructor. NCollection_DoubleMap()127 NCollection_DoubleMap() : NCollection_BaseMap (1, Standard_False, Handle(NCollection_BaseAllocator)()) {} 128 129 //! Constructor NCollection_DoubleMap(const Standard_Integer theNbBuckets,const Handle (NCollection_BaseAllocator)& theAllocator=0L)130 explicit NCollection_DoubleMap (const Standard_Integer theNbBuckets, 131 const Handle(NCollection_BaseAllocator)& theAllocator = 0L) 132 : NCollection_BaseMap (theNbBuckets, Standard_False, theAllocator) {} 133 134 //! Copy constructor NCollection_DoubleMap(const NCollection_DoubleMap & theOther)135 NCollection_DoubleMap (const NCollection_DoubleMap& theOther) 136 : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator) 137 { *this = theOther; } 138 139 //! Exchange the content of two maps without re-allocations. 140 //! Notice that allocators will be swapped as well! Exchange(NCollection_DoubleMap & theOther)141 void Exchange (NCollection_DoubleMap& theOther) 142 { 143 this->exchangeMapsData (theOther); 144 } 145 146 //! Assignment. 147 //! This method does not change the internal allocator. Assign(const NCollection_DoubleMap & theOther)148 NCollection_DoubleMap& Assign (const NCollection_DoubleMap& theOther) 149 { 150 if (this == &theOther) 151 return *this; 152 153 Clear(); 154 Standard_Integer anExt = theOther.Extent(); 155 if (anExt) 156 { 157 ReSize (anExt-1); 158 Iterator anIter(theOther); 159 for (; anIter.More(); anIter.Next()) 160 { 161 TheKey1Type aKey1 = anIter.Key1(); 162 TheKey2Type aKey2 = anIter.Key2(); 163 Standard_Integer iK1 = Hasher1::HashCode (aKey1, NbBuckets()); 164 Standard_Integer iK2 = Hasher2::HashCode (aKey2, NbBuckets()); 165 DoubleMapNode * pNode = new (this->myAllocator) DoubleMapNode (aKey1, aKey2, 166 myData1[iK1], 167 myData2[iK2]); 168 myData1[iK1] = pNode; 169 myData2[iK2] = pNode; 170 Increment(); 171 } 172 } 173 return *this; 174 } 175 176 //! Assignment operator operator =(const NCollection_DoubleMap & theOther)177 NCollection_DoubleMap& operator= (const NCollection_DoubleMap& theOther) 178 { 179 return Assign (theOther); 180 } 181 182 //! ReSize ReSize(const Standard_Integer N)183 void ReSize (const Standard_Integer N) 184 { 185 NCollection_ListNode** ppNewData1 = NULL; 186 NCollection_ListNode** ppNewData2 = NULL; 187 Standard_Integer newBuck; 188 if (BeginResize (N, newBuck, ppNewData1, ppNewData2)) 189 { 190 if (myData1) 191 { 192 DoubleMapNode *p, *q; 193 Standard_Integer i, iK1, iK2; 194 for (i = 0; i <= NbBuckets(); i++) 195 { 196 if (myData1[i]) 197 { 198 p = (DoubleMapNode *) myData1[i]; 199 while (p) 200 { 201 iK1 = Hasher1::HashCode (p->Key1(), newBuck); 202 iK2 = Hasher2::HashCode (p->Key2(), newBuck); 203 q = (DoubleMapNode*) p->Next(); 204 p->Next() = ppNewData1[iK1]; 205 p->Next2() = (DoubleMapNode*)ppNewData2[iK2]; 206 ppNewData1[iK1] = p; 207 ppNewData2[iK2] = p; 208 p = q; 209 } 210 } 211 } 212 } 213 EndResize (N, newBuck, ppNewData1, ppNewData2); 214 } 215 } 216 217 //! Bind Bind(const TheKey1Type & theKey1,const TheKey2Type & theKey2)218 void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2) 219 { 220 if (Resizable()) 221 ReSize(Extent()); 222 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); 223 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); 224 DoubleMapNode * pNode; 225 pNode = (DoubleMapNode *) myData1[iK1]; 226 while (pNode) 227 { 228 if (Hasher1::IsEqual (pNode->Key1(), theKey1)) 229 throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind"); 230 pNode = (DoubleMapNode *) pNode->Next(); 231 } 232 pNode = (DoubleMapNode *) myData2[iK2]; 233 while (pNode) 234 { 235 if (Hasher2::IsEqual (pNode->Key2(), theKey2)) 236 throw Standard_MultiplyDefined("NCollection_DoubleMap:Bind"); 237 pNode = (DoubleMapNode *) pNode->Next(); 238 } 239 pNode = new (this->myAllocator) DoubleMapNode (theKey1, theKey2, 240 myData1[iK1], myData2[iK2]); 241 myData1[iK1] = pNode; 242 myData2[iK2] = pNode; 243 Increment(); 244 } 245 246 //!* AreBound AreBound(const TheKey1Type & theKey1,const TheKey2Type & theKey2) const247 Standard_Boolean AreBound (const TheKey1Type& theKey1, 248 const TheKey2Type& theKey2) const 249 { 250 if (IsEmpty()) 251 return Standard_False; 252 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); 253 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); 254 DoubleMapNode * pNode1, * pNode2; 255 pNode1 = (DoubleMapNode *) myData1[iK1]; 256 while (pNode1) 257 { 258 if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) 259 break; 260 pNode1 = (DoubleMapNode *) pNode1->Next(); 261 } 262 if (pNode1 == NULL) 263 return Standard_False; 264 pNode2 = (DoubleMapNode *) myData2[iK2]; 265 while (pNode2) 266 { 267 if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) 268 break; 269 pNode2 = (DoubleMapNode *) pNode2->Next(); 270 } 271 if (pNode2 == NULL) 272 return Standard_False; 273 274 return (pNode1 == pNode2); 275 } 276 277 //! IsBound1 IsBound1(const TheKey1Type & theKey1) const278 Standard_Boolean IsBound1 (const TheKey1Type& theKey1) const 279 { 280 if (IsEmpty()) 281 return Standard_False; 282 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); 283 DoubleMapNode * pNode1; 284 pNode1 = (DoubleMapNode *) myData1[iK1]; 285 while (pNode1) 286 { 287 if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) 288 return Standard_True; 289 pNode1 = (DoubleMapNode *) pNode1->Next(); 290 } 291 return Standard_False; 292 } 293 294 //! IsBound2 IsBound2(const TheKey2Type & theKey2) const295 Standard_Boolean IsBound2 (const TheKey2Type& theKey2) const 296 { 297 if (IsEmpty()) 298 return Standard_False; 299 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); 300 DoubleMapNode * pNode2; 301 pNode2 = (DoubleMapNode *) myData2[iK2]; 302 while (pNode2) 303 { 304 if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) 305 return Standard_True; 306 pNode2 = (DoubleMapNode *) pNode2->Next2(); 307 } 308 return Standard_False; 309 } 310 311 //! UnBind1 UnBind1(const TheKey1Type & theKey1)312 Standard_Boolean UnBind1 (const TheKey1Type& theKey1) 313 { 314 if (IsEmpty()) 315 return Standard_False; 316 Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); 317 DoubleMapNode * p1, * p2, * q1, *q2; 318 q1 = q2 = NULL; 319 p1 = (DoubleMapNode *) myData1[iK1]; 320 while (p1) 321 { 322 if (Hasher1::IsEqual (p1->Key1(), theKey1)) 323 { 324 // remove from the data1 325 if (q1) 326 q1->Next() = p1->Next(); 327 else 328 myData1[iK1] = (DoubleMapNode*) p1->Next(); 329 Standard_Integer iK2 = Hasher2::HashCode (p1->Key2(), NbBuckets()); 330 p2 = (DoubleMapNode *) myData2[iK2]; 331 while (p2) 332 { 333 if (p2 == p1) 334 { 335 // remove from the data2 336 if (q2) 337 q2->Next2() = p2->Next2(); 338 else 339 myData2[iK2] = (DoubleMapNode*) p2->Next2(); 340 break; 341 } 342 q2 = p2; 343 p2 = (DoubleMapNode*) p2->Next2(); 344 } 345 p1->~DoubleMapNode(); 346 this->myAllocator->Free(p1); 347 Decrement(); 348 return Standard_True; 349 } 350 q1 = p1; 351 p1 = (DoubleMapNode*) p1->Next(); 352 } 353 return Standard_False; 354 } 355 356 //! UnBind2 UnBind2(const TheKey2Type & theKey2)357 Standard_Boolean UnBind2 (const TheKey2Type& theKey2) 358 { 359 if (IsEmpty()) 360 return Standard_False; 361 Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); 362 DoubleMapNode * p1, * p2, * q1, *q2; 363 q1 = q2 = NULL; 364 p2 = (DoubleMapNode *) myData2[iK2]; 365 while (p2) 366 { 367 if (Hasher2::IsEqual (p2->Key2(), theKey2)) 368 { 369 // remove from the data2 370 if (q2) 371 q2->Next() = p2->Next(); 372 else 373 myData2[iK2] = (DoubleMapNode*) p2->Next2(); 374 Standard_Integer iK1 = Hasher1::HashCode (p2->Key1(), NbBuckets()); 375 p1 = (DoubleMapNode *) myData1[iK1]; 376 while (p1) 377 { 378 if (p1 == p2) 379 { 380 // remove from the data1 381 if (q1) 382 q1->Next() = p1->Next(); 383 else 384 myData1[iK1] = (DoubleMapNode*) p1->Next(); 385 break; 386 } 387 q1 = p1; 388 p1 = (DoubleMapNode*) p1->Next(); 389 } 390 p2->~DoubleMapNode(); 391 this->myAllocator->Free(p2); 392 Decrement(); 393 return Standard_True; 394 } 395 q2 = p2; 396 p2 = (DoubleMapNode*) p2->Next2(); 397 } 398 return Standard_False; 399 } 400 401 //! Find the Key1 and return Key2 value. 402 //! Raises an exception if Key1 was not bound. Find1(const TheKey1Type & theKey1) const403 const TheKey2Type& Find1(const TheKey1Type& theKey1) const 404 { 405 if (const TheKey2Type* aKey2 = Seek1 (theKey1)) 406 { 407 return *aKey2; 408 } 409 throw Standard_NoSuchObject("NCollection_DoubleMap::Find1"); 410 } 411 412 //! Find the Key1 and return Key2 value (by copying its value). 413 //! @param [in] theKey1 Key1 to find 414 //! @param [out] theKey2 Key2 to return 415 //! @return TRUE if Key1 has been found Find1(const TheKey1Type & theKey1,TheKey2Type & theKey2) const416 Standard_Boolean Find1 (const TheKey1Type& theKey1, 417 TheKey2Type& theKey2) const 418 { 419 if (const TheKey2Type* aKey2 = Seek1 (theKey1)) 420 { 421 theKey2 = *aKey2; 422 return true; 423 } 424 return false; 425 } 426 427 //! Find the Key1 and return pointer to Key2 or NULL if Key1 is not bound. 428 //! @param [in] theKey1 Key1 to find 429 //! @return pointer to Key2 or NULL if Key1 is not found Seek1(const TheKey1Type & theKey1) const430 const TheKey2Type* Seek1 (const TheKey1Type& theKey1) const 431 { 432 for (DoubleMapNode* aNode1 = !IsEmpty() ? (DoubleMapNode* )myData1[Hasher1::HashCode (theKey1, NbBuckets())] : NULL; 433 aNode1 != NULL; aNode1 = (DoubleMapNode* )aNode1->Next()) 434 { 435 if (Hasher1::IsEqual (aNode1->Key1(), theKey1)) 436 { 437 return &aNode1->Key2(); 438 } 439 } 440 return NULL; 441 } 442 443 //! Find the Key2 and return Key1 value. 444 //! Raises an exception if Key2 was not bound. Find2(const TheKey2Type & theKey2) const445 const TheKey1Type& Find2(const TheKey2Type& theKey2) const 446 { 447 if (const TheKey1Type* aVal1 = Seek2 (theKey2)) 448 { 449 return *aVal1; 450 } 451 throw Standard_NoSuchObject("NCollection_DoubleMap::Find2"); 452 } 453 454 //! Find the Key2 and return Key1 value (by copying its value). 455 //! @param [in] theKey2 Key2 to find 456 //! @param [out] theKey1 Key1 to return 457 //! @return TRUE if Key2 has been found Find2(const TheKey2Type & theKey2,TheKey1Type & theKey1) const458 Standard_Boolean Find2 (const TheKey2Type& theKey2, 459 TheKey1Type& theKey1) const 460 { 461 if (const TheKey1Type* aVal1 = Seek2 (theKey2)) 462 { 463 theKey1 = *aVal1; 464 return Standard_True; 465 } 466 return Standard_False; 467 } 468 469 //! Find the Key2 and return pointer to Key1 or NULL if not bound. 470 //! @param [in] theKey2 Key2 to find 471 //! @return pointer to Key1 if Key2 has been found Seek2(const TheKey2Type & theKey2) const472 const TheKey1Type* Seek2 (const TheKey2Type& theKey2) const 473 { 474 for (DoubleMapNode* aNode2 = !IsEmpty() ? (DoubleMapNode* )myData2[Hasher2::HashCode (theKey2, NbBuckets())] : NULL; 475 aNode2 != NULL; aNode2 = (DoubleMapNode* )aNode2->Next2()) 476 { 477 if (Hasher2::IsEqual (aNode2->Key2(), theKey2)) 478 { 479 return &aNode2->Key1(); 480 } 481 } 482 return NULL; 483 } 484 485 //! Clear data. If doReleaseMemory is false then the table of 486 //! buckets is not released and will be reused. Clear(const Standard_Boolean doReleaseMemory=Standard_True)487 void Clear(const Standard_Boolean doReleaseMemory = Standard_True) 488 { Destroy (DoubleMapNode::delNode, doReleaseMemory); } 489 490 //! Clear data and reset allocator Clear(const Handle (NCollection_BaseAllocator)& theAllocator)491 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) 492 { 493 Clear(); 494 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : 495 NCollection_BaseAllocator::CommonBaseAllocator() ); 496 } 497 498 //! Destructor ~NCollection_DoubleMap(void)499 ~NCollection_DoubleMap (void) 500 { Clear(); } 501 502 //! Size Size(void) const503 Standard_Integer Size(void) const 504 { return Extent(); } 505 }; 506 507 #endif 508