// © Copyright 1997. Joseph Bergin. All rights reserved.

#ifndef ExpandableArray_H
#define ExpandableArray_H

#include <iterator.h>
#include <algo.h>
#include <iostream.h>

template <class T>
class ExpandableArray
{	public:
		typedef T& reference;
		typedef T value_type;
		typedef T* iterator;	// Use ordinary pointers. 

		ExpandableArray()
		:	_values(new T[100]), _size(0), _capacity(100)
		{
		}

		ExpandableArray( long n, const T& val = T() )
		:	_values(new T[2*n]), _size(n), _capacity(2*n)
		{	if(val != T())
			for(long i = 0; i < n; ++i)
				_values[i] = val;
		}
		
// added -- do not include with the library--exercises.  	
		long index(iterator i)const {return i - _values;}
		iterator location(long i)const{return _values + i;}
		
		void pop_back()
		{	_size--;
			long new_capacity;
			if (( new_capacity =_capacity / 2) > _size && new_capacity > 10)
				reserve(new_capacity);
		}
		bool empty()const{return _size == 0;};
		
		const reference operator[]( long w )const{return _values[w];}// discuss
		
		void insert(iterator i, const value_type& v)
		{	if(_size == _capacity) reserve(2*_capacity);
			for(iterator j = end(); j != i; --j)
				*j = *(j-1);
			*i = v;
			_size++;
		}
		
		void erase(iterator i)
		{	for( ; i != end() - 1; ++i)
				*i = *(i+1);
			_size--;
			long new_capacity;
			if(( new_capacity =_capacity / 2) > _size && new_capacity > 10)
				reserve(new_capacity);
		}

		void push_front(const T& t){ insert(begin(), t); }
		
		void pop_front(){ erase(begin());}
		
		void reserve(long n) // make capacity at least n
		{	if(_capacity < n)
			{	T* new_values = new T[n];
				_capacity = n;
				for(int i = 0; i < _size; ++i)
					new_values[i] = _values[i];
				T* temp = _values;
				_values = new_values;
				delete temp;
			}
		}
		
	    void insert (iterator position, iterator first, iterator last)
	    {	long dist = 0;
	    	distance(first, last, dist);
	    	cout<<"dist = "<<dist<<endl;
	    	reserve(_size + dist);
	    	for(iterator j = end() + dist; j != position + dist - 1; --j)
	    		*j =  *(j - dist);
	    	for( ;first != last; first++)
	    		*position++ = *first;
	    	_size += dist;
	    }
		
		reference back(){return _values[_size-1];}
		reference front(){return *_values;}
		const reference back()const {return _values[_size-1];}
		const reference front()const {return *_values;}
		
// end added
		ExpandableArray(const ExpandableArray<T>& A);

		ExpandableArray<T>& operator=(const ExpandableArray<T>& A);

		~ExpandableArray();

		long size()const{ return _size;}

		long capacity()const{ return _capacity;}

		reference operator[]( long w ){ return _values[w];}

		iterator begin()const { return _values; }

		iterator end()const { return _values + _size; }

		void push_back(const T& t)
		{	if( _capacity == _size )
			{	reserve(2*_capacity);
			}
			_values[_size++] = t;
		}

	private:
		T * _values;
		long _size;
		long _capacity;
		
		void copy(const ExpandableArray<T>& A);
		void free();

};

template <class T>
ExpandableArray<T>:: ~ExpandableArray ()
{	free();
}

template <class T>
inline ExpandableArray<T>:: ExpandableArray(const ExpandableArray<T>& A)
{	copy(A);
}

template <class T>
inline ExpandableArray<T>& ExpandableArray<T>:: operator=(const ExpandableArray<T>& A)
{	if(this != &A)
	{	free();
		copy(A);
	}
	return *this;
}

template <class T>
inline void ExpandableArray<T>:: free()
{	delete [] _values;
}

template <class T>
void ExpandableArray<T>:: copy(const ExpandableArray<T>& A)
{	_size = A._size;
	_capacity = A._capacity;
	_values = new T [ _capacity ];
	for(long i = 0; i < _size; ++i)
		_values[i] = A._values[i];
}

template <class T>
ostream& operator<<(ostream& out, const ExpandableArray<T>& a)
{	for( ExpandableArray<T>::iterator i = a.begin(); i != a.end(); i++)
		out << *i<<' ';
	return out;
}

#endif