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