#ifndef EXT_ARRAY_INCLUDED
#define EXT_ARRAY_INCLUDED

#include <memory.h>

namespace ext
{

template <class Ty>
class array
{
	public:
		typedef size_t size_type;
		typedef Ty value_type;
		typedef Ty* value_type_ptr;
		typedef Ty& reference;
		typedef const Ty& const_reference;
		typedef int difference_type;
		
		class const_iterator
		{
			protected:
				value_type *m_ptr;
				
			public:
				const_iterator() { }
				const_iterator(value_type *ptr) { m_ptr=ptr; }
				const_iterator(const const_iterator& other) { m_ptr=other.m_ptr; }
				
				const_iterator& operator ++()	{	m_ptr++; return *this; }
				const_iterator operator ++(int)	{	m_ptr++; return const_iterator(m_ptr - 1); }
				
				const_iterator& operator --()	{	m_ptr--; return *this; }
				const_iterator operator --(int)	{	m_ptr--; return const_iterator(m_ptr + 1); }
				
				const_reference operator * () const { return *m_ptr; }
				const_reference operator -> () const { return *m_ptr; }
				
				bool operator ==(const_iterator& right)	const {	return right.m_ptr==m_ptr; }
				bool operator !=(const_iterator& right)	const {	return right.m_ptr!=m_ptr; }
		};
		
		class iterator : public const_iterator
		{
			public:
				iterator() { }
				iterator(value_type *ptr) : const_iterator(ptr) { }
				iterator(const iterator& other) : const_iterator(other) { }
				
				iterator& operator ++()	{	m_ptr++; return *this; }
				iterator operator ++(int)	{	m_ptr++; return iterator(m_ptr - 1); }
				
				iterator& operator --()	{	m_ptr--; return *this; }
				iterator operator --(int)	{	m_ptr--; return iterator(m_ptr + 1); }
				
				reference operator * () { return *m_ptr; }
				reference operator -> () { return *m_ptr; }
		};
		
	protected:
		value_type *m_first, *m_last, *m_end;
		
	private:
		size_type m_growby;
		
	public:
		size_type size() const { return m_last - m_first; }
		size_type capacity() const { return m_end - m_first; }
		
		size_type growby() const { return m_growby; }
		void growby(size_type grow) const { m_growby=grow; }
		
		array() { m_growby=100; m_first=0; clear(); }
		array(size_type size) { m_growby=100; m_first=0; clear(); resize(size); }
		~array() { delete[] m_first; }
		
		void reserve(size_type newsize)
		{	
			if(newsize > capacity()){
				size_t oldsize=size();
				value_type *newbuf=new value_type[newsize];
				memcpy(newbuf, m_first, oldsize * sizeof(value_type));
				delete[] m_first;
				m_first=newbuf;
				m_end=m_first + newsize;
				m_last=m_first + oldsize;
			}
		}
		
		void resize(size_type newsize)
		{
			if(newsize==0) return;
			reserve(newsize);
			m_last=m_first + newsize;
		}
		
		void resize(size_type newsize, value_type value)
		{
			resize(newsize);
			value_type_ptr pos=m_first;
			for(value_type_ptr pos=m_first; pos < m_last; pos++){
				*pos=value;
			}
		}
		
		void clear()
		{
			delete m_first;
			m_first=0; m_last=0; m_end=0;
		}
		
		reference operator[](difference_type offset) { return *(m_first + offset); }
		const_reference operator[](difference_type offset) const { return *(m_first + offset); }
		
		reference at(difference_type offset) { return *(m_first + offset); }
		const_reference at(difference_type offset) const { return *(m_first + offset); }
		
		iterator begin() { return iterator(m_first); }
		iterator end() { return iterator(m_last); }
		
		const_iterator begin() const { return const_iterator(m_first); }
		const_iterator end() const { return const_iterator(m_last); }
		
		reference front() { return *begin(); }
		reference back() { return *(--end()); }
		
		const_reference front() const { return *begin(); }
		const_reference back() const { return *(end() - 1); }
		
		iterator push_back(const_reference val)
		{
			if(size() == capacity())
				reserve(capacity() + growby());
			*m_last=val;
			return iterator(m_last++);
		}
		
		typedef int compare_callback (const void *, const void *);
		
		void sort(compare_callback *callback)
		{
			qsort(m_first, size(), sizeof(value_type), callback);
		}
		
		void append(array<value_type>& other)
		{
			reserve(size() + other.size());
			memcpy(m_first + size(), other.m_first, other.size() * sizeof(value_type));
			m_last+=other.size();
		}
		
};

}; // namespace ext

#endif // !defined(EXT_ARRAY_INCLUDED)