qt-everywhere-src-5.15.1/qt3d/src/3rdparty/assimp/contrib/irrXML/irrArray.h - orbit - Git at Google

 // Copyright (C) 2002-2005 Nikolaus Gebhardt
 // This file is part of the "Irrlicht Engine" and the "irrXML" project.
 // For conditions of distribution and use, see copyright notice in irrlicht.h and irrXML.h

 #ifndef __IRR_ARRAY_H_INCLUDED__
 #define __IRR_ARRAY_H_INCLUDED__

 #include "irrTypes.h"
 #include "heapsort.h"

 namespace irr
 {
 namespace core
 {

 //!	Self reallocating template array (like stl vector) with additional features.
 /** Some features are: Heap sorting, binary search methods, easier debugging.
 */
 template <class T>
 class array
 {

 public:

 	array()
 		: data(0), allocated(0), used(0),
 			free_when_destroyed(true), is_sorted(true)
 	{
 	}

 	//! Constructs a array and allocates an initial chunk of memory.
 	//! \param start_count: Amount of elements to allocate.
 	array(u32 start_count)
 		: data(0), allocated(0), used(0),
 			free_when_destroyed(true),	is_sorted(true)
 	{
 		reallocate(start_count);
 	}


 	//! Copy constructor
 	array(const array<T>& other)
 		: data(0)
 	{
 		*this = other;
 	}


 	//! Destructor. Frees allocated memory, if set_free_when_destroyed
 	//! was not set to false by the user before.
 	~array()
 	{
 		if (free_when_destroyed)
 			delete [] data;
 	}


 	//! Reallocates the array, make it bigger or smaller.
 	//! \param new_size: New size of array.
 	void reallocate(u32 new_size)
 	{
 		T* old_data = data;

 		data = new T[new_size];
 		allocated = new_size;

 		s32 end = used < new_size ? used : new_size;
 		for (s32 i=0; i<end; ++i)
 			data[i] = old_data[i];

 		if (allocated < used)
 			used = allocated;

 		delete [] old_data;
 	}

 	//! Adds an element at back of array. If the array is to small to
 	//! add this new element, the array is made bigger.
 	//! \param element: Element to add at the back of the array.
 	void push_back(const T& element)
 	{
 		if (used + 1 > allocated)
 		{
 			// reallocate(used * 2 +1);
 			// this doesn't work if the element is in the same array. So
 			// we'll copy the element first to be sure we'll get no data
 			// corruption

 			T e;
 			e = element;           // copy element
 			reallocate(used * 2 +1); // increase data block
 			data[used++] = e;        // push_back
 			is_sorted = false;
 			return;
 		}

 		data[used++] = element;
 		is_sorted = false;
 	}


 	//! Adds an element at the front of the array. If the array is to small to
 	//! add this new element, the array is made bigger. Please note that this
 	//! is slow, because the whole array needs to be copied for this.
 	//! \param element: Element to add at the back of the array.
 	void push_front(const T& element)
 	{
 		if (used + 1 > allocated)
 			reallocate(used * 2 +1);

 		for (int i=(int)used; i>0; --i)
 			data[i] = data[i-1];

 		data[0] = element;
 		is_sorted = false;
 		++used;
 	}


 	//! Insert item into array at specified position. Please use this
 	//! only if you know what you are doing (possible performance loss).
 	//! The preferred method of adding elements should be push_back().
 	//! \param element: Element to be inserted
 	//! \param index: Where position to insert the new element.
 	void insert(const T& element, u32 index=0)
 	{
 		_IRR_DEBUG_BREAK_IF(index>used) // access violation

 		if (used + 1 > allocated)
 			reallocate(used * 2 +1);

 		for (u32 i=used++; i>index; i--)
 			data[i] = data[i-1];

 		data[index] = element;
 		is_sorted = false;
 	}


 	//! Clears the array and deletes all allocated memory.
 	void clear()
 	{
 		delete [] data;
 		data = 0;
 		used = 0;
 		allocated = 0;
 		is_sorted = true;
 	}


 	//! Sets pointer to new array, using this as new workspace.
 	//! \param newPointer: Pointer to new array of elements.
 	//! \param size: Size of the new array.
 	void set_pointer(T* newPointer, u32 size)
 	{
 		delete [] data;
 		data = newPointer;
 		allocated = size;
 		used = size;
 		is_sorted = false;
 	}


 	//! Sets if the array should delete the memory it used.
 	//! \param f: If true, the array frees the allocated memory in its
 	//! destructor, otherwise not. The default is true.
 	void set_free_when_destroyed(bool f)
 	{
 		free_when_destroyed = f;
 	}


 	//! Sets the size of the array.
 	//! \param usedNow: Amount of elements now used.
 	void set_used(u32 usedNow)
 	{
 		if (allocated < usedNow)
 			reallocate(usedNow);

 		used = usedNow;
 	}


 	//! Assignement operator
 	void operator=(const array<T>& other)
 	{
 		if (data)
 			delete [] data;

 		//if (allocated < other.allocated)
 		if (other.allocated == 0)
 			data = 0;
 		else
 			data = new T[other.allocated];

 		used = other.used;
 		free_when_destroyed = other.free_when_destroyed;
 		is_sorted = other.is_sorted;
 		allocated = other.allocated;

 		for (u32 i=0; i<other.used; ++i)
 			data[i] = other.data[i];
 	}


 	//! Direct access operator
 	T& operator [](u32 index)
 	{
 		_IRR_DEBUG_BREAK_IF(index>=used) // access violation

 		return data[index];
 	}


 	//! Direct access operator
 	const T& operator [](u32 index) const
 	{
 		_IRR_DEBUG_BREAK_IF(index>=used) // access violation

 		return data[index];
 	}

     //! Gets last frame
 	const T& getLast() const
 	{
 		_IRR_DEBUG_BREAK_IF(!used) // access violation

 		return data[used-1];
 	}

     //! Gets last frame
 	T& getLast()
 	{
 		_IRR_DEBUG_BREAK_IF(!used) // access violation

 		return data[used-1];
 	}


 	//! Returns a pointer to the array.
 	//! \return Pointer to the array.
 	T* pointer()
 	{
 		return data;
 	}


 	//! Returns a const pointer to the array.
 	//! \return Pointer to the array.
 	const T* const_pointer() const
 	{
 		return data;
 	}


 	//! Returns size of used array.
 	//! \return Size of elements in the array.
 	u32 size() const
 	{
 		return used;
 	}


 	//! Returns amount memory allocated.
 	//! \return Returns amount of memory allocated. The amount of bytes
 	//! allocated would  be allocated_size() * sizeof(ElementsUsed);
 	u32 allocated_size() const
 	{
 		return allocated;
 	}


 	//! Returns true if array is empty
 	//! \return True if the array is empty, false if not.
 	bool empty() const
 	{
 		return used == 0;
 	}


 	//! Sorts the array using heapsort. There is no additional memory waste and
 	//! the algorithm performs (O) n log n in worst case.
 	void sort()
 	{
 		if (is_sorted || used<2)
 			return;

 		heapsort(data, used);
 		is_sorted = true;
 	}


 	//! Performs a binary search for an element, returns -1 if not found.
 	//! The array will be sorted before the binary search if it is not
 	//! already sorted.
 	//! \param element: Element to search for.
 	//! \return Returns position of the searched element if it was found,
 	//! otherwise -1 is returned.
 	s32 binary_search(const T& element)
 	{
 		return binary_search(element, 0, used-1);
 	}


 	//! Performs a binary search for an element, returns -1 if not found.
 	//! The array will be sorted before the binary search if it is not
 	//! already sorted.
 	//! \param element: Element to search for.
 	//! \param left: First left index
 	//! \param right: Last right index.
 	//! \return Returns position of the searched element if it was found,
 	//! otherwise -1 is returned.
 	s32 binary_search(const T& element, s32 left, s32 right)
 	{
 		if (!used)
 			return -1;

 		sort();

 		s32 m;

 		do
 		{
 			m = (left+right)>>1;

 			if (element < data[m])
 				right = m - 1;
 			else
 				left = m + 1;

 		} while((element < data[m] || data[m] < element) && left<=right);

 		// this last line equals to:
 		// " while((element != array[m]) && left<=right);"
 		// but we only want to use the '<' operator.
 		// the same in next line, it is "(element == array[m])"

 		if (!(element < data[m]) && !(data[m] < element))
 			return m;

 		return -1;
 	}


 	//! Finds an element in linear time, which is very slow. Use
 	//! binary_search for faster finding. Only works if =operator is implemented.
 	//! \param element: Element to search for.
 	//! \return Returns position of the searched element if it was found,
 	//! otherwise -1 is returned.
 	s32 linear_search(T& element)
 	{
 		for (u32 i=0; i<used; ++i)
 			if (!(element < data[i]) && !(data[i] < element))
 				return (s32)i;

 		return -1;
 	}


 	//! Finds an element in linear time, which is very slow. Use
 	//! binary_search for faster finding. Only works if =operator is implemented.
 	//! \param element: Element to search for.
 	//! \return Returns position of the searched element if it was found,
 	//! otherwise -1 is returned.
 	s32 linear_reverse_search(T& element)
 	{
 		for (s32 i=used-1; i>=0; --i)
 			if (data[i] == element)
 				return (s32)i;

 		return -1;
 	}


 	//! Erases an element from the array. May be slow, because all elements
 	//! following after the erased element have to be copied.
 	//! \param index: Index of element to be erased.
 	void erase(u32 index)
 	{
 		_IRR_DEBUG_BREAK_IF(index>=used || index<0) // access violation

 		for (u32 i=index+1; i<used; ++i)
 			data[i-1] = data[i];

 		--used;
 	}


 	//! Erases some elements from the array. may be slow, because all elements
 	//! following after the erased element have to be copied.
 	//! \param index: Index of the first element to be erased.
 	//! \param count: Amount of elements to be erased.
 	void erase(u32 index, s32 count)
 	{
 		_IRR_DEBUG_BREAK_IF(index>=used || index<0 || count<1 || index+count>used) // access violation

 		for (u32 i=index+count; i<used; ++i)
 			data[i-count] = data[i];

 		used-= count;
 	}


 	//! Sets if the array is sorted
 	void set_sorted(bool _is_sorted)
 	{
 		is_sorted = _is_sorted;
 	}


 	private:

 		T* data;
 		u32 allocated;
 		u32 used;
 		bool free_when_destroyed;
 		bool is_sorted;
 };


 } // end namespace core
 } // end namespace irr


 #endif
	// Copyright (C) 2002-2005 Nikolaus Gebhardt
	// This file is part of the "Irrlicht Engine" and the "irrXML" project.
	// For conditions of distribution and use, see copyright notice in irrlicht.h and irrXML.h

	#ifndef __IRR_ARRAY_H_INCLUDED__
	#define __IRR_ARRAY_H_INCLUDED__

	#include "irrTypes.h"
	#include "heapsort.h"

	namespace irr
	{
	namespace core
	{

	//! Self reallocating template array (like stl vector) with additional features.
	/** Some features are: Heap sorting, binary search methods, easier debugging.
	*/
	template <class T>
	class array
	{

	public:

	array()
	: data(0), allocated(0), used(0),
	free_when_destroyed(true), is_sorted(true)
	{
	}

	//! Constructs a array and allocates an initial chunk of memory.
	//! \param start_count: Amount of elements to allocate.
	array(u32 start_count)
	: data(0), allocated(0), used(0),
	free_when_destroyed(true), is_sorted(true)
	{
	reallocate(start_count);
	}


	//! Copy constructor
	array(const array<T>& other)
	: data(0)
	{
	*this = other;
	}



	//! Destructor. Frees allocated memory, if set_free_when_destroyed
	//! was not set to false by the user before.
	~array()
	{
	if (free_when_destroyed)
	delete [] data;
	}



	//! Reallocates the array, make it bigger or smaller.
	//! \param new_size: New size of array.
	void reallocate(u32 new_size)
	{
	T* old_data = data;

	data = new T[new_size];
	allocated = new_size;

	s32 end = used < new_size ? used : new_size;
	for (s32 i=0; i<end; ++i)
	data[i] = old_data[i];

	if (allocated < used)
	used = allocated;

	delete [] old_data;
	}

	//! Adds an element at back of array. If the array is to small to
	//! add this new element, the array is made bigger.
	//! \param element: Element to add at the back of the array.
	void push_back(const T& element)
	{
	if (used + 1 > allocated)
	{
	// reallocate(used * 2 +1);
	// this doesn't work if the element is in the same array. So
	// we'll copy the element first to be sure we'll get no data
	// corruption

	T e;
	e = element; // copy element
	reallocate(used * 2 +1); // increase data block
	data[used++] = e; // push_back
	is_sorted = false;
	return;
	}

	data[used++] = element;
	is_sorted = false;
	}


	//! Adds an element at the front of the array. If the array is to small to
	//! add this new element, the array is made bigger. Please note that this
	//! is slow, because the whole array needs to be copied for this.
	//! \param element: Element to add at the back of the array.
	void push_front(const T& element)
	{
	if (used + 1 > allocated)
	reallocate(used * 2 +1);

	for (int i=(int)used; i>0; --i)
	data[i] = data[i-1];

	data[0] = element;
	is_sorted = false;
	++used;
	}


	//! Insert item into array at specified position. Please use this
	//! only if you know what you are doing (possible performance loss).
	//! The preferred method of adding elements should be push_back().
	//! \param element: Element to be inserted
	//! \param index: Where position to insert the new element.
	void insert(const T& element, u32 index=0)
	{
	_IRR_DEBUG_BREAK_IF(index>used) // access violation

	if (used + 1 > allocated)
	reallocate(used * 2 +1);

	for (u32 i=used++; i>index; i--)
	data[i] = data[i-1];

	data[index] = element;
	is_sorted = false;
	}




	//! Clears the array and deletes all allocated memory.
	void clear()
	{
	delete [] data;
	data = 0;
	used = 0;
	allocated = 0;
	is_sorted = true;
	}



	//! Sets pointer to new array, using this as new workspace.
	//! \param newPointer: Pointer to new array of elements.
	//! \param size: Size of the new array.
	void set_pointer(T* newPointer, u32 size)
	{
	delete [] data;
	data = newPointer;
	allocated = size;
	used = size;
	is_sorted = false;
	}



	//! Sets if the array should delete the memory it used.
	//! \param f: If true, the array frees the allocated memory in its
	//! destructor, otherwise not. The default is true.
	void set_free_when_destroyed(bool f)
	{
	free_when_destroyed = f;
	}



	//! Sets the size of the array.
	//! \param usedNow: Amount of elements now used.
	void set_used(u32 usedNow)
	{
	if (allocated < usedNow)
	reallocate(usedNow);

	used = usedNow;
	}



	//! Assignement operator
	void operator=(const array<T>& other)
	{
	if (data)
	delete [] data;

	//if (allocated < other.allocated)
	if (other.allocated == 0)
	data = 0;
	else
	data = new T[other.allocated];

	used = other.used;
	free_when_destroyed = other.free_when_destroyed;
	is_sorted = other.is_sorted;
	allocated = other.allocated;

	for (u32 i=0; i<other.used; ++i)
	data[i] = other.data[i];
	}


	//! Direct access operator
	T& operator [](u32 index)
	{
	_IRR_DEBUG_BREAK_IF(index>=used) // access violation

	return data[index];
	}



	//! Direct access operator
	const T& operator [](u32 index) const
	{
	_IRR_DEBUG_BREAK_IF(index>=used) // access violation

	return data[index];
	}

	//! Gets last frame
	const T& getLast() const
	{
	_IRR_DEBUG_BREAK_IF(!used) // access violation

	return data[used-1];
	}

	//! Gets last frame
	T& getLast()
	{
	_IRR_DEBUG_BREAK_IF(!used) // access violation

	return data[used-1];
	}


	//! Returns a pointer to the array.
	//! \return Pointer to the array.
	T* pointer()
	{
	return data;
	}



	//! Returns a const pointer to the array.
	//! \return Pointer to the array.
	const T* const_pointer() const
	{
	return data;
	}



	//! Returns size of used array.
	//! \return Size of elements in the array.
	u32 size() const
	{
	return used;
	}



	//! Returns amount memory allocated.
	//! \return Returns amount of memory allocated. The amount of bytes
	//! allocated would be allocated_size() * sizeof(ElementsUsed);
	u32 allocated_size() const
	{
	return allocated;
	}



	//! Returns true if array is empty
	//! \return True if the array is empty, false if not.
	bool empty() const
	{
	return used == 0;
	}



	//! Sorts the array using heapsort. There is no additional memory waste and
	//! the algorithm performs (O) n log n in worst case.
	void sort()
	{
	if (is_sorted \|\| used<2)
	return;

	heapsort(data, used);
	is_sorted = true;
	}



	//! Performs a binary search for an element, returns -1 if not found.
	//! The array will be sorted before the binary search if it is not
	//! already sorted.
	//! \param element: Element to search for.
	//! \return Returns position of the searched element if it was found,
	//! otherwise -1 is returned.
	s32 binary_search(const T& element)
	{
	return binary_search(element, 0, used-1);
	}



	//! Performs a binary search for an element, returns -1 if not found.
	//! The array will be sorted before the binary search if it is not
	//! already sorted.
	//! \param element: Element to search for.
	//! \param left: First left index
	//! \param right: Last right index.
	//! \return Returns position of the searched element if it was found,
	//! otherwise -1 is returned.
	s32 binary_search(const T& element, s32 left, s32 right)
	{
	if (!used)
	return -1;

	sort();

	s32 m;

	do
	{
	m = (left+right)>>1;

	if (element < data[m])
	right = m - 1;
	else
	left = m + 1;

	} while((element < data[m] \|\| data[m] < element) && left<=right);

	// this last line equals to:
	// " while((element != array[m]) && left<=right);"
	// but we only want to use the '<' operator.
	// the same in next line, it is "(element == array[m])"

	if (!(element < data[m]) && !(data[m] < element))
	return m;

	return -1;
	}


	//! Finds an element in linear time, which is very slow. Use
	//! binary_search for faster finding. Only works if =operator is implemented.
	//! \param element: Element to search for.
	//! \return Returns position of the searched element if it was found,
	//! otherwise -1 is returned.
	s32 linear_search(T& element)
	{
	for (u32 i=0; i<used; ++i)
	if (!(element < data[i]) && !(data[i] < element))
	return (s32)i;

	return -1;
	}


	//! Finds an element in linear time, which is very slow. Use
	//! binary_search for faster finding. Only works if =operator is implemented.
	//! \param element: Element to search for.
	//! \return Returns position of the searched element if it was found,
	//! otherwise -1 is returned.
	s32 linear_reverse_search(T& element)
	{
	for (s32 i=used-1; i>=0; --i)
	if (data[i] == element)
	return (s32)i;

	return -1;
	}



	//! Erases an element from the array. May be slow, because all elements
	//! following after the erased element have to be copied.
	//! \param index: Index of element to be erased.
	void erase(u32 index)
	{
	_IRR_DEBUG_BREAK_IF(index>=used \|\| index<0) // access violation

	for (u32 i=index+1; i<used; ++i)
	data[i-1] = data[i];

	--used;
	}


	//! Erases some elements from the array. may be slow, because all elements
	//! following after the erased element have to be copied.
	//! \param index: Index of the first element to be erased.
	//! \param count: Amount of elements to be erased.
	void erase(u32 index, s32 count)
	{
	_IRR_DEBUG_BREAK_IF(index>=used \|\| index<0 \|\| count<1 \|\| index+count>used) // access violation

	for (u32 i=index+count; i<used; ++i)
	data[i-count] = data[i];

	used-= count;
	}


	//! Sets if the array is sorted
	void set_sorted(bool _is_sorted)
	{
	is_sorted = _is_sorted;
	}


	private:

	T* data;
	u32 allocated;
	u32 used;
	bool free_when_destroyed;
	bool is_sorted;
	};


	} // end namespace core
	} // end namespace irr



	#endif