/*
								+----------------------------------+
								|                                  |
								|  ***  Tiny vector template  ***  |
								|                                  |
								|   Copyright © -tHE SWINe- 2008   |
								|                                  |
								|           TinyVector.h           |
								|                                  |
								+----------------------------------+
*/

#pragma once
#ifndef __TINY_VECTOR_INCLUDED
#define __TINY_VECTOR_INCLUDED

/**
 *	@file dev/TinyVector.h
 *	@date 2008
 *	@author -tHE SWINe-
 *	@brief Tiny vector template
 *
 *	@date 2012-06-19
 *
 *	Moved multiple inclusion guard before file documentation comment.
 *
 */

#include "../NewFix.h"

/*
 *	template <class _Ty>
 *	class tiny_vector
 *		- template class for tiny vector (ie. container class for
 *		  small array with minimal space amortization)
 */
template <class _Ty>
class tiny_vector {
protected:
	_Ty *m_p_list;

public:
	/*
	 *	tiny_vector::tiny_vector()
	 *		- default constructor
	 */
	tiny_vector()
		:m_p_list(0)
	{}

	/*
	 *	tiny_vector::~tiny_vector()
	 *		- destructor
	 */
	~tiny_vector()
	{
		clear();
	}

	/*
	 *	void tiny_vector::clear()
	 *		- erases anything in the list
	 */
	void clear()
	{
		if(m_p_list) {
			delete[] m_p_list;
			m_p_list = 0;
		}
	}

	/*
	 *	bool tiny_vector::empty() const
	 *		- returns true if vector is empty, otherwise returns false
	 */
	bool empty() const
	{
		return m_p_list == 0;
	}

	/*
	 *	int tiny_vector::size(_Ty terminator) const
	 *		- returns vector size (number of elements before first occurence of terminator
	 *		  or 0 if there are no elements at all)
	 */
	int size(_Ty terminator) const
	{
		if(!m_p_list)
			return 0;
		int n_size = 0;
		while(m_p_list[n_size] != terminator)
			++ n_size;
		return n_size;
	}

	/*
	 *	const _Ty tiny_vector::operator [](int n_index) const
	 *		- const array reference operator
	 */
	const _Ty operator [](int n_index) const
	{
		return m_p_list[n_index];
	}

	/*
	 *	_Ty tiny_vector::operator [](int n_index)
	 *		- array reference operator
	 */
	_Ty &operator [](int n_index)
	{
		return m_p_list[n_index];
	}

	/*
	 *	_Ty *tiny_vector::begin()
	 *		- returns pointer to first element of vector, or 0 in case vector is empty
	 */
	_Ty *begin()
	{
		return m_p_list;
	}

	/*
	 *	const _Ty *tiny_vector::begin() const
	 *		- returns const pointer to first element of vector, or 0 in case vector is empty
	 */
	const _Ty *begin() const
	{
		return m_p_list;
	}

	/*
	 *	_Ty *tiny_vector::end(_Ty terminator)
	 *		- returns pointer to end of vector (pointer to terminator element),
	 *		  or 0 in case vector is empty
	 *		- terminator is value of list terminator
	 */
	_Ty *end(_Ty terminator)
	{
		return m_p_list + size(terminator);
	}

	/*
	 *	const _Ty *tiny_vector::end(_Ty terminator) const
	 *		- returns const pointer to end of vector (pointer to terminator element),
	 *		  or 0 in case vector is empty
	 *		- terminator is value of list terminator
	 */
	const _Ty *end(_Ty terminator) const
	{
		return m_p_list + size(terminator);
	}

	/*
	 *	_Ty *tiny_vector::rbegin(_Ty terminator)
	 *		- returns pointer to the last element of vector, or 0 in case vector is empty
	 *		- terminator is value of list terminator
	 */
	_Ty *rbegin(_Ty terminator)
	{
		return m_p_list + size(terminator) - 1;
	}

	/*
	 *	const _Ty *tiny_vector::rbegin(_Ty terminator) const
	 *		- returns const pointer to the last element of vector, or 0 in case vector is empty
	 *		- terminator is value of list terminator
	 */
	const _Ty *rbegin(_Ty terminator) const
	{
		return m_p_list + size(r_terminator) - 1;
	}

	/*
	 *	_Ty *tiny_vector::rend()
	 *		- returns pointer to element before the first element of vector
	 *		- results are undefined if list is empty
	 */
	_Ty *rend()
	{
		return m_p_list - 1;
	}

	/*
	 *	const _Ty *tiny_vector::rend() const
	 *		- returns const pointer to element before the first element of vector
	 *		- results are undefined if list is empty
	 */
	const _Ty *rend() const
	{
		return m_p_list - 1;
	}

	/*
	 *	void tiny_vector::insert(_Ty *p_before, _Ty elem, _Ty terminator)
	 *		- inserts element elem before p_before
	 *		- terminator is value of list terminator
	 *		- in case there was not enough memory for the new element, vector is cleared
	 *		- note this allocates exactly the amount of memory needed,
	 *		  thus requiring reallocation everytime insert is called. it may
	 *		  therefore be more efficient to insert elements in bigger doses using
	 *		  the second version of insert()
	 */
	void insert(_Ty *p_before, _Ty elem, _Ty terminator)
	{
		int n_size = size(terminator);
		_Ty *p_list = new(std::nothrow) _Ty[n_size + 2];
		if(!p_list) {
			clear();
			return;
		}
		// alloc new list

		_Ty *p_list_ptr = p_list;
		for(_Ty *p_list_src = m_p_list; p_list_src != p_before; ++ p_list_ptr, ++ p_list_src)
			*p_list_ptr = *p_list_src;
		// copy part of list before p_before

		*p_list_ptr ++ = elem;
		// copy value of element being inserted

		for(_Ty *p_list_src = p_before, *p_list_end = p_list + (n_size + 1);
		   p_list_ptr != p_list_end; ++ p_list_ptr, ++ p_list_src)
			*p_list_ptr = *p_list_src;
		// copy part of list after p_before, including terminator

		p_list[n_size + 1] = terminator;
		// terminate

		clear();
		m_p_list = p_list;
		// delete old array, replace with new array
	}

	/*
	 *	void tiny_vector::insert(_Ty *p_before, const _Ty *p_elem_begin,
	 *		const _Ty *p_elem_end, _Ty terminator)
	 *		- inserts range of elements [p_elem_begin, p_elem_end) before p_before
	 *		- terminator is value of list terminator
	 *		- in case there was not enough memory for the new element, vector is cleared
	 */
	void insert(_Ty *p_before, const _Ty *p_elem_begin, const _Ty *p_elem_end, _Ty terminator)
	{
		int n_insert_count = p_elem_end - p_elem_begin;
		if(n_insert_count <= 0)
			return;
		// nothing to insert?

		int n_size = size(terminator);
		_Ty *p_list = new(std::nothrow) _Ty[n_size + n_insert_count + 1];
		if(!p_list) {
			clear();
			return;
		}
		// alloc new list

		_Ty *p_list_ptr = p_list;
		for(_Ty *p_list_src = m_p_list; p_list_src != p_before; ++ p_list_ptr, ++ p_list_src)
			*p_list_ptr = *p_list_src;
		// copy part of list before p_before

		for(; p_elem_begin != p_elem_end; ++ p_list_ptr, ++ p_elem_begin)
			*p_list_ptr = *p_elem_begin;
		// copy values of elements being inserted

		for(_Ty *p_list_src = p_before, *p_list_end = p_list + (n_size + n_insert_count);
		   p_list_ptr != p_list_end; ++ p_list_ptr, ++ p_list_src)
			*p_list_ptr = *p_list_src;
		// copy part of list after p_before, including terminator

		p_list[n_size + n_insert_count] = terminator;
		// terminate

		clear();
		m_p_list = p_list;
		// delete old array, replace with new array
	}

	/*
	 *	void tiny_vector::push_back(_Ty elem, _Ty terminator)
	 *		- inserts elem at the end of the list
	 *		- terminator is value of list terminator
	 *		- in case there was not enough memory for the new element, vector is cleared
	 */
	void push_back(_Ty elem, _Ty terminator)
	{
		insert(end(terminator), elem, terminator);
	}

	/*
	 *	void tiny_vector::insert_back(const _Ty *p_elem_begin,
	 *		const _Ty *p_elem_end, _Ty terminator)
	 *		- inserts range of elements [p_elem_begin, p_elem_end) at the end of the list
	 *		- terminator is value of list terminator
	 *		- in case there was not enough memory for the new element, vector is cleared
	 */
	void insert_back(const _Ty *p_elem_begin, const _Ty *p_elem_end, _Ty terminator)
	{
		insert(end(terminator), p_elem_begin, p_elem_end, terminator);
	}

	/*
	 *	void tiny_vector::push_front(_Ty elem, _Ty terminator)
	 *		- inserts elem at the beginning of the list
	 *		- terminator is value of list terminator
	 *		- in case there was not enough memory for the new element, vector is cleared
	 */
	void push_front(_Ty elem, _Ty terminator)
	{
		insert(begin(), elem, terminator);
	}

	/*
	 *	void tiny_vector::insert_front(const _Ty *p_elem_begin,
	 *		const _Ty *p_elem_end, _Ty terminator)
	 *		- inserts range of elements [p_elem_begin, p_elem_end) at the beginning of the list
	 *		- terminator is value of list terminator
	 *		- in case there was not enough memory for the new element, vector is cleared
	 */
	void insert_front(const _Ty *p_elem_begin, const _Ty *p_elem_end, _Ty terminator)
	{
		insert(begin(), p_elem_begin, p_elem_end, terminator);
	}

	/*
	 *	void tiny_vector::erase(_Ty *p_elem, _Ty terminator)
	 *		- erase element p_elem
	 *		- terminator is value of list terminator
	 */
	void erase(_Ty *p_elem, _Ty terminator)
	{
		int n_size = size(terminator);
		if(!n_size)
			return;
		// nothing to erase in an empty list

		_ASSERTE((p_elem - m_p_list) >= 0 && (p_elem - m_p_list) < n_size);
		// make sure erased elements are inside the list

		if(n_size == 1) {
			_ASSERTE(p_elem == m_p_list);
			clear();
			return;
		}
		// handle case where the only element in the list is erased

		_Ty *p_list = new(std::nothrow) _Ty[n_size];
		if(!p_list) {
			clear();
			return;
		}
		// alloc new list

		_Ty *p_list_ptr = p_list;
		for(_Ty *p_src_list = m_p_list; p_src_list != p_elem; ++ p_list_ptr, ++ p_src_list)
			*p_list_ptr = *p_src_list;
		for(_Ty *p_src_list = p_elem + 1, *p_list_end = p_list + n_size;
		   p_list_ptr != p_list_end; ++ p_list_ptr, ++ p_src_list)
			*p_list_ptr = *p_src_list;
		// copy (including terminator), leave space took up by erased

		_ASSERTE(p_list[n_size - 1] == terminator);
		// make sure it's terminated

		clear();
		m_p_list = p_list;
		// delete old array, replace with new array
	}

	/*
	 *	void tiny_vector::erase_back(_Ty terminator)
	 *		- erase the last element
	 *		- terminator is value of list terminator
	 */
	void erase_back(_Ty terminator)
	{
		erase(rbegin(terminator), terminator);
	}

	/*
	 *	void tiny_vector::erase_front(_Ty terminator)
	 *		- erase the first element
	 *		- terminator is value of list terminator
	 */
	void erase_front(_Ty terminator)
	{
		erase(m_p_list, terminator);
	}

	/*
	 *	void tiny_vector::erase(_Ty *p_elem_begin, _Ty *p_elem_end, _Ty terminator)
	 *		- erase range of elements [p_elem_begin, p_elem_end)
	 *		- terminator is value of list terminator
	 */
	void erase(_Ty *p_elem_begin, _Ty *p_elem_end, _Ty terminator)
	{
		int n_size = size(terminator);
		if(!n_size)
			return;
		// nothing to erase in an empty list

		int n_erase_count = p_elem_end - p_elem_begin;
		if(n_erase_count <= 0)
			return;
		// nothing to erase

		if(n_erase_count == n_size) {
			_ASSERTE(p_elem_begin == m_p_list && p_elem_end == m_p_list + n_size);
			clear();
			return;
		}
		// handle the case when all the elements in the list are erased

		_ASSERTE((p_elem_begin - m_p_list) >= 0 && (p_elem_begin - m_p_list) < n_size);
		_ASSERTE((p_elem_end - m_p_list) > 0 && (p_elem_end - m_p_list) <= n_size);
		// make sure erased elements are inside the list

		_Ty *p_list = new(std::nothrow) _Ty[n_size + 1 - n_erase_count];
		if(!p_list) {
			clear();
			return;
		}
		// alloc new list

		_Ty *p_list_ptr = p_list;
		for(_Ty *p_src_list = m_p_list; p_src_list != p_elem_begin; ++ p_list_ptr, ++ p_src_list)
			*p_list_ptr = *p_src_list;
		for(_Ty *p_src_list = p_elem_end, *p_list_end = p_list + (n_size + 1 - n_erase_count);
		   p_list_ptr != p_list_end; ++ p_list_ptr, ++ p_src_list)
			*p_list_ptr = *p_src_list;
		// copy, leave space took up by erased

		_ASSERTE(p_list[n_size - n_erase_count] == terminator);
		// make sure it's terminated

		clear();
		m_p_list = p_list;
		// delete old array, replace with new array
	}
};

#endif // __TINY_VECTOR_INCLUDED
