1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/assimp/irrXML/irrArray.h	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,444 @@
     1.4 +// Copyright (C) 2002-2005 Nikolaus Gebhardt
     1.5 +// This file is part of the "Irrlicht Engine" and the "irrXML" project.
     1.6 +// For conditions of distribution and use, see copyright notice in irrlicht.h and irrXML.h
     1.7 +
     1.8 +#ifndef __IRR_ARRAY_H_INCLUDED__
     1.9 +#define __IRR_ARRAY_H_INCLUDED__
    1.10 +
    1.11 +#include "irrTypes.h"
    1.12 +#include "heapsort.h"
    1.13 +
    1.14 +namespace irr
    1.15 +{
    1.16 +namespace core
    1.17 +{
    1.18 +
    1.19 +//!	Self reallocating template array (like stl vector) with additional features.
    1.20 +/** Some features are: Heap sorting, binary search methods, easier debugging.
    1.21 +*/
    1.22 +template <class T>
    1.23 +class array
    1.24 +{
    1.25 +
    1.26 +public:
    1.27 +
    1.28 +	array()
    1.29 +		: data(0), allocated(0), used(0),
    1.30 +			free_when_destroyed(true), is_sorted(true)
    1.31 +	{
    1.32 +	}
    1.33 +
    1.34 +	//! Constructs a array and allocates an initial chunk of memory.
    1.35 +	//! \param start_count: Amount of elements to allocate.
    1.36 +	array(u32 start_count)
    1.37 +		: data(0), allocated(0), used(0),
    1.38 +			free_when_destroyed(true),	is_sorted(true)
    1.39 +	{
    1.40 +		reallocate(start_count);
    1.41 +	}
    1.42 +
    1.43 +
    1.44 +	//! Copy constructor
    1.45 +	array(const array<T>& other)
    1.46 +		: data(0)
    1.47 +	{
    1.48 +		*this = other;
    1.49 +	}
    1.50 +
    1.51 +
    1.52 +
    1.53 +	//! Destructor. Frees allocated memory, if set_free_when_destroyed
    1.54 +	//! was not set to false by the user before.
    1.55 +	~array()
    1.56 +	{
    1.57 +		if (free_when_destroyed)
    1.58 +			delete [] data;
    1.59 +	}
    1.60 +
    1.61 +
    1.62 +
    1.63 +	//! Reallocates the array, make it bigger or smaller.
    1.64 +	//! \param new_size: New size of array.
    1.65 +	void reallocate(u32 new_size)
    1.66 +	{
    1.67 +		T* old_data = data;
    1.68 +
    1.69 +		data = new T[new_size];
    1.70 +		allocated = new_size;
    1.71 +		
    1.72 +		s32 end = used < new_size ? used : new_size;
    1.73 +		for (s32 i=0; i<end; ++i)
    1.74 +			data[i] = old_data[i];
    1.75 +
    1.76 +		if (allocated < used)
    1.77 +			used = allocated;
    1.78 +		
    1.79 +		delete [] old_data;
    1.80 +	}
    1.81 +
    1.82 +	//! Adds an element at back of array. If the array is to small to 
    1.83 +	//! add this new element, the array is made bigger.
    1.84 +	//! \param element: Element to add at the back of the array.
    1.85 +	void push_back(const T& element)
    1.86 +	{
    1.87 +		if (used + 1 > allocated)
    1.88 +		{
    1.89 +			// reallocate(used * 2 +1);
    1.90 +			// this doesn't work if the element is in the same array. So
    1.91 +			// we'll copy the element first to be sure we'll get no data
    1.92 +			// corruption
    1.93 +
    1.94 +			T e;
    1.95 +			e = element;           // copy element
    1.96 +			reallocate(used * 2 +1); // increase data block
    1.97 +			data[used++] = e;        // push_back
    1.98 +			is_sorted = false; 
    1.99 +			return;
   1.100 +		}
   1.101 +
   1.102 +		data[used++] = element;
   1.103 +		is_sorted = false;
   1.104 +	}
   1.105 +
   1.106 +
   1.107 +	//! Adds an element at the front of the array. If the array is to small to 
   1.108 +	//! add this new element, the array is made bigger. Please note that this
   1.109 +	//! is slow, because the whole array needs to be copied for this.
   1.110 +	//! \param element: Element to add at the back of the array.
   1.111 +	void push_front(const T& element)
   1.112 +	{
   1.113 +		if (used + 1 > allocated)
   1.114 +			reallocate(used * 2 +1);
   1.115 +
   1.116 +		for (int i=(int)used; i>0; --i)
   1.117 +			data[i] = data[i-1];
   1.118 +
   1.119 +		data[0] = element;
   1.120 +		is_sorted = false;
   1.121 +		++used;
   1.122 +	}
   1.123 +
   1.124 +	
   1.125 +	//! Insert item into array at specified position. Please use this
   1.126 +	//! only if you know what you are doing (possible performance loss). 
   1.127 +	//! The preferred method of adding elements should be push_back().
   1.128 +	//! \param element: Element to be inserted
   1.129 +	//! \param index: Where position to insert the new element.
   1.130 +	void insert(const T& element, u32 index=0) 
   1.131 +	{
   1.132 +		_IRR_DEBUG_BREAK_IF(index>used) // access violation
   1.133 +
   1.134 +		if (used + 1 > allocated)
   1.135 +			reallocate(used * 2 +1);
   1.136 +
   1.137 +		for (u32 i=used++; i>index; i--) 
   1.138 +			data[i] = data[i-1];
   1.139 +
   1.140 +		data[index] = element;
   1.141 +		is_sorted = false;
   1.142 +	}
   1.143 +
   1.144 +
   1.145 +
   1.146 +
   1.147 +	//! Clears the array and deletes all allocated memory.
   1.148 +	void clear()
   1.149 +	{
   1.150 +		delete [] data;
   1.151 +		data = 0;
   1.152 +		used = 0;
   1.153 +		allocated = 0;
   1.154 +		is_sorted = true;
   1.155 +	}
   1.156 +
   1.157 +
   1.158 +
   1.159 +	//! Sets pointer to new array, using this as new workspace.
   1.160 +	//! \param newPointer: Pointer to new array of elements.
   1.161 +	//! \param size: Size of the new array.
   1.162 +	void set_pointer(T* newPointer, u32 size)
   1.163 +	{
   1.164 +		delete [] data;
   1.165 +		data = newPointer;
   1.166 +		allocated = size;
   1.167 +		used = size;
   1.168 +		is_sorted = false;
   1.169 +	}
   1.170 +
   1.171 +
   1.172 +
   1.173 +	//! Sets if the array should delete the memory it used.
   1.174 +	//! \param f: If true, the array frees the allocated memory in its
   1.175 +	//! destructor, otherwise not. The default is true.
   1.176 +	void set_free_when_destroyed(bool f)
   1.177 +	{
   1.178 +		free_when_destroyed = f;
   1.179 +	}
   1.180 +
   1.181 +
   1.182 +
   1.183 +	//! Sets the size of the array.
   1.184 +	//! \param usedNow: Amount of elements now used.
   1.185 +	void set_used(u32 usedNow)
   1.186 +	{
   1.187 +		if (allocated < usedNow)
   1.188 +			reallocate(usedNow);
   1.189 +
   1.190 +		used = usedNow;
   1.191 +	}
   1.192 +
   1.193 +
   1.194 +
   1.195 +	//! Assignement operator
   1.196 +	void operator=(const array<T>& other)
   1.197 +	{
   1.198 +		if (data)
   1.199 +			delete [] data;
   1.200 +
   1.201 +		//if (allocated < other.allocated)
   1.202 +		if (other.allocated == 0)
   1.203 +			data = 0;
   1.204 +		else
   1.205 +			data = new T[other.allocated];
   1.206 +
   1.207 +		used = other.used;
   1.208 +		free_when_destroyed = other.free_when_destroyed;
   1.209 +		is_sorted = other.is_sorted;
   1.210 +		allocated = other.allocated;
   1.211 +
   1.212 +		for (u32 i=0; i<other.used; ++i)
   1.213 +			data[i] = other.data[i];
   1.214 +	}
   1.215 +
   1.216 +
   1.217 +	//! Direct access operator
   1.218 +	T& operator [](u32 index)
   1.219 +	{
   1.220 +		_IRR_DEBUG_BREAK_IF(index>=used) // access violation
   1.221 +
   1.222 +		return data[index];
   1.223 +	}
   1.224 +
   1.225 +
   1.226 +
   1.227 +	//! Direct access operator
   1.228 +	const T& operator [](u32 index) const
   1.229 +	{
   1.230 +		_IRR_DEBUG_BREAK_IF(index>=used) // access violation
   1.231 +
   1.232 +		return data[index];
   1.233 +	}
   1.234 +
   1.235 +    //! Gets last frame
   1.236 +	const T& getLast() const
   1.237 +	{
   1.238 +		_IRR_DEBUG_BREAK_IF(!used) // access violation
   1.239 +
   1.240 +		return data[used-1];
   1.241 +	}
   1.242 +
   1.243 +    //! Gets last frame
   1.244 +	T& getLast()
   1.245 +	{
   1.246 +		_IRR_DEBUG_BREAK_IF(!used) // access violation
   1.247 +
   1.248 +		return data[used-1];
   1.249 +	}
   1.250 +    
   1.251 +
   1.252 +	//! Returns a pointer to the array.
   1.253 +	//! \return Pointer to the array.
   1.254 +	T* pointer()
   1.255 +	{
   1.256 +		return data;
   1.257 +	}
   1.258 +
   1.259 +
   1.260 +
   1.261 +	//! Returns a const pointer to the array.
   1.262 +	//! \return Pointer to the array.
   1.263 +	const T* const_pointer() const
   1.264 +	{
   1.265 +		return data;
   1.266 +	}
   1.267 +
   1.268 +
   1.269 +
   1.270 +	//! Returns size of used array.
   1.271 +	//! \return Size of elements in the array.
   1.272 +	u32 size() const
   1.273 +	{
   1.274 +		return used;
   1.275 +	}
   1.276 +
   1.277 +
   1.278 +
   1.279 +	//! Returns amount memory allocated.
   1.280 +	//! \return Returns amount of memory allocated. The amount of bytes
   1.281 +	//! allocated would  be allocated_size() * sizeof(ElementsUsed);
   1.282 +	u32 allocated_size() const
   1.283 +	{
   1.284 +		return allocated;
   1.285 +	}
   1.286 +
   1.287 +
   1.288 +
   1.289 +	//! Returns true if array is empty
   1.290 +	//! \return True if the array is empty, false if not.
   1.291 +	bool empty() const
   1.292 +	{
   1.293 +		return used == 0;
   1.294 +	}
   1.295 +
   1.296 +
   1.297 +
   1.298 +	//! Sorts the array using heapsort. There is no additional memory waste and
   1.299 +	//! the algorithm performs (O) n log n in worst case.
   1.300 +	void sort()
   1.301 +	{
   1.302 +		if (is_sorted || used<2)
   1.303 +			return;
   1.304 +
   1.305 +		heapsort(data, used);
   1.306 +		is_sorted = true;
   1.307 +	}
   1.308 +
   1.309 +
   1.310 +
   1.311 +	//! Performs a binary search for an element, returns -1 if not found.
   1.312 +	//! The array will be sorted before the binary search if it is not
   1.313 +	//! already sorted.
   1.314 +	//! \param element: Element to search for.
   1.315 +	//! \return Returns position of the searched element if it was found,
   1.316 +	//! otherwise -1 is returned.
   1.317 +	s32 binary_search(const T& element)
   1.318 +	{
   1.319 +		return binary_search(element, 0, used-1);
   1.320 +	}
   1.321 +
   1.322 +
   1.323 +
   1.324 +	//! Performs a binary search for an element, returns -1 if not found.
   1.325 +	//! The array will be sorted before the binary search if it is not
   1.326 +	//! already sorted.
   1.327 +	//! \param element: Element to search for.
   1.328 +	//! \param left: First left index
   1.329 +	//! \param right: Last right index.
   1.330 +	//! \return Returns position of the searched element if it was found,
   1.331 +	//! otherwise -1 is returned.
   1.332 +	s32 binary_search(const T& element, s32 left, s32 right)
   1.333 +	{
   1.334 +		if (!used)
   1.335 +			return -1;
   1.336 +
   1.337 +		sort();
   1.338 +
   1.339 +		s32 m;
   1.340 +
   1.341 +		do
   1.342 +		{
   1.343 +			m = (left+right)>>1;
   1.344 +
   1.345 +			if (element < data[m])
   1.346 +				right = m - 1;
   1.347 +			else
   1.348 +				left = m + 1;
   1.349 +
   1.350 +		} while((element < data[m] || data[m] < element) && left<=right);
   1.351 +
   1.352 +		// this last line equals to:
   1.353 +		// " while((element != array[m]) && left<=right);"
   1.354 +		// but we only want to use the '<' operator.
   1.355 +		// the same in next line, it is "(element == array[m])"
   1.356 +
   1.357 +		if (!(element < data[m]) && !(data[m] < element))
   1.358 +			return m;
   1.359 +
   1.360 +		return -1;
   1.361 +	}
   1.362 +
   1.363 +
   1.364 +	//! Finds an element in linear time, which is very slow. Use
   1.365 +	//! binary_search for faster finding. Only works if =operator is implemented.
   1.366 +	//! \param element: Element to search for.
   1.367 +	//! \return Returns position of the searched element if it was found,
   1.368 +	//! otherwise -1 is returned.
   1.369 +	s32 linear_search(T& element)
   1.370 +	{
   1.371 +		for (u32 i=0; i<used; ++i)
   1.372 +			if (!(element < data[i]) && !(data[i] < element))
   1.373 +				return (s32)i;
   1.374 +
   1.375 +		return -1;
   1.376 +	}
   1.377 +
   1.378 +
   1.379 +	//! Finds an element in linear time, which is very slow. Use
   1.380 +	//! binary_search for faster finding. Only works if =operator is implemented.
   1.381 +	//! \param element: Element to search for.
   1.382 +	//! \return Returns position of the searched element if it was found,
   1.383 +	//! otherwise -1 is returned.
   1.384 +	s32 linear_reverse_search(T& element)
   1.385 +	{
   1.386 +		for (s32 i=used-1; i>=0; --i)
   1.387 +			if (data[i] == element)
   1.388 +				return (s32)i;
   1.389 +
   1.390 +		return -1;
   1.391 +	}
   1.392 +
   1.393 +
   1.394 +
   1.395 +	//! Erases an element from the array. May be slow, because all elements 
   1.396 +	//! following after the erased element have to be copied.
   1.397 +	//! \param index: Index of element to be erased.
   1.398 +	void erase(u32 index)
   1.399 +	{
   1.400 +		_IRR_DEBUG_BREAK_IF(index>=used || index<0) // access violation
   1.401 +
   1.402 +		for (u32 i=index+1; i<used; ++i)
   1.403 +			data[i-1] = data[i];
   1.404 +
   1.405 +		--used;
   1.406 +	}
   1.407 +
   1.408 +
   1.409 +	//! Erases some elements from the array. may be slow, because all elements 
   1.410 +	//! following after the erased element have to be copied.
   1.411 +	//! \param index: Index of the first element to be erased.
   1.412 +	//! \param count: Amount of elements to be erased.
   1.413 +	void erase(u32 index, s32 count)
   1.414 +	{
   1.415 +		_IRR_DEBUG_BREAK_IF(index>=used || index<0 || count<1 || index+count>used) // access violation
   1.416 +
   1.417 +		for (u32 i=index+count; i<used; ++i)
   1.418 +			data[i-count] = data[i];
   1.419 +
   1.420 +		used-= count;
   1.421 +	}
   1.422 +
   1.423 +
   1.424 +	//! Sets if the array is sorted
   1.425 +	void set_sorted(bool _is_sorted)
   1.426 +	{
   1.427 +		is_sorted = _is_sorted;
   1.428 +	}
   1.429 +
   1.430 +			
   1.431 +	private:
   1.432 +
   1.433 +		T* data;
   1.434 +		u32 allocated;
   1.435 +		u32 used;
   1.436 +		bool free_when_destroyed;
   1.437 +		bool is_sorted;
   1.438 +};
   1.439 +
   1.440 +
   1.441 +} // end namespace core
   1.442 +} // end namespace irr
   1.443 +
   1.444 +
   1.445 +
   1.446 +#endif
   1.447 +