vrshoot
view libs/assimp/irrXML/irrArray.h @ 0:b2f14e535253
initial commit
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Sat, 01 Feb 2014 19:58:19 +0200 |
| parents | |
| children |
line source
1 // Copyright (C) 2002-2005 Nikolaus Gebhardt
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
5 #ifndef __IRR_ARRAY_H_INCLUDED__
6 #define __IRR_ARRAY_H_INCLUDED__
8 #include "irrTypes.h"
9 #include "heapsort.h"
11 namespace irr
12 {
13 namespace core
14 {
16 //! Self reallocating template array (like stl vector) with additional features.
17 /** Some features are: Heap sorting, binary search methods, easier debugging.
18 */
19 template <class T>
20 class array
21 {
23 public:
25 array()
26 : data(0), allocated(0), used(0),
27 free_when_destroyed(true), is_sorted(true)
28 {
29 }
31 //! Constructs a array and allocates an initial chunk of memory.
32 //! \param start_count: Amount of elements to allocate.
33 array(u32 start_count)
34 : data(0), allocated(0), used(0),
35 free_when_destroyed(true), is_sorted(true)
36 {
37 reallocate(start_count);
38 }
41 //! Copy constructor
42 array(const array<T>& other)
43 : data(0)
44 {
45 *this = other;
46 }
50 //! Destructor. Frees allocated memory, if set_free_when_destroyed
51 //! was not set to false by the user before.
52 ~array()
53 {
54 if (free_when_destroyed)
55 delete [] data;
56 }
60 //! Reallocates the array, make it bigger or smaller.
61 //! \param new_size: New size of array.
62 void reallocate(u32 new_size)
63 {
64 T* old_data = data;
66 data = new T[new_size];
67 allocated = new_size;
69 s32 end = used < new_size ? used : new_size;
70 for (s32 i=0; i<end; ++i)
71 data[i] = old_data[i];
73 if (allocated < used)
74 used = allocated;
76 delete [] old_data;
77 }
79 //! Adds an element at back of array. If the array is to small to
80 //! add this new element, the array is made bigger.
81 //! \param element: Element to add at the back of the array.
82 void push_back(const T& element)
83 {
84 if (used + 1 > allocated)
85 {
86 // reallocate(used * 2 +1);
87 // this doesn't work if the element is in the same array. So
88 // we'll copy the element first to be sure we'll get no data
89 // corruption
91 T e;
92 e = element; // copy element
93 reallocate(used * 2 +1); // increase data block
94 data[used++] = e; // push_back
95 is_sorted = false;
96 return;
97 }
99 data[used++] = element;
100 is_sorted = false;
101 }
104 //! Adds an element at the front of the array. If the array is to small to
105 //! add this new element, the array is made bigger. Please note that this
106 //! is slow, because the whole array needs to be copied for this.
107 //! \param element: Element to add at the back of the array.
108 void push_front(const T& element)
109 {
110 if (used + 1 > allocated)
111 reallocate(used * 2 +1);
113 for (int i=(int)used; i>0; --i)
114 data[i] = data[i-1];
116 data[0] = element;
117 is_sorted = false;
118 ++used;
119 }
122 //! Insert item into array at specified position. Please use this
123 //! only if you know what you are doing (possible performance loss).
124 //! The preferred method of adding elements should be push_back().
125 //! \param element: Element to be inserted
126 //! \param index: Where position to insert the new element.
127 void insert(const T& element, u32 index=0)
128 {
129 _IRR_DEBUG_BREAK_IF(index>used) // access violation
131 if (used + 1 > allocated)
132 reallocate(used * 2 +1);
134 for (u32 i=used++; i>index; i--)
135 data[i] = data[i-1];
137 data[index] = element;
138 is_sorted = false;
139 }
144 //! Clears the array and deletes all allocated memory.
145 void clear()
146 {
147 delete [] data;
148 data = 0;
149 used = 0;
150 allocated = 0;
151 is_sorted = true;
152 }
156 //! Sets pointer to new array, using this as new workspace.
157 //! \param newPointer: Pointer to new array of elements.
158 //! \param size: Size of the new array.
159 void set_pointer(T* newPointer, u32 size)
160 {
161 delete [] data;
162 data = newPointer;
163 allocated = size;
164 used = size;
165 is_sorted = false;
166 }
170 //! Sets if the array should delete the memory it used.
171 //! \param f: If true, the array frees the allocated memory in its
172 //! destructor, otherwise not. The default is true.
173 void set_free_when_destroyed(bool f)
174 {
175 free_when_destroyed = f;
176 }
180 //! Sets the size of the array.
181 //! \param usedNow: Amount of elements now used.
182 void set_used(u32 usedNow)
183 {
184 if (allocated < usedNow)
185 reallocate(usedNow);
187 used = usedNow;
188 }
192 //! Assignement operator
193 void operator=(const array<T>& other)
194 {
195 if (data)
196 delete [] data;
198 //if (allocated < other.allocated)
199 if (other.allocated == 0)
200 data = 0;
201 else
202 data = new T[other.allocated];
204 used = other.used;
205 free_when_destroyed = other.free_when_destroyed;
206 is_sorted = other.is_sorted;
207 allocated = other.allocated;
209 for (u32 i=0; i<other.used; ++i)
210 data[i] = other.data[i];
211 }
214 //! Direct access operator
215 T& operator [](u32 index)
216 {
217 _IRR_DEBUG_BREAK_IF(index>=used) // access violation
219 return data[index];
220 }
224 //! Direct access operator
225 const T& operator [](u32 index) const
226 {
227 _IRR_DEBUG_BREAK_IF(index>=used) // access violation
229 return data[index];
230 }
232 //! Gets last frame
233 const T& getLast() const
234 {
235 _IRR_DEBUG_BREAK_IF(!used) // access violation
237 return data[used-1];
238 }
240 //! Gets last frame
241 T& getLast()
242 {
243 _IRR_DEBUG_BREAK_IF(!used) // access violation
245 return data[used-1];
246 }
249 //! Returns a pointer to the array.
250 //! \return Pointer to the array.
251 T* pointer()
252 {
253 return data;
254 }
258 //! Returns a const pointer to the array.
259 //! \return Pointer to the array.
260 const T* const_pointer() const
261 {
262 return data;
263 }
267 //! Returns size of used array.
268 //! \return Size of elements in the array.
269 u32 size() const
270 {
271 return used;
272 }
276 //! Returns amount memory allocated.
277 //! \return Returns amount of memory allocated. The amount of bytes
278 //! allocated would be allocated_size() * sizeof(ElementsUsed);
279 u32 allocated_size() const
280 {
281 return allocated;
282 }
286 //! Returns true if array is empty
287 //! \return True if the array is empty, false if not.
288 bool empty() const
289 {
290 return used == 0;
291 }
295 //! Sorts the array using heapsort. There is no additional memory waste and
296 //! the algorithm performs (O) n log n in worst case.
297 void sort()
298 {
299 if (is_sorted || used<2)
300 return;
302 heapsort(data, used);
303 is_sorted = true;
304 }
308 //! Performs a binary search for an element, returns -1 if not found.
309 //! The array will be sorted before the binary search if it is not
310 //! already sorted.
311 //! \param element: Element to search for.
312 //! \return Returns position of the searched element if it was found,
313 //! otherwise -1 is returned.
314 s32 binary_search(const T& element)
315 {
316 return binary_search(element, 0, used-1);
317 }
321 //! Performs a binary search for an element, returns -1 if not found.
322 //! The array will be sorted before the binary search if it is not
323 //! already sorted.
324 //! \param element: Element to search for.
325 //! \param left: First left index
326 //! \param right: Last right index.
327 //! \return Returns position of the searched element if it was found,
328 //! otherwise -1 is returned.
329 s32 binary_search(const T& element, s32 left, s32 right)
330 {
331 if (!used)
332 return -1;
334 sort();
336 s32 m;
338 do
339 {
340 m = (left+right)>>1;
342 if (element < data[m])
343 right = m - 1;
344 else
345 left = m + 1;
347 } while((element < data[m] || data[m] < element) && left<=right);
349 // this last line equals to:
350 // " while((element != array[m]) && left<=right);"
351 // but we only want to use the '<' operator.
352 // the same in next line, it is "(element == array[m])"
354 if (!(element < data[m]) && !(data[m] < element))
355 return m;
357 return -1;
358 }
361 //! Finds an element in linear time, which is very slow. Use
362 //! binary_search for faster finding. Only works if =operator is implemented.
363 //! \param element: Element to search for.
364 //! \return Returns position of the searched element if it was found,
365 //! otherwise -1 is returned.
366 s32 linear_search(T& element)
367 {
368 for (u32 i=0; i<used; ++i)
369 if (!(element < data[i]) && !(data[i] < element))
370 return (s32)i;
372 return -1;
373 }
376 //! Finds an element in linear time, which is very slow. Use
377 //! binary_search for faster finding. Only works if =operator is implemented.
378 //! \param element: Element to search for.
379 //! \return Returns position of the searched element if it was found,
380 //! otherwise -1 is returned.
381 s32 linear_reverse_search(T& element)
382 {
383 for (s32 i=used-1; i>=0; --i)
384 if (data[i] == element)
385 return (s32)i;
387 return -1;
388 }
392 //! Erases an element from the array. May be slow, because all elements
393 //! following after the erased element have to be copied.
394 //! \param index: Index of element to be erased.
395 void erase(u32 index)
396 {
397 _IRR_DEBUG_BREAK_IF(index>=used || index<0) // access violation
399 for (u32 i=index+1; i<used; ++i)
400 data[i-1] = data[i];
402 --used;
403 }
406 //! Erases some elements from the array. may be slow, because all elements
407 //! following after the erased element have to be copied.
408 //! \param index: Index of the first element to be erased.
409 //! \param count: Amount of elements to be erased.
410 void erase(u32 index, s32 count)
411 {
412 _IRR_DEBUG_BREAK_IF(index>=used || index<0 || count<1 || index+count>used) // access violation
414 for (u32 i=index+count; i<used; ++i)
415 data[i-count] = data[i];
417 used-= count;
418 }
421 //! Sets if the array is sorted
422 void set_sorted(bool _is_sorted)
423 {
424 is_sorted = _is_sorted;
425 }
428 private:
430 T* data;
431 u32 allocated;
432 u32 used;
433 bool free_when_destroyed;
434 bool is_sorted;
435 };
438 } // end namespace core
439 } // end namespace irr
443 #endif