Commit | Line | Data |
---|---|---|
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. |
27 | class TColStd_PackedMapOfInteger::TColStd_intMapNode : public TCollection_MapNode | |
7fd59977 | 28 | { |
29 | public: | |
30 | inline TColStd_intMapNode (TCollection_MapNode * ptr = 0L) | |
31 | : TCollection_MapNode (ptr), | |
32 | myMask (0), | |
33 | myData (0) {} | |
34 | ||
35 | inline TColStd_intMapNode (const Standard_Integer theValue, | |
36 | TCollection_MapNode *& ptr) | |
37 | : TCollection_MapNode (ptr), | |
38 | myMask ((unsigned int) (theValue & MASK_HIGH)), | |
39 | myData (1 << (theValue & MASK_LOW)) {} | |
40 | ||
41 | inline TColStd_intMapNode (unsigned int theMask, | |
42 | unsigned int theData, | |
43 | TCollection_MapNode * ptr) | |
44 | : TCollection_MapNode (ptr), | |
45 | myMask (theMask), | |
46 | myData (theData) {} | |
47 | ||
48 | inline unsigned int Mask () const | |
49 | { return myMask; } | |
50 | ||
51 | inline unsigned int Data () const | |
52 | { return myData; } | |
53 | ||
54 | inline unsigned int& ChangeMask () | |
55 | { return myMask; } | |
56 | ||
57 | inline unsigned int& ChangeData () | |
58 | { return myData; } | |
59 | ||
60 | inline Standard_Integer Key () const | |
61 | { return Standard_Integer (myMask & MASK_HIGH); } | |
62 | ||
63 | inline size_t NbValues () const | |
64 | { return size_t(myMask & MASK_LOW) + 1; } | |
65 | ||
66 | inline Standard_Boolean HasValues () const | |
67 | { return (myData != 0); } | |
68 | ||
69 | Standard_Integer HasValue (const Standard_Integer theValue) const | |
70 | { return (myData & (1 << (theValue & MASK_LOW))); } | |
71 | ||
72 | Standard_Boolean AddValue (const Standard_Integer theValue); | |
73 | ||
74 | Standard_Boolean DelValue (const Standard_Integer theValue); | |
75 | ||
76 | /** | |
77 | * Find the smallest non-zero bit under the given mask. Outputs the new mask | |
78 | * that does not contain the detected bit. | |
79 | */ | |
80 | Standard_Integer FindNext (unsigned int& theMask) const; | |
81 | ||
82 | /** | |
83 | * Support of Map interface. | |
84 | */ | |
85 | inline Standard_Integer HashCode (const Standard_Integer theUpper) const | |
86 | { | |
87 | return ::HashCode (Standard_Integer(myMask >> 5), theUpper); | |
88 | } | |
89 | ||
90 | /** | |
91 | * Support of Map interface. | |
92 | */ | |
93 | inline Standard_Boolean IsEqual (const Standard_Integer theOther) const | |
94 | { | |
95 | return ((myMask >> 5) == (unsigned)theOther); | |
96 | } | |
97 | ||
7fd59977 | 98 | private: |
99 | unsigned int myMask; | |
100 | unsigned int myData; | |
101 | }; | |
102 | ||
103 | ||
104 | //======================================================================= | |
105 | //function : TColStd_intMapNode::AddValue | |
106 | //purpose : | |
107 | //======================================================================= | |
108 | ||
683d15cb | 109 | Standard_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 | 126 | Standard_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 | ||
146 | inline size_t TColStd_Population (unsigned int& theMask, | |
147 | const unsigned int theData) | |
148 | { | |
149 | unsigned int aRes = theData - ((theData>>1) & 0x55555555); | |
150 | aRes = (aRes & 0x33333333) + ((aRes>>2) & 0x33333333); | |
151 | aRes = (aRes + (aRes>>4)) & 0x0f0f0f0f; | |
152 | aRes = aRes + (aRes>>8); | |
153 | aRes = aRes + (aRes>>16); | |
154 | theMask = (theMask & MASK_HIGH) | ((aRes-1) & MASK_LOW); | |
155 | return (size_t) (aRes & 0x3f); | |
156 | } | |
157 | ||
158 | //======================================================================= | |
159 | //function : TColStd_intMapNode_findNext | |
683d15cb | 160 | //purpose : |
7fd59977 | 161 | //======================================================================= |
3d77e962 | 162 | Standard_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 | 205 | Standard_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 | ||
249 | TColStd_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 | ||
285 | void 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 | ||
320 | void 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 | ||
347 | Standard_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 | ||
382 | Standard_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 | ||
406 | Standard_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 | ||
442 | Standard_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); | |
a738b534 | 460 | aResult = TColStd_intMapNode_findNext ((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 | ||
471 | Standard_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); | |
a738b534 | 489 | aResult = TColStd_intMapNode_findPrev ((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 | ||
500 | void 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 | ||
594 | Standard_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 | ||
658 | void 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 | ||
727 | Standard_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 | ||
798 | void 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 | ||
866 | Standard_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 | ||
936 | void 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 | ||
1034 | Standard_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 | ||
1118 | Standard_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 | ||
1168 | Standard_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 | ||
1218 | Standard_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 | } |