1 // Created on: 2005-11-05
2 // Created by: Alexander GRIGORIEV
3 // Copyright (c) 2005-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #include <TColStd_PackedMapOfInteger.hxx>
18 #include <TCollection_MapNode.hxx>
19 #include <Standard_Type.hxx>
22 #define MASK_LOW 0x001f
24 #define MASK_HIGH (~MASK_LOW)
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
30 inline TColStd_intMapNode (TCollection_MapNode * ptr = 0L)
31 : TCollection_MapNode (ptr),
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)) {}
41 inline TColStd_intMapNode (unsigned int theMask,
43 TCollection_MapNode * ptr)
44 : TCollection_MapNode (ptr),
48 inline unsigned int Mask () const
51 inline unsigned int Data () const
54 inline unsigned int& ChangeMask ()
57 inline unsigned int& ChangeData ()
60 inline Standard_Integer Key () const
61 { return Standard_Integer (myMask & MASK_HIGH); }
63 inline size_t NbValues () const
64 { return size_t(myMask & MASK_LOW) + 1; }
66 inline Standard_Boolean HasValues () const
67 { return (myData != 0); }
69 Standard_Integer HasValue (const Standard_Integer theValue) const
70 { return (myData & (1 << (theValue & MASK_LOW))); }
72 Standard_Boolean AddValue (const Standard_Integer theValue);
74 Standard_Boolean DelValue (const Standard_Integer theValue);
77 * Find the smallest non-zero bit under the given mask. Outputs the new mask
78 * that does not contain the detected bit.
80 Standard_Integer FindNext (unsigned int& theMask) const;
83 * Support of Map interface.
85 inline Standard_Integer HashCode (const Standard_Integer theUpper) const
87 return ::HashCode (Standard_Integer(myMask >> 5), theUpper);
91 * Support of Map interface.
93 inline Standard_Boolean IsEqual (const Standard_Integer theOther) const
95 return ((myMask >> 5) == (unsigned)theOther);
104 //=======================================================================
105 //function : TColStd_intMapNode::AddValue
107 //=======================================================================
109 Standard_Boolean TColStd_PackedMapOfInteger::TColStd_intMapNode::AddValue (const Standard_Integer theValue)
111 Standard_Boolean aResult (Standard_False);
112 const Standard_Integer aValInt = (1 << (theValue & MASK_LOW));
113 if ((myData & aValInt) == 0) {
116 aResult = Standard_True;
121 //=======================================================================
122 //function : TColStd_intMapNode::DelValue
124 //=======================================================================
126 Standard_Boolean TColStd_PackedMapOfInteger::TColStd_intMapNode::DelValue (const Standard_Integer theValue)
128 Standard_Boolean aResult (Standard_False);
129 const Standard_Integer aValInt = (1 << (theValue & MASK_LOW));
130 if ((myData & aValInt) != 0) {
133 aResult = Standard_True;
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 //=======================================================================
146 inline size_t TColStd_Population (unsigned int& theMask,
147 const unsigned int theData)
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);
158 //=======================================================================
159 //function : TColStd_intMapNode_findNext
161 //=======================================================================
162 Standard_Integer TColStd_PackedMapOfInteger::TColStd_intMapNode_findNext (const TColStd_intMapNode* theNode,
163 unsigned int& theMask)
165 unsigned int val = theNode->Data() & theMask;
168 theMask = ~0U; // void, nothing to do
170 unsigned int aMask = ~0U;
171 if ((val & 0x0000ffff) == 0) {
176 if ((val & 0x000000ff) == 0) {
181 if ((val & 0x0000000f) == 0) {
186 if ((val & 0x00000003) == 0) {
191 if ((val & 0x00000001) == 0) {
195 theMask = (aMask << 1);
197 return nZeros + theNode->Key();
200 //=======================================================================
201 //function : TColStd_intMapNode_findPrev
203 //=======================================================================
204 Standard_Integer TColStd_PackedMapOfInteger::TColStd_intMapNode_findPrev (const TColStd_intMapNode* theNode,
205 unsigned int& theMask)
207 unsigned int val = theNode->Data() & theMask;
210 theMask = ~0U; // void, nothing to do
212 unsigned int aMask = ~0U;
213 if ((val & 0xffff0000) == 0) {
218 if ((val & 0xff000000) == 0) {
223 if ((val & 0xf0000000) == 0) {
228 if ((val & 0xc0000000) == 0) {
233 if ((val & 0x80000000) == 0) {
237 theMask = (aMask >> 1);
239 return (31 - nZeros) + theNode->Key();
242 //=======================================================================
245 //=======================================================================
247 TColStd_PackedMapOfInteger& TColStd_PackedMapOfInteger::Assign
248 (const TColStd_PackedMapOfInteger& theOther)
250 if (this != &theOther) {
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];
262 const Standard_Integer aHashCode = p->HashCode(nBuckets);
264 new TColStd_intMapNode (p->Mask(), p->Data(), aData[aHashCode]);
266 p = reinterpret_cast <const TColStd_intMapNode*> (p->Next());
269 // TColStd_MapIteratorOfPackedMapOfInteger anIt (theOther);
270 // for (; anIt.More(); anIt.Next())
274 myExtent = theOther.myExtent;
278 //=======================================================================
281 //=======================================================================
283 void TColStd_PackedMapOfInteger::ReSize (const Standard_Integer nbBuckets)
285 Standard_Integer newBuck;
286 Standard_Address newData1=NULL, dummy=NULL;
287 if (BeginResize (nbBuckets, newBuck, newData1, dummy))
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++) {
300 k = p->HashCode(newBuck);
301 TCollection_MapNode * q = p->Next();
302 p->Next() = newdata[k];
304 p = static_cast <TColStd_intMapNode*> (q);
309 EndResize (nbBuckets, newBuck, newData1, dummy);
313 //=======================================================================
316 //=======================================================================
318 void TColStd_PackedMapOfInteger::Clear ()
322 TColStd_intMapNode** data =
323 reinterpret_cast <TColStd_intMapNode**> (myData1);
324 TColStd_intMapNode * p;
325 for (i = 0; i <= NbBuckets(); i++) {
329 TCollection_MapNode * q = p->Next();
331 p = static_cast <TColStd_intMapNode*> (q);
336 TCollection_BasicMap::Destroy();
340 //=======================================================================
343 //=======================================================================
345 Standard_Boolean TColStd_PackedMapOfInteger::Add (const Standard_Integer aKey)
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);
357 if (p->IsEqual(aKeyInt)) {
358 aResult = p->AddValue (aKey);
360 goto finish; // goto saves us 4 CPU clocks or 4% performance
362 p = reinterpret_cast <TColStd_intMapNode*> (p->Next());
364 // if (!p) { // not needed, as long as we exit the loop by goto
365 data[aHashCode] = new TColStd_intMapNode(aKey, aBucketHead);
367 aResult = Standard_True;
375 //=======================================================================
376 //function : Contains
378 //=======================================================================
380 Standard_Boolean TColStd_PackedMapOfInteger::Contains
381 (const Standard_Integer aKey) const
383 Standard_Boolean aResult (Standard_False);
385 TColStd_intMapNode** data = (TColStd_intMapNode**) myData1;
386 const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
387 TColStd_intMapNode * p = data[HashCode (aKeyInt, NbBuckets())];
389 if (p->IsEqual(aKeyInt)) {
390 aResult = (p->HasValue (aKey) != 0);
393 p = reinterpret_cast <TColStd_intMapNode*> (p->Next());
399 //=======================================================================
402 //=======================================================================
404 Standard_Boolean TColStd_PackedMapOfInteger::Remove(const Standard_Integer aKey)
406 Standard_Boolean aResult (Standard_False);
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;
415 if (p->IsEqual(aKeyInt)) {
416 aResult = p->DelValue (aKey);
419 if (p->HasValues() == Standard_False) {
421 if (q) q->Next() = p->Next();
422 else aBucketHead = reinterpret_cast<TColStd_intMapNode*>(p->Next());
429 p = reinterpret_cast <TColStd_intMapNode*> (p->Next());
435 //=======================================================================
436 //function : GetMinimalMapped
437 //purpose : Query the minimal contained key value.
438 //=======================================================================
440 Standard_Integer TColStd_PackedMapOfInteger::GetMinimalMapped () const
442 Standard_Integer aResult (IntegerLast());
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) {
452 pFoundNode = reinterpret_cast<const TColStd_intMapNode *>(p);
457 unsigned int aFullMask (0xffffffff);
458 aResult = TColStd_intMapNode_findNext (pFoundNode, aFullMask);
464 //=======================================================================
465 //function : GetMaximalMapped
466 //purpose : Query the maximal contained key value.
467 //=======================================================================
469 Standard_Integer TColStd_PackedMapOfInteger::GetMaximalMapped () const
471 Standard_Integer aResult (IntegerFirst());
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) {
481 pFoundNode = reinterpret_cast<const TColStd_intMapNode *>(p);
486 unsigned int aFullMask (0xffffffff);
487 aResult = TColStd_intMapNode_findPrev (pFoundNode, aFullMask);
493 //=======================================================================
495 //purpose : Boolean operation OR between 2 maps
496 //=======================================================================
498 void TColStd_PackedMapOfInteger::Union (const TColStd_PackedMapOfInteger& theMap1,
499 const TColStd_PackedMapOfInteger& theMap2)
501 if (theMap1.IsEmpty()) // 0 | B == B
503 else if (theMap2.IsEmpty()) // A | 0 == A
505 else if (myData1 == theMap1.myData1)
507 else if (myData1 == theMap2.myData1)
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();
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];
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)];
533 if (p2->IsEqual(aKeyInt)) {
534 aNewData |= p2->Data();
535 nValues = TColStd_Population (aNewMask, aNewData);
538 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
540 // Store the block - result of operation
542 ReSize(InternalExtent());
543 aData = (TColStd_intMapNode**) myData1;
545 const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
546 aData[aHashCode] = new TColStd_intMapNode (aNewMask, aNewData,
550 p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
553 // Iteration of the 2nd map.
554 for (i = 0; i <= nBuckets2; i++) {
555 const TColStd_intMapNode * p2 = aData2[i];
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)];
564 if (p1->IsEqual(aKeyInt))
566 p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
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
572 ReSize(InternalExtent());
573 aData = (TColStd_intMapNode**) myData1;
575 const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
576 aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
579 myExtent += p2->NbValues();
581 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
587 //=======================================================================
589 //purpose : Boolean operation OR with the given map
590 //=======================================================================
592 Standard_Boolean TColStd_PackedMapOfInteger::Unite(const TColStd_PackedMapOfInteger& theMap)
594 if (theMap.IsEmpty() || myData1 == theMap.myData1) // A | 0 == A | A == A
595 return Standard_False;
596 else if ( IsEmpty() ) { // 0 | B == B
598 return Standard_True;
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();
607 // Iteration of the 2nd map.
608 for (Standard_Integer i = 0; i <= nBuckets2; i++) {
609 const TColStd_intMapNode * p2 = aData2[i];
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];
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);
628 p1 = reinterpret_cast <TColStd_intMapNode*> (p1->Next());
630 // If the block is not found in the 1st map, add it to the 1st map
633 ReSize(InternalExtent());
634 aData = (TColStd_intMapNode**) myData1;
635 aHashCode = HashCode (aKeyInt, NbBuckets());
637 aData[aHashCode] = new TColStd_intMapNode (p2->Mask(), p2->Data(),
640 aNewExtent += p2->NbValues();
642 p2 = reinterpret_cast <TColStd_intMapNode*> (p2->Next());
645 Standard_Boolean isChanged = ( myExtent != aNewExtent );
646 myExtent = aNewExtent;
651 //=======================================================================
652 //function : Intersection
653 //purpose : Boolean operation AND between 2 maps
654 //=======================================================================
656 void TColStd_PackedMapOfInteger::Intersection
657 (const TColStd_PackedMapOfInteger& theMap1,
658 const TColStd_PackedMapOfInteger& theMap2)
660 if (theMap1.IsEmpty() || theMap2.IsEmpty()) // A & 0 == 0 & B == 0
662 else if (myData1 == theMap1.myData1)
664 else if (myData1 == theMap2.myData1)
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();
676 aData1 = (const TColStd_intMapNode**) theMap2.myData1;
677 aData2 = (const TColStd_intMapNode**) theMap1.myData1;
678 nBuckets1 = theMap2.NbBuckets();
679 nBuckets2 = theMap1.NbBuckets();
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];
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)];
694 if (p2->IsEqual(aKeyInt)) {
695 const unsigned int aNewData = p1->Data() & p2->Data();
696 // Store the block - result of operation
699 ReSize(InternalExtent());
700 aData = (TColStd_intMapNode**) myData1;
702 const Standard_Integer aHashCode = HashCode (aKeyInt,
704 unsigned int aNewMask = p1->Mask();
705 myExtent += TColStd_Population (aNewMask, aNewData);
706 aData[aHashCode]= new TColStd_intMapNode(aNewMask, aNewData,
712 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
714 p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
720 //=======================================================================
721 //function : Intersect
722 //purpose : Boolean operation AND with the given map
723 //=======================================================================
725 Standard_Boolean TColStd_PackedMapOfInteger::Intersect
726 (const TColStd_PackedMapOfInteger& theMap)
728 if ( IsEmpty() ) // 0 & B == 0
729 return Standard_False;
730 else if (theMap.IsEmpty()) { // A & 0 == 0
732 return Standard_True;
734 else if (myData1 == theMap.myData1) // A & A == A
735 return Standard_False;
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();
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];
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)];
755 if (p2->IsEqual(aKeyInt)) {
756 const unsigned int aNewData = p1->Data() & p2->Data();
757 // Store the block - result of operation
759 p2 = 0L; // no match - the block has to be removed
762 if ( aNewData != p1->Data() )
763 p1->ChangeData() = aNewData;
764 aNewExtent += TColStd_Population (p1->ChangeMask(), aNewData);
768 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
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
778 if (q) q->Next() = pNext;
779 else aData[i] = pNext;
785 Standard_Boolean isChanged = ( myExtent != aNewExtent );
786 myExtent = aNewExtent;
791 //=======================================================================
792 //function : Subtraction
793 //purpose : Boolean operation SUBTRACT between two maps
794 //=======================================================================
796 void TColStd_PackedMapOfInteger::Subtraction
797 (const TColStd_PackedMapOfInteger& theMap1,
798 const TColStd_PackedMapOfInteger& theMap2)
800 if (theMap1.IsEmpty() || theMap2.myData1 == theMap1.myData1) // 0 \ A == A \ A == 0
802 else if (theMap2.IsEmpty()) // A \ 0 == A
804 else if (myData1 == theMap1.myData1)
806 else if (myData1 == theMap2.myData1) {
807 TColStd_PackedMapOfInteger aMap;
808 aMap.Subtraction ( theMap1, theMap2 );
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();
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];
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)];
834 if (p2->IsEqual(aKeyInt)) {
835 aNewData &= ~p2->Data();
836 nValues = TColStd_Population (aNewMask, aNewData);
839 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
841 // Store the block - result of operation
844 ReSize(InternalExtent());
845 aData = (TColStd_intMapNode**) myData1;
847 const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
848 aData[aHashCode]= new TColStd_intMapNode (aNewMask, aNewData,
853 p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
859 //=======================================================================
860 //function : Subtract
861 //purpose : Boolean operation SUBTRACT with the given map
862 //=======================================================================
864 Standard_Boolean TColStd_PackedMapOfInteger::Subtract
865 (const TColStd_PackedMapOfInteger& theMap)
867 if ( IsEmpty() || theMap.IsEmpty() ) // 0 \ B == 0; A \ 0 == A
868 return Standard_False;
869 else if (myData1 == theMap.myData1) { // A \ A == 0
871 return Standard_True;
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];
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)];
893 if (p2->IsEqual(aKeyInt)) {
894 const unsigned int aNewData = p1->Data() & ~p2->Data();
895 // Store the block - result of operation
897 // no match - the block has to be removed
899 if (q) q->Next() = pNext;
900 else aData[i] = pNext;
903 else if ( aNewData != p1->Data() ) {
904 p1->ChangeData() = aNewData;
905 aNewExtent += TColStd_Population (p1->ChangeMask(), aNewData);
909 aNewExtent += p1->NbValues();
914 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
917 aNewExtent += p1->NbValues();
923 Standard_Boolean isChanged = ( myExtent != aNewExtent );
924 myExtent = aNewExtent;
929 //=======================================================================
930 //function : Difference
931 //purpose : Boolean operation XOR
932 //=======================================================================
934 void TColStd_PackedMapOfInteger::Difference (const TColStd_PackedMapOfInteger& theMap1,
935 const TColStd_PackedMapOfInteger& theMap2)
937 if (theMap1.IsEmpty()) // 0 ^ B == B
939 else if (theMap2.IsEmpty()) // A ^ 0 == A
941 else if (myData1 == theMap1.myData1)
943 else if (myData1 == theMap2.myData1)
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();
954 TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
956 // Iteration of the 1st map.
957 for (i = 0; i <= nBuckets1; i++) {
958 const TColStd_intMapNode * p1 = aData1[i];
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)];
970 if (p2->IsEqual(aKeyInt)) {
971 aNewData ^= p2->Data();
972 nValues = TColStd_Population (aNewMask, aNewData);
975 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
977 // Store the block - result of operation
980 ReSize(InternalExtent());
981 aData = (TColStd_intMapNode**) myData1;
983 const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
984 aData[aHashCode]= new TColStd_intMapNode (aNewMask, aNewData,
989 p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
993 // Iteration of the 2nd map.
994 for (i = 0; i <= nBuckets2; i++) {
995 const TColStd_intMapNode * p2 = aData2[i];
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)];
1004 if (p1->IsEqual(aKeyInt))
1006 p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
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
1012 ReSize(InternalExtent());
1013 aData = (TColStd_intMapNode**) myData1;
1015 const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
1016 aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
1019 myExtent += p2->NbValues();
1021 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1027 //=======================================================================
1029 //purpose : Boolean operation XOR
1030 //=======================================================================
1032 Standard_Boolean TColStd_PackedMapOfInteger::Differ(const TColStd_PackedMapOfInteger& theMap)
1034 if (theMap.IsEmpty()) // A ^ 0 = A
1035 return Standard_False;
1036 else if (IsEmpty()) { // 0 ^ B = B
1038 return Standard_True;
1040 else if( myData1 == theMap.myData1) { // A ^ A == 0
1042 return Standard_True;
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];
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;
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());
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
1074 if (q) q->Next() = pNext;
1075 else aData1[i] = pNext;
1078 else if ( aNewData != p1->Data() ) {
1079 p1->ChangeData() = aNewData;
1080 isChanged = Standard_True;
1081 aNewExtent += TColStd_Population (p1->ChangeMask(), aNewData);
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;
1093 ReSize(InternalExtent());
1094 aData = (TColStd_intMapNode**) myData1;
1096 const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
1097 aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
1100 aNewExtent += p2->NbValues();
1101 isChanged = Standard_True;
1103 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1106 myExtent = aNewExtent;
1111 //=======================================================================
1112 //function : IsEqual
1113 //purpose : Boolean operation returns true if this map is equal to the other map
1114 //=======================================================================
1116 Standard_Boolean TColStd_PackedMapOfInteger::IsEqual(const TColStd_PackedMapOfInteger& theMap) const
1118 if (IsEmpty() && theMap.IsEmpty())
1119 return Standard_True;
1120 else if ( Extent() != theMap.Extent() )
1121 return Standard_False;
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;
1129 Standard_Integer i = 0;
1130 // Iteration of this map.
1131 for (; i <= NbBuckets(); i++) {
1132 const TColStd_intMapNode * p1 = aData1[i];
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)];
1143 if ( p2->IsEqual(aKeyInt) ) {
1144 if ( p1->Data() != p2->Data() )
1145 return Standard_False;
1148 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1150 // if the same block not found, maps are different
1152 return Standard_False;
1157 return Standard_True;
1161 //=======================================================================
1162 //function : IsSubset
1163 //purpose : Boolean operation returns true if this map if subset of other map
1164 //=======================================================================
1166 Standard_Boolean TColStd_PackedMapOfInteger::IsSubset (const TColStd_PackedMapOfInteger& theMap) const
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;
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();
1181 Standard_Integer i = 0;
1182 // Iteration of this map.
1183 for (; i <= NbBuckets(); i++) {
1184 const TColStd_intMapNode * p1 = aData1[i];
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)];
1195 return Standard_False;
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;
1202 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1207 return Standard_True;
1211 //=======================================================================
1212 //function : HasIntersection
1213 //purpose : Boolean operation returns true if this map intersects with other map
1214 //=======================================================================
1216 Standard_Boolean TColStd_PackedMapOfInteger::HasIntersection (const TColStd_PackedMapOfInteger& theMap) const
1218 if (IsEmpty() || theMap.IsEmpty()) // A * 0 == 0 * B == 0
1219 return Standard_False;
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;
1227 Standard_Integer i = 0;
1228 // Iteration of this map.
1229 for (; i <= NbBuckets(); i++) {
1230 const TColStd_intMapNode * p1 = aData1[i];
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)];
1241 if (p2->IsEqual(aKeyInt)) {
1242 if ( p1->Data() & p2->Data() )
1243 return Standard_True;
1246 p2 = reinterpret_cast <const TColStd_intMapNode*> (p2->Next());
1251 return Standard_False;