//
//	simplified implementation of deque data type
//
//	Described in Chapter 11 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//

//
//	class deque
//		double ended queue

//
//	class dequeIterator
//		iterator protocol for deque

template <class T> class dequeIterator {
	friend class deque<T>;
	typedef dequeIterator<T> iterator;
public:
		// constructors
	dequeIterator (deque<T> * d, int i) : theDeque(d), index(i) { }
	dequeIterator (dequeIterator<T> & d) 
		: theDeque(d.theDeque), index(d.index) { }

		// iterator operations
	T & operator * () { return (*theDeque)[index]; }
	iterator & operator ++ (int) { ++index; return * this; }
	iterator operator ++ (); // prefix change
	iterator & operator -- (int) { --index; return * this; }
	iterator operator -- (); // postfix change
	bool operator == (iterator & r) 
		{ return theDeque == r.theDeque && index == r.index; }
	bool operator < (iterator & r)
		{ return theDeque == r.theDeque && index < r.index; }
	T & operator [ ] (unsigned int i)
		{ return (*theDeque) [index + i]; } 
	void operator = (iterator & r)
		{ theDeque = r.theDeque; index = r.index; }
	iterator operator + (int i)
		{ return iterator(theDeque, index + i); }
	iterator operator - (int i)
		{ return iterator(theDeque, index - i); }

protected:
	deque<T> * theDeque;
	int index;
};

# include <vector.h>

template <class T> class deque {
public:
	typedef dequeIterator<T> iterator;
	typedef T value_type;

		// constructors
	deque () : vecOne(), vecTwo() { }
	deque (unsigned int size, T & initial) : vecOne (size/2, initial),
		vecTwo (size - (size / 2), initial)  { }
	deque (deque<T> & d) : vecOne(d.vecOne), vecTwo(d.vecTwo) { }

		// operations
	T & 	operator [ ] (unsigned int);
	T & 	front ();
	T & 	back ();
	bool	empty () { return vecOne.empty () && vecTwo.empty (); }
	iterator begin () { return iterator(this, 0); }
	iterator end () { return iterator(this, size ()); }
	void	erase (iterator);
	void	erase (iterator, iterator);
	void	insert (iterator, T &);
	int 	size () { return vecOne.size () + vecTwo.size (); }
	void	push_front (T & value) { vecOne.push_back(value); }
	void	push_back (T & value) { vecTwo.push_back(value); }
	void	pop_front ();
	void	pop_back ();

protected:
	vector<T> vecOne;
	vector<T> vecTwo;
};

template <class T> T & deque<T>::front ()
	// return first element in deque
{
	if (vecOne.empty ())
		return vecTwo.front ();
	else
		return vecOne.back ();
}


template <class T> void deque<T>::pop_front ()
	// remove first element in deque
{
	if (vecOne.empty ())
		vecTwo.erase(vecTwo.begin ());
	else
		vecOne.pop_back ();
}

template <class T> T & deque<T>::operator [ ] (unsigned int index)
	// return given element from deque
{
	int n = vecOne.size ();
	if (index <= n)
		return vecOne [ (n-1) - index ];
	else
		return vecTwo [ index - n ];
}

template <class T> dequeIterator<T> dequeIterator<T>::operator ++ (int)
	// postfix form of increment
{
		// clone, update, return clone
	deque<T>::iterator clone(theDeque, index);
	index++;
	return clone;
}

template <class T> void deque<T>::erase (dequeIterator<T> itr)
	// erase value from deque
{
	int index = itr.index;
	int n = vecOne.size ();
	if (index < n)
		vecOne.erase (vecOne.begin () + ((n-1) - index));
	else
		vecTwo.erase (vecTwo.begin () + (n - index));
}