#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();
	//	List(List & _List);				// Copy Operator überladen
	~List();
	void InsertFront(int key);		// Einfügen eines Knotens am Anfang
	void InsertBack(int key);		// Einfügen eines Knotesn am Ende
	bool getFront(int & key);		// Entnehmen eines Knoten am Anfang
	bool getBack(int & key);		// Entnehmen eines Knoten am Ende
	bool del(int key);			// löschen eines Knotens [key]
	bool search(int key);			// Suchen eines Knoten
	bool swap(int key1, int 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); // Zuweisungsoperatordenieren
	List<T> & operator = (const List<T> * List); // Zuweisungsoperatordenieren
	List<T> & operator + (const List<T> & List_Append) const; // Listen zusammenfuehrenzu einer Liste
	List<T> & operator + (const List<T> * List_Append) const; // Listen zusammenfuehrenzu 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
};
#endif

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()
{
	//( ... löschen Sie alle noch vorhandenen Knoten Node dieser Instanz
	//	Denken Sie auch den die Knoten head und tail.)
	if (head)
	{
		while (head->next)
		{
			head = head->next;
			delete head->prev;
		}
		delete head;
	}
}
template<class T>
void List<T>::InsertFront(int key)
{
	//( ... Erweitern Sie die Methode so, dass ein neuer Knoten Node vorne
	//	(hinter dem Knoten head) in die Liste eingefügt wird. )
	Node<T>* neuerKnoten = new Node<T>(key);
	if (head)
	{
		neuerKnoten->prev = head;
		neuerKnoten->next = head->next;
		head->next->prev = neuerKnoten;
		head->next = neuerKnoten;
		_size++;
	}
}
template<class T>
void List<T>::InsertBack(int key)
{
	//( ... Erweitern Sie die Methode so, dass ein neuer Knoten Node hinten
	//	(vor dem Knoten tail) in die Liste eingefügt wird. )
	Node<T>* neuerKnoten = new Node<T>(key);
	if (tail)
	{
		neuerKnoten->prev = tail->prev;
		neuerKnoten->next = tail;
		tail->prev->next = neuerKnoten;
		tail->prev = neuerKnoten;
		_size++;
	}
}
template<class T>
bool List<T>::getFront(int & key)
{
	//( ... Erweitern Sie die Methode so, dass der erste Knoten der Liste
	//	(hinter head) zurückgegeben und dieser Knoten dann gelöscht wird.
	//	Im Erfolgsfall geben Sie true zurück, sonst false. )
	if (head->next)
	{
		key = head->next->key;
		if (head->next->next)
		{
			head->next->next->prev = head;
		}
		Node<T>* temp = head->next;
		head->next = head->next->next;
		delete temp;
		_size--;
		return true;
	}
	return false;
}
template<class T>
bool List<T>::getBack(int & key)
{
	//(... Erweitern Sie die Methode so, dass der letzte Knoten der Liste
	//	(vor tail) zurückgegeben und dieser Knoten dann gelöscht wird.
	//	Im Erfolgsfall geben Sie true zurück, sonst false. )
	if (tail->prev && tail->prev != head)
	{
		key = tail->prev->key;
		if (tail->prev->prev)
		{
			tail->prev->prev->next = tail;
		}
		Node<T>* temp = tail->prev;
		tail->prev = tail->prev->prev;
		delete temp;
		_size--;
		return true;
	}
	return false;
}
template<class T>
bool List<T>::del(int key)
{
	//(... Die Methode del sucht den Knoten mit dem Wert Key und löscht diesen
	//	im Erfolgsfall aus der Liste.
	//	Im Erfolgsfall geben Sie true zurück, sonst false. )
	Node<T>* searchNode = head;
	while (searchNode->next)
	{
		if (searchNode->key == key)
		{
			if (searchNode->prev)
			{
				searchNode->prev->next = searchNode->next;
			}
			searchNode->next->prev = searchNode->prev;
			delete searchNode;
			_size--;
			return true;
		}
		searchNode = searchNode->next;
	}
	return false;
}
template<class T>
bool List<T>::search(int key)
{
	//(... Die Methode search sucht den Knoten mit dem Wert key
	//	Im Erfolgsfall geben Sie true zurück, sonst false. )
	Node<T>* searchNode = head;
	while (searchNode->next)
	{
		if (searchNode->key == key)
		{
			return true;
		}
		searchNode = searchNode->next;
	}
	return false;
}
template <class T>
bool List<T>::swap(int key1, int key2)
{
	//(... Die Methode swap sucht den Knoten mit dem Wert key1,
	//	dann den Knoten mit dem Wert key2. Diese Knoten werden dann
	//	getauscht, indem die Zeiger der Knoten entsprechend geändert
	//	werden. )
	Node<T>* key_eins = nullptr;
	Node<T>* key_zwei = nullptr;
	Node<T>* tempNode = head->next;
	while (tempNode)
	{
		if (tempNode->key == key1)
		{
			key_eins = tempNode;
		}
		else if (tempNode->key == key2)
		{
			key_zwei = tempNode;
		}
		tempNode = tempNode->next;
	}
	if (key_eins && key_zwei)
	{
		Node<T> tempNode = *key_eins;
		if (key_eins->next)
		{
			key_eins->next->prev = key_zwei;
		}
		if (key_eins->prev)
		{
			key_eins->prev->next = key_zwei;
		}
		if (key_zwei->next)
		{
			key_zwei->next->prev = key_eins;
		}
		if (key_zwei->prev)
		{
			key_zwei->prev->next = key_eins;
		}
		key_eins->next = key_zwei->next;
		key_eins->prev = key_zwei->prev;
		key_zwei->next = tempNode.next;
		key_zwei->prev = tempNode.prev;
		return true;
	}
	return false;
}
template <class T>
int List<T>::size(void)
{
	//(... Die Methode git den Wert von size (Anzahl der Knoten in der Liste) zurück. )
	return _size;

}
template <class T>
bool List<T>::test(void)
{
	//(... Die Methode überprüft die Pointer der Liste. Gestartet wird mit head. Es werden alle
	//	Knoten bis zum tail durchlaufen von dort aus dann die prev-Zeiger bis zum head.
	//	Bei Erfolg wird true zurück gegeben. )
	Node<T>* searchNode = head;
	while (searchNode)
	{
		if (!searchNode->next && searchNode != tail)
		{
			return false;
		}
		searchNode = searchNode->next;
	}
	//loopIndex either is tail or the function alread returned false
	while (searchNode)
	{
		if (!searchNode->prev && searchNode != head)
		{
			return false;
		}
	}
	//if none of the two while loops returned false you can return true!
	return true;
}

// END
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<T> & _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;
	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)
{
	// 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;
	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<T> * 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>
List<T> & List<T>::operator + (const List<T> * List_Append) const
{
	List<T> * 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, 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;
}