HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_RLEBitArray.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: UT_RLEBitArray.h ( UT Library, C++)
7  *
8  * COMMENTS:
9  *
10  * run length encoded bit array
11  *
12  */
13 
14 #ifndef __UT_RLEBitArray__
15 #define __UT_RLEBitArray__
16 
17 #include "UT_API.h"
18 #include "UT_Assert.h"
19 #include "UT_LinkList.h"
20 #include "UT_Swap.h"
21 
22 #include <SYS/SYS_Types.h>
23 
24 #include <limits.h>
25 
26 
28 {
29 public:
30  enum { LOWEST_INDEX = INT_MIN };
31 
33  {
34  mySearchNode = 0;
35  myLastIndex = 0;
36  }
38  {
39  }
40 
42 
43  void swap( UT_RLEBitArray &other );
44 
45  // For most efficient use, call the following increasing values of idx
46 
47  int numBitsSet() const;
48 
49  int getBit(int idx) const;
50  bool getBitRun(int idx, int &start, int &end) const;
51 
52  void setBitTrue(int idx);
53  void setBitFalse(int idx);
54  void setBit( int idx, int value)
55  {
56  if( value )
57  setBitTrue( idx );
58  else
59  setBitFalse( idx );
60  }
61  void setBitRunTrue( int start, int end );
62 
63  int toggleBit(int idx);
64 
65  void clear();
66  bool isEmpty() const;
67  int getNextRun(int &start, int &end, bool first=false);
68 
69  // returns true and sets currentBit to the next set bit
70  // otherwise returns false leaving currentBit unchanged
71  // to start off your search, set currentBit to LOWEST_INDEX (or below the
72  // first set bit)
73  // you could write, for example:
74  // int i = UT_RLEBitArray::LOWEST_INDEX; // (or -1 if applicable)
75  // while( iterate( i ) ) { blah; }
76  bool iterate( int &currentBit );
77 
78  int64 getMemoryUsage() const;
79 
80  void display() const;
81 
82  // operators
83  int operator()(int index) const { return getBit(index); }
84  int operator[](int index) const { return getBit(index); }
85  // A and B
86  const UT_RLEBitArray&operator&=(const UT_RLEBitArray &v);
87  // A or B
88  const UT_RLEBitArray&operator|=(const UT_RLEBitArray &v);
89  // A and not B or not A and B
90  const UT_RLEBitArray&operator^=(const UT_RLEBitArray &v);
91  // A and not B
92  const UT_RLEBitArray&operator-=(const UT_RLEBitArray &v);
93  const UT_RLEBitArray&operator= (const UT_RLEBitArray &v);
94  int operator==(const UT_RLEBitArray &v) const;
95  int operator!=(const UT_RLEBitArray &v) const;
96 
97 protected:
98  class Node;
99 
100 public:
102  {
103  public:
105  : myNode(NULL)
106  , myI(LOWEST_INDEX)
107  {
108  }
109 
110  int operator*() const
111  {
112  return myI;
113  }
114  int bitIndex() const
115  {
116  return myI;
117  }
118 
120  {
121  if (myNode)
122  {
123  ++myI;
124  if (myI > myNode->myEnd)
125  {
126  myNode = static_cast<const Node *>(myNode->next());
127  if (myNode)
128  myI = myNode->myStart;
129  }
130  }
131  return *this;
132  }
133 
134  bool operator==(const const_iterator &rhs) const
135  {
136  if (myNode != rhs.myNode)
137  return false;
138  return (myNode ? (myI == rhs.myI) : true);
139  }
140  bool operator!=(const const_iterator &lhs) const
141  {
142  return !(*this == lhs);
143  }
144 
145  int begin() const
146  {
147  return myNode->myStart;
148  }
149  int end() const // uses STL convention to return exclusive index
150  {
151  return myNode->myEnd + 1;
152  }
153 
154  protected:
156  : myNode(static_cast<const Node *>(list.head()))
157  , myI(myNode ? myNode->myStart : LOWEST_INDEX)
158  {
159  }
160 
161  const Node * myNode;
162  int myI;
163 
164  friend class UT_RLEBitArray;
165  };
166  typedef const_iterator iterator; // no mutable iterator
167 
169  iterator begin() { return iterator(myList); }
170  const_iterator end() const { return const_iterator(); }
171  iterator end() { return iterator(); }
172 
173 protected:
174  void restartSearch() const;
175  void restartSearchForIndex( int idx ) const;
176  void advanceSearchNode() const;
177 
178  // Invariants:
179  // if mySearchNode points to a node (case 1)
180  // the range from [myLastIndex, mySearchNode->myStart-1] is false
181  // the range from [mySearchNode->myStart, mySearchNode->myEnd] is true
182  //
183  // if mySearchNode is NULL (case 2)
184  // the range from [myLastIndex, inf) is false
185  //
186  // restartSearchForIndex( idx ) guarantees that
187  // idx is in the range [myLastIndex, mySearchNode->myEnd] (case 1)
188  // or else idx is in [myLastIndex, inf) (case 2)
189  class Node : public UT_LinkNode
190  {
191  public:
192  Node(int s, int e)
193  : myStart(s)
194  , myEnd(e)
195  {
196  }
197 
198  int myStart;
199  int myEnd;
200  };
201 
203  mutable Node *mySearchNode;
204  mutable int myLastIndex;
205 };
206 
208 
209 
210 inline int
211 UT_RLEBitArray::numBitsSet() const
212 {
213  Node *me;
214  int n = 0;
215 
216  me = (Node *)myList.head();
217 
218  while( me )
219  {
220  n += me->myEnd - me->myStart + 1;
221  me = (Node *)myList.next(me);
222  }
223 
224  return n;
225 }
226 
227 inline void
229 {
230  mySearchNode = (Node *)myList.head();
232 }
233 
234 inline void
236 {
237  if( !mySearchNode || idx < myLastIndex )
238  restartSearch();
239  while( mySearchNode && idx > mySearchNode->myEnd )
241 }
242 
243 inline void
245 {
248 }
249 
250 inline int
252 {
253  restartSearchForIndex( idx );
254 
255  // Somewhere in the middle?
256 
257  if( mySearchNode &&
258  (idx >= mySearchNode->myStart) && (idx <= mySearchNode->myEnd) )
259  return 1;
260 
261  UT_ASSERT( !mySearchNode || idx < mySearchNode->myEnd );
262  return 0;
263 }
264 
265 #endif
GLint first
Definition: glcorearb.h:404
int operator()(int index) const
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
const GLdouble * v
Definition: glcorearb.h:836
int getBit(int idx) const
GLuint start
Definition: glcorearb.h:474
int operator[](int index) const
void restartSearchForIndex(int idx) const
#define UT_API
Definition: UT_API.h:12
void setBit(int idx, int value)
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
long long int64
Definition: SYS_Types.h:106
GLdouble n
Definition: glcorearb.h:2007
void restartSearch() const
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:102
iterator end()
GLuint GLuint end
Definition: glcorearb.h:474
UT_LinkList myList
const_iterator(const UT_LinkList &list)
const_iterator iterator
const_iterator end() const
GLsizei const GLfloat * value
Definition: glcorearb.h:823
void advanceSearchNode() const
GLuint index
Definition: glcorearb.h:785
const_iterator begin() const
bool operator==(const const_iterator &rhs) const
#define UT_SWAPPER_CLASS(T)
Definition: UT_Swap.h:60
iterator begin()
bool operator!=(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:165
#define const
Definition: zconf.h:214
bool operator!=(const const_iterator &lhs) const