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