340666600beb4a8949b40223506e233ddd09cfa1
[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 (reinterpret_cast<const TColStd_intMapNode*>(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 (reinterpret_cast<const TColStd_intMapNode*>(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 (reinterpret_cast<const TColStd_intMapNode*>(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         const TColStd_intMapNode* aNode = reinterpret_cast<const TColStd_intMapNode*>(myNode);
81         myKey = TColStd_intMapNode_findNext (aNode, myIntMask);
82         if (myIntMask != ~0u)
83         {
84           break;
85         }
86       }
87     }
88
89   private:
90     unsigned int     myIntMask; //!< all bits set above the iterated position
91     Standard_Integer myKey;     //!< Currently iterated key
92   };
93
94 public:
95
96   /// Constructor
97   inline  TColStd_PackedMapOfInteger  (const Standard_Integer NbBuckets = 1)
98     : TCollection_BasicMap (NbBuckets, Standard_True),
99       myExtent             (0) {}
100
101   /// Copy constructor
102   inline TColStd_PackedMapOfInteger (const TColStd_PackedMapOfInteger& theOther)
103     : TCollection_BasicMap (1, Standard_True),
104       myExtent             (0)
105   { Assign(theOther); }
106
107   inline TColStd_PackedMapOfInteger&
108                           operator =  (const TColStd_PackedMapOfInteger& Other) 
109   { return Assign(Other); }
110
111   Standard_EXPORT TColStd_PackedMapOfInteger&
112                           Assign        (const TColStd_PackedMapOfInteger&);
113   Standard_EXPORT  void   ReSize        (const Standard_Integer NbBuckets);
114   Standard_EXPORT  void   Clear         ();
115   ~TColStd_PackedMapOfInteger() { Clear(); }
116   Standard_EXPORT  Standard_Boolean
117                           Add           (const Standard_Integer aKey);
118   Standard_EXPORT  Standard_Boolean
119                           Contains      (const Standard_Integer aKey) const;
120   Standard_EXPORT  Standard_Boolean
121                           Remove        (const Standard_Integer aKey);
122
123   inline Standard_Integer NbBuckets     () const
124   { return TCollection_BasicMap::NbBuckets(); }
125
126   inline Standard_Integer Extent        () const
127   { return Standard_Integer (myExtent); }
128
129   inline Standard_Boolean IsEmpty       () const
130   { return TCollection_BasicMap::IsEmpty(); }
131
132   inline void             Statistics    (Standard_OStream& outStream) const
133   { TCollection_BasicMap::Statistics (outStream); }
134
135   /**
136    * Query the minimal contained key value.
137    */
138   Standard_EXPORT Standard_Integer GetMinimalMapped () const;
139
140   /**
141    * Query the maximal contained key value.
142    */
143   Standard_EXPORT Standard_Integer GetMaximalMapped () const;
144
145 public:
146   //!@name Boolean operations with maps as sets of integers
147   //!@{
148
149   /**
150    * Sets this Map to be the result of union (aka addition, fuse, merge, boolean OR) operation between two given Maps.
151    * The new Map contains the values that are contained either in the first map or in the second map or in both.
152    * All previous contents of this Map is cleared. This map (result of the boolean operation) can also be passed as one of operands.
153    */
154   Standard_EXPORT void Union (const TColStd_PackedMapOfInteger&,
155                               const TColStd_PackedMapOfInteger&);
156
157   /**
158    * Apply to this Map the boolean operation union (aka addition, fuse, merge, boolean OR) with another (given) Map.
159    * The result contains the values that were previously contained in this map or contained in the given (operand) map.
160    * This algorithm is similar to method Union().
161    * @return True if content of this map is changed
162    */
163   Standard_EXPORT Standard_Boolean Unite (const TColStd_PackedMapOfInteger&);
164
165   /**
166    * Overloaded operator version of Unite().
167    */
168   TColStd_PackedMapOfInteger& operator |= (const TColStd_PackedMapOfInteger& MM)
169   { Unite(MM); return *this; }
170
171   /**
172    * Sets this Map to be the result of intersection (aka multiplication, common, boolean AND) operation between two given Maps.
173    * The new Map contains only the values that are contained in both map operands.
174    * All previous contents of this Map is cleared. This same map (result of the boolean operation) can also be used as one of operands.
175    * The order of operands makes no difference; the method minimizes internally the number of iterations using the smallest map for the loop.
176    */
177   Standard_EXPORT void Intersection (const TColStd_PackedMapOfInteger&,
178                                      const TColStd_PackedMapOfInteger&);
179
180   /**
181    * Apply to this Map the intersection operation (aka multiplication, common,  boolean AND) with another (given) Map.
182    * The result contains only the values that are contained in both this and the given maps.
183    * This algorithm is similar to method Intersection().
184    * @return True if content of this map is changed
185    */
186   Standard_EXPORT Standard_Boolean Intersect (const TColStd_PackedMapOfInteger&);
187
188   /**
189    * Overloaded operator version of Intersect().
190    */
191   TColStd_PackedMapOfInteger& operator &= (const TColStd_PackedMapOfInteger& MM)
192   { Intersect(MM); return *this; }
193
194   /**
195    * Sets this Map to be the result of subtraction
196    * (aka set-theoretic difference, relative complement, exclude, cut, boolean NOT) operation between two given Maps.
197    * The new Map contains only the values that are contained in the first map operands and not contained in the second one.
198    * All previous contents of this Map is cleared.
199    * This map (result of the boolean operation) can also be used as the first operand.
200    */
201   Standard_EXPORT void Subtraction (const TColStd_PackedMapOfInteger&,
202                                     const TColStd_PackedMapOfInteger&);
203
204   /**
205    * Apply to this Map the subtraction (aka set-theoretic difference, relative complement, exclude, cut, boolean NOT) operation with another (given) Map.
206    * The result contains only the values that were previously contained in this map and not contained in this map.
207    * This algorithm is similar to method Subtract() with two operands.
208    * @return True if contents of this map is changed
209    */
210   Standard_EXPORT Standard_Boolean Subtract (const TColStd_PackedMapOfInteger&);
211
212   /**
213    * Overloaded operator version of Subtract().
214    */
215   TColStd_PackedMapOfInteger& operator -= (const TColStd_PackedMapOfInteger& MM)
216   { Subtract(MM); return *this; }
217
218   /**
219    * Sets this Map to be the result of symmetric difference (aka exclusive disjunction, boolean XOR) operation between two given Maps.
220    * The new Map contains the values that are contained only in the first or the second operand maps but not in both.
221    * All previous contents of this Map is cleared.
222    * This map (result of the boolean operation) can also be used as one of operands.
223    */
224   Standard_EXPORT void Difference (const TColStd_PackedMapOfInteger&,
225                                    const TColStd_PackedMapOfInteger&);
226
227   /**
228    * Apply to this Map the symmetric difference (aka exclusive disjunction, boolean XOR) operation with another (given) Map.
229    * The result contains the values that are contained only in this or the operand map, but not in both.
230    * This algorithm is similar to method Difference().
231    * @return True if contents of this map is changed
232    */
233   Standard_EXPORT Standard_Boolean Differ (const TColStd_PackedMapOfInteger&);
234
235   /**
236    * Overloaded operator version of Differ().
237    */
238   TColStd_PackedMapOfInteger& operator ^= (const TColStd_PackedMapOfInteger& MM)
239   { Differ(MM); return *this; }
240
241   /**
242    * Returns True if this map is equal to the given one, i.e. they contain the
243    * same sets of elements
244    */
245   Standard_EXPORT Standard_Boolean IsEqual (const TColStd_PackedMapOfInteger&) const;
246
247   /**
248    * Overloaded operator version of IsEqual().
249    */
250   Standard_Boolean operator == (const TColStd_PackedMapOfInteger& MM) const
251   { return IsEqual(MM); }
252
253   /**
254    * Returns True if this map is subset of the given one, i.e. all elements 
255    * contained in this map is contained also in the operand map.
256    * if this map is empty that this method returns true for any operand map.
257    */
258   Standard_EXPORT Standard_Boolean IsSubset (const TColStd_PackedMapOfInteger&) const;
259
260   /**
261    * Overloaded operator version of IsSubset().
262    */
263   Standard_Boolean operator <= (const TColStd_PackedMapOfInteger& MM) const
264   { return IsSubset(MM); }
265
266   /**
267    * Returns True if this map has common items with the given one.
268    */
269   Standard_EXPORT Standard_Boolean HasIntersection (const TColStd_PackedMapOfInteger&) const;
270
271   //!@}
272   
273  protected:
274   // ---------- PROTECTED METHODS ----------
275   inline Standard_Integer InternalExtent () const
276   { return TCollection_BasicMap::Extent(); }
277
278 private:
279
280   //! Class implementing a block of 32 consecutive integer values as a node of a Map collection.
281   //! The data are stored in 64 bits as:
282   //!  - bits  0 - 4 : (number of integers stored in the block) - 1;
283   //!  - bits  5 - 31: base address of the block of integers (low bits assumed 0)
284   //!  - bits 32 - 63: 32-bit field where each bit indicates the presence of the corresponding integer in the block.
285   //!                  Number of non-zero bits must be equal to the number expressed in bits 0-4.
286   class TColStd_intMapNode;
287
288   //! Find the smallest non-zero bit under the given mask.
289   //! Outputs the new mask that does not contain the detected bit.
290   Standard_EXPORT static Standard_Integer TColStd_intMapNode_findNext (const TColStd_intMapNode* theNode,
291                                                                        unsigned int& theMask);
292
293   //! Find the highest non-zero bit under the given mask.
294   //! Outputs the new mask that does not contain the detected bit.
295   Standard_EXPORT static Standard_Integer TColStd_intMapNode_findPrev (const TColStd_intMapNode* theNode,
296                                                                        unsigned int& theMask);
297
298 private:
299   size_t myExtent;
300 };
301
302 #endif