/*
 * linked_list.cpp
 *
 *  Created on: 14.11.2013
 *      Author: trifon
 */

#ifndef __LINKED_LIST
#define __LINKED_LIST

#include "list.h"
#include <cstddef>

template <typename T>
struct elem {
	elem(T const& _inf, elem<T>* _link = NULL) :
		inf(_inf), link(_link) {}
	T inf;
	elem<T>* link;
};

template <typename T>
class LinkedList;

template <typename T>
class LinkedListIterator : public Iterator<T> {
private:
	elem<T>* p;
public:

	friend class LinkedList<T>;

	LinkedListIterator(elem<T>* _p = NULL) : p(_p) {}

	LinkedListIterator operator++(int) {
		LinkedListIterator copy = *this;
		++(*this);
		return copy;
	}

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

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

	T& operator*() const {
		/// !!!! p = p->link;
		return p->inf;
	}

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

};

template <typename T>
class LinkedList : public List<T, LinkedListIterator<T> > {
private:
	elem<T> *front, *back;

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

	void delList() {
		if (empty())
			return;
		T x;
		while(deleteAfter(x, begin()));
		I it = begin();
		deleteAt(x, it);
	}

public:
	typedef LinkedListIterator<T> I;

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

	LinkedList(LinkedList const& l) {
		copyList(l);
	}

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

	~LinkedList() {
		delList();
	}

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

	// включване на елемент преди позиция
	// O(n)
	bool insertBefore(T const& x, I const& it) {
		if (!it && !empty())
			return false;
		if (empty()) {
			// Най-вероятно искаме да вмъкнем в празен списък
			return insertAfter(x, it);
		} else {
			if (it == begin()) {
				// искаме да вмъкнем на първо място
				front = new elem<T>(x, front);
				return true;
			} else {
				I pit = findPrevious(it);
				if (!pit)
					return false;
				return insertAfter(x, pit);
			}
		}
	}

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

	// изключване на елемент преди позиция
	// O(n)
	bool deleteBefore(T& x, I const& it)  {
		if (!it || it == begin())
			return false;
		// Основен случай
		I pit = findPrevious(it);
		return deleteAt(x, pit);
	}

	// изключване на елемент след позиция
	// O(1)
	bool deleteAfter(T& x, I const& it)  {
		if (!it || it == end())
			return false;
		// сигурни сме, че it.p, toDelete са != NULL
		elem<T>* toDelete = it.p->link;
		it.p->link = toDelete->link;
		x = toDelete->inf;
		if (toDelete == back)
			back = it.p;
		delete toDelete;
		return true;
	}

	// изключване на елемент на позиция
	// O(n)
	bool deleteAt(T& x, I& it)  {
		if (!it)
			return false;
		if (it == begin()) {
			// изтриваме първи елемент
			elem<T>* toDelete = front;
			front = front->link;
			x = toDelete->inf;
			if (toDelete == back) {
				// изтриваме първи и последен елемент
				back = NULL;
			}
			delete toDelete;
			it.p = NULL;
			return true;
		} else {
			I pit = findPrevious(it);
			it.p = NULL;
			return deleteAfter(x, pit);
		}
	}

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

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

private:
	// O(n)
	I findPrevious(I const& it) const {
		I rit = begin();
		if (!it || it == rit)
			// it е началото, няма предишен елемент!
			return I();
		I rit2 = rit;
		rit++;
		while (rit && rit != it) {
			rit++;
			rit2++;
		}
		if (!rit)
			// it не е итератор в този списък!
			return I();
		return rit2;
	}

};

#endif