HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups 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  const BlockType *data() const { return myBits; }
58 
59  exint numBitsSet() const;
60  exint numBitsClear() const;
61 
62  bool allBitsSet() const;
63  bool allBitsClear() const;
64 
65  inline bool getBit(exint index) const;
66 
67  inline bool setBit(exint index, bool value);// Returns previous bit value.
68  inline bool toggleBit(exint index); // Returns previous bit value.
69 
70  inline bool getBitFast(exint index) const;
71  inline void setBitFast(exint index, bool value);
72  inline void toggleBitFast(exint index);
73 
74  void setBits(exint index, exint nbits, bool value);
75  void toggleBits(exint index, exint nbits);
76 
77  void setAllBits(bool value);
78  void toggleAllBits();
79 
80  // I/O methods:
81  int save(std::ostream &os, bool binary = false) const;
82  bool load(UT_IStream &is);
83 
84  /// Iterate over set bits
85  ///
86  /// eg. for (i = bits.iterateInit(); i >= 0; i = bits.iterateNext(i))
87  /// ... do something with bits(i)
88  ///
89  // @{
90  exint iterateInit() const; // Initialize traversal
91  exint iterateNext(exint currentBit) const; // Find next set bit
92 
93  // Deprecated. Don't use.
94  // SYS_DEPRECATED(15.0)
95  void iterateInit(exint &i) const { i = iterateInit(); }
96  // @}
97 
98 
99  /// Find first or last bit in the array. The functions will return -1 if
100  /// no bits are set (i.e. equivalent to allBitsClear())
101  exint findFirstBit() const;
102  exint findLastBit() const;
103 
104  // operators
105 
106  bool operator()(exint index) const { return getBit(index); }
107  bool operator[](exint index) const { return getBit(index); }
108  UT_BitArray &operator&=(const UT_BitArray &inMap); // and | intersection
109  UT_BitArray &operator|=(const UT_BitArray &inMap); // or | union
110  UT_BitArray &operator^=(const UT_BitArray &inMap); // exclusive or
111  UT_BitArray &operator-=(const UT_BitArray &inMap); // minus
112  UT_BitArray &operator=(const UT_BitArray &inMap); // assignment
113  UT_BitArray &operator=(UT_BitArray &&src); // move assignment
114  bool operator==(const UT_BitArray &inMap) const; // compare
115  bool operator!=(const UT_BitArray &inMap) const
116  { return !(*this == inMap); }
117 
118  void swap(UT_BitArray &other);
119 
120  /// Returns whether there are any intersections between the two arrays
121  bool intersects(const UT_BitArray &inMap) const;
122 
123  int64 getMemoryUsage(bool inclusive=true) const
124  {
125  int64 mem = inclusive ? sizeof(*this) : 0;
126  mem += myWordCount*sizeof(BlockType);
127  return mem;
128  }
129 
130  uint computeHash() const;
131 
132  /// Iterate over bits that are turned on
133  class iterator :
134  public std::iterator<std::forward_iterator_tag, exint>
135 
136  {
137  public:
138  typedef exint type;
139 
141  : myArray(NULL)
142  , myIndex(0)
143  , mySize(0)
144  {}
146  {}
147 
148  /// Get the current iteration state
149  exint getBit() const { return myIndex; }
150  exint operator*() const { return myIndex; }
151 
152  /// @{
153  /// Standard iterator interface
154  bool operator==(const iterator &i) const
155  {
156  return myArray == i.myArray
157  && myIndex == i.myIndex
158  && mySize == i.mySize;
159  }
160  bool operator!=(const iterator &i) const
161  {
162  return !(*this == i);
163  }
164  bool atEnd() const
165  {
166  return myIndex >= mySize;
167  }
168  iterator &operator++() { advance(); return *this; }
169  /// @}
170 
171  void rewind()
172  {
173  if (myArray)
174  {
175  myIndex = myArray->iterateInit();
176  if (myIndex < 0)
177  myIndex = mySize;
178  }
179  }
180  void advance()
181  {
182  myIndex = myArray->iterateNext(myIndex);
183  if (myIndex < 0)
184  myIndex = mySize;
185  }
186  private:
187  iterator(const UT_BitArray *array, bool end)
188  : myArray(array)
189  , mySize(array->size())
190  {
191  if (end)
192  myIndex = mySize;
193  else
194  {
195  rewind();
196  }
197  }
198  const UT_BitArray *myArray;
199  exint myIndex;
200  exint mySize;
201  friend class UT_BitArray;
202  };
204 
205  iterator begin() const { return iterator(this, false); }
206  iterator end() const { return iterator(this, true); }
207 
208 private:
209  static const int myBitsPerWord = sizeof(BlockType)*8;
210  static const int myWordShift = SYS_LOG2F(myBitsPerWord);
211  static const int myWordMask = (1 << myWordShift) - 1;
212 
213  BlockType *myBits;
214  exint myBitCount;
215  exint myWordCount;
216 
217 private:
218  exint iterateFromWord(uint64 wordIndex) const;
219  void swapBlocks32(BlockType *blocks, exint nb_blocks) const;
220  void clearTopWord();
221 
222  // returns the word number in which the given bit would be
223  static inline exint
224  indexWord(exint bit)
225  {
226  return (bit >> myWordShift);
227  }
228 
229  // returns the position in word 'indexWord(bit)' where the given bit is
230  static inline BlockType
231  indexBit(exint bit)
232  {
233  return (BlockType(1) << (bit & myWordMask));
234  }
235 
236  // returns the number of words required for the given number of bits
237  static inline exint
238  numWords(exint size_in_bits)
239  {
240  return (size_in_bits + (myBitsPerWord - 1)) / myBitsPerWord;
241  }
242 
243  void outTo(std::ostream &os) const;
244  friend std::ostream &operator<<(std::ostream &os, const UT_BitArray &map)
245  {
246  map.outTo(os);
247  return os;
248  }
249 };
250 
251 /// Overload for custom formatting of a UT_BitArray. with UTformat.
252 UT_API size_t
253 format(char *buffer, size_t bufsize, const UT_BitArray &b);
254 
255 // Inline methods
256 inline bool
258 {
259  BlockType *word;
260 
261  if( index < 0 || index >= myBitCount )
262  {
263  UT_ASSERT_P( index >= 0 && index < myBitCount );
264  return 0;
265  }
266 
267  word = myBits + indexWord(index);
268  return ((*word & indexBit(index)) != 0);
269 }
270 
271 inline bool
272 UT_BitArray::setBit(exint index, bool value)
273 {
274  BlockType *word;
275  BlockType mask;
276  BlockType previous;
277 
278  if( index < 0 || index >= myBitCount )
279  {
280  UT_ASSERT_P( index >= 0 && index < myBitCount );
281  return 0;
282  }
283 
284  word = myBits + indexWord(index);
285  mask = indexBit(index);
286  previous = *word & mask;
287 
288  if( value ) *word |= mask;
289  else *word &= ~mask;
290 
291  return (previous != 0);
292 }
293 
294 inline bool
296 {
297  BlockType *word;
298  BlockType mask;
299  BlockType previous;
300 
301  if( index < 0 || index >= myBitCount )
302  {
303  UT_ASSERT_P( index >= 0 && index < myBitCount );
304  return 0;
305  }
306 
307  word = myBits + indexWord(index);
308  mask = indexBit(index);
309  previous = *word & mask;
310 
311  *word ^= mask;
312 
313  return (previous != 0);
314 }
315 
316 inline bool
318 {
319  UT_ASSERT_P( index >= 0 && index < myBitCount );
320  BlockType word = myBits[indexWord(index)];
321  int bit = index & myWordMask;
322  return (word >> bit) & BlockType(1);
323 }
324 
325 inline void
326 UT_BitArray::setBitFast(exint index, bool value)
327 {
328  UT_ASSERT_P( index >= 0 && index < myBitCount );
329  BlockType &word = myBits[indexWord(index)];
330  int bit = index & myWordMask;
331  word = (BlockType(value) << bit) | (word & ~(BlockType(1) << bit));
332 }
333 
334 inline void
336 {
337  UT_ASSERT_P( index >= 0 && index < myBitCount );
338  BlockType &word = myBits[indexWord(index)];
339  int bit = index & myWordMask;
340  word ^= (BlockType(1) << bit);
341 }
342 
344 UT_BitArray::iterateFromWord(uint64 wordIndex) const
345 {
346  for (; wordIndex < myWordCount; wordIndex++)
347  {
348  if (myBits[wordIndex])
349  {
350  exint bitIndex = SYSfirstBitSet(myBits[wordIndex]);
351  UT_ASSERT_P(bitIndex + (wordIndex<<myWordShift) < size());
352  return bitIndex + (wordIndex << myWordShift);
353  }
354  }
355 
356  return -1;
357 }
358 
359 
360 inline exint
362 {
363  return iterateFromWord(0);
364 }
365 
366 inline exint
368 {
369  // Negative values imply search from the beginning.
370  if (currentBit < 0)
371  return iterateFromWord(0);
372 
373  // finish searching the current word
374  if (currentBit >= (myBitCount - 1))
375  return -1;
376 
377  int bitIndex = currentBit & myWordMask;
378  exint wordIndex = currentBit >> myWordShift;
379  BlockType *word = &myBits[wordIndex];
380 
381  bitIndex = SYSnextBitSet(*word, bitIndex);
382  if (bitIndex >= 0)
383  {
384  UT_ASSERT_P(bitIndex + (wordIndex<<myWordShift) < size());
385  return bitIndex + (wordIndex << myWordShift);
386  }
387  wordIndex++;
388 
389  return iterateFromWord(wordIndex);
390 }
391 
392 
393 #endif
exint iterateNext(exint currentBit) const
Definition: UT_BitArray.h:367
int64 getMemoryUsage(bool inclusive=true) const
Definition: UT_BitArray.h:123
GLenum GLuint GLsizei bufsize
Definition: glcorearb.h:1817
bool getBit(exint index) const
Definition: UT_BitArray.h:257
#define SYS_DEPRECATED(__V__)
bool getBitFast(exint index) const
Definition: UT_BitArray.h:317
iterator begin() const
Definition: UT_BitArray.h:205
bool toggleBit(exint index)
Definition: UT_BitArray.h:295
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:206
bool operator!=(const iterator &i) const
Definition: UT_BitArray.h:160
#define UT_API
Definition: UT_API.h:13
bool operator[](exint index) const
Definition: UT_BitArray.h:107
GLuint buffer
Definition: glcorearb.h:659
png_uint_32 i
Definition: png.h:2877
GLsizeiptr size
Definition: glcorearb.h:663
#define SYS_LOG2F(x)
Definition: SYS_BitUtil.h:282
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
long long int64
Definition: SYS_Types.h:107
unsigned long long uint64
Definition: SYS_Types.h:108
int64 exint
Definition: SYS_Types.h:116
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:125
void toggleBitFast(exint index)
Definition: UT_BitArray.h:335
iterator & operator++()
Definition: UT_BitArray.h:168
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:154
void setBitFast(exint index, bool value)
Definition: UT_BitArray.h:326
exint size() const
Definition: UT_BitArray.h:46
bool operator!=(const UT_BitArray &inMap) const
Definition: UT_BitArray.h:115
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
Iterate over bits that are turned on.
Definition: UT_BitArray.h:133
const BlockType * data() const
Definition: UT_BitArray.h:57
unsigned int uint
Definition: SYS_Types.h:40
friend std::ostream & operator<<(std::ostream &os, const UT_BitArray &map)
Definition: UT_BitArray.h:244
bool setBit(exint index, bool value)
Definition: UT_BitArray.h:272
iterator const_iterator
Definition: UT_BitArray.h:203
void iterateInit(exint &i) const
Definition: UT_BitArray.h:95
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:149
UT_API size_t format(char *buffer, size_t bufsize, const UT_BitArray &b)
Overload for custom formatting of a UT_BitArray. with UTformat.
#define SYS_NOEXCEPT
Definition: SYS_Compiler.h:55
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:150
void append(bool value)
Definition: UT_BitArray.h:40
exint iterateInit() const
Definition: UT_BitArray.h:361
void swap(TfErrorTransport &l, TfErrorTransport &r)
bool operator()(exint index) const
Definition: UT_BitArray.h:106
bool atEnd() const
Definition: UT_BitArray.h:164
GLenum src
Definition: glcorearb.h:1792