0029764: Foundation Classes, TColStd_MapIteratorOfPackedMapOfInteger - workaround...
[occt.git] / src / TColStd / TColStd_PackedMapOfInteger.hxx
1 // Created on: 2005-11-05
2 // Created by: Alexander GRIGORIEV
3 // Copyright (c) 2005-2014 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
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.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #ifndef TColStd_PackedMapOfInteger_HeaderFile
17 #define TColStd_PackedMapOfInteger_HeaderFile
18
19 #include <Standard_DefineAlloc.hxx>
20 #include <Standard_NoSuchObject.hxx>
21 #include <TCollection_BasicMap.hxx>
22 #include <TCollection_BasicMapIterator.hxx>
23
24 /**
25  * Optimized Map of integer values. Each block of 32 integers is stored in 8 bytes in memory.
26  */
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
32   DEFINE_STANDARD_ALLOC
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     {
49       myKey = myNode != NULL ? TColStd_intMapNode_findNext (myNode, myIntMask) : 0;
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;
57       myKey = myNode != NULL ? TColStd_intMapNode_findNext (myNode, myIntMask) : 0;
58     }
59
60     //! Restart the iteration
61     void Reset()
62     {
63       TCollection_BasicMapIterator::Reset();
64       myIntMask = ~0U;
65       myKey = myNode != NULL ? TColStd_intMapNode_findNext (myNode, myIntMask) : 0;
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       {
80         myKey = TColStd_intMapNode_findNext (myNode, myIntMask);
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:
94
95   /// Constructor
96   inline  TColStd_PackedMapOfInteger  (const Standard_Integer NbBuckets = 1)
97     : TCollection_BasicMap (NbBuckets, Standard_True),
98       myExtent             (0) {}
99
100   /// Copy constructor
101   inline TColStd_PackedMapOfInteger (const TColStd_PackedMapOfInteger& theOther)
102     : TCollection_BasicMap (1, Standard_True),
103       myExtent             (0)
104   { Assign(theOther); }
105
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
128   inline Standard_Boolean IsEmpty       () const
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   //!@{
147
148   /**
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.
152    */
153   Standard_EXPORT void Union (const TColStd_PackedMapOfInteger&,
154                               const TColStd_PackedMapOfInteger&);
155
156   /**
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.
159    * This algorithm is similar to method Union().
160    * @return True if content of this map is changed
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   /**
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.
175    */
176   Standard_EXPORT void Intersection (const TColStd_PackedMapOfInteger&,
177                                      const TColStd_PackedMapOfInteger&);
178
179   /**
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.
182    * This algorithm is similar to method Intersection().
183    * @return True if content of this map is changed
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   /**
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.
199    */
200   Standard_EXPORT void Subtraction (const TColStd_PackedMapOfInteger&,
201                                     const TColStd_PackedMapOfInteger&);
202
203   /**
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.
206    * This algorithm is similar to method Subtract() with two operands.
207    * @return True if contents of this map is changed
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   /**
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.
222    */
223   Standard_EXPORT void Difference (const TColStd_PackedMapOfInteger&,
224                                    const TColStd_PackedMapOfInteger&);
225
226   /**
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.
229    * This algorithm is similar to method Difference().
230    * @return True if contents of this map is changed
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
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;
286
287   //! Find the smallest non-zero bit under the given mask.
288   //! Outputs the new mask that does not contain the detected bit.
289   Standard_EXPORT static Standard_Integer TColStd_intMapNode_findNext (const Standard_Address theNode,
290                                                                        unsigned int& theMask);
291
292   //! Find the highest non-zero bit under the given mask.
293   //! Outputs the new mask that does not contain the detected bit.
294   Standard_EXPORT static Standard_Integer TColStd_intMapNode_findPrev (const Standard_Address theNode,
295                                                                        unsigned int& theMask);
296
297 private:
298   size_t myExtent;
299 };
300
301 #endif