//
//  Typical template dynamic array container class.
//  By S Melax 1998
//
// anyone is free to use, inspect, learn from, or ignore
// the code here as they see fit.
//
// A very simple template array class.
// Its easiest to understand this array
// class by seeing how it is used in code.
//
// For example:
//     for(i=0;i<myarray.count;i++)
//         myarray[i] = somefunction(i);
//
// When the array runs out of room, it
// reallocates memory and doubles the size of its
// storage buffer.  The reason for *doubleing* the amount of
// memory is so the order of any algorithm using this class
// is the same as it would be had you used a regular C array.
// The penalty for reallocating and copying
// For example consider adding n elements to a list.
// Lets sum the number of times elements are "copied".
// The worst case occurs when n=2^k+1 where k is integer.
// In this case we do a big reallocation when we add the last element.
// n elements are copied once, n/2 elements are copied twice,
// n/4 elements are copied 3 times, and so on ...
//    total == n* (1+1/2 + 1/4 + 1/8 + ...) == n * 2
// So we do n*2 copies.  Therefore adding n
// elements to an Array is still O(n).
// The memory usage is also of the same order as if a C array was used.
// An Array uses less than double the minimum needed space.  Again, we
// see that we are within a small constant multiple.
//
// Why no "realloc" to avoid the copy when reallocating memory?
// You have a choice to either use malloc/free and friends
// or to use new/delete.  Its bad mojo to mix these.  new/delete was
// chosen to be C++ish and have the array elements constructors/destructors
// invoked as expected.
//
//

#ifndef SM_ARRAY_H
#define SM_ARRAY_H

#include <assert.h>
#include <stdio.h>

template <class Type>
class Array
{
public:
	Array(int s = 0);
	Array(Array<Type> &array);
	~Array();
	void allocate(int s);
	void SetSize(int s);
	void Pack();
	Type &Add(Type);
	void AddUnique(Type);
	int Contains(Type);
	void Insert(Type, int);
	int IndexOf(Type);
	void Remove(Type);
	void DelIndex(int i);
	Type &DelIndexWithLast(int i);
	Type *element;
	int count;
	int array_size;
	const Type &operator[](int i) const
	{
		assert(i >= 0 && i < count);
		return element[i];
	}
	Type &operator[](int i)
	{
		assert(i >= 0 && i < count);
		return element[i];
	}
	Type &Pop()
	{
		assert(count);
		count--;
		return element[count];
	}
	Array<Type> &copy(const Array<Type> &array);
	Array<Type> &operator=(Array<Type> &array);
};

template <class Type>
Array<Type>::Array(int s)
{
	if (s == -1) return;
	count = 0;
	array_size = 0;
	element = NULL;
	if (s)
	{
		allocate(s);
	}
}

template <class Type>
Array<Type>::Array(Array<Type> &array)
{
	count = 0;
	array_size = 0;
	element = NULL;
	*this = array;
}

template <class Type>
Array<Type> &Array<Type>::copy(const Array<Type> &array)
{
	assert(array.array_size >= 0);
	count = 0;
	for (int i = 0; i < array.count; i++)
	{
		Add(array[i]);
	}
	return *this;
}
template <class Type>
Array<Type> &Array<Type>::operator=(Array<Type> &array)
{
	if (array.array_size < 0)  //  negative number means steal the data buffer instead of copying
	{
		delete[] element;
		element = array.element;
		array_size = -array.array_size;
		count = array.count;
		array.count = array.array_size = 0;
		array.element = NULL;
		return *this;
	}
	count = 0;
	for (int i = 0; i < array.count; i++)
	{
		Add(array[i]);
	}
	return *this;
}

template <class Type>
Array<Type>::~Array()
{
	if (element != NULL && array_size != 0)
	{
		delete[] element;
	}
	count = 0;
	array_size = 0;
	element = NULL;
}

template <class Type>
void Array<Type>::allocate(int s)
{
	assert(s > 0);
	assert(s >= count);
	if (s == array_size) return;
	Type *old = element;
	array_size = s;
	element = new Type[array_size];
	assert(element);
	for (int i = 0; i < count; i++)
	{
		element[i] = old[i];
	}
	if (old) delete[] old;
}

template <class Type>
void Array<Type>::SetSize(int s)
{
	if (s == 0)
	{
		if (element)
		{
			delete[] element;
			element = NULL;
		}
		array_size = s;
	}
	else
	{
		allocate(s);
	}
	count = s;
}

template <class Type>
void Array<Type>::Pack()
{
	allocate(count);
}

template <class Type>
Type &Array<Type>::Add(Type t)
{
	assert(count <= array_size);
	if (count == array_size)
	{
		allocate((array_size) ? array_size * 2 : 16);
	}
	//int i;
	//for(i=0;i<count;i++) {
	// dissallow duplicates
	//	assert(element[i] != t);
	//}
	element[count++] = t;
	return element[count - 1];
}

template <class Type>
int Array<Type>::Contains(Type t)
{
	int i;
	int found = 0;
	for (i = 0; i < count; i++)
	{
		if (element[i] == t) found++;
	}
	return found;
}

template <class Type>
void Array<Type>::AddUnique(Type t)
{
	if (!Contains(t)) Add(t);
}

template <class Type>
void Array<Type>::DelIndex(int i)
{
	assert(i < count);
	count--;
	while (i < count)
	{
		element[i] = element[i + 1];
		i++;
	}
}

template <class Type>
Type &Array<Type>::DelIndexWithLast(int i)
{
	assert(i < count);
	count--;
	if (i < count)
	{
		Type r = element[i];
		element[i] = element[count];
		element[count] = r;
	}
	return element[count];
}

template <class Type>
void Array<Type>::Remove(Type t)
{
	int i;
	for (i = 0; i < count; i++)
	{
		if (element[i] == t)
		{
			break;
		}
	}
	assert(i < count);  // assert object t is in the array.
	DelIndex(i);
	for (i = 0; i < count; i++)
	{
		assert(element[i] != t);
	}
}

template <class Type>
void Array<Type>::Insert(Type t, int k)
{
	int i = count;
	Add(t);  // to allocate space
	while (i > k)
	{
		element[i] = element[i - 1];
		i--;
	}
	assert(i == k);
	element[k] = t;
}

template <class Type>
int Array<Type>::IndexOf(Type t)
{
	int i;
	for (i = 0; i < count; i++)
	{
		if (element[i] == t)
		{
			return i;
		}
	}
	assert(0);
	return -1;
}

#endif