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