diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/irrlicht-1.8/include/irrArray.h | 1254 |
1 files changed, 627 insertions, 627 deletions
diff --git a/libraries/irrlicht-1.8/include/irrArray.h b/libraries/irrlicht-1.8/include/irrArray.h index 7dab593..f9d338d 100644 --- a/libraries/irrlicht-1.8/include/irrArray.h +++ b/libraries/irrlicht-1.8/include/irrArray.h | |||
@@ -1,627 +1,627 @@ | |||
1 | // Copyright (C) 2002-2012 Nikolaus Gebhardt | 1 | // Copyright (C) 2002-2012 Nikolaus Gebhardt |
2 | // This file is part of the "Irrlicht Engine" and the "irrXML" project. | 2 | // This file is part of the "Irrlicht Engine" and the "irrXML" project. |
3 | // For conditions of distribution and use, see copyright notice in irrlicht.h and irrXML.h | 3 | // For conditions of distribution and use, see copyright notice in irrlicht.h and irrXML.h |
4 | 4 | ||
5 | #ifndef __IRR_ARRAY_H_INCLUDED__ | 5 | #ifndef __IRR_ARRAY_H_INCLUDED__ |
6 | #define __IRR_ARRAY_H_INCLUDED__ | 6 | #define __IRR_ARRAY_H_INCLUDED__ |
7 | 7 | ||
8 | #include "irrTypes.h" | 8 | #include "irrTypes.h" |
9 | #include "heapsort.h" | 9 | #include "heapsort.h" |
10 | #include "irrAllocator.h" | 10 | #include "irrAllocator.h" |
11 | #include "irrMath.h" | 11 | #include "irrMath.h" |
12 | 12 | ||
13 | namespace irr | 13 | namespace irr |
14 | { | 14 | { |
15 | namespace core | 15 | namespace core |
16 | { | 16 | { |
17 | 17 | ||
18 | //! Self reallocating template array (like stl vector) with additional features. | 18 | //! Self reallocating template array (like stl vector) with additional features. |
19 | /** Some features are: Heap sorting, binary search methods, easier debugging. | 19 | /** Some features are: Heap sorting, binary search methods, easier debugging. |
20 | */ | 20 | */ |
21 | template <class T, typename TAlloc = irrAllocator<T> > | 21 | template <class T, typename TAlloc = irrAllocator<T> > |
22 | class array | 22 | class array |
23 | { | 23 | { |
24 | 24 | ||
25 | public: | 25 | public: |
26 | 26 | ||
27 | //! Default constructor for empty array. | 27 | //! Default constructor for empty array. |
28 | array() | 28 | array() |
29 | : data(0), allocated(0), used(0), | 29 | : data(0), allocated(0), used(0), |
30 | strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true) | 30 | strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true) |
31 | { | 31 | { |
32 | } | 32 | } |
33 | 33 | ||
34 | 34 | ||
35 | //! Constructs an array and allocates an initial chunk of memory. | 35 | //! Constructs an array and allocates an initial chunk of memory. |
36 | /** \param start_count Amount of elements to pre-allocate. */ | 36 | /** \param start_count Amount of elements to pre-allocate. */ |
37 | array(u32 start_count) | 37 | array(u32 start_count) |
38 | : data(0), allocated(0), used(0), | 38 | : data(0), allocated(0), used(0), |
39 | strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true) | 39 | strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true) |
40 | { | 40 | { |
41 | reallocate(start_count); | 41 | reallocate(start_count); |
42 | } | 42 | } |
43 | 43 | ||
44 | 44 | ||
45 | //! Copy constructor | 45 | //! Copy constructor |
46 | array(const array<T, TAlloc>& other) : data(0) | 46 | array(const array<T, TAlloc>& other) : data(0) |
47 | { | 47 | { |
48 | *this = other; | 48 | *this = other; |
49 | } | 49 | } |
50 | 50 | ||
51 | 51 | ||
52 | //! Destructor. | 52 | //! Destructor. |
53 | /** Frees allocated memory, if set_free_when_destroyed was not set to | 53 | /** Frees allocated memory, if set_free_when_destroyed was not set to |
54 | false by the user before. */ | 54 | false by the user before. */ |
55 | ~array() | 55 | ~array() |
56 | { | 56 | { |
57 | clear(); | 57 | clear(); |
58 | } | 58 | } |
59 | 59 | ||
60 | 60 | ||
61 | //! Reallocates the array, make it bigger or smaller. | 61 | //! Reallocates the array, make it bigger or smaller. |
62 | /** \param new_size New size of array. | 62 | /** \param new_size New size of array. |
63 | \param canShrink Specifies whether the array is reallocated even if | 63 | \param canShrink Specifies whether the array is reallocated even if |
64 | enough space is available. Setting this flag to false can speed up | 64 | enough space is available. Setting this flag to false can speed up |
65 | array usage, but may use more memory than required by the data. | 65 | array usage, but may use more memory than required by the data. |
66 | */ | 66 | */ |
67 | void reallocate(u32 new_size, bool canShrink=true) | 67 | void reallocate(u32 new_size, bool canShrink=true) |
68 | { | 68 | { |
69 | if (allocated==new_size) | 69 | if (allocated==new_size) |
70 | return; | 70 | return; |
71 | if (!canShrink && (new_size < allocated)) | 71 | if (!canShrink && (new_size < allocated)) |
72 | return; | 72 | return; |
73 | 73 | ||
74 | T* old_data = data; | 74 | T* old_data = data; |
75 | 75 | ||
76 | data = allocator.allocate(new_size); //new T[new_size]; | 76 | data = allocator.allocate(new_size); //new T[new_size]; |
77 | allocated = new_size; | 77 | allocated = new_size; |
78 | 78 | ||
79 | // copy old data | 79 | // copy old data |
80 | s32 end = used < new_size ? used : new_size; | 80 | s32 end = used < new_size ? used : new_size; |
81 | 81 | ||
82 | for (s32 i=0; i<end; ++i) | 82 | for (s32 i=0; i<end; ++i) |
83 | { | 83 | { |
84 | // data[i] = old_data[i]; | 84 | // data[i] = old_data[i]; |
85 | allocator.construct(&data[i], old_data[i]); | 85 | allocator.construct(&data[i], old_data[i]); |
86 | } | 86 | } |
87 | 87 | ||
88 | // destruct old data | 88 | // destruct old data |
89 | for (u32 j=0; j<used; ++j) | 89 | for (u32 j=0; j<used; ++j) |
90 | allocator.destruct(&old_data[j]); | 90 | allocator.destruct(&old_data[j]); |
91 | 91 | ||
92 | if (allocated < used) | 92 | if (allocated < used) |
93 | used = allocated; | 93 | used = allocated; |
94 | 94 | ||
95 | allocator.deallocate(old_data); //delete [] old_data; | 95 | allocator.deallocate(old_data); //delete [] old_data; |
96 | } | 96 | } |
97 | 97 | ||
98 | 98 | ||
99 | //! set a new allocation strategy | 99 | //! set a new allocation strategy |
100 | /** if the maximum size of the array is unknown, you can define how big the | 100 | /** if the maximum size of the array is unknown, you can define how big the |
101 | allocation should happen. | 101 | allocation should happen. |
102 | \param newStrategy New strategy to apply to this array. */ | 102 | \param newStrategy New strategy to apply to this array. */ |
103 | void setAllocStrategy ( eAllocStrategy newStrategy = ALLOC_STRATEGY_DOUBLE ) | 103 | void setAllocStrategy ( eAllocStrategy newStrategy = ALLOC_STRATEGY_DOUBLE ) |
104 | { | 104 | { |
105 | strategy = newStrategy; | 105 | strategy = newStrategy; |
106 | } | 106 | } |
107 | 107 | ||
108 | 108 | ||
109 | //! Adds an element at back of array. | 109 | //! Adds an element at back of array. |
110 | /** If the array is too small to add this new element it is made bigger. | 110 | /** If the array is too small to add this new element it is made bigger. |
111 | \param element: Element to add at the back of the array. */ | 111 | \param element: Element to add at the back of the array. */ |
112 | void push_back(const T& element) | 112 | void push_back(const T& element) |
113 | { | 113 | { |
114 | insert(element, used); | 114 | insert(element, used); |
115 | } | 115 | } |
116 | 116 | ||
117 | 117 | ||
118 | //! Adds an element at the front of the array. | 118 | //! Adds an element at the front of the array. |
119 | /** If the array is to small to add this new element, the array is | 119 | /** If the array is to small to add this new element, the array is |
120 | made bigger. Please note that this is slow, because the whole array | 120 | made bigger. Please note that this is slow, because the whole array |
121 | needs to be copied for this. | 121 | needs to be copied for this. |
122 | \param element Element to add at the back of the array. */ | 122 | \param element Element to add at the back of the array. */ |
123 | void push_front(const T& element) | 123 | void push_front(const T& element) |
124 | { | 124 | { |
125 | insert(element); | 125 | insert(element); |
126 | } | 126 | } |
127 | 127 | ||
128 | 128 | ||
129 | //! Insert item into array at specified position. | 129 | //! Insert item into array at specified position. |
130 | /** Please use this only if you know what you are doing (possible | 130 | /** Please use this only if you know what you are doing (possible |
131 | performance loss). The preferred method of adding elements should be | 131 | performance loss). The preferred method of adding elements should be |
132 | push_back(). | 132 | push_back(). |
133 | \param element: Element to be inserted | 133 | \param element: Element to be inserted |
134 | \param index: Where position to insert the new element. */ | 134 | \param index: Where position to insert the new element. */ |
135 | void insert(const T& element, u32 index=0) | 135 | void insert(const T& element, u32 index=0) |
136 | { | 136 | { |
137 | _IRR_DEBUG_BREAK_IF(index>used) // access violation | 137 | _IRR_DEBUG_BREAK_IF(index>used) // access violation |
138 | 138 | ||
139 | if (used + 1 > allocated) | 139 | if (used + 1 > allocated) |
140 | { | 140 | { |
141 | // this doesn't work if the element is in the same | 141 | // this doesn't work if the element is in the same |
142 | // array. So we'll copy the element first to be sure | 142 | // array. So we'll copy the element first to be sure |
143 | // we'll get no data corruption | 143 | // we'll get no data corruption |
144 | const T e(element); | 144 | const T e(element); |
145 | 145 | ||
146 | // increase data block | 146 | // increase data block |
147 | u32 newAlloc; | 147 | u32 newAlloc; |
148 | switch ( strategy ) | 148 | switch ( strategy ) |
149 | { | 149 | { |
150 | case ALLOC_STRATEGY_DOUBLE: | 150 | case ALLOC_STRATEGY_DOUBLE: |
151 | newAlloc = used + 1 + (allocated < 500 ? | 151 | newAlloc = used + 1 + (allocated < 500 ? |
152 | (allocated < 5 ? 5 : used) : used >> 2); | 152 | (allocated < 5 ? 5 : used) : used >> 2); |
153 | break; | 153 | break; |
154 | default: | 154 | default: |
155 | case ALLOC_STRATEGY_SAFE: | 155 | case ALLOC_STRATEGY_SAFE: |
156 | newAlloc = used + 1; | 156 | newAlloc = used + 1; |
157 | break; | 157 | break; |
158 | } | 158 | } |
159 | reallocate( newAlloc); | 159 | reallocate( newAlloc); |
160 | 160 | ||
161 | // move array content and construct new element | 161 | // move array content and construct new element |
162 | // first move end one up | 162 | // first move end one up |
163 | for (u32 i=used; i>index; --i) | 163 | for (u32 i=used; i>index; --i) |
164 | { | 164 | { |
165 | if (i<used) | 165 | if (i<used) |
166 | allocator.destruct(&data[i]); | 166 | allocator.destruct(&data[i]); |
167 | allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1]; | 167 | allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1]; |
168 | } | 168 | } |
169 | // then add new element | 169 | // then add new element |
170 | if (used > index) | 170 | if (used > index) |
171 | allocator.destruct(&data[index]); | 171 | allocator.destruct(&data[index]); |
172 | allocator.construct(&data[index], e); // data[index] = e; | 172 | allocator.construct(&data[index], e); // data[index] = e; |
173 | } | 173 | } |
174 | else | 174 | else |
175 | { | 175 | { |
176 | // element inserted not at end | 176 | // element inserted not at end |
177 | if ( used > index ) | 177 | if ( used > index ) |
178 | { | 178 | { |
179 | // create one new element at the end | 179 | // create one new element at the end |
180 | allocator.construct(&data[used], data[used-1]); | 180 | allocator.construct(&data[used], data[used-1]); |
181 | 181 | ||
182 | // move the rest of the array content | 182 | // move the rest of the array content |
183 | for (u32 i=used-1; i>index; --i) | 183 | for (u32 i=used-1; i>index; --i) |
184 | { | 184 | { |
185 | data[i] = data[i-1]; | 185 | data[i] = data[i-1]; |
186 | } | 186 | } |
187 | // insert the new element | 187 | // insert the new element |
188 | data[index] = element; | 188 | data[index] = element; |
189 | } | 189 | } |
190 | else | 190 | else |
191 | { | 191 | { |
192 | // insert the new element to the end | 192 | // insert the new element to the end |
193 | allocator.construct(&data[index], element); | 193 | allocator.construct(&data[index], element); |
194 | } | 194 | } |
195 | } | 195 | } |
196 | // set to false as we don't know if we have the comparison operators | 196 | // set to false as we don't know if we have the comparison operators |
197 | is_sorted = false; | 197 | is_sorted = false; |
198 | ++used; | 198 | ++used; |
199 | } | 199 | } |
200 | 200 | ||
201 | 201 | ||
202 | //! Clears the array and deletes all allocated memory. | 202 | //! Clears the array and deletes all allocated memory. |
203 | void clear() | 203 | void clear() |
204 | { | 204 | { |
205 | if (free_when_destroyed) | 205 | if (free_when_destroyed) |
206 | { | 206 | { |
207 | for (u32 i=0; i<used; ++i) | 207 | for (u32 i=0; i<used; ++i) |
208 | allocator.destruct(&data[i]); | 208 | allocator.destruct(&data[i]); |
209 | 209 | ||
210 | allocator.deallocate(data); // delete [] data; | 210 | allocator.deallocate(data); // delete [] data; |
211 | } | 211 | } |
212 | data = 0; | 212 | data = 0; |
213 | used = 0; | 213 | used = 0; |
214 | allocated = 0; | 214 | allocated = 0; |
215 | is_sorted = true; | 215 | is_sorted = true; |
216 | } | 216 | } |
217 | 217 | ||
218 | 218 | ||
219 | //! Sets pointer to new array, using this as new workspace. | 219 | //! Sets pointer to new array, using this as new workspace. |
220 | /** Make sure that set_free_when_destroyed is used properly. | 220 | /** Make sure that set_free_when_destroyed is used properly. |
221 | \param newPointer: Pointer to new array of elements. | 221 | \param newPointer: Pointer to new array of elements. |
222 | \param size: Size of the new array. | 222 | \param size: Size of the new array. |
223 | \param _is_sorted Flag which tells whether the new array is already | 223 | \param _is_sorted Flag which tells whether the new array is already |
224 | sorted. | 224 | sorted. |
225 | \param _free_when_destroyed Sets whether the new memory area shall be | 225 | \param _free_when_destroyed Sets whether the new memory area shall be |
226 | freed by the array upon destruction, or if this will be up to the user | 226 | freed by the array upon destruction, or if this will be up to the user |
227 | application. */ | 227 | application. */ |
228 | void set_pointer(T* newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true) | 228 | void set_pointer(T* newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true) |
229 | { | 229 | { |
230 | clear(); | 230 | clear(); |
231 | data = newPointer; | 231 | data = newPointer; |
232 | allocated = size; | 232 | allocated = size; |
233 | used = size; | 233 | used = size; |
234 | is_sorted = _is_sorted; | 234 | is_sorted = _is_sorted; |
235 | free_when_destroyed=_free_when_destroyed; | 235 | free_when_destroyed=_free_when_destroyed; |
236 | } | 236 | } |
237 | 237 | ||
238 | 238 | ||
239 | //! Sets if the array should delete the memory it uses upon destruction. | 239 | //! Sets if the array should delete the memory it uses upon destruction. |
240 | /** Also clear and set_pointer will only delete the (original) memory | 240 | /** Also clear and set_pointer will only delete the (original) memory |
241 | area if this flag is set to true, which is also the default. The | 241 | area if this flag is set to true, which is also the default. The |
242 | methods reallocate, set_used, push_back, push_front, insert, and erase | 242 | methods reallocate, set_used, push_back, push_front, insert, and erase |
243 | will still try to deallocate the original memory, which might cause | 243 | will still try to deallocate the original memory, which might cause |
244 | troubles depending on the intended use of the memory area. | 244 | troubles depending on the intended use of the memory area. |
245 | \param f If true, the array frees the allocated memory in its | 245 | \param f If true, the array frees the allocated memory in its |
246 | destructor, otherwise not. The default is true. */ | 246 | destructor, otherwise not. The default is true. */ |
247 | void set_free_when_destroyed(bool f) | 247 | void set_free_when_destroyed(bool f) |
248 | { | 248 | { |
249 | free_when_destroyed = f; | 249 | free_when_destroyed = f; |
250 | } | 250 | } |
251 | 251 | ||
252 | 252 | ||
253 | //! Sets the size of the array and allocates new elements if necessary. | 253 | //! Sets the size of the array and allocates new elements if necessary. |
254 | /** Please note: This is only secure when using it with simple types, | 254 | /** Please note: This is only secure when using it with simple types, |
255 | because no default constructor will be called for the added elements. | 255 | because no default constructor will be called for the added elements. |
256 | \param usedNow Amount of elements now used. */ | 256 | \param usedNow Amount of elements now used. */ |
257 | void set_used(u32 usedNow) | 257 | void set_used(u32 usedNow) |
258 | { | 258 | { |
259 | if (allocated < usedNow) | 259 | if (allocated < usedNow) |
260 | reallocate(usedNow); | 260 | reallocate(usedNow); |
261 | 261 | ||
262 | used = usedNow; | 262 | used = usedNow; |
263 | } | 263 | } |
264 | 264 | ||
265 | 265 | ||
266 | //! Assignment operator | 266 | //! Assignment operator |
267 | const array<T, TAlloc>& operator=(const array<T, TAlloc>& other) | 267 | const array<T, TAlloc>& operator=(const array<T, TAlloc>& other) |
268 | { | 268 | { |
269 | if (this == &other) | 269 | if (this == &other) |
270 | return *this; | 270 | return *this; |
271 | strategy = other.strategy; | 271 | strategy = other.strategy; |
272 | 272 | ||
273 | if (data) | 273 | if (data) |
274 | clear(); | 274 | clear(); |
275 | 275 | ||
276 | //if (allocated < other.allocated) | 276 | //if (allocated < other.allocated) |
277 | if (other.allocated == 0) | 277 | if (other.allocated == 0) |
278 | data = 0; | 278 | data = 0; |
279 | else | 279 | else |
280 | data = allocator.allocate(other.allocated); // new T[other.allocated]; | 280 | data = allocator.allocate(other.allocated); // new T[other.allocated]; |
281 | 281 | ||
282 | used = other.used; | 282 | used = other.used; |
283 | free_when_destroyed = true; | 283 | free_when_destroyed = true; |
284 | is_sorted = other.is_sorted; | 284 | is_sorted = other.is_sorted; |
285 | allocated = other.allocated; | 285 | allocated = other.allocated; |
286 | 286 | ||
287 | for (u32 i=0; i<other.used; ++i) | 287 | for (u32 i=0; i<other.used; ++i) |
288 | allocator.construct(&data[i], other.data[i]); // data[i] = other.data[i]; | 288 | allocator.construct(&data[i], other.data[i]); // data[i] = other.data[i]; |
289 | 289 | ||
290 | return *this; | 290 | return *this; |
291 | } | 291 | } |
292 | 292 | ||
293 | 293 | ||
294 | //! Equality operator | 294 | //! Equality operator |
295 | bool operator == (const array<T, TAlloc>& other) const | 295 | bool operator == (const array<T, TAlloc>& other) const |
296 | { | 296 | { |
297 | if (used != other.used) | 297 | if (used != other.used) |
298 | return false; | 298 | return false; |
299 | 299 | ||
300 | for (u32 i=0; i<other.used; ++i) | 300 | for (u32 i=0; i<other.used; ++i) |
301 | if (data[i] != other[i]) | 301 | if (data[i] != other[i]) |
302 | return false; | 302 | return false; |
303 | return true; | 303 | return true; |
304 | } | 304 | } |
305 | 305 | ||
306 | 306 | ||
307 | //! Inequality operator | 307 | //! Inequality operator |
308 | bool operator != (const array<T, TAlloc>& other) const | 308 | bool operator != (const array<T, TAlloc>& other) const |
309 | { | 309 | { |
310 | return !(*this==other); | 310 | return !(*this==other); |
311 | } | 311 | } |
312 | 312 | ||
313 | 313 | ||
314 | //! Direct access operator | 314 | //! Direct access operator |
315 | T& operator [](u32 index) | 315 | T& operator [](u32 index) |
316 | { | 316 | { |
317 | _IRR_DEBUG_BREAK_IF(index>=used) // access violation | 317 | _IRR_DEBUG_BREAK_IF(index>=used) // access violation |
318 | 318 | ||
319 | return data[index]; | 319 | return data[index]; |
320 | } | 320 | } |
321 | 321 | ||
322 | 322 | ||
323 | //! Direct const access operator | 323 | //! Direct const access operator |
324 | const T& operator [](u32 index) const | 324 | const T& operator [](u32 index) const |
325 | { | 325 | { |
326 | _IRR_DEBUG_BREAK_IF(index>=used) // access violation | 326 | _IRR_DEBUG_BREAK_IF(index>=used) // access violation |
327 | 327 | ||
328 | return data[index]; | 328 | return data[index]; |
329 | } | 329 | } |
330 | 330 | ||
331 | 331 | ||
332 | //! Gets last element. | 332 | //! Gets last element. |
333 | T& getLast() | 333 | T& getLast() |
334 | { | 334 | { |
335 | _IRR_DEBUG_BREAK_IF(!used) // access violation | 335 | _IRR_DEBUG_BREAK_IF(!used) // access violation |
336 | 336 | ||
337 | return data[used-1]; | 337 | return data[used-1]; |
338 | } | 338 | } |
339 | 339 | ||
340 | 340 | ||
341 | //! Gets last element | 341 | //! Gets last element |
342 | const T& getLast() const | 342 | const T& getLast() const |
343 | { | 343 | { |
344 | _IRR_DEBUG_BREAK_IF(!used) // access violation | 344 | _IRR_DEBUG_BREAK_IF(!used) // access violation |
345 | 345 | ||
346 | return data[used-1]; | 346 | return data[used-1]; |
347 | } | 347 | } |
348 | 348 | ||
349 | 349 | ||
350 | //! Gets a pointer to the array. | 350 | //! Gets a pointer to the array. |
351 | /** \return Pointer to the array. */ | 351 | /** \return Pointer to the array. */ |
352 | T* pointer() | 352 | T* pointer() |
353 | { | 353 | { |
354 | return data; | 354 | return data; |
355 | } | 355 | } |
356 | 356 | ||
357 | 357 | ||
358 | //! Gets a const pointer to the array. | 358 | //! Gets a const pointer to the array. |
359 | /** \return Pointer to the array. */ | 359 | /** \return Pointer to the array. */ |
360 | const T* const_pointer() const | 360 | const T* const_pointer() const |
361 | { | 361 | { |
362 | return data; | 362 | return data; |
363 | } | 363 | } |
364 | 364 | ||
365 | 365 | ||
366 | //! Get number of occupied elements of the array. | 366 | //! Get number of occupied elements of the array. |
367 | /** \return Size of elements in the array which are actually occupied. */ | 367 | /** \return Size of elements in the array which are actually occupied. */ |
368 | u32 size() const | 368 | u32 size() const |
369 | { | 369 | { |
370 | return used; | 370 | return used; |
371 | } | 371 | } |
372 | 372 | ||
373 | 373 | ||
374 | //! Get amount of memory allocated. | 374 | //! Get amount of memory allocated. |
375 | /** \return Amount of memory allocated. The amount of bytes | 375 | /** \return Amount of memory allocated. The amount of bytes |
376 | allocated would be allocated_size() * sizeof(ElementTypeUsed); */ | 376 | allocated would be allocated_size() * sizeof(ElementTypeUsed); */ |
377 | u32 allocated_size() const | 377 | u32 allocated_size() const |
378 | { | 378 | { |
379 | return allocated; | 379 | return allocated; |
380 | } | 380 | } |
381 | 381 | ||
382 | 382 | ||
383 | //! Check if array is empty. | 383 | //! Check if array is empty. |
384 | /** \return True if the array is empty false if not. */ | 384 | /** \return True if the array is empty false if not. */ |
385 | bool empty() const | 385 | bool empty() const |
386 | { | 386 | { |
387 | return used == 0; | 387 | return used == 0; |
388 | } | 388 | } |
389 | 389 | ||
390 | 390 | ||
391 | //! Sorts the array using heapsort. | 391 | //! Sorts the array using heapsort. |
392 | /** There is no additional memory waste and the algorithm performs | 392 | /** There is no additional memory waste and the algorithm performs |
393 | O(n*log n) in worst case. */ | 393 | O(n*log n) in worst case. */ |
394 | void sort() | 394 | void sort() |
395 | { | 395 | { |
396 | if (!is_sorted && used>1) | 396 | if (!is_sorted && used>1) |
397 | heapsort(data, used); | 397 | heapsort(data, used); |
398 | is_sorted = true; | 398 | is_sorted = true; |
399 | } | 399 | } |
400 | 400 | ||
401 | 401 | ||
402 | //! Performs a binary search for an element, returns -1 if not found. | 402 | //! Performs a binary search for an element, returns -1 if not found. |
403 | /** The array will be sorted before the binary search if it is not | 403 | /** The array will be sorted before the binary search if it is not |
404 | already sorted. Caution is advised! Be careful not to call this on | 404 | already sorted. Caution is advised! Be careful not to call this on |
405 | unsorted const arrays, or the slower method will be used. | 405 | unsorted const arrays, or the slower method will be used. |
406 | \param element Element to search for. | 406 | \param element Element to search for. |
407 | \return Position of the searched element if it was found, | 407 | \return Position of the searched element if it was found, |
408 | otherwise -1 is returned. */ | 408 | otherwise -1 is returned. */ |
409 | s32 binary_search(const T& element) | 409 | s32 binary_search(const T& element) |
410 | { | 410 | { |
411 | sort(); | 411 | sort(); |
412 | return binary_search(element, 0, used-1); | 412 | return binary_search(element, 0, used-1); |
413 | } | 413 | } |
414 | 414 | ||
415 | 415 | ||
416 | //! Performs a binary search for an element if possible, returns -1 if not found. | 416 | //! Performs a binary search for an element if possible, returns -1 if not found. |
417 | /** This method is for const arrays and so cannot call sort(), if the array is | 417 | /** This method is for const arrays and so cannot call sort(), if the array is |
418 | not sorted then linear_search will be used instead. Potentially very slow! | 418 | not sorted then linear_search will be used instead. Potentially very slow! |
419 | \param element Element to search for. | 419 | \param element Element to search for. |
420 | \return Position of the searched element if it was found, | 420 | \return Position of the searched element if it was found, |
421 | otherwise -1 is returned. */ | 421 | otherwise -1 is returned. */ |
422 | s32 binary_search(const T& element) const | 422 | s32 binary_search(const T& element) const |
423 | { | 423 | { |
424 | if (is_sorted) | 424 | if (is_sorted) |
425 | return binary_search(element, 0, used-1); | 425 | return binary_search(element, 0, used-1); |
426 | else | 426 | else |
427 | return linear_search(element); | 427 | return linear_search(element); |
428 | } | 428 | } |
429 | 429 | ||
430 | 430 | ||
431 | //! Performs a binary search for an element, returns -1 if not found. | 431 | //! Performs a binary search for an element, returns -1 if not found. |
432 | /** \param element: Element to search for. | 432 | /** \param element: Element to search for. |
433 | \param left First left index | 433 | \param left First left index |
434 | \param right Last right index. | 434 | \param right Last right index. |
435 | \return Position of the searched element if it was found, otherwise -1 | 435 | \return Position of the searched element if it was found, otherwise -1 |
436 | is returned. */ | 436 | is returned. */ |
437 | s32 binary_search(const T& element, s32 left, s32 right) const | 437 | s32 binary_search(const T& element, s32 left, s32 right) const |
438 | { | 438 | { |
439 | if (!used) | 439 | if (!used) |
440 | return -1; | 440 | return -1; |
441 | 441 | ||
442 | s32 m; | 442 | s32 m; |
443 | 443 | ||
444 | do | 444 | do |
445 | { | 445 | { |
446 | m = (left+right)>>1; | 446 | m = (left+right)>>1; |
447 | 447 | ||
448 | if (element < data[m]) | 448 | if (element < data[m]) |
449 | right = m - 1; | 449 | right = m - 1; |
450 | else | 450 | else |
451 | left = m + 1; | 451 | left = m + 1; |
452 | 452 | ||
453 | } while((element < data[m] || data[m] < element) && left<=right); | 453 | } while((element < data[m] || data[m] < element) && left<=right); |
454 | // this last line equals to: | 454 | // this last line equals to: |
455 | // " while((element != array[m]) && left<=right);" | 455 | // " while((element != array[m]) && left<=right);" |
456 | // but we only want to use the '<' operator. | 456 | // but we only want to use the '<' operator. |
457 | // the same in next line, it is "(element == array[m])" | 457 | // the same in next line, it is "(element == array[m])" |
458 | 458 | ||
459 | 459 | ||
460 | if (!(element < data[m]) && !(data[m] < element)) | 460 | if (!(element < data[m]) && !(data[m] < element)) |
461 | return m; | 461 | return m; |
462 | 462 | ||
463 | return -1; | 463 | return -1; |
464 | } | 464 | } |
465 | 465 | ||
466 | 466 | ||
467 | //! Performs a binary search for an element, returns -1 if not found. | 467 | //! Performs a binary search for an element, returns -1 if not found. |
468 | //! it is used for searching a multiset | 468 | //! it is used for searching a multiset |
469 | /** The array will be sorted before the binary search if it is not | 469 | /** The array will be sorted before the binary search if it is not |
470 | already sorted. | 470 | already sorted. |
471 | \param element Element to search for. | 471 | \param element Element to search for. |
472 | \param &last return lastIndex of equal elements | 472 | \param &last return lastIndex of equal elements |
473 | \return Position of the first searched element if it was found, | 473 | \return Position of the first searched element if it was found, |
474 | otherwise -1 is returned. */ | 474 | otherwise -1 is returned. */ |
475 | s32 binary_search_multi(const T& element, s32 &last) | 475 | s32 binary_search_multi(const T& element, s32 &last) |
476 | { | 476 | { |
477 | sort(); | 477 | sort(); |
478 | s32 index = binary_search(element, 0, used-1); | 478 | s32 index = binary_search(element, 0, used-1); |
479 | if ( index < 0 ) | 479 | if ( index < 0 ) |
480 | return index; | 480 | return index; |
481 | 481 | ||
482 | // The search can be somewhere in the middle of the set | 482 | // The search can be somewhere in the middle of the set |
483 | // look linear previous and past the index | 483 | // look linear previous and past the index |
484 | last = index; | 484 | last = index; |
485 | 485 | ||
486 | while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) ) | 486 | while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) ) |
487 | { | 487 | { |
488 | index -= 1; | 488 | index -= 1; |
489 | } | 489 | } |
490 | // look linear up | 490 | // look linear up |
491 | while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) ) | 491 | while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) ) |
492 | { | 492 | { |
493 | last += 1; | 493 | last += 1; |
494 | } | 494 | } |
495 | 495 | ||
496 | return index; | 496 | return index; |
497 | } | 497 | } |
498 | 498 | ||
499 | 499 | ||
500 | //! Finds an element in linear time, which is very slow. | 500 | //! Finds an element in linear time, which is very slow. |
501 | /** Use binary_search for faster finding. Only works if ==operator is | 501 | /** Use binary_search for faster finding. Only works if ==operator is |
502 | implemented. | 502 | implemented. |
503 | \param element Element to search for. | 503 | \param element Element to search for. |
504 | \return Position of the searched element if it was found, otherwise -1 | 504 | \return Position of the searched element if it was found, otherwise -1 |
505 | is returned. */ | 505 | is returned. */ |
506 | s32 linear_search(const T& element) const | 506 | s32 linear_search(const T& element) const |
507 | { | 507 | { |
508 | for (u32 i=0; i<used; ++i) | 508 | for (u32 i=0; i<used; ++i) |
509 | if (element == data[i]) | 509 | if (element == data[i]) |
510 | return (s32)i; | 510 | return (s32)i; |
511 | 511 | ||
512 | return -1; | 512 | return -1; |
513 | } | 513 | } |
514 | 514 | ||
515 | 515 | ||
516 | //! Finds an element in linear time, which is very slow. | 516 | //! Finds an element in linear time, which is very slow. |
517 | /** Use binary_search for faster finding. Only works if ==operator is | 517 | /** Use binary_search for faster finding. Only works if ==operator is |
518 | implemented. | 518 | implemented. |
519 | \param element: Element to search for. | 519 | \param element: Element to search for. |
520 | \return Position of the searched element if it was found, otherwise -1 | 520 | \return Position of the searched element if it was found, otherwise -1 |
521 | is returned. */ | 521 | is returned. */ |
522 | s32 linear_reverse_search(const T& element) const | 522 | s32 linear_reverse_search(const T& element) const |
523 | { | 523 | { |
524 | for (s32 i=used-1; i>=0; --i) | 524 | for (s32 i=used-1; i>=0; --i) |
525 | if (data[i] == element) | 525 | if (data[i] == element) |
526 | return i; | 526 | return i; |
527 | 527 | ||
528 | return -1; | 528 | return -1; |
529 | } | 529 | } |
530 | 530 | ||
531 | 531 | ||
532 | //! Erases an element from the array. | 532 | //! Erases an element from the array. |
533 | /** May be slow, because all elements following after the erased | 533 | /** May be slow, because all elements following after the erased |
534 | element have to be copied. | 534 | element have to be copied. |
535 | \param index: Index of element to be erased. */ | 535 | \param index: Index of element to be erased. */ |
536 | void erase(u32 index) | 536 | void erase(u32 index) |
537 | { | 537 | { |
538 | _IRR_DEBUG_BREAK_IF(index>=used) // access violation | 538 | _IRR_DEBUG_BREAK_IF(index>=used) // access violation |
539 | 539 | ||
540 | for (u32 i=index+1; i<used; ++i) | 540 | for (u32 i=index+1; i<used; ++i) |
541 | { | 541 | { |
542 | allocator.destruct(&data[i-1]); | 542 | allocator.destruct(&data[i-1]); |
543 | allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i]; | 543 | allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i]; |
544 | } | 544 | } |
545 | 545 | ||
546 | allocator.destruct(&data[used-1]); | 546 | allocator.destruct(&data[used-1]); |
547 | 547 | ||
548 | --used; | 548 | --used; |
549 | } | 549 | } |
550 | 550 | ||
551 | 551 | ||
552 | //! Erases some elements from the array. | 552 | //! Erases some elements from the array. |
553 | /** May be slow, because all elements following after the erased | 553 | /** May be slow, because all elements following after the erased |
554 | element have to be copied. | 554 | element have to be copied. |
555 | \param index: Index of the first element to be erased. | 555 | \param index: Index of the first element to be erased. |
556 | \param count: Amount of elements to be erased. */ | 556 | \param count: Amount of elements to be erased. */ |
557 | void erase(u32 index, s32 count) | 557 | void erase(u32 index, s32 count) |
558 | { | 558 | { |
559 | if (index>=used || count<1) | 559 | if (index>=used || count<1) |
560 | return; | 560 | return; |
561 | if (index+count>used) | 561 | if (index+count>used) |
562 | count = used-index; | 562 | count = used-index; |
563 | 563 | ||
564 | u32 i; | 564 | u32 i; |
565 | for (i=index; i<index+count; ++i) | 565 | for (i=index; i<index+count; ++i) |
566 | allocator.destruct(&data[i]); | 566 | allocator.destruct(&data[i]); |
567 | 567 | ||
568 | for (i=index+count; i<used; ++i) | 568 | for (i=index+count; i<used; ++i) |
569 | { | 569 | { |
570 | if (i-count >= index+count) // not already destructed before loop | 570 | if (i-count >= index+count) // not already destructed before loop |
571 | allocator.destruct(&data[i-count]); | 571 | allocator.destruct(&data[i-count]); |
572 | 572 | ||
573 | allocator.construct(&data[i-count], data[i]); // data[i-count] = data[i]; | 573 | allocator.construct(&data[i-count], data[i]); // data[i-count] = data[i]; |
574 | 574 | ||
575 | if (i >= used-count) // those which are not overwritten | 575 | if (i >= used-count) // those which are not overwritten |
576 | allocator.destruct(&data[i]); | 576 | allocator.destruct(&data[i]); |
577 | } | 577 | } |
578 | 578 | ||
579 | used-= count; | 579 | used-= count; |
580 | } | 580 | } |
581 | 581 | ||
582 | 582 | ||
583 | //! Sets if the array is sorted | 583 | //! Sets if the array is sorted |
584 | void set_sorted(bool _is_sorted) | 584 | void set_sorted(bool _is_sorted) |
585 | { | 585 | { |
586 | is_sorted = _is_sorted; | 586 | is_sorted = _is_sorted; |
587 | } | 587 | } |
588 | 588 | ||
589 | 589 | ||
590 | //! Swap the content of this array container with the content of another array | 590 | //! Swap the content of this array container with the content of another array |
591 | /** Afterwards this object will contain the content of the other object and the other | 591 | /** Afterwards this object will contain the content of the other object and the other |
592 | object will contain the content of this object. | 592 | object will contain the content of this object. |
593 | \param other Swap content with this object */ | 593 | \param other Swap content with this object */ |
594 | void swap(array<T, TAlloc>& other) | 594 | void swap(array<T, TAlloc>& other) |
595 | { | 595 | { |
596 | core::swap(data, other.data); | 596 | core::swap(data, other.data); |
597 | core::swap(allocated, other.allocated); | 597 | core::swap(allocated, other.allocated); |
598 | core::swap(used, other.used); | 598 | core::swap(used, other.used); |
599 | core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation | 599 | core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation |
600 | eAllocStrategy helper_strategy(strategy); // can't use core::swap with bitfields | 600 | eAllocStrategy helper_strategy(strategy); // can't use core::swap with bitfields |
601 | strategy = other.strategy; | 601 | strategy = other.strategy; |
602 | other.strategy = helper_strategy; | 602 | other.strategy = helper_strategy; |
603 | bool helper_free_when_destroyed(free_when_destroyed); | 603 | bool helper_free_when_destroyed(free_when_destroyed); |
604 | free_when_destroyed = other.free_when_destroyed; | 604 | free_when_destroyed = other.free_when_destroyed; |
605 | other.free_when_destroyed = helper_free_when_destroyed; | 605 | other.free_when_destroyed = helper_free_when_destroyed; |
606 | bool helper_is_sorted(is_sorted); | 606 | bool helper_is_sorted(is_sorted); |
607 | is_sorted = other.is_sorted; | 607 | is_sorted = other.is_sorted; |
608 | other.is_sorted = helper_is_sorted; | 608 | other.is_sorted = helper_is_sorted; |
609 | } | 609 | } |
610 | 610 | ||
611 | 611 | ||
612 | private: | 612 | private: |
613 | T* data; | 613 | T* data; |
614 | u32 allocated; | 614 | u32 allocated; |
615 | u32 used; | 615 | u32 used; |
616 | TAlloc allocator; | 616 | TAlloc allocator; |
617 | eAllocStrategy strategy:4; | 617 | eAllocStrategy strategy:4; |
618 | bool free_when_destroyed:1; | 618 | bool free_when_destroyed:1; |
619 | bool is_sorted:1; | 619 | bool is_sorted:1; |
620 | }; | 620 | }; |
621 | 621 | ||
622 | 622 | ||
623 | } // end namespace core | 623 | } // end namespace core |
624 | } // end namespace irr | 624 | } // end namespace irr |
625 | 625 | ||
626 | #endif | 626 | #endif |
627 | 627 | ||