#ifndef DOUBLE_LIST_H
#define DOUBLE_LIST_H

/*****************************************
 * UW User ID:  pagunnew
 * Submitted for ECE 250
 * Department of Electrical and Computer Engineering
 * University of Waterloo
 * Calender Term of Submission:  Winter 2011
 *
 * By submitting this file, I affirm that
 * I am the author of all modifications to
 * the provided code.
 *****************************************/

#include "ece250.h"
#include "Double_node.h"
#include "Exception.h"

template <typename Object>
class Double_list {
	private:
		Double_node<Object> *list_head;
		Double_node<Object> *list_tail;
		int node_count;

	public:
		Double_list();
		Double_list( const Double_list & );
		~Double_list();

		Double_list &operator = ( const Double_list & );

		// Accessors

		int size() const;
		bool empty() const;

		Object front() const;
		Object back() const;

		Double_node<Object> *head() const;
		Double_node<Object> *tail() const;

		int count( const Object & ) const;

		// Mutators

		void push_front( const Object & );
		void push_back( const Object & );

		Object pop_front();
		Object pop_back();

		int erase( const Object & );

	// Friends

	template <typename T>
	friend std::ostream &operator << ( std::ostream &, const Double_list<T> & );
};

template <typename Object>
Double_list<Object>::Double_list():list_head(0), list_tail(0), node_count(0) {
	// empty constructor
	// This constructor sets all member variables to 0.
}

template <typename Object>
Double_list<Object>::Double_list( const Double_list<Object> &list ):list_head(0), list_tail(0), node_count(0) {
    // Copy constructor
	*this = list;
}

template <typename Object>
Double_list<Object>::~Double_list<Object>() {
    // Destructor
    // Pop the front until the list is empty
    while ( !empty() )
    {
	 	 pop_front();
    }
}

template <typename Object>
Double_list<Object> &Double_list<Object>::operator = ( const Double_list<Object> &rhs ) {
     // Assignment Operator

	 // Make sure the list isn't linked to itself
	 if ( &rhs == this ) {
	 	 return *this;
	 }

     // Clear the list
	 while ( !empty() ) {
	 	 pop_front();
	 }
     // The list is empty, and is not ready to become rhs

	 // If rhs is empty we are done
	 if ( rhs.empty() ) {
	 	 return *this;
	 }

     // Copy all the nodes over, by pushing the next node to the back of the list.
	 Double_node<Object> *ptr = rhs.head();
	 while(ptr != 0)
     {
        push_back(ptr->retrieve() );
        ptr = ptr->next();
     }

	return *this;
	return *this;
}

template <typename Object>
int Double_list<Object>::size() const {
	// Returns the number of items in the list
	return node_count;
}

template <typename Object>
bool Double_list<Object>::empty() const {
    // Returns true if the list is empty, false otherwise
	return (list_head == 0);
}

template <typename Object>
Object Double_list<Object>::front() const {
    // Returns the object stored in the node pointed to by the head pointer
	// This function throws a underflow if the list is empty
	if (empty())
	{
	    throw underflow();
	}

	return head()->retrieve();
}

template <typename Object>
Object Double_list<Object>::back() const {
    // Returns the object stored in the node pointed to by the tail pointer
	// This function throws a underflow if the list is empty
	if (empty())
	{
	    throw underflow();
	}
	return tail()->retrieve();
}

template <typename Object>
Double_node<Object> *Double_list<Object>::head() const {
	// Returns the head pointer
	return list_head;
}

template <typename Object>
Double_node<Object> *Double_list<Object>::tail() const {
    // Returns the tail pointer
	return list_tail;
}

template <typename Object>
int Double_list<Object>::count( const Object &obj ) const {
	// Returns 1 if the argument is stored by one of the nodes in the linked list and zero otherwise
	for (Double_node<Object> *ptr = head(); ptr!=0; ptr=ptr->next() )
	{
	    if (ptr->retrieve() == obj)
	    {
	        return 1;
	    }
	}
	return 0;
}

template <typename Object>
void Double_list<Object>::push_front( const Object &obj ) {
    // Creates a new Double_node<Object> storing the argument, the next pointer of which is set to
	// the current head pointer. The currect head pointer's previous node is set to the new node.
	// The head pointer is set to this new node. If the list was origionally
	// empty, the tail pointer is set to point to the new node

    Double_node<Object> *new_node;

    // List is empty
    if (size() == 0)
    {
        list_head = new Double_node<Object>(obj, 0, 0);
        list_tail = list_head;
    }
    else
    {
        new_node = new Double_node<Object>(obj, 0, 0);
        // Update pointers
        list_head->previous_node = new_node;
        new_node->next_node = list_head;
        // Set head as new node
        list_head = new_node;
    }

	node_count++;
}

template <typename Object>
void Double_list<Object>::push_back( const Object &obj ) {
    // Creates a new Double_node<Object> storing the argument, the next pointer of which is set to
	// null, and the previous pointer is set to the tail pointer.
	// The head pointer is set to this new node. If the list was origionally empty.

    Double_node<Object> *new_node;

    // List is empty
    if (size() == 0)
    {
        list_tail = new Double_node<Object>(obj, 0, 0);
        list_head = list_tail;
    }
    else
    {
        new_node = new Double_node<Object>(obj, 0, 0);
        // Update pointers
        list_tail->next_node = new_node;
        new_node->previous_node = list_tail;
        // Set tail to the new node
        list_tail = new_node;
    }

	node_count++;
}

template <typename Object>
Object Double_list<Object>::pop_front() {
    // Delete the node at the front of the linked list and, as necessary, update the head and tail pointers.
	// Return the object stored in the node being popped. Throw an underflow exception if the list is empty.

	// Check if linked list is empty
	if  (empty())
	{
	    throw underflow();
	}

	Object temp = front();
	Double_node<Object> *ptr = head();

	// If there is only 1 element left
	if (size() == 1)
	{
	    // List is now empty
        list_head = 0;
        list_tail = 0;
	}
	else
	{
	    // Update pointers
	    list_head = head()->next();
	    list_head->previous_node = 0;
	}
	delete ptr;

    // Update node_count
    node_count = node_count -1;

	return temp;
}

template <typename Object>
Object Double_list<Object>::pop_back() {
    // Delete the node at the back of the linked list and, as necessary, update the head and tail pointers.
	// Return the object stored in the node being popped. Throw an underflow exception if the list is empty.

	// Check if linked list is empty
	if  (empty())
	{
	    throw underflow();
	}

	Object temp = back();
	Double_node<Object> *ptr = tail();

	// If there is only 1 element left
	if (size() == 1)
	{
	    // List is now empty
        list_head = 0;
        list_tail = 0;
	}
	else
	{
	    // Update pointers
	    list_tail = tail()->previous();
	    list_tail->next_node = 0;
	}
	delete ptr;

    // Update node_count
    node_count = node_count -1;

	return temp;
}

template <typename Object>
int Double_list<Object>::erase( const Object &obj ) {
	// Delete the first node in the linked list which contains the object equal to the argument.
	// Updates the head and tail pointers and the next pointer of any other node within the list.
	// Returns 1 if a node was deleted and 0 otherwise.

	// Check if the head matches the object that needs to be deleted. If so pop the front
	if (front() == obj)
	{
        pop_front();
        return 1;
	}
    // Check if the tail matches the object that needs to be deleted. If so pop the back
	if(back() == obj)
	{
	    pop_back();
	    return 1;
	}
    else
    {
        Double_node<Object> *ptr = head();
        // Iterate through nodes
        while(ptr != 0)
        {
            // Assign pointers to the next 2 nodes, so we have 3 in a row
            Double_node<Object> *check = ptr->next();
            Double_node<Object> *anext = check->next();
            if(check->retrieve() == obj)
            {
                // If a match point around the middle one (check)
                ptr->next_node = check->next();
                anext->previous_node = check->previous();
                delete check;
                return 1;
            }
            ptr = ptr->next();
        }
    }
	return 0;
}

// You can modify this function however you want:  it will not be tested

template <typename T>
std::ostream &operator << ( std::ostream &out, const Double_list<T> &list ) {
	out << "head";

	for ( Double_node<T> *ptr = list.head(); ptr != 0; ptr = ptr->next() ) {
		out << " -> " << ptr->retrieve();
	}

	out << " -> 0" << std::endl << "tail";

	for ( Double_node<T> *ptr = list.tail(); ptr != 0; ptr = ptr->previous() ) {
		out << " -> " << ptr->retrieve();
	}

	out << " -> 0";

	return out;
}

// Is an error showing up in ece250.h or elsewhere?
// Did you forget a closing '}' ?

#endif