// Copyright (c) <2007> <Mark Paruzel>
//
// This software is provided 'as-is', without any express or implied
// warranty. In no event will the authors be held liable for any damages
// arising from the use of this software.
//
// Permission is granted to anyone to use this software for any purpose,
// including commercial applications, and to alter it and redistribute it
// freely, subject to the following restrictions:
//
//     1. The origin of this software must not be misrepresented; you must not
//     claim that you wrote the original software. If you use this software
//     in a product, an acknowledgment in the product documentation would be
//     appreciated but is not required.
//
//     2. Altered source versions must be plainly marked as such, and must not be
//     misrepresented as being the original software.
//
//     3. This notice may not be removed or altered from any source
//     distribution.

#pragma once

#ifndef _SYS_ARRAY_
#define _SYS_ARRAY_

#define ARRAY_BUFFER		50
#define ARRAY_MULTIPLIER	3
#define INLINE				__forceinline

template <class T>
class Array
{
	// Member Variables
	T *listArray;
	UInt32 listSize;
	UInt32 listMaxSize;
	UInt32 startIndex;

	// Member functions
	INLINE bool		init(UInt32 newSize = ARRAY_BUFFER);
	bool			grow(UInt32 amount, bool keepOld = true);
	bool			grow();
	INLINE void		destroy();
	INLINE void		memCopy(void *dest, void *src, UInt32 size);

public:

	// Friends have access to private member variables
	friend class Array;

	// Constructors & Destructor
	Array(UInt32 size = 0);
	Array(const T &in);
	Array(Array<T> &in);
	~Array();

	// Capacity Accessors & Modifiers
	INLINE UInt32	getSize();
	INLINE bool		isReady();

	// Element Accessors
	INLINE T		getFront();
	INLINE T		getBack();
	INLINE T		&operator[](UInt32 indx);
	Array<T>		&operator+=(const T &in);
	Array<T>		&operator-=(const T &in);
	Array<T>		operator+(const T &in);
	Array<T>		&operator=(const T &in);
	Array<T>		&operator+=(Array<T> &in);
	Array<T>		&operator=(Array<T> &in);
	Array<T>		operator+(Array<T> &in);
	bool			operator==(Array<T> &in);
	bool			operator!=(Array<T> &in);

	// List Modifiers
	INLINE void		pushBack(const T &in);
	INLINE void		pushFront(const T &in);
	INLINE void		popBack();
	INLINE void		popFront();
	INLINE void		emptyList();
	bool			removeFromList(UInt32 indx);
	bool			removeItem(const T &in);
	Array<T>		subList(UInt32 startIndx, UInt32 length);

};

template <class T>
Array<T>::Array(UInt32 size)
{
	// Initialize
	if (size > 0)
	{
		init(size);
	}else{
		listSize = 0;
		listMaxSize = 0;
		startIndex = 0;
		listArray = NULL;
	}
}

template <class T>
Array<T>::Array(const T &in)
{
	// Initialize
	if (init())
	{
		// Attempt to create a new object of this type
		listArray[startIndex + listSize] = *((T *) &in);
		listSize++;
	}
}

template <class T>
Array<T>::Array(Array<T> &in)
{
	// Initialize
	init(in.getSize() + ARRAY_BUFFER);

	// Copy over the members from one array to the next
	memCopy(&listArray[startIndex], &in.listArray[in.startIndex], in.listSize * sizeof(T));
	listSize = in.listSize;
}

template <class T>
Array<T>::~Array()
{
	// Destroy the array
	destroy();
}

template <class T>
bool Array<T>::init(UInt32 newSize)
{
	// Initialize all the variables
	listSize = 0;
	listMaxSize = 0;
	startIndex = 0;
	listArray = NULL;

	return grow(newSize);
}

template <class T>
void Array<T>::memCopy(void *dest, void *src, UInt32 size)
{
	DWORD dcnt;
	UInt32 sz = size;

	__asm
	{
		push ebx
		push esi
		push edi

		mov esi, src
		mov edi, dest
		mov ecx, sz
		cmp ecx, 32
		jl tail

		shr ecx, 5      ; div by 32
		mov dcnt, ecx

align 4
body:
		mov eax, [esi]
		mov ebx, [esi+4]
		mov ecx, [esi+8]
		mov edx, [esi+12]
		mov [edi],    eax
		mov [edi+4],  ebx
		mov [edi+8],  ecx
		mov [edi+12], edx

		mov eax, [esi+16]
		mov ebx, [esi+20]
		mov ecx, [esi+24]
		mov edx, [esi+28]
		mov [edi+16], eax
		mov [edi+20], ebx
		mov [edi+24], ecx
		mov [edi+28], edx

		add esi, 32
		add edi, 32
		sub dcnt, 1
		jnz body

		mov ecx, sz
		and ecx, 31
		jz end

tail:
		mov al, [esi]
		add esi, 1
		mov [edi], al
		add edi, 1
		sub ecx, 1
		jnz tail

end:

		pop edi
		pop esi
		pop ebx

	}
}

template <class T>
bool Array<T>::grow()
{
	// Automatically pick a grow value
	return grow((listMaxSize + ARRAY_BUFFER) * ARRAY_MULTIPLIER);
}

template <class T>
bool Array<T>::grow(UInt32 amount, bool keepOld)
{
	int newSize = ARRAY_BUFFER + listSize + amount;

	// Allocate enough space for the new array
	T *tempArray = listArray ? (T *) realloc(listArray, newSize * sizeof(T)) : NULL;

	if (!tempArray)
	{
		// If realloc Fails, just make a new array
		tempArray = (T *) malloc(newSize * sizeof(T));

		if (keepOld && listArray)
		{
			// Copy over the existing members (Entire Array)
			memCopy(&tempArray[ARRAY_BUFFER], &listArray[startIndex], listSize * sizeof(T));
		}

		// Delete the old array and use the newly created one
		SAFE_FREE(listArray);
		startIndex = ARRAY_BUFFER;
	}

	listArray = tempArray;
	listMaxSize = newSize;

	return true;
}

template <class T>
void Array<T>::destroy()
{
	// Remove the existance of the array
	SAFE_FREE(listArray);
}

template <class T>
bool Array<T>::isReady()
{
	return listArray ? true : false;
}

template <class T>
UInt32 Array<T>::getSize()
{
	return listSize;
}

template <class T>
T Array<T>::getFront()
{
	return listSize > 0 ? listArray[startIndex] : *((T *) NULL);
}

template <class T>
T Array<T>::getBack()
{
	return listSize > 0 ? listArray[startIndex + listSize - 1] : *((T *) NULL);
}

template <class T>
void Array<T>::pushBack(const T &in)
{
	// If the start of the array is at index zero, then grow it
	if (!listArray || startIndex + listSize >= listMaxSize)
	{
		grow();
	}

	// Copy over the info
	listArray[startIndex + listSize] = *((T *) &in);
	++listSize;
}

template <class T>
void Array<T>::pushFront(const T &in)
{
	// If the start of the array is at index zero, then grow it
	if (!listArray || startIndex == 0)
	{
		grow();
	}

	// Copy over the memory
	listArray[startIndex - 1] = in;
	++listSize;
	--startIndex;
}

template <class T>
T &Array<T>::operator[](UInt32 indx)
{
	// Return nothing if this is a bad index (a crash)
	return (indx < listSize) ? listArray[startIndex + indx] : *((T *) NULL);
}

template <class T>
Array<T> &Array<T>::operator+=(const T &in)
{
	pushBack(in);

	return *this;
}

template <class T>
Array<T> &Array<T>::operator-=(const T &in)
{
	removeItem(in);

	return *this;
}

template <class T>
Array<T> Array<T>::operator+(const T &in)
{
	Array<T> tempArray;

	// Put this array in first and concatinate it with the incoming array
	tempArray = *this;
	tempArray.pushBack(in);

	return tempArray;
}

template <class T>
Array<T> &Array<T>::operator=(const T &in)
{
	if (!listArray)
	{
		grow();
	}

	// If there is something inside this array, clear it out
	if (listSize != 0)
	{
		emptyList();
	}

	// Push this item into the array as the first item
	pushBack(in);

	return *this;
}

template <class T>
Array<T> &Array<T>::operator+=(Array<T> &in)
{
	// If there is not enough space for this array inside ours, enlarge it
	if (!listArray || listMaxSize - (startIndex + listSize) < in.getSize())
	{
		grow(in.getSize());
	}

	// Loop through the items in the incoming list
	memCopy(&listArray[startIndex + listSize], &in.listArray[in.startIndex], in.listSize * sizeof(T));
	listSize += in.listSize;

	return *this;
}

template <class T>
Array<T> &Array<T>::operator=(Array<T> &in)
{
	T *newArray = NULL;

	// Check to see if we are not equating the same array to itself
	if (this != &in)
	{
		if (listArray && in.listSize == 0)
		{
			emptyList();
		}else{
			startIndex = ARRAY_BUFFER;

			// If there is not enough space for this array inside ours, enlarge it
			if (!listArray || listMaxSize - startIndex < in.listSize)
			{
				grow(in.listSize, false);
			}

			// Create a mini list that starts at startIndex
			listSize = in.listSize;
			memCopy(&listArray[startIndex], &in.listArray[in.startIndex], listSize * sizeof(T));
		}
	}

	return *this;
}

template <class T>
Array<T> Array<T>::operator+(Array<T> &in)
{
	Array<T> tempArray(listSize + in.listSize);

	// Concatinate this array with the incoming array and return
	if (listSize > 0)
	{
		tempArray = *this;
	}

	tempArray += in;

	return tempArray;
}

template <class T>
bool Array<T>::operator==(Array<T> &in)
{
	if (listSize == in.getSize())
	{
		// mainLoop through each member in both arrays
		for (UInt32 i = 0; i < listSize; ++i)
		{
			// Compare each member of the array, byte for byte
			if (listArray[startIndex + i] != in.listArray[in.startIndex + i])
			{
				return false;
			}
		}

		return true;
	}

	return false;
}

template <class T>
bool Array<T>::operator!=(Array<T> &in)
{
	return !(*this == in);
}

template <class T>
void Array<T>::popBack()
{
	if (listSize != 0)
	{
		// Keep the deleted value in memory, it will be deleted afterwards in the destructor
		--listSize;
	}
}

template <class T>
void Array<T>::popFront()
{
	if (listSize != 0)
	{
		// Keep the deleted value in memory, it will be deleted afterwards in the destructor
		--listSize;
		++startIndex;
	}
}

template <class T>
void Array<T>::emptyList()
{
	// Keep the contents in memory, they will be deleted in the destructor
	listSize = 0;
	startIndex = ARRAY_BUFFER;
}

template <class T>
bool Array<T>::removeFromList(UInt32 indx)
{
	if (listArray && indx < listSize)
	{
		if (indx == 0)
		{
			// No point in deleting the front, just move the starting Location
			++startIndex;
			--listSize;
		}else if (indx == listSize - 1)
		{
			// If its at the back, just truncate the array
			--listSize;
		}else{
			// Bubble the rest of the values backwards
			memCopy(&listArray[startIndex + indx], &listArray[startIndex + indx + 1], sizeof(T) * ((startIndex + listSize) - (indx + startIndex + 1)));
			--listSize;
		}

		// Point the insert location to the very begining
		if (listSize == 0)
		{
			startIndex = 0;
		}

		return true;
	}

	return false;
}

template <class T>
bool Array<T>::removeItem(const T &in)
{
	for (UInt32 i = startIndex; listArray && i < startIndex + listSize; ++i)
	{
		// If we find an identical member inside our array, then remove it
		if (listArray[i] == in)
		{
			removeFromList(i - startIndex);

			return true;
		}
	}

	return false;
}

template <class T>
Array<T> Array<T>::subList(UInt32 startIndx, UInt32 length)
{
	Array<T> tempArray;
	UInt32 start = startIndx + startIndex;
	UInt32 end = startIndex + startIndx + length;

	if (listArray && startIndx < listSize && length + startIndx < listSize)
	{
		// mainLoop through the array from the start index given to the end
		for (UInt32 i = start; i < end; ++i)
		{
			// Send each member into this new array
			tempArray.pushBack(listArray[i]);
		}
	}

	return tempArray;
}

#endif