#include <iostream>

using std::ostream;

const int D_OK = 0;
const int D_EMPTY = -1;

template <class T> class Deque;

template <class T>
ostream & operator << (ostream &, const Deque<T> &);

template <class T>
class DNode
{
	public:
		T data;
		DNode<T> *next;
		DNode<T> *prev;
		
		DNode(const T &);

		friend class Degue;
		friend ostream& operator <<  <> (ostream &, const Deque<T> &); 
};

template <class T>
class Deque {
	public:

		int listCount;

		DNode<T> *head;
		DNode<T> *tail;

		Deque();
		Deque(const DNode<T> &);
		Deque operator=(const DNode<T> &);
		~Deque();

		bool empty();
		void clear();

		int push_front(const T &);
		int push_back(const T &);

		int pop_front();
		int pop_back();

		int front(T &);
		int back(T &);

		int size();
		
		friend ostream& operator <<  <> (ostream &, const Deque<T> &); 
		

	private:
		
		DNode<T> *duplicate(DNode<T> *);
		void destroy();

};

template <class T>
Deque<T>::Deque() { /* DEFAULT CONSTRUCTOR */

	head = NULL;
	tail = NULL;

	listCount = 0;
}

template <class T>
Deque<T>::Deque(const DNode<T> & d) { /* COPY CONSTRUCTOR */

	/*
	This function merely calls the duplicate() method with the
	head pointer and the head pointer of the list passed in as arguments.
	The node count must also be copied.
	*/
}

template <class T>
Deque<T> Deque<T>::operator=(const DNode<T> &d) { /* = operator */
	
	/*
	Using the destroy() and duplicate functions, this one is fairly straightforward.
	*/
}

template <class T>
Deque<T>::~Deque() { /* DESTRUCTOR */
	/*
	This function should free up all the dynamic memory associated with the deque.
	*/
}

template <class T>
bool Deque<T>::empty() {
	//This method returns a boolean value -- true if the deque is empty, false otherwise.
	//Given the data members in the class, there are three different ways of implementing this function. 
	//Use what seems most obvious to you.
	return true;
}

template <class T>
void Deque<T>::destroy() {
	/*
	This function can be implemented identically to what was done for the linked list assignment.
	This method takes no arguments and returns nothing.
	Its purpose is to free up all of the nodes of the list.
	This function is a utility function which will be used by other member functions.
	Since it is specific to the implementation, it should be declared private.

	The function is implemented with a loop and two pointers. The first pointer is initialized to the head of the list. In the loop, the first pointer points at a node to be freed. But before the node is deleted, the second pointer should be set to point at the next node in the list. After the node is deleted, the first pointer receives the value of the second pointer, in preparation for deleting the next node. This loop should be executed as long as the first pointer points at a node.
	*/
}

template <class T>
void Deque<T>::clear() {

	/*
	This function clears the deque, releasing all of the dynamic memory associated with the deque.
	It makes the deque empty. It calls the destroy() method, clears the head and tail pointers
	and resets the node count.
	*/
}

template <class T>
int Deque<T>::push_front(const T &) {

	/*
	This method takes a reference to a constant piece of data as an argument and returns an integer error code.
	This routine is similar to the insert1 routine of the List class.

	A new node is dynamically created and initialized with the value of the argument.
	If the deque is empty, then both the head and tail pointers should point to the new node.
	If the deque is not empty, then the new node should be inserted at the head of the list.
	The only thing that is different here is that the node that used to be the head of the list should be adjusted so that its previous pointer points at the new node.

	In a doubly linked node insertion remember the heuristic: Set the links in the new node first, and then adjust the links of the neighboring nodes if they exist. Order is very important. Draw diagrams. They can be very helpful.

	In all situations, the count of the number of nodes in the deque should be incremented.
	*/

	return D_EMPTY;
}

template <class T>
int Deque<T>::push_back(const T &) {

	/*
	This method takes a reference to a constant piece of data as an argument and returns an integer error code.

	A new node is dynamically created and initialized with the value of the argument.
	If the deque is empty, then both the head and tail pointers should point to the new node.
	If the deque is not empty, then the new node should be inserted after the node pointed at by the tail pointer. After this insertion, the tail should be updated to point at the new node.

	Don't forget to adjust the count of the number of nodes.
	*/
	return D_EMPTY;
}

template <class T>
int Deque<T>::size() {
	
	/*
	This function simply returns the count of the number of nodes in the deque.
	Since this count is being maintained as part of the deque,
	the nodes do not need to be explicitly counted here.
	*/

	return 0;
}

template <class T>
DNode<T> *duplicate(DNode<T> *source) {

	/*
	The purpose of this utility routine (which should be private) is to make a copy of the deque. It is a recursive function. It takes one argument, a pointer to a DNode. This is the source deque to be copied. The routine should return a pointer to a DNode which is the copy of the list created from the source. This pointer value is also called the destination pointer.

	The stopping condition for this recursive function is the same as it is for most recursive functions involving pointers - a null pointer. If the source pointer is null, the destination pointer should be set to null and the function ends.

	When the source pointer is not null, a new node should be created for the destination pointer, and the data in the new node should be initialized to the data in the source node. Now that the first node has been copied, the rest of the list should be copied. This can be done by a recursive call, passing the next pointers of both the source node.

	There are two differences between this method and the duplicate function of the List class. First, the tail pointer of the deque needs to be set to point to the new node allocated. This should be done before the recursive call. In this way the tail pointer will point to the last node allocated, which will be the last node in the deque when the recursion is finished.

	Secondly, the previous pointers of the nodes must be linked up. This one is difficult to explain, so a code snippet will be given. Before the recursive call the destination pointer points at the new node created. After the recursive call, this new node should be linked to a successor if one exists. That successor must be linked to the new node. The following code will do the trick. Study it to make sure you understand what is happening.
	
	*/
}

template <class T>
int Deque<T>::front(T &value) {

	/*
	This function takes a reference to the deque data type as an argument and returns an integer error code.
	If the list is empty, an appropriate error code is returned.
	Otherwise, the data in the node pointed at by the head pointer is copied into the function argument.
	This function does not change any of the pointers or node count of the deque.
	*/
	return 1;
}

template <class T>
int Deque<T>::back(T &value) {

	/*
	This function takes a reference to the deque data type as an argument and returns an integer error code.
	If the list is empty, an appropriate error code is returned.
	Otherwise, the data in the node pointed at by the tail pointer is copied into the function argument.
	This function does not change any of the pointers or node count of the deque.
	*/
	return 1;
}

template <class T>
int Deque<T>::pop_front() {

	/*
	This function takes no arguments and returns an integer error code.
	If the deque is empty, the appropriate error code is returned.
	Otherwise, the node at the head of the deque is deleted.
	Care must be taken so that the rest of the deque is not lost.
	The node count must also be decremented. If the deque becomes empty, make sure that
	all of the data members of the deque are reset to reflect the state of the deque.
	If the deque is not empty, the node at the head of the list must be given a proper
	value for its link to the previous node.
	*/

	return 1;
}

template <class T>
int Deque<T>::pop_back() {

	/*
	This function takes no arguments and returns an integer error code.
	If the deque is empty, the appropriate error code is returned.
	Otherwise, the node at the tail of the deque is deleted.
	Care must be taken so that the rest of the deque is not lost.
	The node count must also be decremented.
	If the deque becomes empty, make sure that all of the data members of the
	deque are reset to reflect the state of the deque. If the deque is not empty,
	the node at the tail of the list must be given a proper value for its link to the next node.
	*/
	return 1;
}

template <class T>
ostream & operator << (ostream &out, const Deque<T> &d) {

	out << "DEQUE TEST";
	return out;

}