HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_RLEArray.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_RLEArray.h (GT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_RLEArray__
12 #define __UT_RLEArray__
13 
14 #include "UT_API.h"
15 #include "UT_SmallArray.h"
16 #include "UT_Debug.h"
17 #include <iterator>
18 #include <algorithm>
19 
20 class UT_JSONWriter;
21 
22 /// Appending elements to this array will build up a run-length encoded
23 /// compressed array. Random access may not be fast.
24 template <typename T>
26 {
27 public:
28  using value_type = T;
29 
30  struct Run
31  {
32  Run()
33  : myArray()
34  , myRepeat(0)
35  , myStartIndex(0)
36  {
37  }
38  Run(const T &item, exint repeat, exint start_index)
39  : myArray()
40  , mySingle(item)
41  , myRepeat(repeat)
42  , myStartIndex(start_index)
43  {
44  }
45  ~Run() {}
46 
47  SYS_FORCE_INLINE bool isEmpty() const { return myRepeat == 0; }
48  SYS_FORCE_INLINE bool isRun() const { return myRepeat >= 0; }
50  {
51  UT_ASSERT(myRepeat >= 0);
52  return myRepeat;
53  }
55  {
56  return myRepeat >= 0 ? myRepeat : myArray.size();
57  }
58  SYS_FORCE_INLINE exint startIndex() const { return myStartIndex; }
59  SYS_FORCE_INLINE exint endIndex() const { return myStartIndex + size(); }
60  SYS_FORCE_INLINE const T &arrayItem(exint idx) const
61  {
62  return myRepeat >= 0 ? mySingle : myArray[idx];
63  }
64  SYS_FORCE_INLINE const T &operator[](exint idx) const
65  {
66  if (isRun())
67  {
68  UT_ASSERT_P(idx < myRepeat && myArray.size() == 0);
69  return mySingle;
70  }
71  return myArray[idx];
72  }
73 
74  SYS_FORCE_INLINE void appendRun(exint num=1) { myRepeat += num; }
75  SYS_FORCE_INLINE void appendSequence(const T &item)
76  {
77  UT_ASSERT(!isRun());
78  myArray.append(item);
79  }
80 
82  {
83  UT_ASSERT(myRepeat > 0 && myArray.size() == 0);
84  myArray.appendMultiple(mySingle, myRepeat);
85  myArray.append(item);
86  myRepeat = -1;
87  }
88 
89  /// Return the number of items at the end of the sequence which match
90  /// the item.
91  SYS_FORCE_INLINE exint matchesAtEnd(const T &item) const
92  {
93  UT_ASSERT(!isRun() && myArray.size() > 0);
94  for (exint i = myArray.size(); i-- > 0; )
95  {
96  if (myArray[i] != item)
97  return (myArray.size() - 1) - i;
98  }
99  return myArray.size();
100  }
102  {
103  UT_ASSERT(!isRun() && myArray.size() > n);
104  myArray.setSize(myArray.size() - n);
105  UT_ASSERT(myArray.size());
106  }
108  {
109  myStartIndex -= n;
110  UT_ASSERT_P(myStartIndex >= 0);
111  }
112 
114  {
115  return myArray.getMemoryUsage() + sizeof(exint) + sizeof(T);
116  }
117 
118  private:
119  // The small array is big enough to hold a single item
120  UT_Array<T> myArray;
121  T mySingle;
122  exint myRepeat;
123  exint myStartIndex;
124  };
125 
127  : myRuns()
128  , mySize(0)
129  {
130  }
132  : myRuns()
133  , mySize(0)
134  {
135  for (exint i = 0; i < size; ++i)
136  append(data[i]);
137  }
139  : myRuns()
140  , mySize(0)
141  {
142  for (auto &&item : arr)
143  append(item);
144  }
146  {
147  }
148 
149  SYS_FORCE_INLINE bool isEmpty() const { return mySize == 0; }
150  SYS_FORCE_INLINE exint size() const { return mySize; }
151  SYS_FORCE_INLINE exint numRuns() const { return myRuns.size(); }
152  SYS_FORCE_INLINE const Run &run(exint i) const { return myRuns(i); }
154  {
155  mySize = 0;
156  myRuns.clear();
157  }
158 
159  /// This is a slow way of computing the size of the array but can be used
160  /// for debugging.
162  {
163  exint n = 0;
164  for (auto &&run : myRuns)
165  n += run.size();
166  return n;
167  }
168 
170  {
171  exint mem = 0;
172  for (auto &&run : myRuns)
173  mem += run.getMemoryUsage();
174  return mem + myRuns.getMemoryUsage() + sizeof(exint);
175  }
176 
177  // Test whether the array has a single value for the entire array
179  {
180  return myRuns.size() == 1 && myRuns[0].isRun();
181  }
183  {
184  return myRuns[0].arrayItem(0);
185  }
186 
187  /// Note that finding an item is O(log(N)) - where N is the number of runs
188  SYS_FORCE_INLINE const T &findItem(exint idx) const
189  {
190  UT_ASSERT_P(idx >= 0 && idx < mySize);
191  auto &&it = std::lower_bound(myRuns.begin(), myRuns.end(), idx,
192  [](const Run &run, exint value)
193  {
194  // Return true if the run's end index is less
195  // than or equal to the value we're searching
196  // for (the run is earlier in the list than
197  // the one we're looking for).
198  return run.endIndex() <= value;
199  });
200  return (*it)[idx - (*it).startIndex()];
201  }
202 
203  SYS_FORCE_INLINE void appendRun(const T &item, exint n)
204  {
205  if (n == 0)
206  return;
207  if (n < 3)
208  {
209  for (exint i = 0; i < n; ++i)
210  append(item);
211  return;
212  }
213  if (myRuns.size()
214  && myRuns.last().isRun()
215  && item == myRuns.last().arrayItem(0))
216  {
217  myRuns.last().appendRun(n);
218  }
219  else
220  {
221  newRun(item, n);
222  }
223  mySize += n;
224  }
225 
226  SYS_FORCE_INLINE void append(const T &item)
227  {
228  if (mySize == 0)
229  {
230  // First item
231  newRun(item, 1);
232  }
233  else
234  {
235  Run &last = myRuns.last();
236  if (last.isRun())
237  {
238  if (item == last.arrayItem(0))
239  last.appendRun(1);
240  else
241  {
242  if (last.runSize() > 2)
243  {
244  // If we have a run that's over 2 items, we start a new run
245  newRun(item, 1);
246  }
247  else
248  {
249  // Convert the current run into a squence instead of a run
250  last.convertToSequence(item);
251  }
252  }
253  }
254  else
255  {
256  exint n = last.matchesAtEnd(item);
257  if (n >= 3)
258  {
259  last.removeItemsFromEnd(n);
260  newRun(item, n+1);
261  myRuns.last().adjustStartOffset(n);
262  }
263  else
264  {
265  last.appendSequence(item);
266  }
267  }
268  }
269  mySize++;
270  }
271 
272  class iterator
273  : public std::iterator<std::forward_iterator_tag, exint>
274  {
275  public:
276  typedef exint type;
277 
279  : myArray(nullptr)
280  , myRunIndex(0)
281  , myRunOffset(0)
282  {
283  }
285 
286  const T &item() const
287  {
288  return myArray->run(myRunIndex)[myRunOffset];
289  }
290  const T &operator*() const { return item(); }
291 
292  bool operator==(const iterator &i) const
293  {
294  return myArray == i.myArray
295  && myRunIndex == i.myRunIndex
296  && myRunOffset == i.myRunOffset;
297  }
298  bool operator!=(const iterator &i) const
299  {
300  return !(*this == i);
301  }
302  bool atEnd() const
303  {
304  return myRunIndex >= myArray->numRuns();
305  }
306  iterator &operator++() { advance(); return *this; }
307  void rewind()
308  {
309  if (myArray)
310  {
311  myRunIndex = 0;
312  myRunOffset = 0;
313  }
314  }
315  void advance()
316  {
317  myRunOffset++;
318  if (myRunOffset >= myArray->run(myRunIndex).size())
319  {
320  // Advance to the next run
321  myRunIndex++;
322  myRunOffset = 0;
323  }
324  }
325  private:
326  iterator(const UT_RLEArray<T> &array, bool end)
327  : myArray(&array)
328  , myRunIndex(end ? array.numRuns() : 0)
329  , myRunOffset(0)
330  {
331  }
332  const UT_RLEArray<T> *myArray;
333  exint myRunIndex; // Index into array of runs
334  exint myRunOffset; // Index into run's items
335  friend class UT_RLEArray<T>;
336  };
337  using const_iterator = iterator;
338 
339  SYS_FORCE_INLINE iterator begin() const { return iterator(*this, false); }
340  SYS_FORCE_INLINE iterator end() const { return iterator(*this, true); }
341 
342 private:
343  SYS_FORCE_INLINE void newRun(const T &item, exint size)
344  {
345  myRuns.emplace_back(item, size, mySize);
346  }
348  exint mySize;
349 };
350 
351 #endif
GLsizeiptr size
Definition: glew.h:1681
iterator & operator++()
Definition: UT_RLEArray.h:306
SYS_FORCE_INLINE exint numRuns() const
Definition: UT_RLEArray.h:151
SYS_FORCE_INLINE void appendRun(exint num=1)
Definition: UT_RLEArray.h:74
SYS_FORCE_INLINE bool isEmpty() const
Definition: UT_RLEArray.h:47
const T & operator*() const
Definition: UT_RLEArray.h:290
int64 exint
Definition: SYS_Types.h:125
SYS_FORCE_INLINE exint matchesAtEnd(const T &item) const
Definition: UT_RLEArray.h:91
SYS_FORCE_INLINE void append(const T &item)
Definition: UT_RLEArray.h:226
Class which writes ASCII or binary JSON streams.
Definition: UT_JSONWriter.h:34
SYS_FORCE_INLINE const Run & run(exint i) const
Definition: UT_RLEArray.h:152
SYS_FORCE_INLINE const T & uniformItem() const
Definition: UT_RLEArray.h:182
bool operator==(const iterator &i) const
Definition: UT_RLEArray.h:292
UT_RLEArray(const UT_Array< T > &arr)
Definition: UT_RLEArray.h:138
SYS_FORCE_INLINE void appendRun(const T &item, exint n)
Definition: UT_RLEArray.h:203
SYS_FORCE_INLINE bool isUniform() const
Definition: UT_RLEArray.h:178
SYS_FORCE_INLINE exint size() const
Definition: UT_RLEArray.h:54
SYS_FORCE_INLINE void clear()
Definition: UT_RLEArray.h:153
GLint GLenum GLsizei GLint GLsizei const void * data
Definition: glew.h:1379
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:134
SYS_FORCE_INLINE void appendSequence(const T &item)
Definition: UT_RLEArray.h:75
UT_RLEArray(const T *data, exint size)
Definition: UT_RLEArray.h:131
const T & item() const
Definition: UT_RLEArray.h:286
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
SYS_FORCE_INLINE bool isEmpty() const
Definition: UT_RLEArray.h:149
GLuint GLuint end
Definition: glew.h:1253
GLsizei n
Definition: glew.h:4040
SYS_FORCE_INLINE void adjustStartOffset(exint n)
Definition: UT_RLEArray.h:107
SYS_FORCE_INLINE exint size() const
Definition: UT_RLEArray.h:150
SYS_FORCE_INLINE exint getMemoryUsage() const
Definition: UT_RLEArray.h:113
SYS_FORCE_INLINE iterator begin() const
Definition: UT_RLEArray.h:339
SYS_FORCE_INLINE const T & operator[](exint idx) const
Definition: UT_RLEArray.h:64
SYS_FORCE_INLINE void convertToSequence(const T &item)
Definition: UT_RLEArray.h:81
SYS_FORCE_INLINE iterator end() const
Definition: UT_RLEArray.h:340
SYS_FORCE_INLINE exint getMemoryUsage() const
Definition: UT_RLEArray.h:169
SYS_FORCE_INLINE void removeItemsFromEnd(exint n)
Definition: UT_RLEArray.h:101
SYS_FORCE_INLINE exint startIndex() const
Definition: UT_RLEArray.h:58
std::string OIIO_API repeat(string_view str, int n)
Repeat a string formed by concatenating str n times.
GLuint num
Definition: glew.h:2690
SYS_FORCE_INLINE const T & arrayItem(exint idx) const
Definition: UT_RLEArray.h:60
bool operator!=(const iterator &i) const
Definition: UT_RLEArray.h:298
SYS_FORCE_INLINE exint countSize() const
Definition: UT_RLEArray.h:161
GLenum array
Definition: glew.h:9066
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:135
SYS_FORCE_INLINE exint endIndex() const
Definition: UT_RLEArray.h:59
SYS_FORCE_INLINE bool isRun() const
Definition: UT_RLEArray.h:48
bool atEnd() const
Definition: UT_RLEArray.h:302
SYS_FORCE_INLINE exint runSize() const
Definition: UT_RLEArray.h:49
Run(const T &item, exint repeat, exint start_index)
Definition: UT_RLEArray.h:38
SYS_FORCE_INLINE const T & findItem(exint idx) const
Note that finding an item is O(log(N)) - where N is the number of runs.
Definition: UT_RLEArray.h:188
GLsizei const GLfloat * value
Definition: glew.h:1849