#ifndef SORTED_LIST_H
#define SORTED_LIST_H

#include<iostream>

using std::ostream;
using std::istream;

template<class T>
struct SNode
{
	SNode(const T& NewItem);
	~SNode();

	T* pItem;
	SNode<T>* pNext;
	SNode<T>* pPrevious;
};

template<class T>
SNode<T>::SNode(const T& NewItem)
{
	pNext = NULL;
	pPrevious = NULL;
	pItem = new T(NewItem);
}

template<class T>
SNode<T>::~SNode()
{
	pNext = NULL;
	pPrevious = NULL;

	if (pItem != NULL)
	{
		delete pItem;
	}
}


//Copy Constructer required for type T
//Operator == required for type T
//Operator == required that takes an r-value of keyType

template<class T, class KeyType>
class CSortedList
{
	friend ostream &operator<<( ostream & output, const CSortedList<T,KeyType>& List);
	friend istream &operator>>( istream & input, CSortedList<T,KeyType>& List);

	public:
		CSortedList();
		~CSortedList();

		long Count() const;
		bool IsEmpty() const;
		bool Contains(const KeyType& SearchItem);

		void Insert(const T& NewItem);
		void Delete(const KeyType& ItemToRemove);

	private:
		SNode<T>* m_pFront;
		long m_Count;

		void DeleteAll();
		void DeleteFront();
};

template<class T, class KeyType>
ostream &operator<<( ostream & output, const CSortedList<T,KeyType>& List)
{
	SNode<T>* pCurrent = List.m_pFront;


	while(pCurrent != NULL)
	{
		if (pCurrent->pItem != NULL)
		{
			output << *(pCurrent->pItem);
		}

		pCurrent = pCurrent->pNext;
	}

	return output;
}

template<class T, class KeyType>
istream &operator>>( istream & input, CSortedList<T,KeyType>& List)
{
	T Item;
	
	List.DeleteAll();

	while(!input.eof())
	{
		input >> Item;
		List.Insert(Item);
	}

	return input;
}

template<class T, class KeyType>
CSortedList<T,KeyType>::CSortedList()
{
	m_pFront = NULL;
	m_Count = 0;
}

template<class T, class KeyType>
CSortedList<T,KeyType>::~CSortedList()
{
	DeleteAll();
}

template<class T, class KeyType>
long CSortedList<T,KeyType>::Count() const
{
	return m_Count;
}

template<class T, class KeyType>
bool CSortedList<T,KeyType>::IsEmpty() const
{
	return (m_Count == 0);
}

template<class T, class KeyType>
void CSortedList<T,KeyType>::DeleteAll()
{
	while(m_pFront != NULL)
	{
		DeleteFront();
	}
}

template<class T, class KeyType>
void CSortedList<T,KeyType>::DeleteFront()
{
	if (m_pFront != NULL)
	{
		SNode<T>* pNodeToDelete = m_pFront;
	
		m_pFront = m_pFront->pNext;
		
		if (m_pFront != NULL)
		{
			m_pFront->pPrevious = NULL;
		}

		delete pNodeToDelete;
		pNodeToDelete = NULL;

		m_Count--;
	}
}

template<class T, class KeyType>
void CSortedList<T,KeyType>::Delete(const KeyType& ItemToRemove)
{
	SNode<T>* pCurrent = m_pFront;

	bool NodeDeleted = false;

	while(pCurrent != NULL && !NodeDeleted)
	{
		if (pCurrent->pItem != NULL)
		{
			if(*(pCurrent->pItem) == ItemToRemove)
			{
				if (pCurrent->pPrevious != NULL)
				{
					pCurrent->pPrevious->pNext = pCurrent->pNext;
				}

				if (pCurrent->pNext != NULL)
				{
					pCurrent->pNext->pPrevious = pCurrent->pPrevious;
				}

				delete pCurrent;
				pCurrent = NULL;

				NodeDeleted = true;
				
				m_Count--;
			}
		}

		if (!NodeDeleted)
		{
			pCurrent = pCurrent->pNext;
		}
	}

	if (!NodeDeleted)
	{
		throw("Delete Failed, unable to find item.");
	}
}

template<class T, class KeyType>
void CSortedList<T,KeyType>::Insert(const T& NewItem )
{
	SNode<T>* pCurrent = m_pFront;
	SNode<T>* pNewNode = new SNode<T>(NewItem);

	bool NodeAdded = false;

	if (m_pFront == NULL)
	{
		m_pFront = pNewNode;
		NodeAdded = true;
	}

	while(!NodeAdded)
	{
		if(*(pCurrent->pItem) == NewItem)
		{
			throw("Already in list.");
			NodeAdded = true;
		}
		else if(*(pCurrent->pItem) < NewItem && pCurrent->pNext == NULL)
		{
			//add new node after current node
			pNewNode->pNext = pCurrent->pNext;
			pNewNode->pPrevious = pCurrent;
			pCurrent->pNext = pNewNode;
			NodeAdded = true;
		}
		else if(*(pCurrent->pItem) > NewItem)
		{
			//add new node before current node
			if (pCurrent == m_pFront)
			{
				m_pFront = pNewNode;
			}

			pNewNode->pNext = pCurrent;
			pNewNode->pPrevious = pCurrent->pPrevious;
			
			if (pCurrent->pPrevious != NULL)
			{
				pCurrent->pPrevious->pNext = pNewNode;
			}
			
			pCurrent->pPrevious = pNewNode;

			NodeAdded = true;
		}
		else
		{
			pCurrent = pCurrent->pNext;
		}
	}

	if (NodeAdded)	
	{
		m_Count++;
	}
	else
	{
		throw("Insert Failed.");
	}
}

template<class T, class KeyType>
bool CSortedList<T,KeyType>::Contains(const KeyType& ItemToFind)
{
	SNode<T>* pCurrent = m_pFront;

	bool NodeFound = false;

	while(pCurrent != NULL && !NodeFound)
	{
		if (pCurrent->pItem != NULL)
		{
			if(*(pCurrent->pItem) == ItemToFind)
			{
				NodeFound = true;
			}
		}

		pCurrent = pCurrent->pNext;
	}

	return NodeFound;
}

#endif