src/TColStd/TColStd_PackedMapOfInteger.cxx

   1 // Created on: 2005-11-05
   2 // Created by: Alexander GRIGORIEV
   3 // Copyright (c) 2005-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 #include <TColStd_PackedMapOfInteger.hxx>
  17 #include <TColStd_MapIteratorOfPackedMapOfInteger.hxx>
  18 #include <TCollection_MapNode.hxx>
  19 #include <Standard_DefineHandle.hxx>
  20
  21 // 5 lower bits
  22 #define MASK_LOW  0x001f
  23 // 27 upper bits
  24 #define MASK_HIGH (~MASK_LOW)
  25
  26 /**
  27  * Class implementing a block of 32 consecutive integer values as a node of
  28  * a Map collection. The data are stored in 64 bits as:
  29  * - bits  0 - 4 : (number of integers stored in the block) - 1;
  30  * - bits  5 - 31: base address of the block of integers (low bits assumed 0)
  31  * - bits 32 - 63: 32-bit field where each bit indicates the presence of the
  32  *                 corresponding integer in the block. Number of non-zero bits
  33  *                 must be equal to the number expressed in bits 0-4.
  34  */
  35 class TColStd_intMapNode : public TCollection_MapNode
  36 {
  37 public:
  38   inline TColStd_intMapNode (TCollection_MapNode * ptr = 0L)
  39     : TCollection_MapNode       (ptr),
  40       myMask                    (0),
  41       myData                    (0) {}
  42
  43   inline TColStd_intMapNode (const Standard_Integer theValue,
  44                              TCollection_MapNode *& ptr)
  45     : TCollection_MapNode (ptr),
  46       myMask              ((unsigned int) (theValue & MASK_HIGH)),
  47       myData              (1 << (theValue & MASK_LOW)) {}
  48
  49   inline TColStd_intMapNode (unsigned int        theMask,
  50                              unsigned int        theData,
  51                              TCollection_MapNode * ptr)
  52     : TCollection_MapNode (ptr),
  53       myMask              (theMask),
  54       myData              (theData) {}
  55
  56   inline unsigned int           Mask        () const
  57   { return myMask; }
  58
  59   inline unsigned int           Data        () const
  60   { return myData; }
  61
  62   inline unsigned int&          ChangeMask  ()
  63   { return myMask; }
  64
  65   inline unsigned int&          ChangeData  ()
  66   { return myData; }
  67
  68   inline Standard_Integer       Key         () const
  69   { return Standard_Integer (myMask & MASK_HIGH); }
  70
  71   inline size_t                 NbValues    () const
  72   { return size_t(myMask & MASK_LOW) + 1; }
  73
  74   inline Standard_Boolean       HasValues   () const
  75   { return (myData != 0); }
  76
  77   Standard_Integer              HasValue (const Standard_Integer theValue) const
  78   { return (myData & (1 << (theValue & MASK_LOW))); }
  79
  80   Standard_Boolean              AddValue (const Standard_Integer theValue);
  81
  82   Standard_Boolean              DelValue (const Standard_Integer theValue);
  83
  84   /**
  85    * Find the smallest non-zero bit under the given mask. Outputs the new mask
  86    * that does not contain the detected bit.
  87    */
  88   Standard_Integer              FindNext (unsigned int& theMask) const;
  89
  90   /**
  91    * Support of Map interface.
  92    */
  93   inline Standard_Integer       HashCode (const Standard_Integer theUpper) const
  94   {
  95     return ::HashCode (Standard_Integer(myMask >> 5), theUpper);
  96   }
  97
  98   /**
  99    * Support of Map interface.
 100    */
 101   inline Standard_Boolean       IsEqual  (const Standard_Integer theOther) const
 102   {
 103     return ((myMask >> 5) == (unsigned)theOther);
 104   }
 105
 106   /**
 107    * Local friend function, used in TColStd_MapIteratorOfPackedMapOfInteger.
 108    */
 109   friend Standard_Integer TColStd_intMapNode_findNext(const TColStd_intMapNode*,
 110                                                       unsigned int& );
 111
 112   /**
 113    * Local friend function.
 114    */
 115   friend Standard_Integer TColStd_intMapNode_findPrev(const TColStd_intMapNode*,
 116                                                       unsigned int& );
 117
 118 private:
 119   unsigned int      myMask;
 120   unsigned int      myData;
 121 };
 122
 123
 124 //=======================================================================
 125 //function : TColStd_intMapNode::AddValue
 126 //purpose  :
 127 //=======================================================================
 128
 129 Standard_Boolean TColStd_intMapNode::AddValue (const Standard_Integer theValue)
 130 {
 131   Standard_Boolean aResult (Standard_False);
 132   const Standard_Integer aValInt = (1 << (theValue & MASK_LOW));
 133   if ((myData & aValInt) == 0) {
 134     myData ^= aValInt;
 135     myMask++;
 136     aResult = Standard_True;
 137   }
 138   return aResult;
 139 }
 140
 141 //=======================================================================
 142 //function : TColStd_intMapNode::DelValue
 143 //purpose  :
 144 //=======================================================================
 145
 146 Standard_Boolean TColStd_intMapNode::DelValue (const Standard_Integer theValue)
 147 {
 148   Standard_Boolean aResult (Standard_False);
 149   const Standard_Integer aValInt = (1 << (theValue & MASK_LOW));
 150   if ((myData & aValInt) != 0) {
 151     myData ^= aValInt;
 152     myMask--;
 153     aResult = Standard_True;
 154   }
 155   return aResult;
 156 }
 157
 158 //=======================================================================
 159 //function : TColStd_Population
 160 //purpose  : Compute the population (i.e., the number of non-zero bits) of
 161 //           the 32-bit word theData. The population is stored decremented
 162 //           as it is defined in TColStd_intMapNode.
 163 //source   : H.S.Warren, Hacker''s Delight, Addison-Wesley Inc. 2002, Ch.5.1
 164 //=======================================================================
 165
 166 inline size_t TColStd_Population (unsigned int&      theMask,
 167                                   const unsigned int theData)
 168 {
 169   unsigned int aRes = theData - ((theData>>1) & 0x55555555);
 170   aRes  = (aRes & 0x33333333) + ((aRes>>2)    & 0x33333333);
 171   aRes  = (aRes + (aRes>>4)) & 0x0f0f0f0f;
 172   aRes = aRes + (aRes>>8);
 173   aRes = aRes + (aRes>>16);
 174   theMask = (theMask & MASK_HIGH) | ((aRes-1) & MASK_LOW);
 175   return (size_t) (aRes & 0x3f);
 176 }
 177
 178 //=======================================================================
 179 //function : TColStd_intMapNode_findNext
 180 //purpose  : Find the smallest non-zero bit under the given mask. Outputs
 181 //           the new mask that does not contain the detected bit.
 182 //=======================================================================
 183
 184 Standard_Integer TColStd_intMapNode_findNext (const TColStd_intMapNode* theNode,
 185                                               unsigned int&             theMask)
 186 {
 187   unsigned int val = theNode->myData & theMask;
 188   int nZeros (0);
 189   if (val == 0)
 190     theMask = ~0U;   // void, nothing to do
 191   else{
 192     unsigned int aMask = ~0U;
 193     if ((val & 0x0000ffff) == 0) {
 194       aMask = 0xffff0000;
 195       nZeros = 16;
 196       val >>= 16;
 197     }
 198     if ((val & 0x000000ff) == 0) {
 199       aMask <<= 8;
 200       nZeros += 8;
 201       val >>= 8;
 202     }
 203     if ((val & 0x0000000f) == 0) {
 204       aMask <<= 4;
 205       nZeros += 4;
 206       val >>= 4;
 207     }
 208     if ((val & 0x00000003) == 0) {
 209       aMask <<= 2;
 210       nZeros += 2;
 211       val >>= 2;
 212     }
 213     if ((val & 0x00000001) == 0) {
 214       aMask <<= 1;
 215       nZeros ++;
 216     }
 217     theMask = (aMask << 1);
 218   }
 219   return nZeros + theNode->Key();
 220 }
 221
 222 //=======================================================================
 223 //function : TColStd_intMapNode_findPrev
 224 //purpose  : Find the highest non-zero bit under the given mask. Outputs
 225 //           the new mask that does not contain the detected bit.
 226 //=======================================================================
 227
 228 Standard_Integer TColStd_intMapNode_findPrev (const TColStd_intMapNode* theNode,
 229                                               unsigned int&             theMask)
 230 {
 231   unsigned int val = theNode->myData & theMask;
 232   int nZeros (0);
 233   if (val == 0)
 234     theMask = ~0U;   // void, nothing to do
 235   else {
 236     unsigned int aMask = ~0U;
 237     if ((val & 0xffff0000) == 0) {
 238       aMask = 0x0000ffff;
 239       nZeros = 16;
 240       val <<= 16;
 241     }
 242     if ((val & 0xff000000) == 0) {
 243       aMask >>= 8;
 244       nZeros += 8;
 245       val <<= 8;
 246     }
 247     if ((val & 0xf0000000) == 0) {
 248       aMask >>= 4;
 249       nZeros += 4;
 250       val <<= 4;
 251     }
 252     if ((val & 0xc0000000) == 0) {
 253       aMask >>= 2;
 254       nZeros += 2;
 255       val <<= 2;
 256     }
 257     if ((val & 0x80000000) == 0) {
 258       aMask >>= 1;
 259       nZeros ++;
 260     }
 261     theMask = (aMask >> 1);
 262   }
 263   return (31 - nZeros) + theNode->Key();
 264 }
 265
 266 //=======================================================================
 267 //function : Assign
 268 //purpose  :
 269 //=======================================================================
 270
 271 TColStd_PackedMapOfInteger& TColStd_PackedMapOfInteger::Assign
 272                                   (const TColStd_PackedMapOfInteger& theOther)
 273 {
 274   if (this != &theOther) {
 275     Clear();
 276     if  (!theOther.IsEmpty()) {
 277       ReSize (theOther.InternalExtent());
 278       const Standard_Integer nBucketsSrc = theOther.NbBuckets();
 279       const Standard_Integer nBuckets    = NbBuckets();
 280       const TColStd_intMapNode** aDataSrc =
 281         (const TColStd_intMapNode**) theOther.myData1;
 282       TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
 283       for (Standard_Integer i = 0; i <= nBucketsSrc; i++) {
 284         const TColStd_intMapNode * p = aDataSrc[i];
 285         while (p) {
 286           const Standard_Integer aHashCode = p->HashCode(nBuckets);
 287           aData[aHashCode] =
 288             new TColStd_intMapNode (p->Mask(), p->Data(), aData[aHashCode]);
 289           Increment();
 290           p = reinterpret_cast <const TColStd_intMapNode*> (p->Next());
 291         }
 292       }
 293 //       TColStd_MapIteratorOfPackedMapOfInteger anIt (theOther);
 294 //       for (; anIt.More(); anIt.Next())
 295 //         Add (anIt.Key());
 296     }
 297   }
 298   myExtent  = theOther.myExtent;
 299   return * this;
 300 }
 301
 302 //=======================================================================
 303 //function : ReSize
 304 //purpose  :
 305 //=======================================================================
 306
 307 void TColStd_PackedMapOfInteger::ReSize (const Standard_Integer nbBuckets)
 308 {
 309   Standard_Integer newBuck;
 310   Standard_Address newData1=NULL, dummy=NULL;
 311   if (BeginResize (nbBuckets, newBuck, newData1, dummy))
 312   {
 313     if (myData1) {
 314       TColStd_intMapNode** newdata =
 315         reinterpret_cast <TColStd_intMapNode**> (newData1);
 316       TColStd_intMapNode** olddata =
 317         reinterpret_cast <TColStd_intMapNode**> (myData1);
 318       TColStd_intMapNode * p;
 319       Standard_Integer i,k;
 320       for (i = 0; i <= NbBuckets(); i++) {
 321         if (olddata[i]) {
 322           p = olddata[i];
 323           while (p) {
 324             k = p->HashCode(newBuck);
 325             TCollection_MapNode * q = p->Next();
 326             p->Next() = newdata[k];
 327             newdata[k] = p;
 328             p = static_cast <TColStd_intMapNode*> (q);
 329           }
 330         }
 331       }
 332     }
 333     EndResize (nbBuckets, newBuck, newData1, dummy);
 334   }
 335 }
 336
 337 //=======================================================================
 338 //function : Clear
 339 //purpose  :
 340 //=======================================================================
 341
 342 void TColStd_PackedMapOfInteger::Clear ()
 343 {
 344   if (!IsEmpty()) {
 345     Standard_Integer i;
 346     TColStd_intMapNode** data =
 347       reinterpret_cast <TColStd_intMapNode**> (myData1);
 348     TColStd_intMapNode * p;
 349     for (i = 0; i <= NbBuckets(); i++) {
 350       if (data[i]) {
 351         p = data[i];
 352         while (p) {
 353           TCollection_MapNode * q = p->Next();
 354           delete p;
 355           p = static_cast <TColStd_intMapNode*> (q);
 356         }
 357       }
 358     }
 359   }
 360   TCollection_BasicMap::Destroy();
 361   myExtent = 0;
 362 }
 363
 364 //=======================================================================
 365 //function : Add
 366 //purpose  :
 367 //=======================================================================
 368
 369 Standard_Boolean TColStd_PackedMapOfInteger::Add (const Standard_Integer aKey)
 370 {
 371   if (Resizable())
 372     ReSize(InternalExtent());
 373   Standard_Boolean aResult (Standard_False);
 374   TColStd_intMapNode  ** data =
 375     reinterpret_cast <TColStd_intMapNode**> (myData1);
 376   const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
 377   const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
 378   TCollection_MapNodePtr aBucketHead = data[aHashCode];
 379   TColStd_intMapNode   * p = static_cast<TColStd_intMapNode*> (aBucketHead);
 380   while (p) {
 381     if (p->IsEqual(aKeyInt)) {
 382       aResult = p->AddValue (aKey);
 383 //       break;
 384       goto finish;  // goto saves us 4 CPU clocks or 4% performance
 385     }
 386     p = reinterpret_cast <TColStd_intMapNode*> (p->Next());
 387   }
 388 //    if (!p) {         // not needed, as long as we exit the loop by goto
 389     data[aHashCode] = new TColStd_intMapNode(aKey, aBucketHead);
 390     Increment();
 391     aResult = Standard_True;
 392 //    }
 393  finish:
 394   if (aResult)
 395     myExtent++;
 396   return aResult;
 397 }
 398
 399 //=======================================================================
 400 //function : Contains
 401 //purpose  :
 402 //=======================================================================
 403
 404 Standard_Boolean TColStd_PackedMapOfInteger::Contains
 405                                         (const Standard_Integer aKey) const
 406 {
 407   Standard_Boolean aResult (Standard_False);
 408   if (!IsEmpty()) {
 409     TColStd_intMapNode** data = (TColStd_intMapNode**) myData1;
 410     const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
 411     TColStd_intMapNode * p = data[HashCode (aKeyInt, NbBuckets())];
 412     while (p) {
 413       if (p->IsEqual(aKeyInt)) {
 414         aResult = (p->HasValue (aKey) != 0);
 415         break;
 416       }
 417       p = reinterpret_cast <TColStd_intMapNode*> (p->Next());
 418     }
 419   }
 420   return aResult;
 421 }
 422
 423 //=======================================================================
 424 //function : Remove
 425 //purpose  :
 426 //=======================================================================
 427
 428 Standard_Boolean TColStd_PackedMapOfInteger::Remove(const Standard_Integer aKey)
 429 {
 430   Standard_Boolean aResult (Standard_False);
 431   if (!IsEmpty()) {
 432     TColStd_intMapNode**   data =
 433       reinterpret_cast <TColStd_intMapNode**> (myData1);
 434     const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
 435     TColStd_intMapNode*&   aBucketHead = data[HashCode(aKeyInt, NbBuckets())];
 436     TColStd_intMapNode*    p = aBucketHead;
 437     TColStd_intMapNode*    q = 0L;
 438     while (p) {
 439       if (p->IsEqual(aKeyInt)) {
 440         aResult = p->DelValue (aKey);
 441         if (aResult) {
 442           myExtent--;
 443           if (p->HasValues() == Standard_False) {
 444             Decrement();
 445             if (q) q->Next() = p->Next();
 446             else aBucketHead = reinterpret_cast<TColStd_intMapNode*>(p->Next());
 447             delete p;
 448           }
 449         }
 450         break;
 451       }
 452       q = p;
 453       p = reinterpret_cast <TColStd_intMapNode*> (p->Next());
 454     }
 455   }
 456   return aResult;
 457 }
 458
 459 //=======================================================================
 460 //function : GetMinimalMapped
 461 //purpose  : Query the minimal contained key value.
 462 //=======================================================================
 463
 464 Standard_Integer TColStd_PackedMapOfInteger::GetMinimalMapped () const
 465 {
 466   Standard_Integer aResult (IntegerLast());
 467   if (!IsEmpty()) {
 468     const TCollection_MapNode** aData = (const TCollection_MapNode**) myData1;
 469     const TColStd_intMapNode * pFoundNode = 0L;
 470     for (Standard_Integer i = 0; i <= NbBuckets(); i++) {
 471       for (const TCollection_MapNode * p = aData[i]; p != 0L; p = p->Next()) {
 472         const Standard_Integer aKey =
 473           reinterpret_cast <const TColStd_intMapNode *>(p)->Key();
 474         if (aResult > aKey) {
 475           aResult = aKey;
 476           pFoundNode = reinterpret_cast<const TColStd_intMapNode *>(p);
 477         }
 478       }
 479     }
 480     if (pFoundNode) {
 481       unsigned int aFullMask (0xffffffff);
 482       aResult = TColStd_intMapNode_findNext (pFoundNode, aFullMask);
 483     }
 484   }
 485   return aResult;
 486 }
 487
 488 //=======================================================================
 489 //function : GetMaximalMapped
 490 //purpose  : Query the maximal contained key value.
 491 //=======================================================================
 492
 493 Standard_Integer TColStd_PackedMapOfInteger::GetMaximalMapped () const
 494 {
 495   Standard_Integer aResult (IntegerFirst());
 496   if (!IsEmpty()) {
 497     const TCollection_MapNode** aData = (const TCollection_MapNode**) myData1;
 498     const TColStd_intMapNode * pFoundNode = 0L;
 499     for (Standard_Integer i = 0; i <= NbBuckets(); i++) {
 500       for (const TCollection_MapNode * p = aData[i]; p != 0L; p = p->Next()) {
 501         const Standard_Integer aKey =
 502           reinterpret_cast <const TColStd_intMapNode *>(p)->Key();
 503         if (aResult < aKey) {
 504           aResult = aKey;
 505           pFoundNode = reinterpret_cast<const TColStd_intMapNode *>(p);
 506         }
 507       }
 508     }
 509     if (pFoundNode) {
 510       unsigned int aFullMask (0xffffffff);
 511       aResult = TColStd_intMapNode_findPrev (pFoundNode, aFullMask);
 512     }
 513   }
 514   return aResult;
 515 }
 516
 517 //=======================================================================
 518 //function : Union
 519 //purpose  : Boolean operation OR between 2 maps
 520 //=======================================================================
 521
 522 void TColStd_PackedMapOfInteger::Union (const TColStd_PackedMapOfInteger& theMap1,
 523                                         const TColStd_PackedMapOfInteger& theMap2)
 524 {
 525   if (theMap1.IsEmpty()) // 0 | B == B
 526     Assign (theMap2);
 527   else if (theMap2.IsEmpty()) // A | 0 == A
 528     Assign (theMap1);
 529   else if (myData1 == theMap1.myData1)
 530     Unite (theMap2);
 531   else if (myData1 == theMap2.myData1)
 532     Unite (theMap1);
 533   else {
 534     Standard_Integer i;
 535     const TColStd_intMapNode** aData1 =
 536       (const TColStd_intMapNode**) theMap1.myData1;
 537     const TColStd_intMapNode** aData2 =
 538       (const TColStd_intMapNode**) theMap2.myData1;
 539     const Standard_Integer nBuckets1 = theMap1.NbBuckets();
 540     const Standard_Integer nBuckets2 = theMap2.NbBuckets();
 541     Clear();
 542     TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
 543     // Iteration of the 1st map.
 544     for (i = 0; i <= nBuckets1; i++) {
 545       const TColStd_intMapNode * p1 = aData1[i];
 546       while (p1 != 0L) {
 547         // Find aKey - the base address of currently iterated block
 548         const Standard_Integer aKey = p1->Key();
 549         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
 550         unsigned int aNewMask = p1->Mask();
 551         unsigned int aNewData = p1->Data();
 552         size_t       nValues (p1->NbValues());
 553         // Find the corresponding block in the 2nd map
 554         const TColStd_intMapNode * p2 =
 555           aData2 [HashCode (aKeyInt, nBuckets2)];
 556         while (p2) {
 557           if (p2->IsEqual(aKeyInt)) {
 558             aNewData |= p2->Data();
 559             nValues = TColStd_Population (aNewMask, aNewData);
 560             break;
 561           }
 562           p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
 563         }
 564         // Store the block - result of operation
 565         if (Resizable()) {
 566           ReSize(InternalExtent());
 567           aData = (TColStd_intMapNode**) myData1;
 568         }
 569         const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
 570         aData[aHashCode] = new TColStd_intMapNode (aNewMask, aNewData,
 571                                                    aData[aHashCode]);
 572         Increment();
 573         myExtent += nValues;
 574         p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
 575       }
 576     }
 577     // Iteration of the 2nd map.
 578     for (i = 0; i <= nBuckets2; i++) {
 579       const TColStd_intMapNode * p2 = aData2[i];
 580       while (p2 != 0L) {
 581         // Find aKey - the base address of currently iterated block
 582         const Standard_Integer aKey = p2->Key();
 583         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
 584         // Find the corresponding block in the 1st map
 585         const TColStd_intMapNode * p1 =
 586           aData1 [HashCode (aKeyInt, nBuckets1)];
 587         while (p1) {
 588           if (p1->IsEqual(aKeyInt))
 589             break;
 590           p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
 591         }
 592         // Add the block from the 2nd map only in the case when the similar
 593         // block has not been found in the 1st map
 594         if (p1 == 0L) {
 595           if (Resizable()) {
 596             ReSize(InternalExtent());
 597             aData = (TColStd_intMapNode**) myData1;
 598           }
 599           const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
 600           aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
 601                                                     aData[aHashCode]);
 602           Increment();
 603           myExtent += p2->NbValues();
 604         }
 605         p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
 606       }
 607     }
 608   }
 609 }
 610
 611 //=======================================================================
 612 //function : Unite
 613 //purpose  : Boolean operation OR with the given map
 614 //=======================================================================
 615
 616 Standard_Boolean TColStd_PackedMapOfInteger::Unite(const TColStd_PackedMapOfInteger& theMap)
 617 {
 618   if (theMap.IsEmpty() || myData1 == theMap.myData1) // A | 0 == A | A == A
 619     return Standard_False;
 620   else if ( IsEmpty() ) { // 0 | B == B
 621     Assign ( theMap );
 622     return Standard_True;
 623   }
 624   else {
 625     size_t aNewExtent (myExtent);
 626     TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
 627     const TColStd_intMapNode** aData2 =
 628       (const TColStd_intMapNode**) theMap.myData1;
 629     const Standard_Integer nBuckets2 = theMap.NbBuckets();
 630
 631     // Iteration of the 2nd map.
 632     for (Standard_Integer i = 0; i <= nBuckets2; i++) {
 633       const TColStd_intMapNode * p2 = aData2[i];
 634       while (p2 != 0L) {
 635         // Find aKey - the base address of currently iterated block of integers
 636         const Standard_Integer aKey = p2->Key();
 637         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
 638         // Find the corresponding block in the 1st (this) map
 639         Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
 640         TColStd_intMapNode * p1 = aData[aHashCode];
 641         while (p1) {
 642           if (p1->IsEqual(aKeyInt)) {
 643             const size_t anOldPop = p1->NbValues();
 644             unsigned int newData = p1->Data() | p2->Data();
 645             if ( newData != p1->Data() ) {
 646               p1->ChangeData() = newData;
 647               aNewExtent = aNewExtent - anOldPop +
 648                            TColStd_Population (p1->ChangeMask(), newData);
 649             }
 650             break;
 651           }
 652           p1 = reinterpret_cast <TColStd_intMapNode*> (p1->Next());
 653         }
 654         // If the block is not found in the 1st map, add it to the 1st map
 655         if (p1 == 0L) {
 656           if (Resizable()) {
 657             ReSize(InternalExtent());
 658             aData = (TColStd_intMapNode**) myData1;
 659             aHashCode = HashCode (aKeyInt, NbBuckets());
 660           }
 661           aData[aHashCode] = new TColStd_intMapNode (p2->Mask(), p2->Data(),
 662                                                      aData[aHashCode]);
 663           Increment();
 664           aNewExtent += p2->NbValues();
 665         }
 666         p2 = reinterpret_cast <TColStd_intMapNode*> (p2->Next());
 667       }
 668     }
 669     Standard_Boolean isChanged = ( myExtent != aNewExtent );
 670     myExtent = aNewExtent;
 671     return isChanged;
 672   }
 673 }
 674
 675 //=======================================================================
 676 //function : Intersection
 677 //purpose  : Boolean operation AND between 2 maps
 678 //=======================================================================
 679
 680 void TColStd_PackedMapOfInteger::Intersection
 681                                 (const TColStd_PackedMapOfInteger& theMap1,
 682                                  const TColStd_PackedMapOfInteger& theMap2)
 683 {
 684   if (theMap1.IsEmpty() || theMap2.IsEmpty()) // A & 0 == 0 & B == 0
 685     Clear();
 686   else if (myData1 == theMap1.myData1)
 687     Intersect (theMap2);
 688   else if (myData1 == theMap2.myData1)
 689     Intersect (theMap1);
 690   else {
 691     const TColStd_intMapNode** aData1, ** aData2;
 692     Standard_Integer nBuckets1, nBuckets2;
 693     if (theMap1.Extent() < theMap2.Extent()) {
 694       aData1 = (const TColStd_intMapNode**) theMap1.myData1;
 695       aData2 = (const TColStd_intMapNode**) theMap2.myData1;
 696       nBuckets1 = theMap1.NbBuckets();
 697       nBuckets2 = theMap2.NbBuckets();
 698     }
 699     else {
 700       aData1 = (const TColStd_intMapNode**) theMap2.myData1;
 701       aData2 = (const TColStd_intMapNode**) theMap1.myData1;
 702       nBuckets1 = theMap2.NbBuckets();
 703       nBuckets2 = theMap1.NbBuckets();
 704     }
 705     Clear();
 706     TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
 707     // Iteration of the 1st map.
 708     for (Standard_Integer i = 0; i <= nBuckets1; i++) {
 709       const TColStd_intMapNode * p1 = aData1[i];
 710       while (p1 != 0L) {
 711         // Find aKey - the base address of currently iterated block
 712         const Standard_Integer aKey = p1->Key();
 713         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
 714         // Find the corresponding block in the 2nd map
 715         const TColStd_intMapNode * p2 =
 716           aData2 [HashCode (aKeyInt, nBuckets2)];
 717         while (p2) {
 718           if (p2->IsEqual(aKeyInt)) {
 719             const unsigned int aNewData = p1->Data() & p2->Data();
 720             // Store the block - result of operation
 721             if (aNewData) {
 722               if (Resizable()) {
 723                 ReSize(InternalExtent());
 724                 aData = (TColStd_intMapNode**) myData1;
 725               }
 726               const Standard_Integer aHashCode = HashCode (aKeyInt,
 727                                                            NbBuckets());
 728               unsigned int aNewMask = p1->Mask();
 729               myExtent += TColStd_Population (aNewMask, aNewData);
 730               aData[aHashCode]= new TColStd_intMapNode(aNewMask, aNewData,
 731                                                        aData[aHashCode]);
 732               Increment();
 733             }
 734             break;
 735           }
 736           p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
 737         }
 738         p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
 739       }
 740     }
 741   }
 742 }
 743
 744 //=======================================================================
 745 //function : Intersect
 746 //purpose  : Boolean operation AND with the given map
 747 //=======================================================================
 748
 749 Standard_Boolean TColStd_PackedMapOfInteger::Intersect
 750                  (const TColStd_PackedMapOfInteger& theMap)
 751 {
 752   if ( IsEmpty() ) // 0 & B == 0
 753     return Standard_False;
 754   else if (theMap.IsEmpty()) { // A & 0 == 0
 755     Clear();
 756     return Standard_True;
 757   }
 758   else if (myData1 == theMap.myData1) // A & A == A
 759     return Standard_False;
 760   else {
 761     size_t aNewExtent (0);
 762     TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
 763     const TColStd_intMapNode** aData2 =
 764       (const TColStd_intMapNode**) theMap.myData1;
 765     const Standard_Integer nBuckets2 = theMap.NbBuckets();
 766
 767     // Iteration of this map.
 768     for (Standard_Integer i = 0; i <= NbBuckets(); i++) {
 769       TColStd_intMapNode * q  = 0L;
 770       TColStd_intMapNode * p1 = aData[i];
 771       while (p1 != 0L) {
 772         // Find aKey - the base address of currently iterated block of integers
 773         const Standard_Integer aKey = p1->Key();
 774         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
 775         // Find the corresponding block in the 2nd map
 776         const TColStd_intMapNode * p2 =
 777           aData2 [HashCode (aKeyInt, nBuckets2)];
 778         while (p2) {
 779           if (p2->IsEqual(aKeyInt)) {
 780             const unsigned int aNewData = p1->Data() & p2->Data();
 781             // Store the block - result of operation
 782             if (aNewData == 0)
 783               p2 = 0L;  // no match - the block has to be removed
 784             else
 785             {
 786               if ( aNewData != p1->Data() )
 787                 p1->ChangeData() = aNewData;
 788               aNewExtent += TColStd_Population (p1->ChangeMask(), aNewData);
 789             }
 790             break;
 791           }
 792           p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
 793         }
 794         TColStd_intMapNode* pNext =
 795           reinterpret_cast <TColStd_intMapNode*> (p1->Next());
 796         // If p2!=NULL, then the map node is kept and we move to the next one
 797         // Otherwise we should remove the current node
 798         if (p2)
 799           q = p1;
 800         else {
 801           Decrement();
 802           if (q)  q->Next() = pNext;
 803           else    aData[i]  = pNext;
 804           delete p1;
 805         }
 806         p1 = pNext;
 807       }
 808     }
 809     Standard_Boolean isChanged = ( myExtent != aNewExtent );
 810     myExtent = aNewExtent;
 811     return isChanged;
 812   }
 813 }
 814
 815 //=======================================================================
 816 //function : Subtraction
 817 //purpose  : Boolean operation SUBTRACT between two maps
 818 //=======================================================================
 819
 820 void TColStd_PackedMapOfInteger::Subtraction
 821                                 (const TColStd_PackedMapOfInteger& theMap1,
 822                                  const TColStd_PackedMapOfInteger& theMap2)
 823 {
 824   if (theMap1.IsEmpty() || theMap2.myData1 == theMap1.myData1) // 0 \ A == A \ A == 0
 825     Clear();
 826   else if (theMap2.IsEmpty()) // A \ 0 == A
 827     Assign (theMap1);
 828   else if (myData1 == theMap1.myData1)
 829     Subtract (theMap2);
 830   else if (myData1 == theMap2.myData1) {
 831     TColStd_PackedMapOfInteger aMap;
 832     aMap.Subtraction ( theMap1, theMap2 );
 833     Assign ( aMap );
 834   }
 835   else {
 836     const TColStd_intMapNode** aData1 =
 837       (const TColStd_intMapNode**) theMap1.myData1;
 838     const TColStd_intMapNode** aData2 =
 839       (const TColStd_intMapNode**) theMap2.myData1;
 840     const Standard_Integer nBuckets1 = theMap1.NbBuckets();
 841     const Standard_Integer nBuckets2 = theMap2.NbBuckets();
 842     Clear();
 843     TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
 844     // Iteration of the 1st map.
 845     for (Standard_Integer i = 0; i <= nBuckets1; i++) {
 846       const TColStd_intMapNode * p1 = aData1[i];
 847       while (p1 != 0L) {
 848         // Find aKey - the base address of currently iterated block of integers
 849         const Standard_Integer aKey = p1->Key();
 850         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
 851         unsigned int aNewMask = p1->Mask();
 852         unsigned int aNewData = p1->Data();
 853         size_t       nValues (p1->NbValues());
 854         // Find the corresponding block in the 2nd map
 855         const TColStd_intMapNode * p2 =
 856           aData2 [HashCode (aKeyInt, nBuckets2)];
 857         while (p2) {
 858           if (p2->IsEqual(aKeyInt)) {
 859             aNewData &= ~p2->Data();
 860             nValues = TColStd_Population (aNewMask, aNewData);
 861             break;
 862           }
 863           p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
 864         }
 865         // Store the block - result of operation
 866         if (aNewData) {
 867           if (Resizable()) {
 868             ReSize(InternalExtent());
 869             aData = (TColStd_intMapNode**) myData1;
 870           }
 871           const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
 872           aData[aHashCode]= new TColStd_intMapNode (aNewMask, aNewData,
 873                                                     aData[aHashCode]);
 874           Increment();
 875           myExtent += nValues;
 876         }
 877         p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
 878       }
 879     }
 880   }
 881 }
 882
 883 //=======================================================================
 884 //function : Subtract
 885 //purpose  : Boolean operation SUBTRACT with the given map
 886 //=======================================================================
 887
 888 Standard_Boolean TColStd_PackedMapOfInteger::Subtract
 889                                 (const TColStd_PackedMapOfInteger& theMap)
 890 {
 891   if ( IsEmpty() || theMap.IsEmpty() ) // 0 \ B == 0; A \ 0 == A
 892     return Standard_False;
 893   else if (myData1 == theMap.myData1) { // A \ A == 0
 894     Clear();
 895     return Standard_True;
 896   }
 897   else {
 898     size_t aNewExtent (0);
 899     TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
 900     const TColStd_intMapNode** aData2 =
 901       (const TColStd_intMapNode**) theMap.myData1;
 902     const Standard_Integer nBuckets2 = theMap.NbBuckets();
 903     // Iteration of this map.
 904     for (Standard_Integer i = 0; i <= NbBuckets(); i++) {
 905       TColStd_intMapNode * q  = 0L;
 906       TColStd_intMapNode * p1 = aData[i];
 907       while (p1 != 0L) {
 908         // Find aKey - the base address of currently iterated block of integers
 909         const Standard_Integer aKey = p1->Key();
 910         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
 911         TColStd_intMapNode* pNext =
 912           reinterpret_cast <TColStd_intMapNode*> (p1->Next());
 913         // Find the corresponding block in the 2nd map
 914         const TColStd_intMapNode * p2 =
 915           aData2 [HashCode (aKeyInt, nBuckets2)];
 916         while (p2) {
 917           if (p2->IsEqual(aKeyInt)) {
 918             const unsigned int aNewData = p1->Data() & ~p2->Data();
 919             // Store the block - result of operation
 920             if (aNewData == 0) {
 921               // no match - the block has to be removed
 922               Decrement();
 923               if (q)  q->Next() = pNext;
 924               else    aData[i]  = pNext;
 925               delete p1;
 926             }
 927             else if ( aNewData != p1->Data() ) {
 928               p1->ChangeData() = aNewData;
 929               aNewExtent += TColStd_Population (p1->ChangeMask(), aNewData);
 930               q = p1;
 931             }
 932             else {
 933               aNewExtent += p1->NbValues();
 934               q = p1;
 935             }
 936             break;
 937           }
 938           p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
 939         }
 940         if (p2 == 0L) {
 941           aNewExtent += p1->NbValues();
 942           q = p1;
 943         }
 944         p1 = pNext;
 945       }
 946     }
 947     Standard_Boolean isChanged = ( myExtent != aNewExtent );
 948     myExtent = aNewExtent;
 949     return isChanged;
 950   }
 951 }
 952
 953 //=======================================================================
 954 //function : Difference
 955 //purpose  : Boolean operation XOR
 956 //=======================================================================
 957
 958 void TColStd_PackedMapOfInteger::Difference  (const TColStd_PackedMapOfInteger& theMap1,
 959                                               const TColStd_PackedMapOfInteger& theMap2)
 960 {
 961   if (theMap1.IsEmpty()) // 0 ^ B == B
 962     Assign (theMap2);
 963   else if (theMap2.IsEmpty()) // A ^ 0 == A
 964     Assign (theMap1);
 965   else if (myData1 == theMap1.myData1)
 966     Differ(theMap2);
 967   else if (myData1 == theMap2.myData1)
 968     Differ(theMap1);
 969   else {
 970     Standard_Integer i;
 971     const TColStd_intMapNode** aData1 =
 972       (const TColStd_intMapNode**) theMap1.myData1;
 973     const TColStd_intMapNode** aData2 =
 974       (const TColStd_intMapNode**) theMap2.myData1;
 975     const Standard_Integer nBuckets1 = theMap1.NbBuckets();
 976     const Standard_Integer nBuckets2 = theMap2.NbBuckets();
 977     Clear();
 978     TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
 979
 980     // Iteration of the 1st map.
 981     for (i = 0; i <= nBuckets1; i++) {
 982       const TColStd_intMapNode * p1 = aData1[i];
 983       while (p1 != 0L) {
 984         // Find aKey - the base address of currently iterated block of integers
 985         const Standard_Integer aKey = p1->Key();
 986         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
 987         unsigned int aNewMask = p1->Mask();
 988         unsigned int aNewData = p1->Data();
 989         size_t       nValues (p1->NbValues());
 990         // Find the corresponding block in the 2nd map
 991         const TColStd_intMapNode * p2 =
 992           aData2 [HashCode (aKeyInt, nBuckets2)];
 993         while (p2) {
 994           if (p2->IsEqual(aKeyInt)) {
 995             aNewData ^= p2->Data();
 996             nValues = TColStd_Population (aNewMask, aNewData);
 997             break;
 998           }
 999           p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1000         }
1001         // Store the block - result of operation
1002         if (aNewData) {
1003           if (Resizable()) {
1004             ReSize(InternalExtent());
1005             aData = (TColStd_intMapNode**) myData1;
1006           }
1007           const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
1008           aData[aHashCode]= new TColStd_intMapNode (aNewMask, aNewData,
1009                                                     aData[aHashCode]);
1010           Increment();
1011           myExtent += nValues;
1012         }
1013         p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
1014       }
1015     }
1016
1017     // Iteration of the 2nd map.
1018     for (i = 0; i <= nBuckets2; i++) {
1019       const TColStd_intMapNode * p2 = aData2[i];
1020       while (p2 != 0L) {
1021         // Find aKey - the base address of currently iterated block
1022         const Standard_Integer aKey = p2->Key();
1023         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
1024         // Find the corresponding block in the 1st map
1025         const TColStd_intMapNode * p1 =
1026           aData1 [HashCode (aKeyInt, nBuckets1)];
1027         while (p1) {
1028           if (p1->IsEqual(aKeyInt))
1029             break;
1030           p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
1031         }
1032         // Add the block from the 2nd map only in the case when the similar
1033         // block has not been found in the 1st map
1034         if (p1 == 0L) {
1035           if (Resizable()) {
1036             ReSize(InternalExtent());
1037             aData = (TColStd_intMapNode**) myData1;
1038           }
1039           const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
1040           aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
1041                                                     aData[aHashCode]);
1042           Increment();
1043           myExtent += p2->NbValues();
1044         }
1045         p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1046       }
1047     }
1048   }
1049 }
1050
1051 //=======================================================================
1052 //function : Differ
1053 //purpose  : Boolean operation XOR
1054 //=======================================================================
1055
1056 Standard_Boolean TColStd_PackedMapOfInteger::Differ(const TColStd_PackedMapOfInteger& theMap)
1057 {
1058   if (theMap.IsEmpty()) // A ^ 0 = A
1059     return Standard_False;
1060   else if (IsEmpty()) { // 0 ^ B = B
1061     Assign ( theMap );
1062     return Standard_True;
1063   }
1064   else if( myData1 == theMap.myData1) { // A ^ A == 0
1065     Clear();
1066     return Standard_True;
1067   }
1068   else {
1069     size_t aNewExtent (0);
1070     TColStd_intMapNode** aData1 = (TColStd_intMapNode**) myData1;
1071     const TColStd_intMapNode** aData2 =
1072       (const TColStd_intMapNode**) theMap.myData1;
1073     const Standard_Integer nBuckets2 = theMap.NbBuckets();
1074     Standard_Boolean isChanged = Standard_False;
1075     Standard_Integer i = 0;
1076     // Iteration by other map
1077     for ( ; i <= nBuckets2; i++) {
1078        TColStd_intMapNode * q  = 0L;
1079       const TColStd_intMapNode * p2 = aData2[i];
1080       while (p2 != 0L) {
1081         // Find aKey - the base address of currently iterated block
1082         const Standard_Integer aKey = p2->Key();
1083         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
1084
1085         // Find the corresponding block in the 1st map
1086         TColStd_intMapNode * p1 =
1087           aData1[HashCode (aKeyInt, NbBuckets())];
1088         TColStd_intMapNode* pNext =
1089           reinterpret_cast <TColStd_intMapNode*> (p1->Next());
1090
1091         while (p1) {
1092           if (p1->IsEqual(aKeyInt)) {
1093             const unsigned int aNewData = p1->Data() ^ p2->Data();
1094             // Store the block - result of operation
1095             if (aNewData == 0) {
1096               // no match - the block has to be removed
1097               Decrement();
1098               if (q)  q->Next() = pNext;
1099               else    aData1[i]  = pNext;
1100               delete p1;
1101             }
1102             else if ( aNewData != p1->Data() ) {
1103               p1->ChangeData() = aNewData;
1104               isChanged = Standard_True;
1105               aNewExtent += TColStd_Population (p1->ChangeMask(), aNewData);
1106               q = p1;
1107             }
1108             break;
1109           }
1110           p1 = pNext;
1111         }
1112         // Add the block from the 2nd map only in the case when the similar
1113         // block has not been found in the 1st map
1114         TColStd_intMapNode** aData = NULL;
1115         if (p1 == 0L) {
1116           if (Resizable()) {
1117             ReSize(InternalExtent());
1118             aData = (TColStd_intMapNode**) myData1;
1119           }
1120           const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
1121           aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
1122                                                     aData[aHashCode]);
1123           Increment();
1124           aNewExtent += p2->NbValues();
1125           isChanged = Standard_True;
1126         }
1127         p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1128       }
1129     }
1130     myExtent = aNewExtent;
1131     return isChanged;
1132   }
1133 }
1134
1135 //=======================================================================
1136 //function : IsEqual
1137 //purpose  : Boolean operation returns true if this map is equal to the other map
1138 //=======================================================================
1139
1140 Standard_Boolean TColStd_PackedMapOfInteger::IsEqual(const TColStd_PackedMapOfInteger& theMap) const
1141 {
1142   if (IsEmpty() && theMap.IsEmpty())
1143     return Standard_True;
1144   else if ( Extent() != theMap.Extent() )
1145     return Standard_False;
1146   else {
1147     const TColStd_intMapNode** aData1 = (const TColStd_intMapNode**) myData1;
1148     const TColStd_intMapNode** aData2 = (const TColStd_intMapNode**) theMap.myData1;
1149     const Standard_Integer nBuckets2 = theMap.NbBuckets();
1150     if(aData1 == aData2)
1151       return Standard_True;
1152
1153     Standard_Integer i = 0;
1154     // Iteration of this map.
1155     for (; i <= NbBuckets(); i++) {
1156       const TColStd_intMapNode * p1 = aData1[i];
1157       while (p1 != 0L) {
1158         // Find aKey - the base address of currently iterated block of integers
1159         const Standard_Integer aKey = p1->Key();
1160         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
1161         TColStd_intMapNode* pNext =
1162           reinterpret_cast <TColStd_intMapNode*> (p1->Next());
1163         // Find the corresponding block in the 2nd map
1164         const TColStd_intMapNode * p2 =
1165           aData2 [HashCode (aKeyInt, nBuckets2)];
1166         while (p2) {
1167           if ( p2->IsEqual(aKeyInt) ) {
1168             if ( p1->Data() != p2->Data() )
1169               return Standard_False;
1170             break;
1171           }
1172           p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1173         }
1174         // if the same block not found, maps are different
1175         if (p2 == 0L)
1176           return Standard_False;
1177
1178         p1 = pNext;
1179       }
1180     }
1181     return Standard_True;
1182   }
1183 }
1184
1185 //=======================================================================
1186 //function : IsSubset
1187 //purpose  : Boolean operation returns true if this map if subset of other map
1188 //=======================================================================
1189
1190 Standard_Boolean TColStd_PackedMapOfInteger::IsSubset (const TColStd_PackedMapOfInteger& theMap) const
1191 {
1192   if ( IsEmpty() ) // 0 <= A
1193     return Standard_True;
1194   else if ( theMap.IsEmpty() ) // ! ( A <= 0 )
1195     return Standard_False;
1196   else if ( Extent() > theMap.Extent() )
1197     return Standard_False;
1198   else {
1199     const TColStd_intMapNode** aData1 = (const TColStd_intMapNode**) myData1;
1200     const TColStd_intMapNode** aData2 = (const TColStd_intMapNode**) theMap.myData1;
1201     if(aData1 == aData2)
1202       return Standard_True;
1203     const Standard_Integer nBuckets2 = theMap.NbBuckets();
1204
1205     Standard_Integer i = 0;
1206     // Iteration of this map.
1207     for (; i <= NbBuckets(); i++) {
1208       const TColStd_intMapNode * p1 = aData1[i];
1209       while (p1 != 0L) {
1210         // Find aKey - the base address of currently iterated block of integers
1211         const Standard_Integer aKey = p1->Key();
1212         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
1213         TColStd_intMapNode* pNext =
1214           reinterpret_cast <TColStd_intMapNode*> (p1->Next());
1215         // Find the corresponding block in the 2nd map
1216         const TColStd_intMapNode * p2 =
1217           aData2 [HashCode (aKeyInt, nBuckets2)];
1218         while (p2) {
1219           if ( p2->IsEqual(aKeyInt) ) {
1220             if ( p1->Data() & ~p2->Data() ) // at least one bit set in p1 is not set in p2
1221               return Standard_False;
1222             break;
1223           }
1224           p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1225         }
1226         p1 = pNext;
1227       }
1228     }
1229     return Standard_True;
1230   }
1231 }
1232
1233 //=======================================================================
1234 //function : HasIntersection
1235 //purpose  : Boolean operation returns true if this map intersects with other map
1236 //=======================================================================
1237
1238 Standard_Boolean TColStd_PackedMapOfInteger::HasIntersection (const TColStd_PackedMapOfInteger& theMap) const
1239 {
1240   if (IsEmpty() || theMap.IsEmpty()) // A * 0 == 0 * B == 0
1241     return Standard_False;
1242   else {
1243     const TColStd_intMapNode** aData1 = (const TColStd_intMapNode**) myData1;
1244     const TColStd_intMapNode** aData2 = (const TColStd_intMapNode**) theMap.myData1;
1245     const Standard_Integer nBuckets2 = theMap.NbBuckets();
1246     if(aData1 == aData2)
1247       return Standard_True;
1248
1249     Standard_Integer i = 0;
1250     // Iteration of this map.
1251     for (; i <= NbBuckets(); i++) {
1252       const TColStd_intMapNode * p1 = aData1[i];
1253       while (p1 != 0L) {
1254         // Find aKey - the base address of currently iterated block of integers
1255         const Standard_Integer aKey = p1->Key();
1256         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
1257         TColStd_intMapNode* pNext =
1258           reinterpret_cast <TColStd_intMapNode*> (p1->Next());
1259         // Find the corresponding block in the 2nd map
1260         const TColStd_intMapNode * p2 =
1261           aData2 [HashCode (aKeyInt, nBuckets2)];
1262         while (p2) {
1263           if (p2->IsEqual(aKeyInt)) {
1264             if ( p1->Data() & p2->Data() )
1265               return Standard_True;
1266             break;
1267           }
1268           p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1269         }
1270         p1 = pNext;
1271       }
1272     }
1273     return Standard_False;
1274   }
1275 }