//-----------------------------------------------------------------------------
// Заголовочный файл DList.h
//-----------------------------------------------------------------------------
template<class T> class DListIterator; // объявление класса

template<class T>
class DListNode
{
public:
	T data;
	DListNode<T>* next;
	DListNode<T>* previous;
};
	
template <class T>
class DLinkedList
{
public:
	DListNode<T>* head;
	DListNode<T>* tail;
	int count;
	
	DLinkedList ();
	~DLinkedList();

	void PushBack(T);
	void PushFront(T);
	void PopFront();
	void PopBack();
	void Remove (DListIterator<T>&);
	void Insert (DListIterator<T>&, T);
};
	
template<class T>
class DListIterator
{
public:
	DListNode<T>* node;

	DListIterator(DListNode<T>*);
	DListIterator();
	void Forward();
	void Backward();
	bool Valid();
};

template<class T>
DLinkedList<T>::DLinkedList () : head(NULL), tail(NULL), count(0)	{}

template<class T>
DLinkedList<T>::~DLinkedList()
{
	DListNode<T>* temp;
	while (head != NULL)
	{
		temp = head->next;
		delete head;
		head = temp;
	}
}
	
// Добавление элемента в конец списка.
template<class T>
void DLinkedList<T>::PushBack(T d)
{
	if (count > 0)
	{
		DListNode<T>* temp = new DListNode<T>;
		temp->next = NULL;
		temp->previous = tail;
		temp->data = d;
		tail->next = temp;
		tail = temp;
		count++;
	}
	else if (count == 0)
	{
		DListNode<T>* temp = new DListNode<T>;
		temp->next = NULL;
		temp->previous = NULL;
		temp->data = d;
		head = tail = temp;
		count++;
	}
}
	
// Добавление элемента в начало списка
template<class T>
void DLinkedList<T>::PushFront(T d)
{
	if (count > 0)
	{
		DListNode<T>* temp = new DListNode<T>;
		temp->next = head;
		temp->previous = NULL;
		temp->data = d;
		head->previous = temp;
		head = temp;
		count++;
	}
	else if (count == 0)
	{
		DListNode<T>* temp = new DListNode<T>;
		temp->next = NULL;
		temp->previous = NULL;
		temp->data = d;
		head = tail = temp;
		count++;
	}
}
	
// Удаление элемента из начала списка.
template<class T>
void DLinkedList<T>::PopFront()
{
	if (count == 1)
	{
		delete head;
		head = tail = NULL;
		count--;
	}
	else if (count == 2)
	{
		delete head;
		tail->previous = NULL;
		head = tail;
		count--;
	}
	else if (count > 2)
	{
		DListNode<T>* temp = head->next;
		delete head;
		head = temp;
		head->previous = NULL;
		count--;
	}
}
	
// Удаление элемента из конца списка.
template<class T>
void DLinkedList<T>::PopBack()
{
	if (count == 1)
	{
		delete tail;
		head = tail = NULL;
		count--;
	}
	else if (count == 2)
	{
		delete tail;
		head->next = NULL;
		tail = head;
		count--;
	}
	else if (count > 2)
	{
		DListNode<T>* temp = tail->previous;
		delete tail;
		tail = temp;
		tail->next = NULL;
		count--;
	}
}
	
// Вставка нового элемента в список.
template<class T>
void DLinkedList<T>::Insert (DListIterator<T>& itr, T d)
{
	if (count == 0)
	{
		DListNode<T>* temp = new DListNode<T>;
		head = tail = temp;
		head->next = NULL;
		head->previous = NULL;
		head->data = d;
		itr.node = head;
		count++;
	}
	else if (count == 1 && itr.Valid())
	{
		DListNode<T>* temp = new DListNode<T>;
		head->next = temp;
		temp->previous = head;
		temp->next = NULL;
		temp->data = d;
		tail = itr.node = temp;
		count++;
	}
	else if (count > 1 && itr.Valid())
	{
		if (itr.node == tail)
		{
			DListNode<T>* temp = new DListNode<T>;
			temp->previous = itr.node;
			temp->data = d;
			temp->next = NULL;
			tail->next = temp;
			tail = itr.node = temp;
		}
		else
		{
			DListNode<T>* temp = new DListNode<T>;
			DListNode<T>* next = itr.node->next;
			DListNode<T>* prev = itr.node;
			temp->next = next;
			temp->previous = prev;
			temp->data = d;
			next->previous = temp;
			prev->next = temp;
			itr.node = temp;
		}
		count++;
	}
}
	
// Удаление элемента из списка.
template <class T>
void DLinkedList<T>::Remove (DListIterator<T>& itr)
{
	if (count == 1)
	{
		delete head;
		head = tail = itr.node = NULL;
		count--;
	}
	if (count > 1 && itr.Valid())
	{
		if (itr.node == tail)
		{
			tail = itr.node->previous;
			delete itr.node;
			tail->next = NULL;
			itr.node = head;
		}
		if (itr.node == head)
		{
			head = itr.node->next;
			delete itr.node;
			head->previous = NULL;
			itr.node = head;
		}
		else
		{
			DListNode<T>* next = itr.node->next;
			DListNode<T>* prev = itr.node->previous;
			next->previous = prev;
			prev->next = next;
			delete itr.node;
			itr.node = next;			
		}
		count--;
	}
}
	
	
template<class T>
DListIterator<T>::DListIterator (DListNode<T>* n)
{ node = n; }
	
template<class T>
DListIterator<T>::DListIterator ()
{ node = NULL; }
	
template<class T>
void DListIterator<T>::Forward ()
{
	if (node != NULL)
		node = node->next;
}
	
template<class T>
void DListIterator<T>::Backward ()
{
	if (node != NULL)
		node = node->previous;
}
	
template<class T>
bool DListIterator<T>::Valid()
{
	if (node == NULL)
		return 0;
	return 1;
}