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)
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)
33 return theKey & MASK_HIGH;
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)
42 return HashCode (theKey >> 5, theUpperBound);
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)
51 return hashCodeForKey (static_cast<unsigned int> (theKey), theUpperBound);
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
59 explicit inline TColStd_intMapNode (TCollection_MapNode * ptr = 0L)
60 : TCollection_MapNode (ptr),
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)) {}
70 inline TColStd_intMapNode (unsigned int theMask,
72 TCollection_MapNode * ptr)
73 : TCollection_MapNode (ptr),
77 inline unsigned int Mask () const
80 inline unsigned int Data () const
83 inline unsigned int& ChangeMask ()
86 inline unsigned int& ChangeData ()
89 inline Standard_Integer Key() const
91 return static_cast<Standard_Integer> (maskedKey());
94 inline size_t NbValues () const
95 { return size_t(myMask & MASK_LOW) + 1; }
97 inline Standard_Boolean HasValues () const
98 { return (myData != 0); }
100 Standard_Integer HasValue (const Standard_Integer theValue) const
101 { return (myData & (1 << (theValue & MASK_LOW))); }
103 Standard_Boolean AddValue (const Standard_Integer theValue);
105 Standard_Boolean DelValue (const Standard_Integer theValue);
108 * Find the smallest non-zero bit under the given mask. Outputs the new mask
109 * that does not contain the detected bit.
111 Standard_Integer FindNext (unsigned int& theMask) const;
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
118 return hashCodeForKey (myMask, theUpperBound);
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
126 return isEqual (::maskedKey (static_cast<unsigned int> (theOtherKey)));
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
134 return isEqual (theOtherMapNode.maskedKey());
138 //! Returns the key of this map node with the mask applied to it
139 unsigned int maskedKey() const
141 return ::maskedKey (myMask);
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
149 return maskedKey() == theOtherMaskedKey;
158 //=======================================================================
159 //function : TColStd_intMapNode::AddValue
161 //=======================================================================
163 Standard_Boolean TColStd_PackedMapOfInteger::TColStd_intMapNode::AddValue (const Standard_Integer theValue)
165 Standard_Boolean aResult (Standard_False);
166 const Standard_Integer aValInt = (1 << (theValue & MASK_LOW));
167 if ((myData & aValInt) == 0) {
170 aResult = Standard_True;
175 //=======================================================================
176 //function : TColStd_intMapNode::DelValue
178 //=======================================================================
180 Standard_Boolean TColStd_PackedMapOfInteger::TColStd_intMapNode::DelValue (const Standard_Integer theValue)
182 Standard_Boolean aResult (Standard_False);
183 const Standard_Integer aValInt = (1 << (theValue & MASK_LOW));
184 if ((myData & aValInt) != 0) {
187 aResult = Standard_True;
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 //=======================================================================
200 inline size_t TColStd_Population (unsigned int& theMask,
201 const unsigned int theData)
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);
212 //=======================================================================
213 //function : TColStd_intMapNode_findNext
215 //=======================================================================
216 Standard_Integer TColStd_PackedMapOfInteger::TColStd_intMapNode_findNext (const Standard_Address theNode,
217 unsigned int& theMask)
219 const TColStd_intMapNode* aNode = reinterpret_cast<const TColStd_intMapNode*> (theNode);
220 unsigned int val = aNode->Data() & theMask;
223 theMask = ~0U; // void, nothing to do
225 unsigned int aMask = ~0U;
226 if ((val & 0x0000ffff) == 0) {
231 if ((val & 0x000000ff) == 0) {
236 if ((val & 0x0000000f) == 0) {
241 if ((val & 0x00000003) == 0) {
246 if ((val & 0x00000001) == 0) {
250 theMask = (aMask << 1);
252 return nZeros + aNode->Key();
255 //=======================================================================
256 //function : TColStd_intMapNode_findPrev
258 //=======================================================================
259 Standard_Integer TColStd_PackedMapOfInteger::TColStd_intMapNode_findPrev (const Standard_Address theNode,
260 unsigned int& theMask)
262 const TColStd_intMapNode* aNode = reinterpret_cast<const TColStd_intMapNode*> (theNode);
263 unsigned int val = aNode->Data() & theMask;
266 theMask = ~0U; // void, nothing to do
268 unsigned int aMask = ~0U;
269 if ((val & 0xffff0000) == 0) {
274 if ((val & 0xff000000) == 0) {
279 if ((val & 0xf0000000) == 0) {
284 if ((val & 0xc0000000) == 0) {
289 if ((val & 0x80000000) == 0) {
293 theMask = (aMask >> 1);
295 return (31 - nZeros) + aNode->Key();
298 //=======================================================================
301 //=======================================================================
303 TColStd_PackedMapOfInteger& TColStd_PackedMapOfInteger::Assign
304 (const TColStd_PackedMapOfInteger& theOther)
306 if (this != &theOther) {
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];
318 const Standard_Integer aHashCode = p->HashCode(nBuckets);
320 new TColStd_intMapNode (p->Mask(), p->Data(), aData[aHashCode]);
322 p = static_cast <const TColStd_intMapNode*> (p->Next());
325 // TColStd_MapIteratorOfPackedMapOfInteger anIt (theOther);
326 // for (; anIt.More(); anIt.Next())
330 myExtent = theOther.myExtent;
334 //=======================================================================
337 //=======================================================================
339 void TColStd_PackedMapOfInteger::ReSize (const Standard_Integer nbBuckets)
341 Standard_Integer newBuck;
342 Standard_Address newData1=NULL, dummy=NULL;
343 if (BeginResize (nbBuckets, newBuck, newData1, dummy))
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++) {
356 k = p->HashCode(newBuck);
357 TCollection_MapNode * q = p->Next();
358 p->Next() = newdata[k];
360 p = static_cast <TColStd_intMapNode*> (q);
365 EndResize (nbBuckets, newBuck, newData1, dummy);
369 //=======================================================================
372 //=======================================================================
374 void TColStd_PackedMapOfInteger::Clear ()
378 TColStd_intMapNode** data =
379 reinterpret_cast <TColStd_intMapNode**> (myData1);
380 TColStd_intMapNode * p;
381 for (i = 0; i <= NbBuckets(); i++) {
385 TCollection_MapNode * q = p->Next();
387 p = static_cast <TColStd_intMapNode*> (q);
392 TCollection_BasicMap::Destroy();
396 //=======================================================================
399 //=======================================================================
401 Standard_Boolean TColStd_PackedMapOfInteger::Add (const Standard_Integer aKey)
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);
412 if (p->IsEqual(aKey)) {
413 aResult = p->AddValue (aKey);
415 goto finish; // goto saves us 4 CPU clocks or 4% performance
417 p = static_cast <TColStd_intMapNode*> (p->Next());
419 // if (!p) { // not needed, as long as we exit the loop by goto
420 data[aHashCode] = new TColStd_intMapNode(aKey, aBucketHead);
422 aResult = Standard_True;
430 //=======================================================================
431 //function : Contains
433 //=======================================================================
435 Standard_Boolean TColStd_PackedMapOfInteger::Contains
436 (const Standard_Integer aKey) const
438 Standard_Boolean aResult (Standard_False);
440 TColStd_intMapNode** data = (TColStd_intMapNode**) myData1;
441 TColStd_intMapNode * p = data[hashCodeForKey (aKey, NbBuckets())];
443 if (p->IsEqual(aKey)) {
444 aResult = (p->HasValue (aKey) != 0);
447 p = static_cast <TColStd_intMapNode*> (p->Next());
453 //=======================================================================
456 //=======================================================================
458 Standard_Boolean TColStd_PackedMapOfInteger::Remove(const Standard_Integer aKey)
460 Standard_Boolean aResult (Standard_False);
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;
468 if (p->IsEqual(aKey)) {
469 aResult = p->DelValue (aKey);
472 if (p->HasValues() == Standard_False) {
474 if (q) q->Next() = p->Next();
475 else aBucketHead = static_cast<TColStd_intMapNode*>(p->Next());
482 p = static_cast <TColStd_intMapNode*> (p->Next());
488 //=======================================================================
489 //function : GetMinimalMapped
490 //purpose : Query the minimal contained key value.
491 //=======================================================================
493 Standard_Integer TColStd_PackedMapOfInteger::GetMinimalMapped () const
495 Standard_Integer aResult (IntegerLast());
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 = static_cast <const TColStd_intMapNode *>(p)->Key();
502 if (aResult > aKey) {
504 pFoundNode = static_cast<const TColStd_intMapNode *>(p);
509 unsigned int aFullMask (0xffffffff);
510 aResult = TColStd_intMapNode_findNext ((Standard_Address )pFoundNode, aFullMask);
516 //=======================================================================
517 //function : GetMaximalMapped
518 //purpose : Query the maximal contained key value.
519 //=======================================================================
521 Standard_Integer TColStd_PackedMapOfInteger::GetMaximalMapped () const
523 Standard_Integer aResult (IntegerFirst());
525 const TCollection_MapNode** aData = (const TCollection_MapNode**) myData1;
526 const TColStd_intMapNode * pFoundNode = 0L;
527 for (Standard_Integer i = 0; i <= NbBuckets(); i++) {
528 for (const TCollection_MapNode * p = aData[i]; p != 0L; p = p->Next()) {
529 const Standard_Integer aKey = static_cast <const TColStd_intMapNode *>(p)->Key();
530 if (aResult < aKey) {
532 pFoundNode = static_cast<const TColStd_intMapNode *>(p);
537 unsigned int aFullMask (0xffffffff);
538 aResult = TColStd_intMapNode_findPrev ((Standard_Address )pFoundNode, aFullMask);
544 //=======================================================================
546 //purpose : Boolean operation OR between 2 maps
547 //=======================================================================
549 void TColStd_PackedMapOfInteger::Union (const TColStd_PackedMapOfInteger& theMap1,
550 const TColStd_PackedMapOfInteger& theMap2)
552 if (theMap1.IsEmpty()) // 0 | B == B
554 else if (theMap2.IsEmpty()) // A | 0 == A
556 else if (myData1 == theMap1.myData1)
558 else if (myData1 == theMap2.myData1)
562 const TColStd_intMapNode** aData1 =
563 (const TColStd_intMapNode**) theMap1.myData1;
564 const TColStd_intMapNode** aData2 =
565 (const TColStd_intMapNode**) theMap2.myData1;
566 const Standard_Integer nBuckets1 = theMap1.NbBuckets();
567 const Standard_Integer nBuckets2 = theMap2.NbBuckets();
569 TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
570 // Iteration of the 1st map.
571 for (i = 0; i <= nBuckets1; i++) {
572 const TColStd_intMapNode * p1 = aData1[i];
574 unsigned int aNewMask = p1->Mask();
575 unsigned int aNewData = p1->Data();
576 size_t nValues (p1->NbValues());
577 // Find the corresponding block in the 2nd map
578 const TColStd_intMapNode * p2 =
579 aData2 [p1->HashCode(nBuckets2)];
581 if (p2->IsEqual(*p1)) {
582 aNewData |= p2->Data();
583 nValues = TColStd_Population (aNewMask, aNewData);
586 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
588 // Store the block - result of operation
590 ReSize(InternalExtent());
591 aData = (TColStd_intMapNode**) myData1;
593 const Standard_Integer aHashCode = p1->HashCode (NbBuckets());
594 aData[aHashCode] = new TColStd_intMapNode (aNewMask, aNewData,
598 p1 = static_cast <const TColStd_intMapNode*> (p1->Next());
601 // Iteration of the 2nd map.
602 for (i = 0; i <= nBuckets2; i++) {
603 const TColStd_intMapNode * p2 = aData2[i];
605 // Find the corresponding block in the 1st map
606 const TColStd_intMapNode * p1 =
607 aData1 [p2->HashCode (nBuckets1)];
609 if (p1->IsEqual(*p2))
611 p1 = static_cast <const TColStd_intMapNode*> (p1->Next());
613 // Add the block from the 2nd map only in the case when the similar
614 // block has not been found in the 1st map
617 ReSize(InternalExtent());
618 aData = (TColStd_intMapNode**) myData1;
620 const Standard_Integer aHashCode = p2->HashCode (NbBuckets());
621 aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
624 myExtent += p2->NbValues();
626 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
632 //=======================================================================
634 //purpose : Boolean operation OR with the given map
635 //=======================================================================
637 Standard_Boolean TColStd_PackedMapOfInteger::Unite(const TColStd_PackedMapOfInteger& theMap)
639 if (theMap.IsEmpty() || myData1 == theMap.myData1) // A | 0 == A | A == A
640 return Standard_False;
641 else if ( IsEmpty() ) { // 0 | B == B
643 return Standard_True;
646 size_t aNewExtent (myExtent);
647 TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
648 const TColStd_intMapNode** aData2 =
649 (const TColStd_intMapNode**) theMap.myData1;
650 const Standard_Integer nBuckets2 = theMap.NbBuckets();
652 // Iteration of the 2nd map.
653 for (Standard_Integer i = 0; i <= nBuckets2; i++) {
654 const TColStd_intMapNode * p2 = aData2[i];
656 // Find the corresponding block in the 1st (this) map
657 Standard_Integer aHashCode = p2->HashCode (NbBuckets());
658 TColStd_intMapNode * p1 = aData[aHashCode];
660 if (p1->IsEqual(*p2)) {
661 const size_t anOldPop = p1->NbValues();
662 unsigned int newData = p1->Data() | p2->Data();
663 if ( newData != p1->Data() ) {
664 p1->ChangeData() = newData;
665 aNewExtent = aNewExtent - anOldPop +
666 TColStd_Population (p1->ChangeMask(), newData);
670 p1 = static_cast <TColStd_intMapNode*> (p1->Next());
672 // If the block is not found in the 1st map, add it to the 1st map
675 ReSize(InternalExtent());
676 aData = (TColStd_intMapNode**) myData1;
677 aHashCode = p2->HashCode (NbBuckets());
679 aData[aHashCode] = new TColStd_intMapNode (p2->Mask(), p2->Data(),
682 aNewExtent += p2->NbValues();
684 p2 = static_cast <TColStd_intMapNode*> (p2->Next());
687 Standard_Boolean isChanged = ( myExtent != aNewExtent );
688 myExtent = aNewExtent;
693 //=======================================================================
694 //function : Intersection
695 //purpose : Boolean operation AND between 2 maps
696 //=======================================================================
698 void TColStd_PackedMapOfInteger::Intersection
699 (const TColStd_PackedMapOfInteger& theMap1,
700 const TColStd_PackedMapOfInteger& theMap2)
702 if (theMap1.IsEmpty() || theMap2.IsEmpty()) // A & 0 == 0 & B == 0
704 else if (myData1 == theMap1.myData1)
706 else if (myData1 == theMap2.myData1)
709 const TColStd_intMapNode** aData1, ** aData2;
710 Standard_Integer nBuckets1, nBuckets2;
711 if (theMap1.Extent() < theMap2.Extent()) {
712 aData1 = (const TColStd_intMapNode**) theMap1.myData1;
713 aData2 = (const TColStd_intMapNode**) theMap2.myData1;
714 nBuckets1 = theMap1.NbBuckets();
715 nBuckets2 = theMap2.NbBuckets();
718 aData1 = (const TColStd_intMapNode**) theMap2.myData1;
719 aData2 = (const TColStd_intMapNode**) theMap1.myData1;
720 nBuckets1 = theMap2.NbBuckets();
721 nBuckets2 = theMap1.NbBuckets();
724 TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
725 // Iteration of the 1st map.
726 for (Standard_Integer i = 0; i <= nBuckets1; i++) {
727 const TColStd_intMapNode * p1 = aData1[i];
729 // Find the corresponding block in the 2nd map
730 const TColStd_intMapNode * p2 =
731 aData2 [p1->HashCode (nBuckets2)];
733 if (p2->IsEqual(*p1)) {
734 const unsigned int aNewData = p1->Data() & p2->Data();
735 // Store the block - result of operation
738 ReSize(InternalExtent());
739 aData = (TColStd_intMapNode**) myData1;
741 const Standard_Integer aHashCode = p1->HashCode (NbBuckets());
742 unsigned int aNewMask = p1->Mask();
743 myExtent += TColStd_Population (aNewMask, aNewData);
744 aData[aHashCode]= new TColStd_intMapNode(aNewMask, aNewData,
750 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
752 p1 = static_cast <const TColStd_intMapNode*> (p1->Next());
758 //=======================================================================
759 //function : Intersect
760 //purpose : Boolean operation AND with the given map
761 //=======================================================================
763 Standard_Boolean TColStd_PackedMapOfInteger::Intersect
764 (const TColStd_PackedMapOfInteger& theMap)
766 if ( IsEmpty() ) // 0 & B == 0
767 return Standard_False;
768 else if (theMap.IsEmpty()) { // A & 0 == 0
770 return Standard_True;
772 else if (myData1 == theMap.myData1) // A & A == A
773 return Standard_False;
775 size_t aNewExtent (0);
776 TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
777 const TColStd_intMapNode** aData2 =
778 (const TColStd_intMapNode**) theMap.myData1;
779 const Standard_Integer nBuckets2 = theMap.NbBuckets();
781 // Iteration of this map.
782 for (Standard_Integer i = 0; i <= NbBuckets(); i++) {
783 TColStd_intMapNode * q = 0L;
784 TColStd_intMapNode * p1 = aData[i];
786 // Find the corresponding block in the 2nd map
787 const TColStd_intMapNode * p2 =
788 aData2 [p1->HashCode (nBuckets2)];
790 if (p2->IsEqual(*p1)) {
791 const unsigned int aNewData = p1->Data() & p2->Data();
792 // Store the block - result of operation
794 p2 = 0L; // no match - the block has to be removed
797 if ( aNewData != p1->Data() )
798 p1->ChangeData() = aNewData;
799 aNewExtent += TColStd_Population (p1->ChangeMask(), aNewData);
803 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
805 TColStd_intMapNode* pNext = static_cast <TColStd_intMapNode*> (p1->Next());
806 // If p2!=NULL, then the map node is kept and we move to the next one
807 // Otherwise we should remove the current node
812 if (q) q->Next() = pNext;
813 else aData[i] = pNext;
819 Standard_Boolean isChanged = ( myExtent != aNewExtent );
820 myExtent = aNewExtent;
825 //=======================================================================
826 //function : Subtraction
827 //purpose : Boolean operation SUBTRACT between two maps
828 //=======================================================================
830 void TColStd_PackedMapOfInteger::Subtraction
831 (const TColStd_PackedMapOfInteger& theMap1,
832 const TColStd_PackedMapOfInteger& theMap2)
834 if (theMap1.IsEmpty() || theMap2.myData1 == theMap1.myData1) // 0 \ A == A \ A == 0
836 else if (theMap2.IsEmpty()) // A \ 0 == A
838 else if (myData1 == theMap1.myData1)
840 else if (myData1 == theMap2.myData1) {
841 TColStd_PackedMapOfInteger aMap;
842 aMap.Subtraction ( theMap1, theMap2 );
846 const TColStd_intMapNode** aData1 =
847 (const TColStd_intMapNode**) theMap1.myData1;
848 const TColStd_intMapNode** aData2 =
849 (const TColStd_intMapNode**) theMap2.myData1;
850 const Standard_Integer nBuckets1 = theMap1.NbBuckets();
851 const Standard_Integer nBuckets2 = theMap2.NbBuckets();
853 TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
854 // Iteration of the 1st map.
855 for (Standard_Integer i = 0; i <= nBuckets1; i++) {
856 const TColStd_intMapNode * p1 = aData1[i];
858 unsigned int aNewMask = p1->Mask();
859 unsigned int aNewData = p1->Data();
860 size_t nValues (p1->NbValues());
861 // Find the corresponding block in the 2nd map
862 const TColStd_intMapNode * p2 =
863 aData2 [p1->HashCode (nBuckets2)];
865 if (p2->IsEqual(*p1)) {
866 aNewData &= ~p2->Data();
867 nValues = TColStd_Population (aNewMask, aNewData);
870 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
872 // Store the block - result of operation
875 ReSize(InternalExtent());
876 aData = (TColStd_intMapNode**) myData1;
878 const Standard_Integer aHashCode = p1->HashCode (NbBuckets());
879 aData[aHashCode]= new TColStd_intMapNode (aNewMask, aNewData,
884 p1 = static_cast <const TColStd_intMapNode*> (p1->Next());
890 //=======================================================================
891 //function : Subtract
892 //purpose : Boolean operation SUBTRACT with the given map
893 //=======================================================================
895 Standard_Boolean TColStd_PackedMapOfInteger::Subtract
896 (const TColStd_PackedMapOfInteger& theMap)
898 if ( IsEmpty() || theMap.IsEmpty() ) // 0 \ B == 0; A \ 0 == A
899 return Standard_False;
900 else if (myData1 == theMap.myData1) { // A \ A == 0
902 return Standard_True;
905 size_t aNewExtent (0);
906 TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
907 const TColStd_intMapNode** aData2 =
908 (const TColStd_intMapNode**) theMap.myData1;
909 const Standard_Integer nBuckets2 = theMap.NbBuckets();
910 // Iteration of this map.
911 for (Standard_Integer i = 0; i <= NbBuckets(); i++) {
912 TColStd_intMapNode * q = 0L;
913 TColStd_intMapNode * p1 = aData[i];
915 TColStd_intMapNode* pNext = static_cast <TColStd_intMapNode*> (p1->Next());
916 // Find the corresponding block in the 2nd map
917 const TColStd_intMapNode * p2 =
918 aData2 [p1->HashCode (nBuckets2)];
920 if (p2->IsEqual(*p1)) {
921 const unsigned int aNewData = p1->Data() & ~p2->Data();
922 // Store the block - result of operation
924 // no match - the block has to be removed
926 if (q) q->Next() = pNext;
927 else aData[i] = pNext;
930 else if ( aNewData != p1->Data() ) {
931 p1->ChangeData() = aNewData;
932 aNewExtent += TColStd_Population (p1->ChangeMask(), aNewData);
936 aNewExtent += p1->NbValues();
941 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
944 aNewExtent += p1->NbValues();
950 Standard_Boolean isChanged = ( myExtent != aNewExtent );
951 myExtent = aNewExtent;
956 //=======================================================================
957 //function : Difference
958 //purpose : Boolean operation XOR
959 //=======================================================================
961 void TColStd_PackedMapOfInteger::Difference (const TColStd_PackedMapOfInteger& theMap1,
962 const TColStd_PackedMapOfInteger& theMap2)
964 if (theMap1.IsEmpty()) // 0 ^ B == B
966 else if (theMap2.IsEmpty()) // A ^ 0 == A
968 else if (myData1 == theMap1.myData1)
970 else if (myData1 == theMap2.myData1)
974 const TColStd_intMapNode** aData1 =
975 (const TColStd_intMapNode**) theMap1.myData1;
976 const TColStd_intMapNode** aData2 =
977 (const TColStd_intMapNode**) theMap2.myData1;
978 const Standard_Integer nBuckets1 = theMap1.NbBuckets();
979 const Standard_Integer nBuckets2 = theMap2.NbBuckets();
981 TColStd_intMapNode** aData = (TColStd_intMapNode**) myData1;
983 // Iteration of the 1st map.
984 for (i = 0; i <= nBuckets1; i++) {
985 const TColStd_intMapNode * p1 = aData1[i];
987 unsigned int aNewMask = p1->Mask();
988 unsigned int aNewData = p1->Data();
989 size_t nValues (p1->NbValues());
990 // Find the corresponding block in the 2nd map
991 const TColStd_intMapNode * p2 =
992 aData2 [p1->HashCode (nBuckets2)];
994 if (p2->IsEqual(*p1)) {
995 aNewData ^= p2->Data();
996 nValues = TColStd_Population (aNewMask, aNewData);
999 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
1001 // Store the block - result of operation
1004 ReSize(InternalExtent());
1005 aData = (TColStd_intMapNode**) myData1;
1007 const Standard_Integer aHashCode = p1->HashCode (NbBuckets());
1008 aData[aHashCode]= new TColStd_intMapNode (aNewMask, aNewData,
1011 myExtent += nValues;
1013 p1 = static_cast <const TColStd_intMapNode*> (p1->Next());
1017 // Iteration of the 2nd map.
1018 for (i = 0; i <= nBuckets2; i++) {
1019 const TColStd_intMapNode * p2 = aData2[i];
1021 // Find the corresponding block in the 1st map
1022 const TColStd_intMapNode * p1 =
1023 aData1 [p2->HashCode (nBuckets1)];
1025 if (p1->IsEqual(*p2))
1027 p1 = static_cast <const TColStd_intMapNode*> (p1->Next());
1029 // Add the block from the 2nd map only in the case when the similar
1030 // block has not been found in the 1st map
1033 ReSize(InternalExtent());
1034 aData = (TColStd_intMapNode**) myData1;
1036 const Standard_Integer aHashCode = p2->HashCode (NbBuckets());
1037 aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
1040 myExtent += p2->NbValues();
1042 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
1048 //=======================================================================
1050 //purpose : Boolean operation XOR
1051 //=======================================================================
1053 Standard_Boolean TColStd_PackedMapOfInteger::Differ(const TColStd_PackedMapOfInteger& theMap)
1055 if (theMap.IsEmpty()) // A ^ 0 = A
1056 return Standard_False;
1057 else if (IsEmpty()) { // 0 ^ B = B
1059 return Standard_True;
1061 else if( myData1 == theMap.myData1) { // A ^ A == 0
1063 return Standard_True;
1066 size_t aNewExtent (0);
1067 TColStd_intMapNode** aData1 = (TColStd_intMapNode**) myData1;
1068 const TColStd_intMapNode** aData2 =
1069 (const TColStd_intMapNode**) theMap.myData1;
1070 const Standard_Integer nBuckets2 = theMap.NbBuckets();
1071 Standard_Boolean isChanged = Standard_False;
1072 Standard_Integer i = 0;
1073 // Iteration by other map
1074 for ( ; i <= nBuckets2; i++) {
1075 TColStd_intMapNode * q = 0L;
1076 const TColStd_intMapNode * p2 = aData2[i];
1078 // Find the corresponding block in the 1st map
1079 TColStd_intMapNode * p1 =
1080 aData1[p2->HashCode (NbBuckets())];
1081 TColStd_intMapNode* pNext = static_cast <TColStd_intMapNode*> (p1->Next());
1084 if (p1->IsEqual(*p2)) {
1085 const unsigned int aNewData = p1->Data() ^ p2->Data();
1086 // Store the block - result of operation
1087 if (aNewData == 0) {
1088 // no match - the block has to be removed
1090 if (q) q->Next() = pNext;
1091 else aData1[i] = pNext;
1094 else if ( aNewData != p1->Data() ) {
1095 p1->ChangeData() = aNewData;
1096 isChanged = Standard_True;
1097 aNewExtent += TColStd_Population (p1->ChangeMask(), aNewData);
1104 // Add the block from the 2nd map only in the case when the similar
1105 // block has not been found in the 1st map
1106 TColStd_intMapNode** aData = NULL;
1109 ReSize(InternalExtent());
1110 aData = (TColStd_intMapNode**) myData1;
1112 const Standard_Integer aHashCode = p2->HashCode (NbBuckets());
1113 aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
1116 aNewExtent += p2->NbValues();
1117 isChanged = Standard_True;
1119 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
1122 myExtent = aNewExtent;
1127 //=======================================================================
1128 //function : IsEqual
1129 //purpose : Boolean operation returns true if this map is equal to the other map
1130 //=======================================================================
1132 Standard_Boolean TColStd_PackedMapOfInteger::IsEqual(const TColStd_PackedMapOfInteger& theMap) const
1134 if (IsEmpty() && theMap.IsEmpty())
1135 return Standard_True;
1136 else if ( Extent() != theMap.Extent() )
1137 return Standard_False;
1139 const TColStd_intMapNode** aData1 = (const TColStd_intMapNode**) myData1;
1140 const TColStd_intMapNode** aData2 = (const TColStd_intMapNode**) theMap.myData1;
1141 const Standard_Integer nBuckets2 = theMap.NbBuckets();
1142 if(aData1 == aData2)
1143 return Standard_True;
1145 Standard_Integer i = 0;
1146 // Iteration of this map.
1147 for (; i <= NbBuckets(); i++) {
1148 const TColStd_intMapNode * p1 = aData1[i];
1150 TColStd_intMapNode* pNext = static_cast <TColStd_intMapNode*> (p1->Next());
1151 // Find the corresponding block in the 2nd map
1152 const TColStd_intMapNode * p2 =
1153 aData2 [p1->HashCode (nBuckets2)];
1155 if ( p2->IsEqual(*p1) ) {
1156 if ( p1->Data() != p2->Data() )
1157 return Standard_False;
1160 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
1162 // if the same block not found, maps are different
1164 return Standard_False;
1169 return Standard_True;
1173 //=======================================================================
1174 //function : IsSubset
1175 //purpose : Boolean operation returns true if this map if subset of other map
1176 //=======================================================================
1178 Standard_Boolean TColStd_PackedMapOfInteger::IsSubset (const TColStd_PackedMapOfInteger& theMap) const
1180 if ( IsEmpty() ) // 0 <= A
1181 return Standard_True;
1182 else if ( theMap.IsEmpty() ) // ! ( A <= 0 )
1183 return Standard_False;
1184 else if ( Extent() > theMap.Extent() )
1185 return Standard_False;
1187 const TColStd_intMapNode** aData1 = (const TColStd_intMapNode**) myData1;
1188 const TColStd_intMapNode** aData2 = (const TColStd_intMapNode**) theMap.myData1;
1189 if(aData1 == aData2)
1190 return Standard_True;
1191 const Standard_Integer nBuckets2 = theMap.NbBuckets();
1193 Standard_Integer i = 0;
1194 // Iteration of this map.
1195 for (; i <= NbBuckets(); i++) {
1196 const TColStd_intMapNode * p1 = aData1[i];
1198 TColStd_intMapNode* pNext = static_cast <TColStd_intMapNode*> (p1->Next());
1199 // Find the corresponding block in the 2nd map
1200 const TColStd_intMapNode * p2 =
1201 aData2 [p1->HashCode (nBuckets2)];
1203 return Standard_False;
1205 if ( p2->IsEqual(*p1) ) {
1206 if ( p1->Data() & ~p2->Data() ) // at least one bit set in p1 is not set in p2
1207 return Standard_False;
1210 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
1215 return Standard_True;
1219 //=======================================================================
1220 //function : HasIntersection
1221 //purpose : Boolean operation returns true if this map intersects with other map
1222 //=======================================================================
1224 Standard_Boolean TColStd_PackedMapOfInteger::HasIntersection (const TColStd_PackedMapOfInteger& theMap) const
1226 if (IsEmpty() || theMap.IsEmpty()) // A * 0 == 0 * B == 0
1227 return Standard_False;
1229 const TColStd_intMapNode** aData1 = (const TColStd_intMapNode**) myData1;
1230 const TColStd_intMapNode** aData2 = (const TColStd_intMapNode**) theMap.myData1;
1231 const Standard_Integer nBuckets2 = theMap.NbBuckets();
1232 if(aData1 == aData2)
1233 return Standard_True;
1235 Standard_Integer i = 0;
1236 // Iteration of this map.
1237 for (; i <= NbBuckets(); i++) {
1238 const TColStd_intMapNode * p1 = aData1[i];
1240 TColStd_intMapNode* pNext = static_cast <TColStd_intMapNode*> (p1->Next());
1241 // Find the corresponding block in the 2nd map
1242 const TColStd_intMapNode * p2 =
1243 aData2 [p1->HashCode (nBuckets2)];
1245 if (p2->IsEqual(*p1)) {
1246 if ( p1->Data() & p2->Data() )
1247 return Standard_True;
1250 p2 = static_cast <const TColStd_intMapNode*> (p2->Next());
1255 return Standard_False;