#ifndef _LIST_H
#define _LIST_H
#include "Node.h"
#include <string>
#include <iostream>
template <class T>
class List
{
	/*
	Die Klasse List dient zur Verwaltung von Knoten (Node). Mit Hilfe der Klasse List
	kann ein Stapel oder Warteschlange realisiert werden.
	*/
private:
	struct form { std::string start = "<< "; std::string zwischen = ", "; std::string ende = " >>\n"; } _form;
	Node<T> * head, *tail;
	int _size;
public:
	List<T>();
	//	List(List & _List);				// Copy Operator überladen
	~List<T>();
	void InsertFront(T key);		// Einfügen eines Knotens am Anfang
	void InsertBack(T key);		// Einfügen eines Knotesn am Ende
	bool getFront(T & key);		// Entnehmen eines Knoten am Anfang
	bool getBack(T & key);		// Entnehmen eines Knoten am Ende
	bool del(T key);			// löschen eines Knotens [key]
	bool search(T key);			// Suchen eines Knoten
	bool swap(T key1, T key2);	// Knoten in der Liste vertauschen
	int size(void);					// Größe der Lise (Anzahl der Knoten)
	bool test(void);				// Überprüfen der Zeigerstruktur der Liste
	void format(const std::string & start, const std::string & zwischen, const std::string & ende); // Mit der format−Methode kann die Ausgabe gesteuert werden: operator <<
	List<T> & operator = (const List<T> & List); // Zuweisungsoperator definieren
	List<T> & operator = (const List<T> * List); // Zuweisungsoperator definieren
	List<T> & operator + (const List<T> & List_Append) const; // Listen zusammenfuehren zu einer Liste
	List<T> & operator + (const List<T> * List_Append) const; // Listen zusammenfuehren zu einer Liste
	template <typename T>
		friend std::ostream & operator << (std::ostream & stream, const List<T> & Liste); // Ausgabeoperator ueberladen
	template <typename T>
		friend std::ostream & operator << (std::ostream & stream, const List<T> * Liste); // Ausgabeoperator ueberladen
};

template <class T>
List<T>::List()
{
	head = new Node<T>;
	tail = new Node<T>;
	_size = 0;
	head->next = tail;
	tail->prev = head;
}

template <class T>
List<T>::~List() {
	Node<T> *del = head;
	Node<T> *temp = head->next;
	while (temp->next != nullptr) {
		delete del;
		del = temp;
		temp = temp->next;
	}
}

template <class T>
void List<T>::InsertFront(T key) {
	Node<T> *new_Node = new Node<T>(key, nullptr, head);
	if (head->next != tail) {
		new_Node->next = head->next;
		head->next->prev = new_Node;
	}
	head->next = new_Node;
	if (_size == 0) {
		new_Node->next = tail;
		tail->prev = new_Node;
	}
	_size++;
}

template <class T>
void List<T>::InsertBack(T key) {
	Node<T> *new_Node = new Node<T>(key, tail);
	if (tail->prev != head) {
		new_Node->prev = tail->prev;
		tail->prev->next = new_Node;
	}
	tail->prev = new_Node;
	if (_size == 0) {
		new_Node->prev = head;
		head->next = new_Node;
	}
	_size++;
}

template <class T>
bool List<T>::getFront(T & key) {
	if (head->next != tail) {
		Node<T> *temp = new Node<T>;
		temp = head->next;
		tail->next = temp->next;
		std::cout << temp->key << std::endl;
		temp->next->prev = tail;
		_size--;
		return true;
	}
	else
		return false;
}

template <class T>
bool List<T>::getBack(T & key) {
	if (tail->prev != head) {
		Node<T> *temp = tail->prev;
		tail->prev = temp->prev;
		tail->prev->next = tail;
		key = temp->key;
		_size--;
		delete temp;
		return true;
	}
	else
		return false;
}

template <class T>
bool List<T>::del(T key) {
	Node<T> *temp = new Node();
	temp = head->next;
	while (temp->next != tail) {
		if (temp->key == key) {
			temp->prev->next = temp->next;
			temp->next->prev = temp->prev;
			delete temp;
			_size--;
			return true;
		}
		temp = temp->next;
	}
	delete temp;
	return false;
}

template <class T>
bool List<T>::search(T key) {	//sucht nach einem Node<T> mit key == int key
	Node<T> temp = *head->next;
	while (temp.next != tail) {
		if (temp.key == key) {
			return true;
		}
		else
			temp = *temp.next;
	}

	return false;
}

template <class T>
bool List<T>::swap(T key1, T key2) {
	if (!this->search(key1) || !this->search(key2))
		return 0;
	Node<T> *temp_1 = head->next;
	while (temp_1->next != tail) {
		if (temp_1->key == key1 || temp_1->key == key2) {
			break;
		}
		temp_1 = temp_1->next;
	}
	Node<T> *temp_2 = tail->prev;
	while (temp_2->prev != head) {
		if (temp_2->key == key1 || temp_2->key == key2) {
			break;
		}
		temp_2 = temp_2->prev;
	}

	if (temp_1->next != temp_2 || temp_2->prev != temp_1) {
		temp_1->prev->next = temp_2;
		temp_2->prev->next = temp_1;

		temp_1->next->prev = temp_2;
		temp_2->next->prev = temp_1;

		Node<T> *temp = new Node<T>;
		temp->prev = temp_1->prev;
		temp->next = temp_1->next;

		temp_1->next = temp_2->next;
		temp_1->prev = temp_2->prev;

		temp_2->prev = temp->prev;
		temp_2->next = temp->next;
	}
	else {
		temp_1->next = temp_2->next;
		temp_1->prev->next = temp_2;
		temp_1->prev = temp_2;
		temp_2->prev = temp_1->prev;
		temp_2->next->prev = temp_1;
		temp_2->next = temp_1;
	}


	return true;
}

template <class T>
int List<T>::size(void) {
	return _size;
}

template <class T>
bool List<T>::test(void) {
	Node<T> *temp = head;
	for (int i = 0; i < _size; i++) {
		temp = temp->next;
	}
	if (temp->next != tail) {
		delete temp;
		return false;
	}
	temp = tail;
	for (int i = 0; i < _size; i++) {
		temp = temp->prev;
	}
	if (temp->prev != head) {
		delete temp;
		return false;
	}
	return true;
}

template <class T>
void List<T>::format(const std::string & start, const std::string & zwischen, const std::string & ende) {
	// Setzen der Formatierung für den überladenen Streamingoperator <<
	_form.start = start;			// Ausgabe zu Beginn der Liste
	_form.zwischen = zwischen;		// Ausgabe zwischen zwei Knoten
	_form.ende = ende;				// Ausgabe am Ende der Liste
}

template <class T>
List<T> & List<T>::operator = (const List & _List) {
	// in dem Objekt _List sind die Knoten enthalten, die Kopiert werden sollen.
	// Kopiert wird in das Objekt "this"
	if (this == &_List) return *this;	//  !! keine Aktion notwendig
	Node<T> * tmp_node = new Node<T>;
	if (_size)
	{
		Node<T> * tmp_del;
		tmp_node = head->next;
		while (tmp_node != tail)		// Alle eventuell vorhandenen Knoten in this löschen
		{
			tmp_del = tmp_node;
			tmp_node = tmp_node->next;
			delete tmp_del;
		}
		_size = 0;
		head->next = tail;
		tail->prev = head;
	}
	tmp_node = _List.head->next;
	while (tmp_node != _List.tail)
	{
		InsertBack(tmp_node->key);
		tmp_node = tmp_node->next;
	}
	return *this;
}

template <class T>
List<T> & List<T>::operator = (const List * _List) {
	// in dem Objekt _List sind die Knoten enthalten, die Kopiert werden sollen.
	// Kopiert wird in das Objekt "this"
	if (this == _List) return *this;	//  !! keine Aktion notwendig
	Node<T> * tmp_node = new Node<T>;;
	if (_size)
	{
		Node<T> * tmp_del;
		tmp_node = head->next;
		while (tmp_node != tail)		// Alle eventuell vorhandenen Knoten in this löschen
		{
			tmp_del = tmp_node;
			tmp_node = tmp_node->next;
			delete tmp_del;
		}
		_size = 0;
		head->next = tail;
		tail->prev = head;
	}
	tmp_node = _List->head->next;
	while (tmp_node != _List->tail)
	{
		InsertBack(tmp_node->key);
		tmp_node = tmp_node->next;
	}
	return *this;
}

template <class T>
List<T> & List<T>::operator + (const List<T> & List_Append) const {
	List * tmp = new List;
	Node<T> * tmp_node = new Node<T>;
	tmp_node = head->next;
	while (tmp_node != tail) {
		tmp->InsertBack(tmp_node->key);
		tmp_node = tmp_node->next;
	}
	if (!List_Append._size) return *tmp;
	tmp_node = List_Append.head->next;
	while (tmp_node != List_Append.tail) {
		tmp->InsertBack(tmp_node->key);
		tmp_node = tmp_node->next;
	}
	return *tmp;
}

template <class T>
List<T> & List<T>::operator + (const List * List_Append) const {
	List * tmp = new List;
	Node<T> * tmp_node;
	tmp_node = head->next;
	while (tmp_node != tail) {
		tmp->InsertBack(tmp_node->key);
		tmp_node = tmp_node->next;
	}
	if (!List_Append->_size) return *tmp;
	tmp_node = List_Append->head->next;
	while (tmp_node != List_Append->tail) {
		tmp->InsertBack(tmp_node->key);
		tmp_node = tmp_node->next;
	}
	return *tmp;
}

template <class T>
std::ostream & operator<<(std::ostream  & stream, List<T> const & Liste) {
	stream << Liste._form.start;
	for (Node<T> * tmp = Liste.head->next; tmp != Liste.tail; tmp = tmp->next)
		stream << tmp->key << (tmp->next == Liste.tail ? Liste._form.ende : Liste._form.zwischen);
	return stream;
}

template <class T>
std::ostream & operator << (std::ostream & stream, const List<T> * Liste)
{
	stream << Liste->_form.start;
	for (Node<T> * tmp = Liste->head->next; tmp != Liste->tail; tmp = tmp->next)
		stream << tmp->key << (tmp->next == Liste->tail ? Liste->_form.ende : Liste->_form.zwischen);
	return stream;
}
#endif