package collections_ws15;

import java.util.NoSuchElementException;

public class DoublyLinkedList<T> {
	private Element<T> head = null; // Erstes Element der Liste
	private int size = 0; // Anzahl Elemente der Liste
	
	// Gibt den Inhalt der Liste an Position pos zurueck.
	public T get(int pos) {
		if (pos < 0 || pos >= size)					// Fehlerbehandlung (entspricht IndexOutOfBounds)
			throw new NoSuchElementException();		// Exception werfen (vgl. Aufgabenstellung)
		
		int i = 0;									// Zähler, um beim Index <pos> abzubrechen (alternativ: pos herunterzählen bis 0)
		
		Element<T> current = head;					// Standardschleife: Wir beginnen mit dem ersten Element
		while (i < pos) {							// Bedingung: Bis wir am Wunschindex angekommen sind ("&& current != null" zusätzlich möglich)
			current = current.getNext();			//   Standardschleife: Weiterzählen
			i++;									//   Indexzähler erhöhen
		}
		
		return current.getInfo();					// Inhalt (info) des Elements zurückgeben
	}

	// Fuegt hinten ein Element ein.
	public void addLast(T info) {
		if (head == null) { 							// Liste ist leer (entspricht "size == 0")
			head = new Element<T>(info, null, null);	//   Neues Element erzeugen (kein Vorgänger/Nachfolger) und in head speichern
			size++;										//   Listengröße erhöhen
		} else { 										// Liste nicht leer (mind. 1 Element schon enthalten)
			Element<T> current = head;					//   Standardschleife: Wir beginnen mit dem ersten Element
			while (current.getNext() != null) {			//   Standardschleife: Für alle Elemente der Liste außer das letzte
				current = current.getNext();			//     Standardschleife: Weiterzählen
			}											//   -> in current ist jetzt das letzte Element der Liste gespeichert (für dieses wurde ja nicht mehr weitergezählt zu null)
			
			Element<T> neues;
			neues = new Element<>(info, current, null);	// Neues Element erzeugen (info als info übergeben) und zwischenspeichern
			//neuesElement.setPrev(current); 			// Vorgänger auf bisherigen letzten setzen (bereits im Konstruktor geschehen, daher nicht nochmal nötig)
			current.setNext(neues);						// Nachfolger des bisherigen letzten auf das eingefügte Element setzen (Verknüpfung herstellen)
			size++;										// Listengröße erhöhen
		}
		
	}

	// Kehrt die Liste um
	public void reverse() {
		Element<T> current = head; 					// Standardschleife: Wir beginnen mit dem ersten Element
		
		while (current != null) { 					// Standardschleife: Für alle Elemente der Liste
			Element<T> prev = current.getPrev(); 	// (alten) Vorgänger in prev zwischenspeichern
			Element<T> next = current.getNext(); 	// (alten) Nachfolger in next zwischenspeichern
			// Vertauschen von prev und next-Zeiger:
			current.setPrev(next); 					// prev wird auf next gesetzt
			current.setNext(prev); 					// next wird auf prev gesetzt (bevor prev verändert wird, da zwischengespeichert)
			
			if (next == null) 						// Wenn wir keinen Nachfolger mehr haben, dann sind wir beim (alten) letzten Element [dieser Vergleich ist nicht nötig]
				head = current; 					// -> das ist nun unser (neues) erstes Element
			
			current = next;  						// Standardschleife: Weiterzählen (current = current.next)
		}
	}
}