#ifndef List_H_
#define List_H_


template <typename T>
struct Node
{
	Node(const T &);
	Node()
		:data(T()), next(0)
	{}
	Node *next;
	T data;
};

template <typename T>
Node<T>::Node(const T &x)
:next(0), data(x)
{}


template <typename T>
class List
{
public:
	class Iterator
	{
	public:
		Iterator(List& l)
			:list(l), node(l.tail)
		{
			
		}
		T& Current() { return node ->data; }
		void First()
		{
			node = list.tail;
		}
		bool IsDone()
		{
			if (node == NULL)
			{
				return true;
			}
			return false;
		}
		void Next()
		{
			node = node ->next;
		}
	private:
		List& list;
		Node<T>* node;
	};
public:
	List();
	List(const List& l);
	const List& operator =(const List& l);
	bool operator ==(const List& l);
	~List();
	bool IsEmpty() const;
	void PushBack(const T& x);
	void PushFront(const T& x);
	T Top() const { return head ->data; }
	int Size(){ return _count; }
	T Pop();
	void Clear();
private:
	Node<T> *head;
	Node<T> *tail;
	int _count;
};

template <typename T>
List<T>::List()
:head(0), tail(0), _count(0)
{}

template <typename T>
List<T>::List(const List& l)
{
	if (l.IsEmpty())
	{
		head = NULL;
		tail = head;
		_count = 0;
		return;
	}
	head = new Node<T>(*l.tail);
	tail = head;
	Node<T>* temp = l.tail ->next;
	_count = l._count;

	while (temp != NULL)
	{
		head->next = new Node<T>(*temp);
		head = head ->next;
		temp = temp ->next;
	}
}

template <typename T>
const List<T>& List<T>::operator =(const List& l)
{
	if (&l != this)
	{
		if (l.IsEmpty())
		{
			return *this;
		}
		head = new Node<T>(l.Top());
		tail = head;
		Node<T>* temp = l.tail;
		_count = l._count;
		while (temp != NULL)
		{
			temp = temp ->next;
			head ->next = new Node<T>(temp->data);
			head = head ->next;
		}
	}
	return *this;
}


template <typename T>
List<T>::~List()
{
	Clear();
}

template <typename T>
void List<T>::PushBack(const T &x)
{
	++_count;
	if (head == NULL)
	{
		head = new Node<T>(x);
		tail = head;
	}
	else
	{
		head ->next = new Node<T>(x);
		head = head ->next;
	}
}

template <typename T>
void List<T>::PushFront(const T& x)
{
	++_count;
	if (head == NULL)
	{
		head = new Node<T>(x);
		tail = head;
	}
	else
	{
		Node<T>* temp = tail;
		tail = new Node<T>(x);
		tail->next = temp;
	}
}


template <typename T>
T List<T>::Pop()
{
	--_count;
	assert(tail != NULL);
	Node<T> *temp = tail;
	tail = tail ->next;
	T t = temp ->data;
	delete temp;
	return t;
	
}



template <typename T>
void List<T>::Clear()
{
	_count = 0;
	Node<T> *temp = tail;
	while (tail != NULL)
	{
		tail = tail ->next;
		delete temp;
		temp = tail;
	}
	tail = NULL;
	head = tail;
}


template <typename T>
bool List<T>::IsEmpty() const
{
	return tail == NULL;
}

template <typename T>
bool List<T>::operator ==(const List& l)
{
	if (l._count != _count)
	{
		return false;
	}

	Node<T>* t1 = tail;
	Node<T>* t2 = l.tail;

	while (t1 != head)
	{
		if (t1 ->data != t2 ->data)
		{
			return false;
		}
		t1 = t1 ->next;
		t2 = t2 ->next;
	}
	return true;
}

#endif