#include<cassert>

template <class T> class LinkIterator;
template <class T> class LinkList;

template <class T>
class LinkNode
{
	friend class LinkIterator<T>;
	friend class LinkList<T>;



public://
	//class member initilization list
	LinkNode() : m_next(0), m_previous(0)
	{

	}

	T m_data;
	LinkNode *m_next;
	LinkNode *m_previous;
};

template <class T>
class LinkIterator
{
public://
	LinkNode<T> *m_node;

public:
	LinkIterator()
	{
		m_node = NULL;
	}

	~LinkIterator()
	{

	}

	void operator= (LinkNode<T> *node)
	{
		m_node = node;
	}

	T &operator*()
	{
		assert(m_node != NULL);
		return m_node->m_data;
	}

	void operator++()
	{
		assert (m_node !=NULL);
		m_node = m_node->m_next;
	}
	void operator++(int)
	{
		assert(m_node !=NULL);
		m_node = m_node->m_next;
	}

	void operator--()
	{
		assert(m_node != NULL);
		m_node = m_node->m_previous;
	}

	void operator--(int)
	{
		assert(m_node != NULL);
		m_node = m_node->m_previous;
	}

	bool operator != (LinkNode<T> *node)
	{
		return(m_node != node);
	}
	bool operator == (LinkNode<T> *node)
	{
		return (m_node == node);
	}
};

template<class T>
class LinkList
{
private:
	int m_size;

	LinkNode<T> *m_root;
	LinkNode<T> *m_lastNode;

public:
	int counter;
	LinkList()
		:m_size(0), m_root(NULL), m_lastNode(NULL)
	{
	}
	~LinkList()
	{
		while (m_root)
		{
			Pop();
		}
	}

	LinkNode<T> *Begin()
	{
		assert (m_root !=NULL);
		return m_root;
	}
	LinkNode<T> *End()
	{
		return NULL;
	}
	LinkNode<T> *Last()
	{
		return m_lastNode;
	}
	int GetSize()
	{
		return m_size;
	}

	void Push(T newData, LinkIterator<T> position)
	{
		LinkNode<T> *node = new LinkNode<T>;

		//LinkList<int> lList;

		assert (node != NULL);

		node -> m_data = newData;
		node ->m_next = NULL;
		node->m_previous = NULL;

		//position = lList.Begin();

		if(position.m_node->m_previous == NULL)					// First and last nodes checked
		{
			Push_Front(newData);
		}else if(position.m_node == m_lastNode)
		{
			Push(newData);
		}else
		{
			node->m_next = position.m_node;
			node ->m_previous = position.m_node->m_previous;
			position.m_node ->m_previous = node;

			position--;
			position--;
			position.m_node->m_next = node;
		}



		//m_lastNode = node;

		m_size++;
	}

	void Push(T newData)        //old
	{
		LinkNode<T> *node = new LinkNode<T>;


		assert (node != NULL);

		node -> m_data = newData;
		node ->m_next = NULL;
		node->m_previous = NULL;

		if ( m_lastNode != NULL)
		{
			m_lastNode ->m_next = node;
			node->m_previous = m_lastNode;
		}
		else
		{
			m_root = node;
		}

		m_lastNode = node;

		m_size++;
	}


	void Push_Front( T newData)
	{
		LinkNode<T> *node = new LinkNode<T>;

		assert (node != NULL);

		node ->m_data = newData;
		node ->m_next = NULL;
		node ->m_previous = node;

		if (m_root !=NULL)
		{
			node ->m_next = m_root;
			m_root->m_previous = node;
			m_root = node;
		}
		else
		{
			m_root = node;
			m_lastNode = node;
		}
		m_size++;
	}

	void Pop()
	{
		assert (m_root != NULL);

		if (m_root ->m_next ==NULL)
		{
			delete m_root;
			m_root = NULL;
		}
		else
		{
			LinkNode<T> *prevNode = m_lastNode->m_previous;

			prevNode->m_next = NULL;
			delete m_lastNode;
			prevNode ->m_next=NULL;
			m_lastNode=prevNode;
		}
		m_size = (m_size = 0 ? m_size:m_size-1);
	}

		void Pop( LinkIterator<T> position)											//NEW
	{
		assert (m_root != NULL);

		if (position.m_node->m_previous == NULL)
		{
			delete m_root;
			m_root = NULL;
		}
		else
		{
			LinkNode<T> *prevNode = m_lastNode->m_previous;

			prevNode->m_next = NULL;
			delete m_lastNode;
			prevNode ->m_next=NULL;
			m_lastNode=prevNode;
		}
		m_size = (m_size = 0 ? m_size:m_size-1);
	}

	void Pop_Front()
	{
		assert (m_root !=NULL);

		LinkNode <T> *temp = m_root;

		m_root = m_root -> m_next;

		if(m_root != NULL)
		{
			m_root->m_previous = NULL;
		}

		delete temp;
		m_size = (m_size = 0 ? m_size : m_size-1);
	}
};