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