HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_SparseArrayImpl.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 library (C++)
7  *
8  * COMMENTS: Mantains a sparse array of values.
9  *
10  */
11 
12 #ifndef __UT_SparseArrayImpl__
13 #define __UT_SparseArrayImpl__
14 
15 #ifndef __UT_SparseArray_h__
16 #error Do not include this file directly. Include UT_SparesArray.h instead.
17 #endif
18 
19 template <typename T>
21 {
22 }
23 
24 template <typename T>
26 {
27  clear();
28 }
29 
30 template <typename T>
31 void
33 {
34  int i;
35 
36  // TODO: Optimize by using bisection to find where it needs to be located
37  for (i = myArray.entries()-1; i >= 0; i--)
38  {
39  if (myArray(i)->myIndex == index)
40  {
41  myArray(i)->myData = data;
42  return;
43  }
44  if (myArray(i)->myIndex < index) break;
45  }
46  if (i == (int)(myArray.entries()-1))
47  myArray.append(new SparseEntry(index, data));
48  else
49  {
50  i++;
51  myArray.insert(new SparseEntry(index, data), i);
52  }
53 }
54 
55 template <typename T>
56 void
58 {
59  int iidx; // Internal index
60  if ((iidx = find(index)) >= 0)
61  {
62  delete myArray(iidx);
63  myArray.removeIndex(iidx);
64  }
65 }
66 
67 template <typename T>
68 void
70 {
71  for (exint i = 0; i < myArray.entries(); ++i)
72  delete myArray(i);
73  myArray.setCapacity(0);
74 }
75 
76 template <typename T>
77 T
79 {
80  index = -1;
81  if (raw_index >= 0 && raw_index < myArray.entries())
82  {
83  index = myArray(raw_index)->myIndex;
84  return myArray(raw_index)->myData;
85  }
86  return T(0);
87 }
88 
89 template <typename T>
90 T
92 {
93  int iidx;
94  return ((iidx = find(index)) >= 0) ? myArray(iidx)->myData : T(0);
95 }
96 
97 template <typename T>
98 const T
100 {
101  int iidx;
102  return ((iidx = find(index)) >= 0) ? myArray(iidx)->myData : T(0);
103 }
104 
105 //
106 // Use bisection to find the value if it exists
107 template <typename T>
108 int
110 {
111  int low, high, mid, val;
112 
113  high = myArray.entries()-1;
114  if (high < 1)
115  {
116  return (high == 0 && myArray(0)->myIndex == index) ? 0 : -1;
117  }
118  low = 0;
119 
120  do {
121  mid = (high+low) >> 1;
122  val = myArray(mid)->myIndex;
123  if (val == index) return mid;
124  if (val < index) low = mid;
125  else high = mid;
126  } while (high - low > 1);
127  if (myArray(high)->myIndex == index) return high;
128  if (myArray(low)->myIndex == index) return low;
129  return -1; // Not found
130 }
131 
132 #endif // __UT_SparseArrayImpl__
T getRawEntry(int raw_index, int &index)
png_uint_32 i
Definition: png.h:2877
int64 exint
Definition: SYS_Types.h:116
int find(int index) const
GLboolean * data
Definition: glcorearb.h:130
T operator()(unsigned int i)
GLuint index
Definition: glcorearb.h:785
GLuint GLfloat * val
Definition: glcorearb.h:1607
void removeIndex(int index)
void append(int index, T data)