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