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

#include "list.h"

template <typename T>
struct elem2 {
	elem2(T const& _inf,
			elem2<T>* _next = NULL,
			elem2<T>* _prev = NULL) :
			inf(_inf),
			next(_next),
			prev(_prev) {}
	T inf;
	elem2 *next, *prev;
};

template <typename T>
class DoubleLinkedList;

template <typename T>
class DoubleLinkedListIterator : public Iterator<T> {
private:
	elem2<T>* p;
public:
	DoubleLinkedListIterator(elem2<T>* _p = NULL) : p(_p) {}

	friend class DoubleLinkedList<T>;

	// преместване напред, връща старата стойност
	DoubleLinkedListIterator operator++(int) {
		DoubleLinkedListIterator copy = *this;
		++(*this);
		return copy;
	}

	// преместване напред, връща новата стойност
	Iterator<T>& operator++() {
		if (p != NULL)
			p = p->next;
		return *this;
	}

	// преместване назад, връща старата стойност
	DoubleLinkedListIterator operator--(int) {
		DoubleLinkedListIterator copy = *this;
		--(*this);
		return copy;
	}

	// преместване назад, връща новата стойност
	Iterator<T>& operator--() {
		if (p != NULL)
			p = p->prev;
		return *this;
	}

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

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

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

template <typename T>
class DoubleLinkedList : public List<T, DoubleLinkedListIterator<T> > {
private:
	elem2<T> *front, *back;

	void copyList(DoubleLinkedList const& dl) {
		front = back = NULL;
		for(I it = dl.begin(); it; ++it)
			this->toEnd(*it);
	}

	void delList() {
		T x;
		I it = begin();
		while(deleteAt(x, it));
	}
public:
	typedef DoubleLinkedListIterator<T> I;

	DoubleLinkedList() : front(NULL), back(NULL) {}

	DoubleLinkedList(DoubleLinkedList const& dl) {
		copyList(dl);
	}

	DoubleLinkedList& operator=(DoubleLinkedList const& dl) {
		if (&dl != this) {
			delList();
			copyList(dl);
		}
		return *this;
	}

	~DoubleLinkedList() {
		delList();
	}
	// проверява дали списъкът е празен
	bool empty() const  {
		return front == NULL;
	}

	// включване на елемент преди позиция
	// O(1)
	bool insertBefore(T const& x, I const& it)  {
		if (!it && !empty())
			return false;
		if (empty()) {
			back = front = new elem2<T>(x);
		} else {
			elem2<T>* p = new elem2<T>(x, it.p, it.p->prev);
			if (it.p->prev != NULL)
				// имаме предишен (не вмъкваме преди първия)
				it.p->prev->next = p;
			else
				// нямаме предишен (вмъкваме преди първия)
				front = p;
			it.p->prev = p;
		}
		return true;
	}

	// включване на елемент след позиция
	// O(1)
	bool insertAfter(T const& x, I const& it)  {
		if (!it && !empty())
			return false;
		if (empty()) {
			front = back = new elem2<T>(x);
		} else {
			elem2<T>* p = new elem2<T>(x, it.p->next, it.p);
			if (it.p->next != NULL)
				// имаме следващ (не вмъкваме след последния)
				it.p->next->prev = p;
			else
				// нямаме следващ (вмъкваме след последния)
				back = p;
			it.p->next = p;
		}
		return true;
	}

	// изключване на елемент преди позиция
	bool deleteBefore(T& x, I const& it)  {
		if (!it)
			return false;
		I it2 = it;
		it2--;
		return deleteAt(x, it2);
	}

	// изключване на елемент след позиция
	bool deleteAfter(T& x, I const& it)  {
		if (!it)
			return false;
		I it2 = it;
		it2++;
		return deleteAt(x, it2);
	}


	// изключване на елемент на позиция
	bool deleteAt(T& x, I& it)  {
		if (!it)
			return false;
		x = *it;
		if (it.p->prev != NULL)
			it.p->prev->next = it.p->next;
		else
			// изтриваме първия елемент
			front = it.p->next;
		if (it.p->next != NULL)
			it.p->next->prev = it.p->prev;
		else
			back = it.p->prev;
		delete it.p;
		it.p = NULL;
		return true;
	}

	// итератор към началото
	I begin() const  {
		return I(front);
	}

	// итератор към края
	I end() const  {
		return I(back);
	}
};