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