/*
 * double_linked_list.cpp
 *
 *  Created on: 21.11.2012
 *      Author: trifon
 */

#include "list.h"

template <typename T>
struct elem2
{
	elem2 *prev, *next;
	T inf;
};

template <typename T>
class DoubleLinkedList;

template <typename T>
class DoubleLinkedListIterator :
		public Iterator<T> {
	friend class DoubleLinkedList<T>;

	elem2<T>* p;

public:

	DoubleLinkedListIterator(elem2<T>* _p = NULL) :
		p(_p) {}

	Iterator<T>& operator++()
	{
		if (p != NULL)
			p = p->next;
		return *this;
	}

	Iterator<T>& operator--()
	{
		if (p != NULL)
			p = p->prev;
		return *this;
	}

	DoubleLinkedListIterator<T> operator++(int)
	{
		DoubleLinkedListIterator<T> it = *this;
		++(*this);
		return it;
	}

	DoubleLinkedListIterator<T> operator--(int)
	{
		DoubleLinkedListIterator<T> it = *this;
		--(*this);
		return it;
	}

	T& operator*() const
	{
		return p->inf;
	}

	operator bool() const
	{
		return p != NULL;
	}

	bool operator==(Iterator<T> const& it) const
	{
		DoubleLinkedListIterator<T> const& dllit =
				 (DoubleLinkedListIterator<T> const&)it;
		return p == dllit.p;
	}
};

template <typename T=int>
class DoubleLinkedList : public List<T,
				DoubleLinkedListIterator<T> >
{
private:
	elem2<T> *start, *end;

	// O(n)
	void copyList(DoubleLinkedList<T> const& dl)
	{
		start = end = NULL;
		for(I it = dl.iteratorBegin(); it; ++it)
			toEnd(*it);
	}

	void deleteList()
	{
		if (start == NULL) return;
		while (start->next != NULL)
		{
			start = start->next;
			delete start->prev;
		}
		delete start;
		start = end = NULL;
	}

public:

	typedef DoubleLinkedListIterator<T> I;

	DoubleLinkedList() : start(NULL), end(NULL)
	{}

	DoubleLinkedList(DoubleLinkedList<T> const& dl)
	{
		copyList(dl);
	}

	DoubleLinkedList<T>& operator=(DoubleLinkedList<T> const& dl)
	{
		if (&dl != this)
		{
			deleteList();
			copyList(dl);
		}
		return *this;
	}

	~DoubleLinkedList()
	{
		deleteList();
	}

	bool empty() const {
		return start == NULL;
	}

	void toEnd(T const& x) {
		insertAfter(x, iteratorEnd());
	}

	// O(1)
	void insertAfter(T const& x, I const& it)
	{
		if (!it && !empty()) return;
		elem2<T>* p = new elem2<T>;
		p->inf = x;
		if (empty())
		{
			start = end = p;
			p->next = p->prev = NULL;
		} else {
			if (it.p->next == NULL)
				end = p;
			else
				it.p->next->prev = p;
			p->prev = it.p;
			p->next = it.p->next;
			it.p->next = p;
		}
	}

	void insertBefore(T const& x, I const& it)
	{
		if (!it && !empty()) return;
		elem2<T>* p = new elem2<T>;
		p->inf = x;
		if (empty())
		{
			start = end = p;
			p->prev = p->next = NULL;
		} else {
			if (it.p->prev == NULL)
				start = p;
			else
				it.p->prev->next = p;
			p->prev = it.p->prev;
			p->next = it.p;
			it.p->prev = p;
		}
	}


	I iteratorBegin() const
	{
		return I(start);
	}

	I iteratorEnd() const
	{
		return I(end);
	}

	bool deleteAt(T& x, I& it) {
		if (!it) return false;
		if (it.p->next == NULL)
			end = it.p->prev;
		else
			it.p->next->prev = it.p->prev;
		if (it.p->prev == NULL)
			start = it.p->next;
		else
			it.p->prev->next = it.p->next;
		x = *it;
		delete it.p;
		it.p = NULL;
		return true;
	}

	bool deleteBefore(T& x, I& it) {
		I itprev = it;
		--itprev;
		return deleteAt(x, itprev);
	}

	bool deleteAfter(T& x, I& it) {
		I itnext = it;
		++itnext;
		return deleteAt(x, itnext);
	}

	void print() const
	{
		for(I it = iteratorBegin(); it; ++it)
			cout << *it << ' ';
		cout << endl;
	}
};