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