|
1 #ifndef __RIARRAY_H |
|
2 #define __RIARRAY_H |
|
3 |
|
4 /*------------------------------------------------------------------------ |
|
5 * |
|
6 * OpenVG 1.1 Reference Implementation |
|
7 * ----------------------------------- |
|
8 * |
|
9 * Copyright (c) 2007 The Khronos Group Inc. |
|
10 * Portions copyright (c) 2010 Nokia Corporation and/or its subsidiary(-ies). |
|
11 * |
|
12 * Permission is hereby granted, free of charge, to any person obtaining a |
|
13 * copy of this software and /or associated documentation files |
|
14 * (the "Materials "), to deal in the Materials without restriction, |
|
15 * including without limitation the rights to use, copy, modify, merge, |
|
16 * publish, distribute, sublicense, and/or sell copies of the Materials, |
|
17 * and to permit persons to whom the Materials are furnished to do so, |
|
18 * subject to the following conditions: |
|
19 * |
|
20 * The above copyright notice and this permission notice shall be included |
|
21 * in all copies or substantial portions of the Materials. |
|
22 * |
|
23 * THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
|
24 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
|
25 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. |
|
26 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, |
|
27 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR |
|
28 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE MATERIALS OR |
|
29 * THE USE OR OTHER DEALINGS IN THE MATERIALS. |
|
30 * |
|
31 *//** |
|
32 * \file |
|
33 * \brief Array class. |
|
34 * \note |
|
35 *//*-------------------------------------------------------------------*/ |
|
36 |
|
37 #ifndef __RIDEFS_H |
|
38 #include "riDefs.h" |
|
39 #endif |
|
40 |
|
41 #include <string.h> //for memcpy |
|
42 |
|
43 namespace OpenVGRI |
|
44 { |
|
45 |
|
46 //======================================================================= |
|
47 |
|
48 /*-------------------------------------------------------------------*//*! |
|
49 * \brief An array class similar to std::vector. |
|
50 * \param |
|
51 * \return |
|
52 * \note Follows std::vector's naming convention (except resizeAndReallocate). |
|
53 *//*-------------------------------------------------------------------*/ |
|
54 |
|
55 template <class Item> class Array |
|
56 { |
|
57 public: |
|
58 friend class Rasterizer; |
|
59 |
|
60 Array() : m_array(NULL), m_size(0), m_allocated(0) {} //throws bad_alloc |
|
61 ~Array() |
|
62 { |
|
63 RI_DELETE_ARRAY(m_array); |
|
64 } |
|
65 |
|
66 void swap(Array& s) |
|
67 { |
|
68 Item* tarray = m_array; |
|
69 m_array = s.m_array; |
|
70 s.m_array = tarray; |
|
71 |
|
72 int tsize = m_size; |
|
73 m_size = s.m_size; |
|
74 s.m_size = tsize; |
|
75 |
|
76 int tallocated = m_allocated; |
|
77 m_allocated = s.m_allocated; |
|
78 s.m_allocated = tallocated; |
|
79 } |
|
80 |
|
81 //if more room is needed, reallocate, otherwise return |
|
82 void reserve( int items ) //throws bad_alloc |
|
83 { |
|
84 RI_ASSERT( items >= 0 ); |
|
85 if( items <= m_allocated ) |
|
86 return; //if there is room already, return |
|
87 |
|
88 RI_ASSERT( items > m_allocated ); |
|
89 |
|
90 Item* newa = RI_NEW_ARRAY(Item, items); //throws bad_alloc if runs out of memory |
|
91 for(int i=0;i<m_size;i++) |
|
92 newa[i] = m_array[i]; |
|
93 RI_DELETE_ARRAY(m_array); |
|
94 m_array = newa; |
|
95 m_allocated = items; |
|
96 //doesn't change size |
|
97 } |
|
98 |
|
99 //reserve and change size |
|
100 void resize( int items ) //throws bad_alloc |
|
101 { |
|
102 reserve( items ); //throws bad_alloc if runs out of memory |
|
103 m_size = items; |
|
104 } |
|
105 |
|
106 //resize and allocate exactly the correct amount of memory |
|
107 void resizeAndReallocate( int items ) //throws bad_alloc |
|
108 { |
|
109 RI_ASSERT( items >= 0 ); |
|
110 if( items == m_allocated ) |
|
111 { |
|
112 m_size = items; |
|
113 return; |
|
114 } |
|
115 |
|
116 if( items == 0 ) |
|
117 { |
|
118 RI_DELETE_ARRAY(m_array); |
|
119 m_size = 0; |
|
120 m_allocated = 0; |
|
121 return; |
|
122 } |
|
123 |
|
124 Item* newa = RI_NEW_ARRAY(Item, items); //throws bad_alloc if runs out of memory |
|
125 int copySize = (m_size < items) ? m_size : items; //min(m_size,items) |
|
126 for(int i=0;i<copySize;i++) |
|
127 newa[i] = m_array[i]; |
|
128 RI_DELETE_ARRAY(m_array); |
|
129 m_array = newa; |
|
130 m_allocated = items; |
|
131 m_size = items; //changes also size |
|
132 } |
|
133 void clear() |
|
134 { |
|
135 m_size = 0; |
|
136 } |
|
137 |
|
138 //sort array (needs operator< defined for Item. Define it with < for increasing order and > for decreasing.) |
|
139 void sort() |
|
140 { |
|
141 if(m_size <= 1) |
|
142 return; |
|
143 quicksort(0, m_size - 1); |
|
144 } |
|
145 |
|
146 void sort(int first, int last) |
|
147 { |
|
148 RI_ASSERT(first <= last); |
|
149 RI_ASSERT((first >= 0) && (last < m_size)); |
|
150 |
|
151 if (m_size <= 1) |
|
152 return; |
|
153 |
|
154 if ((last - first) < 1) |
|
155 return; |
|
156 |
|
157 quicksort(first, last); |
|
158 #if defined(RI_DEBUG) |
|
159 for (int i = first+1; i <= last; i++) |
|
160 { |
|
161 RI_ASSERT(m_array[i-1] <= m_array[i]); |
|
162 } |
|
163 #endif |
|
164 } |
|
165 |
|
166 int findIndex(const Item& item) |
|
167 { |
|
168 for(int i = 0; i < m_size; i++) |
|
169 if (m_array[i] == item) |
|
170 return i; |
|
171 return -1; |
|
172 } |
|
173 |
|
174 //remove the first occurrence of an item from the array |
|
175 bool remove(const Item& item) |
|
176 { |
|
177 int i=0; |
|
178 for(;i<m_size;i++) |
|
179 { |
|
180 if(m_array[i] == item) |
|
181 break; |
|
182 } |
|
183 if(i >= m_size) |
|
184 return false; //not found |
|
185 for(;i<m_size-1;i++) |
|
186 { |
|
187 m_array[i] = m_array[i+1]; |
|
188 } |
|
189 m_size--; |
|
190 return true; |
|
191 } |
|
192 |
|
193 RI_INLINE void push_back( const Item& item ) //throws bad_alloc |
|
194 { |
|
195 if( m_size >= m_allocated ) |
|
196 reserve( (!m_allocated) ? 8 : m_allocated * 2 ); //by default, reserve 8. throws bad_alloc if runs out of memory |
|
197 m_array[m_size++] = item; |
|
198 } |
|
199 RI_INLINE int size() const { return m_size; } |
|
200 RI_INLINE Item& operator[](int i) { RI_ASSERT(i >= 0 && i < m_size); return m_array[i]; } |
|
201 RI_INLINE const Item& operator[](int i) const { RI_ASSERT(i >= 0 && i < m_size); return m_array[i]; } |
|
202 |
|
203 private: |
|
204 Array(const Array& s); //!< Not allowed. |
|
205 void operator=(const Array& s); //!< Not allowed. |
|
206 |
|
207 void quicksort(int left, int right) |
|
208 { |
|
209 int i = left, j = right; |
|
210 Item x = m_array[(left+right)>>1]; |
|
211 |
|
212 do |
|
213 { |
|
214 while (m_array[i] < x) |
|
215 i++; |
|
216 while (x < m_array[j]) |
|
217 j--; |
|
218 if (i<=j) |
|
219 { |
|
220 Item tmp = m_array[i]; |
|
221 m_array[i] = m_array[j]; |
|
222 m_array[j] = tmp; |
|
223 i++; |
|
224 j--; |
|
225 } |
|
226 } while (i<=j); |
|
227 |
|
228 if(left < j) quicksort(left, j); |
|
229 if(i < right) quicksort(i, right); |
|
230 } |
|
231 |
|
232 |
|
233 Item* m_array; |
|
234 int m_size; |
|
235 int m_allocated; |
|
236 }; |
|
237 |
|
238 //======================================================================= |
|
239 |
|
240 } //namespace OpenVGRI |
|
241 |
|
242 #endif /* __RIARRAY_H */ |