aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/irrlicht-1.8/include/irrArray.h
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/irrlicht-1.8/include/irrArray.h')
-rw-r--r--libraries/irrlicht-1.8/include/irrArray.h1254
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
13namespace irr 13namespace irr
14{ 14{
15namespace core 15namespace 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*/
21template <class T, typename TAlloc = irrAllocator<T> > 21template <class T, typename TAlloc = irrAllocator<T> >
22class array 22class array
23{ 23{
24 24
25public: 25public:
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
612private: 612private:
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
generated by cgit v1.1 at 2024-07-11 18:58:14 +0000