// vector.h
//
//////////////////////////////////////////////////////////////////////

#if !defined(__vector_h__)
#define __vector_h__

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <new>

#ifndef _VECTOR_

class VectorData
{
public:
	VectorData();
	VectorData(const VectorData& data);
	~VectorData();

public:
	void InitValues();
	void AllocBuffer(int nAllocLength);	
	void ReleaseBuffer(int nNewLength = -1);	
	void Empty();	
	void Append(char* pBuffer, int nLength);
	int Delete(int nIndex, int nCount = 1);
	int Insert(int nIndex, char* pBuffer, int nLength);	
	operator LPCSTR() const
	{	return (LPCSTR)m_pBuffer; }
	bool IsEmpty() const
	{	return m_nLength == 0; }
	int GetLength() const
	{	return m_nLength;	}
	// assign and equal operator
	const VectorData& Assign(char* pBuffer, int nLength);	
	const VectorData& operator=(const VectorData& data)
	{
		LPCSTR lpcs = data;
		return Assign((char*)lpcs, data.GetLength());
	}
	const bool operator==(const VectorData& data)
	{	return m_nLength == data.m_nLength && memcmp(m_pBuffer, data.m_pBuffer, m_nLength) == 0;	}

public:
	char *m_pBuffer;
	int m_nAllocLength;
	int m_nLength;
	int m_nGrowBytes;
};

template<class T> class vector
{
protected:
	VectorData m_data;

public:
	typedef T* iterator;
	typedef const T* const_iterator;
	typedef T& reference;
	typedef const T& const_reference;
	vector()
	{	}
	vector(int n, const_reference x = T())
	{	resize(n, x);	}
	vector(const vector& x)
	{	assign(x.begin(), x.end()-1); }
	vector(const_iterator first, const_iterator last)
	{	assign(first, last);	}
	~vector()
	{	clear();	}
	const vector& operator=(const vector& v)
	{	m_data = v.m_data;	return *this;	}
	void vfree(int n)
	{	((iterator)m_data.m_pBuffer+n)->~T(); }
	void vfree(int from, int to)
	{	for(int n = from; n <= to; n++) vfree(n); }
	void reserve(int n)
	{	
		vfree(n, size()-1);
		if(n < size())	
			m_data.ReleaseBuffer(n*sizeof(T));
	}
	int capacity() const
	{	return size();	}
	iterator begin()
	{	return (iterator)m_data.m_pBuffer;	}
	const_iterator begin() const
	{	return (const_iterator)m_data.m_pBuffer;	}
	iterator end()
	{	return (iterator)m_data.m_pBuffer+size();	}
	iterator end() const
	{	return (iterator)m_data.m_pBuffer+size();	}
	void resize(int n, T x = T())
	{
		reserve(n);
		for(int i = size(); i < n; i++)
		{
			m_data.Append((char*)&x, sizeof(T));
			new ((void *)((iterator)m_data.m_pBuffer+i)) T(x);
		}
	}
	// for objects that don't need to call constructor
	void resizeEx(int n)
	{	m_data.ReleaseBuffer(n*sizeof(T));	}
	int size() const
	{	return m_data.m_nLength/sizeof(T);	}
	bool empty() const
	{	return m_data.m_nLength == 0;	}
	reference at(int pos)
	{	return *((iterator)m_data.m_pBuffer+pos);	}
	const_reference at(int pos) const
	{	return *((iterator)m_data.m_pBuffer+pos);	}
	reference operator[](int pos)
	{	return *((iterator)m_data.m_pBuffer+pos);	}
	const_reference operator[](int pos) const
	{	return *((iterator)m_data.m_pBuffer+pos);	}
	reference front()
	{	return at(0);	}
	const_reference front() const
	{	return at(0);	}
	reference back()
	{	return at(size()-1);	}
	const_reference back() const
	{	return at(size()-1);	}
	void push_back(const_reference x)
	{	insert(end(), x);	}
	void pop_back()
	{	
		int nSize = size();
		vfree(nSize-1);	
		m_data.Delete((nSize-1)*sizeof(T), sizeof(T));	
	}
	void assign(const_iterator first, const_iterator last)
	{	resize(last-first+1);	for(iterator i = (iterator)first, me = begin(); i <= (iterator)last; i++) *me++ = *i;	}
	void assignEx(const_iterator first, const_iterator last)
	{	resizeEx(last-first+1);	memcpy(begin(), first, (last-first+1)*sizeof(T));	}
	void assign(int n, const_reference x = T())
	{	resize(n);	iterator me = begin();	for(int i = 0; i < n; i++)	*me++ = x;	}
	iterator insert(iterator it, const_reference x = T())
	{	
		int n = it-(iterator)m_data.m_pBuffer;
		m_data.Insert(n*sizeof(T), (char*)&x, sizeof(T));	
		new ((void *)((iterator)m_data.m_pBuffer+n)) T(x);
		return (iterator)m_data.m_pBuffer+n;	
	}
	void insert(iterator it, int n, const_reference x)
	{	
		int nIndex = (it-begin())/sizeof(T);
		for(int i = 0; i < n; i++)	
			insert(begin()+nIndex++, x);
	}
	void insert(iterator it, const_iterator first, const_iterator last)
	{
		int nIndex = (it-begin())/sizeof(T);
		for(iterator i = (iterator)first; i <= (iterator)last; i++)	
			insert(begin()+nIndex++, *i);	
	}
	iterator erase(iterator it)
	{	
		vfree(it-begin());
		m_data.Delete((it-begin())*sizeof(T), sizeof(T)); 
		return it;	
	}
	iterator erase(iterator first, iterator last)
	{
		vfree(first-begin(), last-begin());
		m_data.Delete((first-begin())*sizeof(T), last-first+sizeof(T));	
		return first;
	}
	void clear()
	{	vfree(0, size()-1);	m_data.Empty();	}
	void swap(vector& x)
	{	VectorData temp = m_data;	m_data = x.m_data;	x.m_data = temp;	}
};
#endif

#endif // !defined(__vector_h__)