1 // Created on: 2005-11-05
2 // Created by: Alexander GRIGORIEV
3 // Copyright (c) 2005-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef TColStd_PackedMapOfInteger_HeaderFile
17 #define TColStd_PackedMapOfInteger_HeaderFile
19 #include <Standard.hxx>
20 #include <Standard_Address.hxx>
21 #include <Standard_Boolean.hxx>
22 #include <Standard_DefineAlloc.hxx>
23 #include <Standard_Integer.hxx>
24 #include <Standard_NoSuchObject.hxx>
25 #include <Standard_OStream.hxx>
26 #include <Standard_Handle.hxx>
29 * Optimized Map of integer values. Each block of 32 integers is stored in 8 bytes in memory.
31 class TColStd_PackedMapOfInteger
39 static const unsigned int MASK_LOW = 0x001f;
42 static const unsigned int MASK_HIGH = ~MASK_LOW;
44 //! Class implementing a block of 32 consecutive integer values as a node of a Map collection.
45 //! The data are stored in 64 bits as:
46 //! - bits 0 - 4 : (number of integers stored in the block) - 1;
47 //! - bits 5 - 31: base address of the block of integers (low bits assumed 0)
48 //! - bits 32 - 63: 32-bit field where each bit indicates the presence of the corresponding integer in the block.
49 //! Number of non-zero bits must be equal to the number expressed in bits 0-4.
50 class TColStd_intMapNode
53 TColStd_intMapNode (TColStd_intMapNode* thePtr = NULL)
54 : myNext (thePtr), myMask (0), myData (0) {}
56 TColStd_intMapNode (Standard_Integer theValue, TColStd_intMapNode*& thePtr)
58 myMask ((unsigned int) (theValue & MASK_HIGH)),
59 myData (1 << (theValue & MASK_LOW)) {}
61 TColStd_intMapNode (unsigned int theMask, unsigned int theData, TColStd_intMapNode* thePtr)
66 unsigned int Mask() const { return myMask; }
68 unsigned int Data() const { return myData; }
70 unsigned int& ChangeMask() { return myMask; }
72 unsigned int& ChangeData() { return myData; }
74 //! Compute the sequential index of this packed node in the map.
75 Standard_Integer Key() const { return Standard_Integer (myMask & MASK_HIGH); }
77 //! Return the number of set integer keys.
78 size_t NbValues() const { return size_t(myMask & MASK_LOW) + 1; }
80 //! Return TRUE if this packed node is not empty.
81 Standard_Boolean HasValues() const { return (myData != 0); }
83 //! Return TRUE if the given integer key is set within this packed node.
84 Standard_Integer HasValue (Standard_Integer theValue) const { return (myData & (1 << (theValue & MASK_LOW))); }
86 //! Add integer key to this packed node.
87 //! @return TRUE if key has been added
88 Standard_Boolean AddValue (Standard_Integer theValue)
90 const Standard_Integer aValInt = (1 << (theValue & MASK_LOW));
91 if ((myData & aValInt) == 0)
97 return Standard_False;
100 //! Delete integer key from this packed node.
101 //! @return TRUE if key has been deleted
102 Standard_Boolean DelValue (Standard_Integer theValue)
104 const Standard_Integer aValInt = (1 << (theValue & MASK_LOW));
105 if ((myData & aValInt) != 0)
109 return Standard_True;
111 return Standard_False;
114 //! Find the smallest non-zero bit under the given mask. Outputs the new mask
115 //! that does not contain the detected bit.
116 Standard_Integer FindNext (unsigned int& theMask) const;
118 //! Return the next node having the same hash code.
119 TColStd_intMapNode* Next() const { return myNext; }
121 //! Set the next node having the same hash code.
122 void SetNext (TColStd_intMapNode* theNext) { myNext = theNext; }
125 //! Support of Map interface.
126 Standard_Integer HashCode (Standard_Integer theUpper) const
128 return ::HashCode (Standard_Integer(myMask >> 5), theUpper);
131 //! Support of Map interface.
132 Standard_Boolean IsEqual (Standard_Integer theOther) const
134 return ((myMask >> 5) == (unsigned)theOther);
138 TColStd_intMapNode* myNext;
145 //! Iterator of class TColStd_PackedMapOfInteger.
150 /// Empty Constructor.
160 Iterator (const TColStd_PackedMapOfInteger& theMap)
161 : myBuckets (theMap.myData1),
163 myNbBuckets (theMap.myData1 != NULL ? theMap.myNbBuckets : -1),
168 myKey = myNode != NULL ? TColStd_intMapNode_findNext (myNode, myIntMask) : 0;
171 //! Re-initialize with the same or another Map instance.
172 void Initialize (const TColStd_PackedMapOfInteger& theMap)
174 myBuckets = theMap.myData1;
177 myNbBuckets = theMap.myData1 != NULL ? theMap.myNbBuckets : -1;
181 myKey = myNode != NULL ? TColStd_intMapNode_findNext (myNode, myIntMask) : 0;
184 //! Restart the iteration
192 myKey = myNode != NULL ? TColStd_intMapNode_findNext (myNode, myIntMask) : 0;
195 //! Query the iterated key.
196 Standard_Integer Key() const
198 Standard_NoSuchObject_Raise_if ((myIntMask == ~0U), "TColStd_MapIteratorOfPackedMapOfInteger::Key");
202 //! Return TRUE if iterator points to the node.
203 Standard_Boolean More() const { return myNode != NULL; }
205 //! Increment the iterator
208 for (; myNode != NULL; next())
210 myKey = TColStd_intMapNode_findNext (myNode, myIntMask);
211 if (myIntMask != ~0u)
218 //! Go to the next bucket in the map.
221 if (myBuckets == NULL)
228 myNode = myNode->Next();
231 while (myNode == NULL)
234 if (myBucket > myNbBuckets)
238 myNode = myBuckets[myBucket];
243 TColStd_intMapNode** myBuckets;
244 TColStd_intMapNode* myNode;
245 Standard_Integer myNbBuckets;
246 Standard_Integer myBucket;
248 unsigned int myIntMask; //!< all bits set above the iterated position
249 Standard_Integer myKey; //!< Currently iterated key
255 TColStd_PackedMapOfInteger (const Standard_Integer theNbBuckets = 1)
257 myNbBuckets (theNbBuckets),
258 myNbPackedMapNodes (0),
262 TColStd_PackedMapOfInteger (const TColStd_PackedMapOfInteger& theOther)
265 myNbPackedMapNodes (0),
271 inline TColStd_PackedMapOfInteger&
272 operator = (const TColStd_PackedMapOfInteger& Other)
273 { return Assign(Other); }
275 Standard_EXPORT TColStd_PackedMapOfInteger&
276 Assign (const TColStd_PackedMapOfInteger&);
277 Standard_EXPORT void ReSize (const Standard_Integer NbBuckets);
278 Standard_EXPORT void Clear ();
279 ~TColStd_PackedMapOfInteger() { Clear(); }
280 Standard_EXPORT Standard_Boolean
281 Add (const Standard_Integer aKey);
282 Standard_EXPORT Standard_Boolean
283 Contains (const Standard_Integer aKey) const;
284 Standard_EXPORT Standard_Boolean
285 Remove (const Standard_Integer aKey);
287 //! Returns the number of map buckets (not that since integers are packed in this map, the number is smaller than extent).
288 Standard_Integer NbBuckets() const { return myNbBuckets; }
290 //! Returns map extent.
291 Standard_Integer Extent() const { return Standard_Integer (myExtent); }
293 //! Returns TRUE if map is empty.
294 Standard_Boolean IsEmpty() const { return myNbPackedMapNodes == 0; }
297 * Query the minimal contained key value.
299 Standard_EXPORT Standard_Integer GetMinimalMapped () const;
302 * Query the maximal contained key value.
304 Standard_EXPORT Standard_Integer GetMaximalMapped () const;
306 //! Prints useful statistics about the map.
307 //! It can be used to test the quality of the hashcoding.
308 Standard_EXPORT void Statistics (Standard_OStream& theStream) const;
311 //!@name Boolean operations with maps as sets of integers
315 * Sets this Map to be the result of union (aka addition, fuse, merge, boolean OR) operation between two given Maps.
316 * The new Map contains the values that are contained either in the first map or in the second map or in both.
317 * All previous contents of this Map is cleared. This map (result of the boolean operation) can also be passed as one of operands.
319 Standard_EXPORT void Union (const TColStd_PackedMapOfInteger&,
320 const TColStd_PackedMapOfInteger&);
323 * Apply to this Map the boolean operation union (aka addition, fuse, merge, boolean OR) with another (given) Map.
324 * The result contains the values that were previously contained in this map or contained in the given (operand) map.
325 * This algorithm is similar to method Union().
326 * @return True if content of this map is changed
328 Standard_EXPORT Standard_Boolean Unite (const TColStd_PackedMapOfInteger&);
331 * Overloaded operator version of Unite().
333 TColStd_PackedMapOfInteger& operator |= (const TColStd_PackedMapOfInteger& MM)
334 { Unite(MM); return *this; }
337 * Sets this Map to be the result of intersection (aka multiplication, common, boolean AND) operation between two given Maps.
338 * The new Map contains only the values that are contained in both map operands.
339 * All previous contents of this Map is cleared. This same map (result of the boolean operation) can also be used as one of operands.
340 * The order of operands makes no difference; the method minimizes internally the number of iterations using the smallest map for the loop.
342 Standard_EXPORT void Intersection (const TColStd_PackedMapOfInteger&,
343 const TColStd_PackedMapOfInteger&);
346 * Apply to this Map the intersection operation (aka multiplication, common, boolean AND) with another (given) Map.
347 * The result contains only the values that are contained in both this and the given maps.
348 * This algorithm is similar to method Intersection().
349 * @return True if content of this map is changed
351 Standard_EXPORT Standard_Boolean Intersect (const TColStd_PackedMapOfInteger&);
354 * Overloaded operator version of Intersect().
356 TColStd_PackedMapOfInteger& operator &= (const TColStd_PackedMapOfInteger& MM)
357 { Intersect(MM); return *this; }
360 * Sets this Map to be the result of subtraction
361 * (aka set-theoretic difference, relative complement, exclude, cut, boolean NOT) operation between two given Maps.
362 * The new Map contains only the values that are contained in the first map operands and not contained in the second one.
363 * All previous contents of this Map is cleared.
364 * This map (result of the boolean operation) can also be used as the first operand.
366 Standard_EXPORT void Subtraction (const TColStd_PackedMapOfInteger&,
367 const TColStd_PackedMapOfInteger&);
370 * Apply to this Map the subtraction (aka set-theoretic difference, relative complement, exclude, cut, boolean NOT) operation with another (given) Map.
371 * The result contains only the values that were previously contained in this map and not contained in this map.
372 * This algorithm is similar to method Subtract() with two operands.
373 * @return True if contents of this map is changed
375 Standard_EXPORT Standard_Boolean Subtract (const TColStd_PackedMapOfInteger&);
378 * Overloaded operator version of Subtract().
380 TColStd_PackedMapOfInteger& operator -= (const TColStd_PackedMapOfInteger& MM)
381 { Subtract(MM); return *this; }
384 * Sets this Map to be the result of symmetric difference (aka exclusive disjunction, boolean XOR) operation between two given Maps.
385 * The new Map contains the values that are contained only in the first or the second operand maps but not in both.
386 * All previous contents of this Map is cleared.
387 * This map (result of the boolean operation) can also be used as one of operands.
389 Standard_EXPORT void Difference (const TColStd_PackedMapOfInteger&,
390 const TColStd_PackedMapOfInteger&);
393 * Apply to this Map the symmetric difference (aka exclusive disjunction, boolean XOR) operation with another (given) Map.
394 * The result contains the values that are contained only in this or the operand map, but not in both.
395 * This algorithm is similar to method Difference().
396 * @return True if contents of this map is changed
398 Standard_EXPORT Standard_Boolean Differ (const TColStd_PackedMapOfInteger&);
401 * Overloaded operator version of Differ().
403 TColStd_PackedMapOfInteger& operator ^= (const TColStd_PackedMapOfInteger& MM)
404 { Differ(MM); return *this; }
407 * Returns True if this map is equal to the given one, i.e. they contain the
408 * same sets of elements
410 Standard_EXPORT Standard_Boolean IsEqual (const TColStd_PackedMapOfInteger&) const;
413 * Overloaded operator version of IsEqual().
415 Standard_Boolean operator == (const TColStd_PackedMapOfInteger& MM) const
416 { return IsEqual(MM); }
419 * Returns True if this map is subset of the given one, i.e. all elements
420 * contained in this map is contained also in the operand map.
421 * if this map is empty that this method returns true for any operand map.
423 Standard_EXPORT Standard_Boolean IsSubset (const TColStd_PackedMapOfInteger&) const;
426 * Overloaded operator version of IsSubset().
428 Standard_Boolean operator <= (const TColStd_PackedMapOfInteger& MM) const
429 { return IsSubset(MM); }
432 * Returns True if this map has common items with the given one.
434 Standard_EXPORT Standard_Boolean HasIntersection (const TColStd_PackedMapOfInteger&) const;
440 //! Returns TRUE if resizing the map should be considered.
441 Standard_Boolean Resizable() const { return IsEmpty() || (myNbPackedMapNodes > myNbBuckets); }
443 //! Return an integer index for specified key.
444 static Standard_Integer packedKeyIndex (Standard_Integer theKey) { return (unsigned)theKey >> 5; }
448 //! Find the smallest non-zero bit under the given mask.
449 //! Outputs the new mask that does not contain the detected bit.
450 Standard_EXPORT static Standard_Integer TColStd_intMapNode_findNext (const Standard_Address theNode,
451 unsigned int& theMask);
453 //! Find the highest non-zero bit under the given mask.
454 //! Outputs the new mask that does not contain the detected bit.
455 Standard_EXPORT static Standard_Integer TColStd_intMapNode_findPrev (const Standard_Address theNode,
456 unsigned int& theMask);
458 //! Compute the population (i.e., the number of non-zero bits) of the 32-bit word theData.
459 //! The population is stored decremented as it is defined in TColStd_intMapNode.
460 //! Source: H.S.Warren, Hacker's Delight, Addison-Wesley Inc. 2002, Ch.5.1
461 static size_t TColStd_Population (unsigned int& theMask, unsigned int theData)
463 unsigned int aRes = theData - ((theData>>1) & 0x55555555);
464 aRes = (aRes & 0x33333333) + ((aRes>>2) & 0x33333333);
465 aRes = (aRes + (aRes>>4)) & 0x0f0f0f0f;
466 aRes = aRes + (aRes>>8);
467 aRes = aRes + (aRes>>16);
468 theMask = (theMask & TColStd_PackedMapOfInteger::MASK_HIGH) | ((aRes - 1) & TColStd_PackedMapOfInteger::MASK_LOW);
469 return size_t(aRes & 0x3f);
474 TColStd_intMapNode** myData1; //!< data array
475 Standard_Integer myNbBuckets; //!< number of buckets (size of data array)
476 Standard_Integer myNbPackedMapNodes; //!< amount of packed map nodes
477 Standard_Size myExtent; //!< extent of this map (number of unpacked integer keys)