/***************************************************/
/* Autor: Uwe Homm                                 */
/* Datum: 19. Dezember 2011                         */
/* Zweck: Einfach verkettete generische Liste      */
/*        Enstpricht der Klasse List aus dem       */
/*        hessischen Landesabitur für DV und DV/ET */
/***************************************************/
#ifndef ___LISTE___
#define ___LISTE___

template <class T>
class Liste
{
private:
	class Element
	{
		friend class Liste;
	private:
		Element* next;
		T value;
	};

	unsigned int count;
	Element* head;

public:
	Liste(void){
		head = nullptr;
		count=0;		
	};
	
	~Liste(void){
		
		T rc;
		while ( head != nullptr ) {
			rc = remove(0);
		}

	};

//**********************************************
// add()

	void add(T v){
		Element* n = new Element();
	
		n->next = nullptr;
		n->value = v;

		//Liste ist noch leer
		if ( head == nullptr )
			head = n;
		else
		{
			//Fügt zu Beginn der Liste ein
			n->next = head;
			head = n;
		}

		count++;
	};

//**********************************************
// contains()

	bool contains(T v){

		//Hilfspointer
		Element* tmp;
		//Zeiger auf erstes LE bzw. leere Liste
		tmp = head;

		while ( tmp != nullptr )
		{
			if ( v == tmp->value )
				return true;
			tmp = tmp->next;
		}

		return false;
	}

//**********************************************
// get()

	T* get(unsigned int pos){

		if ( pos > count || count==0)
			return nullptr;
		
		//Hilfspointer
		Element* tmp;
		//Zeiger auf erstes LE bzw. leere Liste
		tmp = head;

		int counter = 0;
		T* rc = nullptr;

		for ( unsigned int i=0; i < pos; i++)
			tmp = tmp->next;

		rc = &(tmp->value);

		return rc;
	}

//**********************************************
// indexOf()

	int indexOf(T v){

		//Hilfspointer
		Element* tmp;
		//Zeiger auf erstes LE bzw. leere Liste
		tmp = head;

		int counter = 0;
		int rc = -1;

		while ( tmp != nullptr )
		{
			if ( v == tmp->value )
			{
				rc = counter;
				break;
			}
			tmp = tmp->next;
			counter++;
		}

		return rc;
	}

//**********************************************
// remove()

	T remove(unsigned int pos){

		//Hilfsvariable für die Daten
		T rc;

		//Nur wenn die Position existiert
		if ( pos < count )
		{

			//1. Fall: Das erste LE entfernen
			if ( pos == 0)
			{
				//Hilfspointer
				Element* tmp;
				//Hilfszeiger für zu löschendes erstes Element
				tmp = head;
				//Listhead auf Nachfolger erstes Element setzen
				head = tmp->next;
				//Daten für Rückgabe sichern
				rc = tmp->value;
				delete tmp;
				count--;
				return rc;
			}
		
			//2. Fall: LE irgendwo in der Liste entfernen
			if ( pos > 0 )
			{
				//Hilfspointer
				Element* tmp;
				//Zeiger auf erstes LE
				tmp = head;
			
				//Bis zum LE vor dem zu löschenden LE laufen
				for (unsigned int i=1; i<pos; i++)
				{
					tmp = tmp->next;
				}

				//Daten sichern für Rückgabe
				rc = tmp->next->value;

				//Pointer auf zu löschendes Element sichern
				int *ptr = (int*)tmp->next;
			
				//Falls letztes LE gelöscht werden soll
				if ( tmp->next->next == nullptr )
					tmp->next = nullptr;
				else
					//Ansonsten übernachstes LE an aktuelles LE hängen
					tmp->next = tmp->next->next;

		
				delete ptr;
				count--;
				return rc;
			}
		}
		
		return rc;
	};

//**********************************************
// size()

	unsigned int size(){
		return this->count;
	};

//**********************************************
// clearList()

/* Nicht in der Landesabiturklasse enthalten*/

	unsigned int clearList(){

		unsigned int ctr = 0;
		while ( count > 0 )
		{
			remove(0);
			ctr++;
		}

		return ctr;
	}

};
#endif