#ifndef LIST_HPP
#define	LIST_HPP

using namespace std;

#include "Node.h"

template <class TYPE>
class List
{
public:
	List();
	~List();

	void			insertFront		(const TYPE &newData);
	void			insertBack		(const TYPE &newData);

	bool			removeFront		(TYPE &);
	bool			removeBack		(TYPE &);
	
	bool			isEmpty			() const;
	void			print			(unsigned int index) const;
	void			getNodes		(unsigned int i, TYPE &whereTo) const;
	void			deleteNode		(const TYPE &deleteItem);
	void			deleteNodeByRef	(int Index);
	bool			changeData		(unsigned int index, TYPE &whereFrom);

	void			popFront		();
	unsigned int	length			() const;

	Node<TYPE> *	getFirst		();
	Node<TYPE> *	getPtrToNode	(int index);

private:
	Node<TYPE>		*first;
	Node<TYPE>		*last;
	Node<TYPE>		*getNewNode(const TYPE &newData);
};
template <class TYPE>
List<TYPE>::List() : first(0), last(0)
{
	/* Empty constructor - functionality in declaration */
}
template <class TYPE>
List<TYPE>::~List()
{
	if(!isEmpty())
	{
		Node<TYPE> *current = first;
		Node<TYPE> *temp;

		while(current != 0)
		{
			temp = current;
			current = current->next;
			delete temp;
		}//end: while
	}//end: if
}
template <class TYPE>
void List<TYPE>::insertFront(const TYPE &newData)
{
	Node<TYPE> *newPtr = getNewNode(newData);
	if(isEmpty())	first = last = newPtr;
	else			{ newPtr->next = first; first = newPtr; }
}
template <class TYPE>
void List<TYPE>::insertBack(const TYPE &newData)
{
	Node<TYPE> *newPtr = getNewNode(newData);
	if(newPtr == NULL) return;
	if(isEmpty()) first = last = newPtr;
	else { last->next = newPtr; last = newPtr; }
}
template <class TYPE>
bool List<TYPE>::removeFront(TYPE &value)
{
	if(isEmpty()) return false;
	else
	{
		Node<TYPE> *temp = first;
		if(first == last)	first = last = 0;
		else				first = first->next;
		value = temp->Data; delete temp;	
	}
	return true;
}
template <class TYPE>
void List<TYPE>::popFront()
{
	if(isEmpty())	return;
	else
	{
		Node<TYPE>			*temp = first;
		if(first == last)	first = last = 0;
		else				first = first->next;
		delete temp;
	}
}
template <class TYPE>
bool List<TYPE>::removeBack(TYPE &value)
{
	if(isEmpty())
		return false;
	else
	{
		Node<TYPE> *temp = last;

		if(first == last)
			first = last = 0;
		else
		{
			Node<TYPE> *current = first;

			while(current->next != last)
				current = current->next;

			last = current;
			current->next = 0;
		}

		value = temp->Data;
		delete temp;
		return true;
	}
}
template <class TYPE>
bool List<TYPE>::isEmpty() const
{
	//Returns TRUE if the list is indeed empty
	return (first == 0);
}
template <class TYPE>
Node<TYPE> *List<TYPE>::getNewNode(const TYPE &newData)
{
	return new Node<TYPE>(newData);
}
template <class TYPE>
void List<TYPE>::print(unsigned int index) const
{
	unsigned int counter = 0;
	if(isEmpty()) return;
	Node<TYPE> *current = first;
	while(current != 0)
	{
		if(counter == index)
		{
		//	cout << current->Data;
		}
		++counter;
		current = current->next;
	}
//	cout << "\n\n";
}
template <class TYPE>
void List<TYPE>::getNodes(unsigned int index, TYPE &whereTo) const
{
	if(isEmpty()) return;
	unsigned int counter; counter = 0; Node<TYPE> *current = first;
	while(current != 0)
	{
		if(counter == index) { whereTo = current->Data; current = NULL; return; }
		current = current->next; ++counter;
	}
}
template <class TYPE>
bool List<TYPE>::changeData(unsigned int index, TYPE &whereFrom)
{
	unsigned int counter;
	Node<TYPE> *current = first;

	if(isEmpty()) return false;
	counter = 0;

	while(current != 0)
	{
		if(counter == index)
		{
			current->Data = whereFrom;
			return true;
		}
		current = current->next;
		++counter;
	}
	return false;
}
template <class TYPE>
unsigned int List<TYPE>::length() const
{
	unsigned int counter; Node<TYPE> *current = first;
	if(isEmpty()) return 0;
	counter = 0;
	while(current != 0) { ++counter; current = current->next; }
	return counter;
}
template <class TYPE>
void List<TYPE>::deleteNode(const TYPE &deleteItem)
{
	Node<TYPE> *current; Node<TYPE> *trailCurrent; bool found = false;
	if(first == NULL) return;
	else
	{
		if(first->Data == deleteItem)
		{
			current = first; first	= first->next;
			if(first == NULL) last = NULL; delete current;
		}
		else
		{
			found = false; trailCurrent = first; current = first->next;
			while((!found) && (current != NULL))
			{
				if(current->Data != deleteItem) { trailCurrent = current; current = current->next; }
				else found = true;
			}
			if(found == true)
			{ trailCurrent->next = current->next; if(last == current) last = trailCurrent; delete current; }
		}
	}
}
template <class TYPE>
void List<TYPE>::deleteNodeByRef(int Index)
{
	Node<TYPE> *current; Node<TYPE> *trailCurrent; int Count = 0;
	if(first == NULL) return;
	else
	{
		if(Count == Index)
		{
			current = first;
			first = first->next;
			if(first == NULL) last = NULL;
			delete current;
		}
		else
		{
			trailCurrent = first; current = first->next;
			while(Count != Index && current != NULL)
			{
				if(Count != Index)
				{
					trailCurrent = current;
					current = current->next;
					Count++;
				}
				else 
				{
					trailCurrent->next = current->next;
					if(last == current) last = trailCurrent;
					delete current;
				}
			}
		}
	}
}
template <class TYPE>
Node<TYPE>* List<TYPE>::getFirst()
{
	return first;
}
template <class TYPE>
Node<TYPE>* List<TYPE>::getPtrToNode(int i)
{
	unsigned int counter;

	if(isEmpty()) return;
	counter = 0; Node<TYPE> *current = first;
	while(current != 0)
	{
		if(counter + 1 == i) return current->next;
		current = current->next;
		++counter;
	}
	return NULL;
}
#endif
/*
#include<iostream>
#include<string>

using namespace std;
using std::string;

template<class Type>
class Node
{
public:
private:
	Type info;
	Node<Type> *link;
};

template<class Type>
class linkedList
{
public:
	linkedList() { first = last = NULL; }
	linkedList(const linkedList<Type>& other);
	~linkedList();
	const linkedList& operator= (const linkedList<Type>&);
	void initialList() { dstroyList(); }
	bool isEmpty() { return (first == NULL); }
	bool isFull()  { return false; }
	void print();
	unsigned short length();
	void destroyList();
	void retrieveFirst(Type& firstElement) { firstElement = first->info; }
	void search (const Type& item);
	void insertFirst (const Type& item);
	void insertLast (const Type& item);
	void deleteNode (const Type& item);
private:
	Node<Type> *first;
	Node<Type> *last;
};

template<class Type>
void linkedList<Type>::destroyList()
{
	Node<Type> *temp;
	while (first != NULL)
	{
		temp = first;
		first = first->link;
		delete temp;
	}
	last = NULL;
}

template<class Type>
void linkedList<Type>::print()
{
	Node<Type> *current;
	current = first;
	while (current != NULL)
	{
		cout << current->info << " ";
		current = current->link;
	}
}

template<class Type>
unsigned short linkedList<Type>::length()
{
	unsigned short count = 0;
	Node<Type> *current;
	current = first;
	while (current != NULL)
	{
		count++;
		current = current->link;
	}
	return count;
}

template<class Type>
void linkedList<Type>::search (const Type& item)
{
	Node<Type> *current;
	bool found;
	if (first == NULL) cout << "The list is empty." << endl;
	else 
	{
		current = first;
		found = false;
		while (!found && current != NULL)
		{
			if (current->info == item) found = true;
			else current = current->link;
		}

		if (found) cout << "The item is in the list." << endl;
		else cout << "Item in not in the list." << endl;
	}
}

template<class Type>
void linkedList<Type>::insertFirst(const Type& item)
{
	Node<Type> *newNode;
	newNode = new Node<Type>;
	newNode->info = item;
	newNode->link = first;
	first = newNode;
	if (last == NULL) last = newNode;
}

template<class Type>
void linkedList<Type>::insertLast(const Type& item)
{
	Node<Type> *newNode;
	newNode = new Node<Type>;
	newNode->info = item;
	newNode->link = NULL;

	if (first == NULL) first = last = newNode;
	else 
	{
		last->link = newNode;
		last = newNode;
	}
}

template<class Type>
void linkedList<Type>::deleteNode(const Type& item)
{
	Node<Type> *current;
	Node<Type> *trailCurrent;
	bool found;

	if (first == NULL) cout << "The list is empty\n";

	else
	{
		if (first->info == item)
		{
			current = first;
			first = first->link;
			if (first == NULL) last = NULL;
			delete current;
		}
		else 
		{
			found = false;
			trailCurrent = first;
			current = first->link;
			while ((!found) && (current != NULL))
			{
				if (current->info != item)
				{
					trailCurrent = current;
					current = current->link;
				}
				else found = true;
			}

			if (found)
			{
				trailCurrent->link = current->link;
				if (last == current) last = trailCurrent;
				delete current;
			}

			else cout << "Item to be deleted is not in the list" << endl;
		}
	}
}

template<class Type>
linkedList<Type>::~linkedList()
{
	Node<Type> *temp;
	while (first != NULL)
	{
		temp = first;
		first = first->link;
		delete temp;
	}

	last = NULL;
}

template<class Type>
linkedList<Type>::linkedList (const linkedList<Type>& other)
{
	Node<Type> *newNode;
	Node<Type> *current;

	if (other.first == NULL) first = last = NULL;

	else 
	{
		current = other.first;
		first = new Node<Type>;
		first->info = current->info;
		first->link = NULL;

		last = first;
		current = current->link;

		while (current != NULL)
		{
			newNode = new Node<Type>;
			newNode->info = current->info;
			newNode->link = NULL;

			last->link = newNode;
			last = newNode;
			current = current->link;
		}
	}
}

template<class Type>
const linkedList<Type>& linkedList<Type>::operator = (const linkedList<Type>& other)
{
	Node<Type> *newNode;
	Node<Type> *current;

	if(this != &other)
	{
		if (first != NULL) destroList();
		if (other.first == NULL) first = last = NULL;
		else 
		{
			current = other.first;
			first = new Node<Type>;
			first->info = current->info;
			first->link = NULL;
			last = first;
			current = current->link;

			while (current != NULL)
			{
				newNode = new Node<Type>;
				newNode->info = current->info;
				newNode->link = NULL;
				last->link = newNode;
				last = newNode;
				current = current->link;
			}
		}
	}
	 
	return *this;
}

//----------------------------------------------------------------------
//----------------------------------------------------------------------

template<class Type>
class orderedList : public linkedList<Type>
{
public:
	void search (const Type& item);
	void insertNode (const Type& item);
	void deleteNode (const Type& item);
	void printReverse () const;
private:
	void reversePrint (Node<Type> *current) const;
};


int main()
{

	return 0;
}

*/