HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
SIM_PtrArraySorted.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  */
7 
8 #ifndef __SIM_PtrArraySorted_h__
9 #define __SIM_PtrArraySorted_h__
10 
11 #include <UT/UT_ValArray.h>
12 
13 namespace
14 {
15  static inline int
16  comparePointers(void *const* a, void *const* b)
17  {
18  ptrdiff_t pa = ptrdiff_t(*a), pb = ptrdiff_t(*b);
19  if (pa < pb) return -1;
20  if (pa > pb) return 1;
21  return 0;
22  }
23 }
24 
26 template <class T>
28 {
29 public:
31  : myComparator(
32  typename UT_ValArray<T>::Comparator(
33  comparePointers))
34  { }
35 
37  typename UT_ValArray<T>::Comparator comparator)
38  : myComparator(comparator)
39  { }
41  { }
42 
43  void setComparator(typename
45  { myComparator = cmp; myArray.sort(myComparator); }
46  void sort()
47  { myArray.sort(myComparator); }
48 
49  exint size() const
50  {
51  return myArray.size();
52  }
53  void setSize(exint newsize)
54  {
55  myArray.setSize(newsize);
56  }
57  void setCapacity(exint newcapacity)
58  {
59  myArray.setCapacity(newcapacity);
60  }
61  exint entries() const
62  { return size(); }
63  void entries(int newnumentries)
64  { setSize(newnumentries); }
65  void resize(int newsize)
66  { setCapacity(newsize); }
67 
68  T operator()(int index) const
69  { return myArray(index); }
70  T last() const
71  { return myArray.last(); }
72  int find(T ptr) const
73  { return myArray.find(ptr, myComparator); }
74 
75  bool operator==(const SIM_PtrArraySorted &cmp) const
76  {
77  T ptr, cmpptr;
78  int idx, num, diff;
79 
80  if( entries() != cmp.entries() )
81  return false;
82 
83  num = entries();
84  for( idx = 0; idx < num; idx++ )
85  {
86  ptr = myArray(idx);
87  cmpptr = cmp.myArray(idx);
88  diff = myComparator(&ptr, &cmpptr);
89 
90  if( diff != 0 )
91  return false;
92  }
93 
94  return true;
95  }
96 
97  bool containsAny(const SIM_PtrArraySorted &cmp) const
98  {
99  T ptr, cmpptr;
100  int idx, cmpidx, num, numcmp, diff;
101 
102  numcmp = cmp.entries();
103  num = entries();
104  for( idx = 0, cmpidx = 0;
105  idx < num && cmpidx < numcmp; )
106  {
107  ptr = myArray(idx);
108  cmpptr = cmp.myArray(cmpidx);
109  diff = myComparator(&ptr, &cmpptr);
110 
111  if( diff < 0 )
112  {
113  idx++;
114  }
115  else if( diff > 0 )
116  {
117  cmpidx++;
118  }
119  else
120  {
121  return true;
122  }
123  }
124 
125  return false;
126  }
127  bool containsFully(const SIM_PtrArraySorted &cmp) const
128  {
129  T ptr, cmpptr;
130  int idx, cmpidx, num, numcmp, diff;
131 
132  numcmp = cmp.entries();
133  num = entries();
134  for( idx = 0, cmpidx = 0;
135  idx < num && cmpidx < numcmp; )
136  {
137  ptr = myArray(idx);
138  cmpptr = cmp.myArray(cmpidx);
139  diff = myComparator(&ptr, &cmpptr);
140 
141  if( diff < 0 )
142  {
143  idx++;
144  }
145  else if( diff > 0 )
146  {
147  return false;
148  }
149  else
150  {
151  idx++;
152  cmpidx++;
153  }
154  }
155 
156  return (cmpidx >= numcmp) ? true : false;
157  }
158 
159  void remove(int index)
160  { myArray.removeIndex(index); }
161  void remove(T ptr)
162  { int pos = find(ptr); if( pos >= 0 ) remove(pos); }
163  void remove(const SIM_PtrArraySorted &src)
164  {
165  T srcptr, destptr;
166  int idx, srcidx, diff, numsrc;
167  bool removed = false;
168 
169  numsrc = src.entries();
170  for( idx = 0, srcidx = 0;
171  srcidx < numsrc && idx < entries(); )
172  {
173  destptr = myArray(idx);
174  srcptr = src.myArray(srcidx);
175  diff = myComparator(&destptr, &srcptr);
176 
177  if( diff < 0 )
178  {
179  idx++;
180  }
181  else
182  {
183  if( diff == 0 )
184  {
185  myArray(idx) = 0;
186  removed = true;
187  idx++;
188  }
189  srcidx++;
190  }
191  }
192  if( removed )
193  myArray.removeZeros();
194  }
195  void keepOnly(const SIM_PtrArraySorted &src)
196  {
197  T srcptr, destptr;
198  int idx, srcidx, diff, numsrc;
199  bool removed = false;
200 
201  numsrc = src.entries();
202  for( idx = 0, srcidx = 0; idx < entries(); )
203  {
204  if( srcidx < numsrc )
205  {
206  destptr = myArray(idx);
207  srcptr = src.myArray(srcidx);
208  diff = myComparator(&destptr, &srcptr);
209  }
210  else
211  diff = -1;
212 
213  if( diff < 0 )
214  {
215  myArray(idx) = 0;
216  removed = true;
217  idx++;
218  }
219  else
220  {
221  if( diff == 0 )
222  idx++;
223  srcidx++;
224  }
225  }
226  if( removed )
227  myArray.removeZeros();
228  }
229 
230  const SIM_PtrArraySorted &operator=(const SIM_PtrArraySorted &src)
231  { set(src); return *this; }
232  int add(T ptr)
233  {
234  return myArray.
235  uniqueSortedInsert(ptr, myComparator);
236  }
237  void set(const SIM_PtrArraySorted &src)
238  {
239  myComparator = src.myComparator;
240  myArray = src.myArray;
241  }
243  SIM_PtrArraySorted &duplicates)
244  {
245  T lastptr, nextptr;
246  int idx;
247 
248  myArray = src;
249  sort();
250  for( idx = 1; idx < entries(); idx++ )
251  {
252  lastptr = myArray(idx-1);
253  nextptr = myArray(idx);
254  if( myComparator(&lastptr, &nextptr) == 0 )
255  {
256  duplicates.add(lastptr);
257  myArray(idx-1) = 0;
258  }
259  }
260  if( duplicates.entries() )
261  myArray.removeZeros();
262  }
263  void merge(const SIM_PtrArraySorted &src)
264  {
265  // shift existing entries
266  int n_src = src.entries();
267  if(!n_src)
268  return;
269  int i = entries();
270  int n = i + n_src;
271  resize(n);
272  entries(n);
273  int idx = n;
274  T srcptr = src.myArray(0);
275  for(--i; i >= 0 && myComparator(&myArray(i), &srcptr) > 0; --i)
276  {
277  myArray(--idx) = myArray(i);
278  }
279  ++i;
280  // merge items into the hole at [i, i+n_src)
281  int merge_start = i;
282  int src_idx = 0;
283  for(;;)
284  {
285  if(idx < n)
286  {
287  if(src_idx == n_src)
288  break;
289  int cmp = myComparator(&myArray(idx), &src.myArray(src_idx));
290  if(cmp < 0)
291  myArray(i++) = myArray(idx++);
292  else
293  myArray(i++) = src.myArray(src_idx++);
294  continue;
295  }
296  while(src_idx < n_src)
297  myArray(i++) = src.myArray(src_idx++);
298  break;
299  }
300  // remove duplicates
301  if(!merge_start)
302  ++merge_start;
303  for(int i = merge_start; i < n; ++i)
304  {
305  if(myComparator(&myArray(i), &myArray(i - 1)))
306  myArray(merge_start++) = myArray(i);
307  }
308  entries(merge_start);
309  }
310  void SYS_DEPRECATED(13.0) mergeSelected(const SIM_PtrArraySorted &src,
311  bool (*selectfunc)(T))
312  {
313  T srcptr, destptr;
314  int idx, srcidx, diff, numsrc;
315 
316  numsrc = src.entries();
317  for( idx = 0, srcidx = 0; srcidx < numsrc; )
318  {
319  // Just skip over any source pointers that
320  // aren't accepted by the select function.
321  if( selectfunc(src.myArray(srcidx)) )
322  {
323  if( idx < entries() )
324  {
325  destptr = myArray(idx);
326  srcptr = src.myArray(srcidx);
327  diff = myComparator(&destptr, &srcptr);
328  }
329  else
330  diff = 1;
331  if( diff < 0 )
332  {
333  idx++;
334  }
335  else
336  {
337  if( diff > 0 )
338  myArray.insert(src(srcidx), idx);
339  idx++;
340  srcidx++;
341  }
342  }
343  else
344  srcidx++;
345  }
346  }
347 
348 
349  // Not that this function can ruin the sort order. Use with caution.
351  { myArray.append(ptr); }
352  // This function gets our contained UT_ValArray.
354  { return myArray; }
355  // This function gets our contained UT_ValArray.
357  { return myArray; }
358 
359 private:
360  typename UT_ValArray<T>::Comparator myComparator;
361  UT_ValArray<T> myArray;
362 };
364 
365 
366 #endif
void merge(const SIM_PtrArraySorted &src)
exint entries() const
#define SYS_DEPRECATED(__V__)
#define SYS_DEPRECATED_PUSH_DISABLE()
#define SYS_DEPRECATED_POP_DISABLE()
png_voidp ptr
Definition: png.h:2145
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
void resize(int newsize)
void setComparator(typename UT_ValArray< T >::Comparator cmp)
png_uint_32 i
Definition: png.h:2877
GLsizeiptr size
Definition: glcorearb.h:663
GLdouble n
Definition: glcorearb.h:2007
const SIM_PtrArraySorted & operator=(const SIM_PtrArraySorted &src)
int64 exint
Definition: SYS_Types.h:109
void setUnsorted(const UT_ValArray< T > &src, SIM_PtrArraySorted &duplicates)
void entries(int newnumentries)
void set(const SIM_PtrArraySorted &src)
bool operator==(const SIM_PtrArraySorted &cmp) const
UT_ValArray< T > & getRawArray()
void setCapacity(exint newcapacity)
void setSize(exint newsize)
int find(T ptr) const
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
int cmp(T a, T b)
Definition: ImathFun.h:119
bool containsAny(const SIM_PtrArraySorted &cmp) const
png_infop png_sPLT_tpp entries
Definition: png.h:2481
SIM_PtrArraySorted(typename UT_ValArray< T >::Comparator comparator)
GLuint index
Definition: glcorearb.h:785
void keepOnly(const SIM_PtrArraySorted &src)
T operator()(int index) const
png_infop png_uint_32 int num
Definition: png.h:2158
#define const
Definition: zconf.h:214
bool containsFully(const SIM_PtrArraySorted &cmp) const
const UT_ValArray< T > & getRawArray() const
GLenum src
Definition: glcorearb.h:1792