0025112: Undo of modification of the attribute TDataStd_IntPackedMap works wrong
[occt.git] / 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         if (!p2)
1219           return Standard_False;
1220         while (p2) {
1221           if ( p2->IsEqual(aKeyInt) ) {
1222             if ( p1->Data() & ~p2->Data() ) // at least one bit set in p1 is not set in p2
1223               return Standard_False;
1224             break;
1225           }
1226           p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1227         }
1228         p1 = pNext;
1229       }
1230     }
1231     return Standard_True;
1232   }
1233 }
1234
1235 //=======================================================================
1236 //function : HasIntersection
1237 //purpose  : Boolean operation returns true if this map intersects with other map
1238 //=======================================================================
1239
1240 Standard_Boolean TColStd_PackedMapOfInteger::HasIntersection (const TColStd_PackedMapOfInteger& theMap) const
1241 {
1242   if (IsEmpty() || theMap.IsEmpty()) // A * 0 == 0 * B == 0
1243     return Standard_False;
1244   else {
1245     const TColStd_intMapNode** aData1 = (const TColStd_intMapNode**) myData1;
1246     const TColStd_intMapNode** aData2 = (const TColStd_intMapNode**) theMap.myData1;
1247     const Standard_Integer nBuckets2 = theMap.NbBuckets();
1248     if(aData1 == aData2)
1249       return Standard_True;
1250         
1251     Standard_Integer i = 0;
1252     // Iteration of this map.
1253     for (; i <= NbBuckets(); i++) {
1254       const TColStd_intMapNode * p1 = aData1[i];
1255       while (p1 != 0L) {
1256         // Find aKey - the base address of currently iterated block of integers
1257         const Standard_Integer aKey = p1->Key();
1258         const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
1259         TColStd_intMapNode* pNext =
1260           reinterpret_cast <TColStd_intMapNode*> (p1->Next());
1261         // Find the corresponding block in the 2nd map
1262         const TColStd_intMapNode * p2 =
1263           aData2 [HashCode (aKeyInt, nBuckets2)];
1264         while (p2) {
1265           if (p2->IsEqual(aKeyInt)) {
1266             if ( p1->Data() & p2->Data() )
1267               return Standard_True;
1268             break;
1269           }
1270           p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1271         }
1272         p1 = pNext;
1273       }
1274     }
1275     return Standard_False;
1276   }
1277 }