#ifndef DLL_H
#define DLL_H
#include <iostream>

template <class T>
class DLL
{

	struct Node
	{
		T element;
		Node* next;
		Node* prev;
	};

	//head pointer which points to the first node in the SLL
	Node* m_head;
	Node* m_tail;

public:
	DLL(void);
	~DLL(void);

	void addHead( T value );
	 
	//removes a head
	void removeHead();
	//clears a node completely
	void Clear();

	//Prints to screen
	void Print();

	//finds a elemnet
	bool Find( T value );

	//find and remove a element
	bool FindAndRemove( T value );

	//adds the tail
	void addTail( T value);

	//removes the tail
	void RemoveTail();

	//insert a node
	void insert( T value );

	//sort the value
	void LinearSort();

};
#endif

template <class T> DLL<T>::DLL(void)
{
	m_head = 0;
	m_tail = 0;
}
template <class T> DLL<T>::~DLL(void)
{

}

//adds a head
template <class T> void DLL<T>::addHead( T value )
{
	if(!m_head)
	{
		// Dynamically create a new node
		Node* n = new Node;

		//Set N to value to passed node into fuction
		n->element = value;

		// Set the pointer to the current head
		n->next = 0;

		n->prev = 0;

		// Point head to new headnode
		m_head = n;
		m_tail = n;
	}
	else
	{
		// Dynamically create a new node
		Node* n = new Node;

		//Set N to value to passed node into fuction
		n->element = value;

		// Set the pointer to the current head
		n->next = m_head;
		m_head->prev = n;
		n->prev = 0;

		// Point head to new headnode
		m_head = n;
	}

}

//removes a head
template <class T> void DLL<T>::removeHead()
{
	// create a pointer (tmp) that points to head
	Node* tmp = m_head;

	// move head to tmps next node
	m_head = tmp->next; //alternatively, m_head = m_head->next

	//delete tmp's node
	m_head->prev = 0;

	delete tmp;

}
//clears a node completely
template <class T> void DLL<T>::Clear()
{
	while(m_head)
	{

		// create a pointer (tmp) that points to head
		Node* tmp = m_head;

		// move head to tmps next node
		m_head = tmp->next; //alternatively, m_head = m_head->next

		//delete tmp's node
		delete tmp;
	}
}

//Prints to screen
template <class T> void DLL<T>::Print()
{
	Node* tmp = m_head;
	while(tmp)
	{
		cout << tmp->element << " <-> ";

		tmp = tmp->next;
	}
	cout << "X\n";

	//delete tmp
	delete tmp;
}

//finds a elemnet
template <class T> bool DLL<T>::Find( T value )
{
	Node* tmp = m_tail;
	while(tmp)
	{
		if(tmp->element == value)
		{
			delete tmp;
			return true;
		}

		tmp = tmp->next;
	}
	return false;
}

//find and remove a element
template <class T> bool DLL<T>::FindAndRemove( T value )
{
	if(value == m_head->element)
	{
		removeHead();
		return true;
	}

	Node* tmp = m_head;

	while(tmp)
	{
		if(tmp->element == value)
		{

			tmp->prev->next = tmp->next;
			tmp->next->prev = tmp->prev;

			delete tmp;

			return true;
		}
		tmp = tmp->next;

	}
	return false;
}

//adds the tail
template <class T> void DLL<T>::addTail( T value)
{

	if(!m_tail)
	{
		// Dynamically create a new node
		Node* n = new Node;

		//Set N to value to passed node into fuction
		n->element = value;

		// Set the pointer to the current head
		n->next = 0;

		n->prev = 0;

		// Point head to new headnode
		m_head = n;
		m_tail = n;
	}
	else
	{
		// Dynamically create a new node
		Node* n = new Node;

		//Set N to value to passed node into fuction
		n->element = value;

		// Set the pointer to the current head
		n->prev = m_tail;
		m_tail->next = n;
		n->next = 0;

		// Point head to new headnode
		m_tail = n;
	}

}

//removes the tail
template <class T> void DLL<T>::RemoveTail()
{
	// create a pointer (tmp) that points to head
	Node* tmp = m_head;

	// move head to tmps next node
	m_tail->next = 0;
	m_tail->prev = tmp->prev;

	//delete tmp's node
	delete tmp;
}

//insert a node
template <class T> void DLL<T>::insert( T value )
{
	//2 parameters, the value you store in the SLL, 
	//and the value inside of a node to insert after 
	//a node containing it, if that node is not found, call addTail()

	if(!m_head)
		addHead(value);
	else
	{
		Node* tmp = m_head;
		if(!tmp->next)
			addTail(value);
		else
		{
			while(tmp->element > value && tmp->next)
			{
				tmp = tmp->next;
				if(value > tmp->element)
				{
					Node* add = new Node;
					add->element = value;
					tmp->prev->next = add;
					add->prev = tmp->prev;
					add->next = tmp;
					tmp->prev = add;

				}
				else if(!tmp->next)
				{
					addTail(value);
					break;
				}
			}
		}
	}
}

//sort the value
template <class T> void DLL<T>::LinearSort()
{
	Node* tmp = m_head->next;
	Node* tmp2 = tmp->prev;

	bool flag = false;
	while(tmp)
	{

		if((tmp2->element) > (tmp->element))
		{
			int swap = tmp2->element;

			tmp2->element = tmp->element;
			tmp->element = swap;

			flag = true;
		}
		tmp2 =  tmp;		
		tmp = tmp->next;

		if(flag == true  && !tmp)
		{
			tmp = m_head->next;
			tmp2 = tmp->prev;
			flag = false;
		}

	}

}