///////////////////////////////////////////////////////////////////////////////
/// @file deArray.hpp
///
/// @brief templated array class
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Sept 2001
/// @author Assassin
/// @remarks Creation
///
/// @date Jan 2002
/// @author Assassin
/// @remarks Bug fixes
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DEARRAY_HPP
#define DEARRAY_HPP

#include "deGlobalTypes.hpp"

#ifndef NULL
#define NULL (0)
#endif
#pragma warning (disable : 4284) // return type for 'identifier::operator –>' is not a UDT or reference to a UDT. Will produce errors if applied using infix notation
#pragma warning (disable : 4710) // function not inlined

template <typename T>
class deTWrapper
{
private:
	T m_data;
public:
	deTWrapper() : m_data() {}
	deTWrapper(const T & ref) : m_data(ref) {}
	virtual ~deTWrapper() {}
	deTWrapper<T>& operator=(const T& ref) { m_data = ref; return *this; }
	deTWrapper<T>& operator=(const deTWrapper<T>& ref) { m_data = ref.m_data; return *this; }
	operator T& () { return m_data; }
	T* operator&() { return &m_data; }
};

/// templated resizable linear array storage class
template <class T>
class deTArray
{
private:
	size_t	m_Length;
	size_t	m_Capacity;
	T*		m_Items;
public:
	static u32 SmallestLargerPow2(u32 x)
	{
		int retval = 1;
		if (x & 0xffff0000)
		{ retval += 16; x >>= 16; }
		if (x & 0x0000ff00)
		{ retval += 8; x >>= 8; }
		if (x & 0x000000f0)
		{ retval += 4; x >>= 4; }
		if (x & 0x0000000c)
		{ retval += 2; x >>= 2; }
		if (x & 0x00000002)
		{ retval += 1; x >>= 1; }
		return (1 << retval);
	}
#ifdef _DEBUG
	class iterator
	{
	private:
		const deTArray<T>* m_Holder;
		T* m_Ref;
	protected:
		friend class deTArray<T>;
		iterator(T* ref, const deTArray<T>* holder) : m_Ref(ref), m_Holder(holder) {}
	public:
		iterator() : m_Ref(0), m_Holder(0) {}
		~iterator() {}
		T& operator*() const
		{
			DE_ASSERT (m_Ref >= m_Holder->begin().m_Ref && m_Ref < m_Holder->end().m_Ref);
			return *m_Ref;
		}
		T* operator->() const
		{ return &operator*(); }
		void operator++() { ++m_Ref; }
		void operator--() { --m_Ref; }
		bool operator==(const iterator & other) const
		{ return m_Ref == other.m_Ref; }
		bool operator!=(const iterator & other) const
		{ return m_Ref != other.m_Ref; }
	};
private:
	inline iterator make_iterator(size_t index) const
	{
		return iterator(&m_Items[index], this);
	}
	inline size_t iterator_index(const iterator& it)
	{
		return it.m_Ref - m_Items;
	}
public:
#else
	typedef T* iterator;
private:
	inline iterator make_iterator(size_t index) const
	{
		return &m_Items[index];
	}
	inline size_t iterator_index(const iterator& it)
	{
		return it - m_Items;
	}
public:
#endif

	deTArray(void)
	:m_Length(0), m_Capacity(0), m_Items(NULL)	{}
	deTArray(const deTArray & RHS)
	:m_Length(RHS.m_Length),m_Capacity(RHS.m_Capacity)
	{
		if (m_Capacity > 0)
		{
			size_t i;
			m_Items = new T[m_Capacity];
			for (i = 0; i < m_Length; i++)
				m_Items[i] = RHS.m_Items[i];
		}
		else
			m_Items = NULL;
	}
	deTArray(size_t InitialSize)
	:m_Length(InitialSize),m_Capacity(InitialSize)
	{
		if (m_Capacity > 0)
			m_Items = new T[m_Capacity];
		else
			m_Items = NULL;
	}
	deTArray(size_t InitialSize,const T & Value)
	:m_Length(InitialSize),m_Capacity(InitialSize)
	{
		if (m_Capacity > 0)
		{
			u32 i;
			m_Items = new T[m_Capacity];
			for (i = 0; i < m_Length; i++)
				m_Items[i] = Value;
		}
		else
			m_Items = NULL;
	}
	~deTArray()
	{
		if (m_Items != NULL)
		{
			delete [] m_Items;
			m_Items = NULL;
		}
	}

	deTArray <T> & operator=(const deTArray <T> & ref)
	{
		Resize(0);
		Resize(ref.m_Length);
		for (u32 i = 0; i < m_Length; ++i)
			m_Items[i] = ref.m_Items[i];

		return *this;
	}

	inline T& operator[](size_t ArrayItemIndex)			// L-value
	{
		#ifdef _DEBUG
		if (ArrayItemIndex < 0 || ArrayItemIndex >= m_Length)
		{
			// you've tried to access an invalid array element
			BREAK_EXECUTION();
		}
		#endif
		return m_Items[ArrayItemIndex];
	}
	inline const T& operator[](size_t ArrayItemIndex) const	// R-value
	{
		#ifdef _DEBUG
		if (ArrayItemIndex < 0 || ArrayItemIndex >= m_Length)
		{
			// you've tried to access an invalid array element
			BREAK_EXECUTION();
		}
		#endif
		return m_Items[ArrayItemIndex];
	}
	inline iterator get_iterator(size_t ArrayItemIndex) const
	{
		return make_iterator(ArrayItemIndex);
	}
	
	inline deBoolean PushBack(const T& element)
	{
		int i = m_Length;
		if (m_Length >= m_Capacity)
		{
			// this will increment m_Length internally
			if (!Resize(m_Length+1))
				return deFALSE;
		}
		else
		{
			++m_Length;
		}
		m_Items[i] = element;
		return deTRUE;
	}

	inline deBoolean InsertArrayQuick(const T* Array, size_t StartIndex, size_t NumElements)
	{
		if (StartIndex + NumElements > m_Length)
			return deFALSE;
		if (Array == NULL)
			return deFALSE;
		memcpy(&(m_Items[StartIndex]), Array, NumElements*sizeof(T));
		return deTRUE;
	}

	inline iterator IncrementSize()
	{
		if (Resize(m_Length+1))
			return make_iterator(m_Length-1);
		return end();
	}

	inline iterator IncrementSizeQuick(deBoolean ZeroMem = deFALSE)
	{
		if (ResizeQuick(m_Length+1, ZeroMem))
			return make_iterator(m_Length-1);
		return end();
	}
	
	deBoolean Reserve(size_t NewSize, deBoolean PrimitiveType = deFALSE)
	{
		size_t NewCapacity;
		NewCapacity = SmallestLargerPow2(NewSize);

		// if smaller but not by much, keep current capacity
		if (NewCapacity <= m_Capacity && NewCapacity >= m_Capacity/2)
			return deTRUE;

		T *NewItems;
		NewItems = new T[NewCapacity];

		if (NewItems == NULL)
			return deFALSE;
		
		if (m_Items)
		{
			if (PrimitiveType)
			{
				int i = min(m_Length, NewSize);
				memcpy(NewItems, m_Items, i * sizeof(T));
			}
			else
			{
				int k = min(m_Length, NewSize);
				for (int i=0; i < k; i++)
				{
					NewItems[i] = m_Items[i];
				}
			}
			delete[] m_Items;
		}
		m_Capacity = NewCapacity;
		m_Items = NewItems;
		return deTRUE;
	}
	
	deBoolean Resize(size_t NewSize)
	{
		if (NewSize < 0)
			return deFALSE;

		if (NewSize == m_Length)
			return deTRUE;

		if (NewSize == 0)
		{
			m_Length = m_Capacity = 0;
			delete[] m_Items;
			m_Items = NULL;
			return deTRUE;
		}
		
		if (m_Capacity < NewSize)
		{
			if (!Reserve(NewSize))
				return deFALSE;
		}
		m_Length = NewSize;
		return deTRUE;
	}

	// WARNING!!!
	// Only use this method on primitive types in the array
	// such as int, char, etc. If you use this on a class that
	// maintains special information, it will most likely break.
	// Use Resize in those cases, as it deals with classes properly.
	// WARNING!!
	deBoolean ResizeQuick(size_t NewSize, deBoolean ZeroMem = deFALSE)
	{
		if (NewSize < 0)
			return deFALSE;

		if (NewSize == m_Length)
			return deTRUE;

		if (NewSize == 0)
		{
			m_Length = m_Capacity = 0;
			delete[] m_Items;
			m_Items = NULL;
			return deTRUE;
		}
		
		if (m_Capacity < NewSize)
		{
			if (!Reserve(NewSize, deTRUE))
				return deFALSE;
		}
		if (ZeroMem && NewSize > m_Length)
		{
			memset(m_Items + m_Length, 0, (NewSize - m_Length)*sizeof(T));
		}
		m_Length = NewSize;
		return deTRUE;
	}

	deBoolean RemoveElementAt(size_t index)
	{
		if (index < 0 || index >= m_Length)
		{
			DEBUGRETURN(deFALSE, "RemoveElementAt: Invalid array index");
		}

		int i;
		int NewSize = m_Length - 1;
		
		if (NewSize == 0)
		{
			m_Length = 0;
			return deTRUE;
		}

		for (i = index; i < NewSize; i++)
		{
			m_Items[i] = m_Items[i+1];
		}
		m_Length = NewSize;
		return deTRUE;
	}

	inline T* GetCArray() const	{ return m_Items; }

	inline size_t Length() const	{ return m_Length; }
	
public:
	// STL compliance
	inline size_t size() const	{ return m_Length; }
	inline size_t capacity()const	{ return m_Capacity; }
	inline iterator begin() const { return make_iterator(0); }
	inline iterator end() const { return make_iterator(m_Length); }
	inline deBoolean resize(size_t NewSize) { return Resize(NewSize); }
	inline iterator push_back(const T& element) { PushBack(element); return get_iterator(m_Length-1); }
	inline iterator erase(iterator& it) { int index = iterator_index(it); RemoveElementAt(index); return make_iterator(index); }
};

#endif
