HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_BitArray.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: BitArray.h
7  *
8  * COMMENTS:
9  *
10  */
11 
12 #ifndef _UT_BitArray_
13 #define _UT_BitArray_
14 
15 #include "UT_API.h"
16 #include "UT_Assert.h"
17 #include <SYS/SYS_Deprecated.h>
18 #include <SYS/SYS_Types.h>
19 #include <SYS/SYS_BitUtil.h>
20 #include <iosfwd>
21 #include <iterator>
22 
23 class UT_IStream;
24 
25 
26 //
27 // This class implements a one dimensional array of bits.
28 //
30  typedef uint64 BlockType;
31 
32 public:
33  UT_BitArray();
34  UT_BitArray(const UT_BitArray &src);
36  explicit UT_BitArray(exint size);
37  ~UT_BitArray();
38 
39  void insert(exint index, bool value);
40  void append(bool value) { insert(myBitCount, value); }
41  void remove(exint index);
42 
43  // Cyclically shift the entire array by shift_offset.
44  void cycle(exint shift_offset);
45 
46  exint size() const { return myBitCount; }
47  void setSize(exint new_size);
48 
49  void clear() { setSize(0); }
50 
51  SYS_DEPRECATED(14.0)
52  exint getSize() const { return size(); }
53 
54  SYS_DEPRECATED(14.0)
55  void resize(exint size) { setSize(size); }
56 
57  exint numBitsSet() const;
58  exint numBitsClear() const;
59 
60  bool allBitsSet() const;
61  bool allBitsClear() const;
62 
63  inline bool getBit(exint index) const;
64 
65  inline bool setBit(exint index, bool value);// Returns previous bit value.
66  inline bool toggleBit(exint index); // Returns previous bit value.
67 
68  inline bool getBitFast(exint index) const;
69  inline void setBitFast(exint index, bool value);
70  inline void toggleBitFast(exint index);
71 
72  void setBits(exint index, exint nbits, bool value);
73  void toggleBits(exint index, exint nbits);
74 
75  void setAllBits(bool value);
76  void toggleAllBits();
77 
78  // I/O methods:
79  int save(std::ostream &os, bool binary = false) const;
80  bool load(UT_IStream &is);
81 
82  /// Iterate over set bits
83  ///
84  /// eg. for (i = bits.iterateInit(); i >= 0; i = bits.iterateNext(i))
85  /// ... do something with bits(i)
86  ///
87  // @{
88  exint iterateInit() const; // Initialize traversal
89  exint iterateNext(exint currentBit) const; // Find next set bit
90 
91  // Deprecated. Don't use.
92  // SYS_DEPRECATED(15.0)
93  void iterateInit(exint &i) const { i = iterateInit(); }
94  // @}
95 
96 
97  /// Find first or last bit in the array. The functions will return -1 if
98  /// no bits are set (i.e. equivalent to allBitsClear())
99  exint findFirstBit() const;
100  exint findLastBit() const;
101 
102  // operators
103 
104  bool operator()(exint index) const { return getBit(index); }
105  bool operator[](exint index) const { return getBit(index); }
106  UT_BitArray &operator&=(const UT_BitArray &inMap); // and | intersection
107  UT_BitArray &operator|=(const UT_BitArray &inMap); // or | union
108  UT_BitArray &operator^=(const UT_BitArray &inMap); // exclusive or
109  UT_BitArray &operator-=(const UT_BitArray &inMap); // minus
110  UT_BitArray &operator=(const UT_BitArray &inMap); // assignment
111  UT_BitArray &operator=(UT_BitArray &&src); // move assignment
112  bool operator==(const UT_BitArray &inMap) const; // compare
113  bool operator!=(const UT_BitArray &inMap) const
114  { return !(*this == inMap); }
115 
116  void swap(UT_BitArray &other);
117 
118  /// Returns whether there are any intersections between the two arrays
119  bool intersects(const UT_BitArray &inMap) const;
120 
121  int64 getMemoryUsage(bool inclusive=true) const
122  {
123  int64 mem = inclusive ? sizeof(*this) : 0;
124  mem += myWordCount*sizeof(BlockType);
125  return mem;
126  }
127 
128  uint computeHash() const;
129 
130  /// Iterate over bits that are turned on
131  class iterator :
132  public std::iterator<std::forward_iterator_tag, exint>
133 
134  {
135  public:
136  typedef exint type;
137 
139  : myArray(NULL)
140  , myIndex(0)
141  , mySize(0)
142  {}
144  {}
145 
146  /// Get the current iteration state
147  exint getBit() const { return myIndex; }
148  exint operator*() const { return myIndex; }
149 
150  /// @{
151  /// Standard iterator interface
152  bool operator==(const iterator &i) const
153  {
154  return myArray == i.myArray
155  && myIndex == i.myIndex
156  && mySize == i.mySize;
157  }
158  bool operator!=(const iterator &i) const
159  {
160  return !(*this == i);
161  }
162  bool atEnd() const
163  {
164  return myIndex >= mySize;
165  }
166  iterator &operator++() { advance(); return *this; }
167  /// @}
168 
169  void rewind()
170  {
171  if (myArray)
172  {
173  myIndex = myArray->iterateInit();
174  if (myIndex < 0)
175  myIndex = mySize;
176  }
177  }
178  void advance()
179  {
180  myIndex = myArray->iterateNext(myIndex);
181  if (myIndex < 0)
182  myIndex = mySize;
183  }
184  private:
185  iterator(const UT_BitArray *array, bool end)
186  : myArray(array)
187  , mySize(array->size())
188  {
189  if (end)
190  myIndex = mySize;
191  else
192  {
193  rewind();
194  }
195  }
196  const UT_BitArray *myArray;
197  exint myIndex;
198  exint mySize;
199  friend class UT_BitArray;
200  };
202 
203  iterator begin() const { return iterator(this, false); }
204  iterator end() const { return iterator(this, true); }
205 
206 private:
207  static const int myBitsPerWord = sizeof(BlockType)*8;
208  static const int myWordShift = SYS_LOG2F(myBitsPerWord);
209  static const int myWordMask = (1 << myWordShift) - 1;
210 
211  BlockType *myBits;
212  exint myBitCount;
213  exint myWordCount;
214 
215 private:
216  exint iterateFromWord(uint64 wordIndex) const;
217  void swapBlocks32(BlockType *blocks, exint nb_blocks) const;
218  void clearTopWord();
219 
220  // returns the word number in which the given bit would be
221  static inline exint
222  indexWord(exint bit)
223  {
224  return (bit >> myWordShift);
225  }
226 
227  // returns the position in word 'indexWord(bit)' where the given bit is
228  static inline BlockType
229  indexBit(exint bit)
230  {
231  return (BlockType(1) << (bit & myWordMask));
232  }
233 
234  // returns the number of words required for the given number of bits
235  static inline exint
236  numWords(exint size_in_bits)
237  {
238  return (size_in_bits + (myBitsPerWord - 1)) / myBitsPerWord;
239  }
240 
241  void outTo(std::ostream &os) const;
242  friend std::ostream &operator<<(std::ostream &os, const UT_BitArray &map)
243  {
244  map.outTo(os);
245  return os;
246  }
247 };
248 
249 // Inline methods
250 inline bool
252 {
253  BlockType *word;
254 
255  if( index < 0 || index >= myBitCount )
256  {
257  UT_ASSERT_P( index >= 0 && index < myBitCount );
258  return 0;
259  }
260 
261  word = myBits + indexWord(index);
262  return ((*word & indexBit(index)) != 0);
263 }
264 
265 inline bool
266 UT_BitArray::setBit(exint index, bool value)
267 {
268  BlockType *word;
269  BlockType mask;
270  BlockType previous;
271 
272  if( index < 0 || index >= myBitCount )
273  {
274  UT_ASSERT_P( index >= 0 && index < myBitCount );
275  return 0;
276  }
277 
278  word = myBits + indexWord(index);
279  mask = indexBit(index);
280  previous = *word & mask;
281 
282  if( value ) *word |= mask;
283  else *word &= ~mask;
284 
285  return (previous != 0);
286 }
287 
288 inline bool
290 {
291  BlockType *word;
292  BlockType mask;
293  BlockType previous;
294 
295  if( index < 0 || index >= myBitCount )
296  {
297  UT_ASSERT_P( index >= 0 && index < myBitCount );
298  return 0;
299  }
300 
301  word = myBits + indexWord(index);
302  mask = indexBit(index);
303  previous = *word & mask;
304 
305  *word ^= mask;
306 
307  return (previous != 0);
308 }
309 
310 inline bool
312 {
313  UT_ASSERT_P( index >= 0 && index < myBitCount );
314  BlockType word = myBits[indexWord(index)];
315  int bit = index & myWordMask;
316  return (word >> bit) & BlockType(1);
317 }
318 
319 inline void
320 UT_BitArray::setBitFast(exint index, bool value)
321 {
322  UT_ASSERT_P( index >= 0 && index < myBitCount );
323  BlockType &word = myBits[indexWord(index)];
324  int bit = index & myWordMask;
325  word = (BlockType(value) << bit) | (word & ~(BlockType(1) << bit));
326 }
327 
328 inline void
330 {
331  UT_ASSERT_P( index >= 0 && index < myBitCount );
332  BlockType &word = myBits[indexWord(index)];
333  int bit = index & myWordMask;
334  word ^= (BlockType(1) << bit);
335 }
336 
338 UT_BitArray::iterateFromWord(uint64 wordIndex) const
339 {
340  for (; wordIndex < myWordCount; wordIndex++)
341  {
342  if (myBits[wordIndex])
343  {
344  exint bitIndex = SYSfirstBitSet(myBits[wordIndex]);
345  UT_ASSERT_P(bitIndex + (wordIndex<<myWordShift) < size());
346  return bitIndex + (wordIndex << myWordShift);
347  }
348  }
349 
350  return -1;
351 }
352 
353 
354 inline exint
356 {
357  return iterateFromWord(0);
358 }
359 
360 inline exint
362 {
363  // Negative values imply search from the beginning.
364  if (currentBit < 0)
365  return iterateFromWord(0);
366 
367  // finish searching the current word
368  if (currentBit >= (myBitCount - 1))
369  return -1;
370 
371  int bitIndex = currentBit & myWordMask;
372  exint wordIndex = currentBit >> myWordShift;
373  BlockType *word = &myBits[wordIndex];
374 
375  bitIndex = SYSnextBitSet(*word, bitIndex);
376  if (bitIndex >= 0)
377  {
378  UT_ASSERT_P(bitIndex + (wordIndex<<myWordShift) < size());
379  return bitIndex + (wordIndex << myWordShift);
380  }
381  wordIndex++;
382 
383  return iterateFromWord(wordIndex);
384 }
385 
386 
387 #endif
exint iterateNext(exint currentBit) const
Definition: UT_BitArray.h:361
int64 getMemoryUsage(bool inclusive=true) const
Definition: UT_BitArray.h:121
bool getBit(exint index) const
Definition: UT_BitArray.h:251
#define SYS_DEPRECATED(__V__)
bool getBitFast(exint index) const
Definition: UT_BitArray.h:311
iterator begin() const
Definition: UT_BitArray.h:203
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
Definition: UT_ArraySet.h:1561
bool toggleBit(exint index)
Definition: UT_BitArray.h:289
typedef void(APIENTRYP PFNGLCULLFACEPROC)(GLenum mode)
const GLuint GLenum const void * binary
Definition: glcorearb.h:1923
GLint GLuint mask
Definition: glcorearb.h:123
iterator end() const
Definition: UT_BitArray.h:204
bool operator!=(const iterator &i) const
Definition: UT_BitArray.h:158
#define UT_API
Definition: UT_API.h:12
bool operator[](exint index) const
Definition: UT_BitArray.h:105
png_uint_32 i
Definition: png.h:2877
GLsizeiptr size
Definition: glcorearb.h:663
#define SYS_LOG2F(x)
Definition: SYS_BitUtil.h:282
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:101
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
long long int64
Definition: SYS_Types.h:100
unsigned long long uint64
Definition: SYS_Types.h:101
int64 exint
Definition: SYS_Types.h:109
void toggleBitFast(exint index)
Definition: UT_BitArray.h:329
iterator & operator++()
Definition: UT_BitArray.h:166
GLuint GLuint end
Definition: glcorearb.h:474
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
bool operator==(const iterator &i) const
Definition: UT_BitArray.h:152
void setBitFast(exint index, bool value)
Definition: UT_BitArray.h:320
exint size() const
Definition: UT_BitArray.h:46
bool operator!=(const UT_BitArray &inMap) const
Definition: UT_BitArray.h:113
Iterate over bits that are turned on.
Definition: UT_BitArray.h:131
unsigned int uint
Definition: SYS_Types.h:33
friend std::ostream & operator<<(std::ostream &os, const UT_BitArray &map)
Definition: UT_BitArray.h:242
bool setBit(exint index, bool value)
Definition: UT_BitArray.h:266
iterator const_iterator
Definition: UT_BitArray.h:201
void iterateInit(exint &i) const
Definition: UT_BitArray.h:93
GLsizei const GLfloat * value
Definition: glcorearb.h:823
void clear()
Definition: UT_BitArray.h:49
exint getBit() const
Get the current iteration state.
Definition: UT_BitArray.h:147
#define SYS_NOEXCEPT
Definition: SYS_Compiler.h:49
bool intersects(const Box< Vec3< T > > &b, const Line3< T > &r, Vec3< T > &ip)
Definition: ImathBoxAlgo.h:728
GLuint index
Definition: glcorearb.h:785
exint operator*() const
Definition: UT_BitArray.h:148
void append(bool value)
Definition: UT_BitArray.h:40
exint iterateInit() const
Definition: UT_BitArray.h:355
bool operator()(exint index) const
Definition: UT_BitArray.h:104
bool atEnd() const
Definition: UT_BitArray.h:162
GLenum src
Definition: glcorearb.h:1792