0029764: Foundation Classes, TColStd_MapIteratorOfPackedMapOfInteger - workaround...
[occt.git] / src / TColStd / TColStd_PackedMapOfInteger.hxx
CommitLineData
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#ifndef TColStd_PackedMapOfInteger_HeaderFile
17#define TColStd_PackedMapOfInteger_HeaderFile
18
1c35b92f 19#include <Standard_DefineAlloc.hxx>
683d15cb 20#include <Standard_NoSuchObject.hxx>
7fd59977 21#include <TCollection_BasicMap.hxx>
683d15cb 22#include <TCollection_BasicMapIterator.hxx>
7fd59977 23
24/**
ebc93ae7 25 * Optimized Map of integer values. Each block of 32 integers is stored in 8 bytes in memory.
7fd59977 26 */
7fd59977 27class TColStd_PackedMapOfInteger : private TCollection_BasicMap
28{
29 public:
30 // operators new and delete must be defined explicitly
31 // since inherited ones are not accessible
1c35b92f 32 DEFINE_STANDARD_ALLOC
683d15cb 33
34public:
35
36 //! Iterator of class TColStd_PackedMapOfInteger.
37 class Iterator : public TCollection_BasicMapIterator
38 {
39 public:
40
41 /// Empty Constructor.
42 Iterator() : myIntMask (~0U), myKey (0) {}
43
44 /// Constructor.
45 Iterator (const TColStd_PackedMapOfInteger& theMap)
46 : TCollection_BasicMapIterator (theMap),
47 myIntMask (~0U)
48 {
3d77e962 49 myKey = myNode != NULL ? TColStd_intMapNode_findNext (myNode, myIntMask) : 0;
683d15cb 50 }
51
52 //! Re-initialize with the same or another Map instance.
53 void Initialize (const TColStd_PackedMapOfInteger& theMap)
54 {
55 TCollection_BasicMapIterator::Initialize (theMap);
56 myIntMask = ~0U;
3d77e962 57 myKey = myNode != NULL ? TColStd_intMapNode_findNext (myNode, myIntMask) : 0;
683d15cb 58 }
59
60 //! Restart the iteration
61 void Reset()
62 {
63 TCollection_BasicMapIterator::Reset();
64 myIntMask = ~0U;
3d77e962 65 myKey = myNode != NULL ? TColStd_intMapNode_findNext (myNode, myIntMask) : 0;
683d15cb 66 }
67
68 //! Query the iterated key.
69 Standard_Integer Key() const
70 {
71 Standard_NoSuchObject_Raise_if ((myIntMask == ~0U), "TColStd_MapIteratorOfPackedMapOfInteger::Key");
72 return myKey;
73 }
74
75 //! Increment the iterator
76 void Next()
77 {
78 for (; myNode != NULL; TCollection_BasicMapIterator::Next())
79 {
3d77e962 80 myKey = TColStd_intMapNode_findNext (myNode, myIntMask);
683d15cb 81 if (myIntMask != ~0u)
82 {
83 break;
84 }
85 }
86 }
87
88 private:
89 unsigned int myIntMask; //!< all bits set above the iterated position
90 Standard_Integer myKey; //!< Currently iterated key
91 };
92
93public:
7fd59977 94
95 /// Constructor
96 inline TColStd_PackedMapOfInteger (const Standard_Integer NbBuckets = 1)
97 : TCollection_BasicMap (NbBuckets, Standard_True),
98 myExtent (0) {}
99
39ef94f8 100 /// Copy constructor
101 inline TColStd_PackedMapOfInteger (const TColStd_PackedMapOfInteger& theOther)
102 : TCollection_BasicMap (1, Standard_True),
103 myExtent (0)
104 { Assign(theOther); }
105
7fd59977 106 inline TColStd_PackedMapOfInteger&
107 operator = (const TColStd_PackedMapOfInteger& Other)
108 { return Assign(Other); }
109
110 Standard_EXPORT TColStd_PackedMapOfInteger&
111 Assign (const TColStd_PackedMapOfInteger&);
112 Standard_EXPORT void ReSize (const Standard_Integer NbBuckets);
113 Standard_EXPORT void Clear ();
114 ~TColStd_PackedMapOfInteger() { Clear(); }
115 Standard_EXPORT Standard_Boolean
116 Add (const Standard_Integer aKey);
117 Standard_EXPORT Standard_Boolean
118 Contains (const Standard_Integer aKey) const;
119 Standard_EXPORT Standard_Boolean
120 Remove (const Standard_Integer aKey);
121
122 inline Standard_Integer NbBuckets () const
123 { return TCollection_BasicMap::NbBuckets(); }
124
125 inline Standard_Integer Extent () const
126 { return Standard_Integer (myExtent); }
127
dde68833 128 inline Standard_Boolean IsEmpty () const
7fd59977 129 { return TCollection_BasicMap::IsEmpty(); }
130
131 inline void Statistics (Standard_OStream& outStream) const
132 { TCollection_BasicMap::Statistics (outStream); }
133
134 /**
135 * Query the minimal contained key value.
136 */
137 Standard_EXPORT Standard_Integer GetMinimalMapped () const;
138
139 /**
140 * Query the maximal contained key value.
141 */
142 Standard_EXPORT Standard_Integer GetMaximalMapped () const;
143
144public:
145 //!@name Boolean operations with maps as sets of integers
146 //!@{
ebc93ae7 147
7fd59977 148 /**
ebc93ae7 149 * Sets this Map to be the result of union (aka addition, fuse, merge, boolean OR) operation between two given Maps.
150 * The new Map contains the values that are contained either in the first map or in the second map or in both.
151 * All previous contents of this Map is cleared. This map (result of the boolean operation) can also be passed as one of operands.
7fd59977 152 */
153 Standard_EXPORT void Union (const TColStd_PackedMapOfInteger&,
154 const TColStd_PackedMapOfInteger&);
155
156 /**
ebc93ae7 157 * Apply to this Map the boolean operation union (aka addition, fuse, merge, boolean OR) with another (given) Map.
158 * The result contains the values that were previously contained in this map or contained in the given (operand) map.
7fd59977 159 * This algorithm is similar to method Union().
ebc93ae7 160 * @return True if content of this map is changed
7fd59977 161 */
162 Standard_EXPORT Standard_Boolean Unite (const TColStd_PackedMapOfInteger&);
163
164 /**
165 * Overloaded operator version of Unite().
166 */
167 TColStd_PackedMapOfInteger& operator |= (const TColStd_PackedMapOfInteger& MM)
168 { Unite(MM); return *this; }
169
170 /**
ebc93ae7 171 * Sets this Map to be the result of intersection (aka multiplication, common, boolean AND) operation between two given Maps.
172 * The new Map contains only the values that are contained in both map operands.
173 * All previous contents of this Map is cleared. This same map (result of the boolean operation) can also be used as one of operands.
174 * The order of operands makes no difference; the method minimizes internally the number of iterations using the smallest map for the loop.
7fd59977 175 */
176 Standard_EXPORT void Intersection (const TColStd_PackedMapOfInteger&,
177 const TColStd_PackedMapOfInteger&);
178
179 /**
ebc93ae7 180 * Apply to this Map the intersection operation (aka multiplication, common, boolean AND) with another (given) Map.
181 * The result contains only the values that are contained in both this and the given maps.
7fd59977 182 * This algorithm is similar to method Intersection().
ebc93ae7 183 * @return True if content of this map is changed
7fd59977 184 */
185 Standard_EXPORT Standard_Boolean Intersect (const TColStd_PackedMapOfInteger&);
186
187 /**
188 * Overloaded operator version of Intersect().
189 */
190 TColStd_PackedMapOfInteger& operator &= (const TColStd_PackedMapOfInteger& MM)
191 { Intersect(MM); return *this; }
192
193 /**
ebc93ae7 194 * Sets this Map to be the result of subtraction
195 * (aka set-theoretic difference, relative complement, exclude, cut, boolean NOT) operation between two given Maps.
196 * The new Map contains only the values that are contained in the first map operands and not contained in the second one.
197 * All previous contents of this Map is cleared.
198 * This map (result of the boolean operation) can also be used as the first operand.
7fd59977 199 */
200 Standard_EXPORT void Subtraction (const TColStd_PackedMapOfInteger&,
201 const TColStd_PackedMapOfInteger&);
202
203 /**
ebc93ae7 204 * Apply to this Map the subtraction (aka set-theoretic difference, relative complement, exclude, cut, boolean NOT) operation with another (given) Map.
205 * The result contains only the values that were previously contained in this map and not contained in this map.
7fd59977 206 * This algorithm is similar to method Subtract() with two operands.
ebc93ae7 207 * @return True if contents of this map is changed
7fd59977 208 */
209 Standard_EXPORT Standard_Boolean Subtract (const TColStd_PackedMapOfInteger&);
210
211 /**
212 * Overloaded operator version of Subtract().
213 */
214 TColStd_PackedMapOfInteger& operator -= (const TColStd_PackedMapOfInteger& MM)
215 { Subtract(MM); return *this; }
216
217 /**
ebc93ae7 218 * Sets this Map to be the result of symmetric difference (aka exclusive disjunction, boolean XOR) operation between two given Maps.
219 * The new Map contains the values that are contained only in the first or the second operand maps but not in both.
220 * All previous contents of this Map is cleared.
221 * This map (result of the boolean operation) can also be used as one of operands.
7fd59977 222 */
223 Standard_EXPORT void Difference (const TColStd_PackedMapOfInteger&,
224 const TColStd_PackedMapOfInteger&);
225
226 /**
ebc93ae7 227 * Apply to this Map the symmetric difference (aka exclusive disjunction, boolean XOR) operation with another (given) Map.
228 * The result contains the values that are contained only in this or the operand map, but not in both.
7fd59977 229 * This algorithm is similar to method Difference().
ebc93ae7 230 * @return True if contents of this map is changed
7fd59977 231 */
232 Standard_EXPORT Standard_Boolean Differ (const TColStd_PackedMapOfInteger&);
233
234 /**
235 * Overloaded operator version of Differ().
236 */
237 TColStd_PackedMapOfInteger& operator ^= (const TColStd_PackedMapOfInteger& MM)
238 { Differ(MM); return *this; }
239
240 /**
241 * Returns True if this map is equal to the given one, i.e. they contain the
242 * same sets of elements
243 */
244 Standard_EXPORT Standard_Boolean IsEqual (const TColStd_PackedMapOfInteger&) const;
245
246 /**
247 * Overloaded operator version of IsEqual().
248 */
249 Standard_Boolean operator == (const TColStd_PackedMapOfInteger& MM) const
250 { return IsEqual(MM); }
251
252 /**
253 * Returns True if this map is subset of the given one, i.e. all elements
254 * contained in this map is contained also in the operand map.
255 * if this map is empty that this method returns true for any operand map.
256 */
257 Standard_EXPORT Standard_Boolean IsSubset (const TColStd_PackedMapOfInteger&) const;
258
259 /**
260 * Overloaded operator version of IsSubset().
261 */
262 Standard_Boolean operator <= (const TColStd_PackedMapOfInteger& MM) const
263 { return IsSubset(MM); }
264
265 /**
266 * Returns True if this map has common items with the given one.
267 */
268 Standard_EXPORT Standard_Boolean HasIntersection (const TColStd_PackedMapOfInteger&) const;
269
270 //!@}
271
272 protected:
273 // ---------- PROTECTED METHODS ----------
274 inline Standard_Integer InternalExtent () const
275 { return TCollection_BasicMap::Extent(); }
276
683d15cb 277private:
278
279 //! Class implementing a block of 32 consecutive integer values as a node of a Map collection.
280 //! The data are stored in 64 bits as:
281 //! - bits 0 - 4 : (number of integers stored in the block) - 1;
282 //! - bits 5 - 31: base address of the block of integers (low bits assumed 0)
283 //! - bits 32 - 63: 32-bit field where each bit indicates the presence of the corresponding integer in the block.
284 //! Number of non-zero bits must be equal to the number expressed in bits 0-4.
285 class TColStd_intMapNode;
7fd59977 286
683d15cb 287 //! Find the smallest non-zero bit under the given mask.
288 //! Outputs the new mask that does not contain the detected bit.
3d77e962 289 Standard_EXPORT static Standard_Integer TColStd_intMapNode_findNext (const Standard_Address theNode,
683d15cb 290 unsigned int& theMask);
7fd59977 291
683d15cb 292 //! Find the highest non-zero bit under the given mask.
293 //! Outputs the new mask that does not contain the detected bit.
3d77e962 294 Standard_EXPORT static Standard_Integer TColStd_intMapNode_findPrev (const Standard_Address theNode,
683d15cb 295 unsigned int& theMask);
7fd59977 296
683d15cb 297private:
298 size_t myExtent;
7fd59977 299};
300
301#endif