package kreisbrecher_ws1718;

import java.util.Set;

public class CycleBreaker implements Runnable {

	private Graph graph;
	private int firstIndex;

	public CycleBreaker(Graph graph, int first) {
		this.graph = graph; // verschattet
		firstIndex = first;
	}

	public void run() {
		try {
			traverse(-1, firstIndex); // beginne mit der zum ersten Knoten, d. h. wir gehen zum Startknoten und 
									  // behandeln diesen (from spielt hier noch keine Rolle) 
		} catch (InterruptedException e) { }
	}
	

	/**
	 * Diese Methode betrachtet den Knoten mit dem Index <to>. Zusätzlich wird
	 * jedoch noch der Index des direkten Vorgängers (<from>) übergeben, sodass die
	 * Kante von <from> nach <to> gelöscht werden kann, falls beim Betrachten des
	 * Knotens <to> ein Zyklus entdeckt wird. Das heißt also, dass wir nicht mit
	 * einer Schleife über alle Nachfolger iterieren, sondern immer nur einen
	 * Nachfolger betrachten und dann für jeden Nachfolger (Schleife am Ende)
	 * traverse aufrufen. Würden wir über die Nachfolger iterieren und diese dann
	 * ggf. löschen, so bekämen wir ggf. eine ConcurrentMdoificationException, da
	 * man nicht aus einer Collection (hier: Set) entfernen darf während man darüber
	 * iteriert. Daher können wir also nicht über die Nachfolger von from iterieren
	 * sondern betrachten immer nur die Verbindung from->to gefolgt von je einem
	 * rekursiven Aufruf für alle Nachfolger von to, also traverse(to,
	 * ersterNachfolgerVonTo), ...
	 * EDIT: Bekommen  ConcurrentMod. ggf. trotzdem noch...
	 */
	private void traverse(int from, int to) throws InterruptedException {
		// Eigene Thread-ID zwischenspeichern in myId
		long myId = Thread.currentThread().getId(); // ID ist stets >= 0

		Node node = graph.getNode(to); // Zielknoten zwischenspeichern (holen per Index to)
		
		boolean recursiveCalls = false;  // Schritt 3 ausführen nach synchronized?
		
		synchronized (node) { // [C] Zur selben Zeit darf immer nur ein Zugriff auf einen bestimmten Knoten passieren
							  // ("... unkoordinierte parallele Zugriffe auf Daten stattfinden")
			// 1.
			if (node.threadId > myId) { // Thread-ID des Zielknotens größer als myId
				System.out.println("Ignorieren");
				// -> Ignorieren
			}
			// 2.
			else if (node.threadId == myId && node.locked) {
				// <=> Zielknoten bereits durch den aktuellen Thread blockiert
				System.out.println("Knoten " + to + " bereits von mir (Thread " + myId + ") belegt "
								 + "-> Zyklus -> Kante von " + from + " nach " + to + " entfernen.");
				graph.removeEdge(from, to); // Kante zum Zielknoten entfernen				
				// -> Schritt 3. jetzt nicht ausführen, sondern zurückkehren zu from (vorheriger rekursiver Aufruf),
				//    da die Kante from->to nun ja nicht mehr existiert und wir also auch nicht von to weitergehen dürfen.
			} 
			else {
				// <=> Zielknoten noch nicht blockiert -> jetzt blockieren
				// [B] "Thread muss u. U. warten, bis ein anderer Thread den Zielknoten
				// verlassen hat".
				System.out.println("Thread " + myId + " versucht Knoten " + to + " zu belegen.");
				while (node.locked)
					node.wait(); // warte darauf, dass der andere genau diesen Knoten freigibt (-> notify)

				// [A] "Generell gilt, dass der Zielnoten ... vom aktuellen Thread blockiert
				// werden muss".
				node.locked = true;
				node.threadId = myId; // Knoten wird durch den aktuellen Thread belegt
				System.out.println("Knoten " + to + " wurde belegt durch Thread " + myId + ".");
				
				recursiveCalls = true;
			}
		}
		
		/* 
		 * Unterbrechung des synchronized-Bereichs für die rekursiven Aufrufe. Würde ich
		 * statt dem boolean recursiveCalls direkt oben (wo ich es auf true setze) die 
		 * rekursiven Aufrufe machen, dann würde ich das Lock für node nicht freigeben.
		 */
		if (recursiveCalls) {
			// 3.
			// Ausgehende Kanten vom Knoten <to> in <edgesFromTo> speichern
			Set<Integer> edgesFromTo = graph.getEdges(to);
			// Rekursiv alle ausgehenden Kanten der direkten Nachbarn von <to> besuchen
			for (int dest : edgesFromTo)
				traverse(to, dest); // HIER KANN CONCURRENTMODICATIONEXCEPTION AUFTRETEN
		}
		
		synchronized (node) {  // neues synchronized
			node.locked = false;
			System.out.println("Knoten " + to + " wieder freigegeben.");
			node.notify(); // der nächste Thread (der oben mittels node.wait() auf die Freigabe wartet) wird benachrichtigt
		}
	}
	
	
	
	// Offizielle Musterlösung (fehlerhaft wie meine): Gibt ConcurrentModification im ungünstigen Fall (Kante 6->5 entfernt)
	private void traverseMusterloesung(int from, int to) throws InterruptedException {
		long myId = Thread.currentThread().getId(); // ID ist stets >= 0

		Node node = graph.getNode(to);
		boolean workWithNode = false;
		boolean cycle = false;

		synchronized (node) {
			while (node.threadId < myId && node.locked)
				node.wait();
			if (node.threadId <= myId) {
				cycle = node.locked && myId == node.threadId;
				workWithNode = true;
				node.locked = true;
				node.threadId = myId;
			}
		}

		if (!workWithNode)
			return;

		if (cycle && from != to) {
			graph.removeEdge(from, to);
			System.out.println("remove " + from + "->"+ to);
		} else {
			java.util.Set<Integer> edgesFromTo = graph.getEdges(to);
			for (int dest : edgesFromTo)
				traverse(to, dest);
		}

		synchronized (node) {
			node.locked = false;
			node.notifyAll();
		}
	}

	
	
	// Einfacher nachvollziehbar, allerdings mit Deadlock, da die rekursiven Aufruf im synchronized-Block passieren
	private void traverseSimple(int from, int to) throws InterruptedException {
		long myId = Thread.currentThread().getId();
		
		Node node = graph.getNode(to);

		synchronized (node) {
			if (node.threadId > myId) {
				// -> Ignorieren
			} else if (node.threadId == myId && node.locked) {
				System.out.println("Removed " + from + " -> " + to);
				graph.removeEdge(from, to);
			} else {
				while (node.locked)
					node.wait();
				node.locked = true;
				node.threadId = myId;
				
				Set<Integer> edgesFromTo = graph.getEdges(to);
				for (int dest : edgesFromTo)
					traverse(to, dest);
			}
			// -> Freigeben
			node.locked = false;
			node.notify();
		}
	}
}