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