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