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