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 |
27 | class 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 | |
34 | public: |
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 | |
93 | public: |
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 | |
144 | public: |
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 |
277 | private: |
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 |
297 | private: |
298 | size_t myExtent; |
7fd59977 |
299 | }; |
300 | |
301 | #endif |