import simpleio.*; //aus audlib

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * Stadplan
 * Diese Klasse kapselt die Orte und Strassen eines Stadplanes
 * @author IFIS
 * @version 1.1
 */
public class Stadtplan {

	private List<Ort> orte;			// Menge der Orte
	private List<Strasse> strassen;	// Menge der Strassen
	private boolean[][] A;			// Adjazenzmatrix
	private List<Ort> bereitsBesuchteOrte;


	/**
	 * Implementierung zu Aufgabe 1.a)
	 * Gibt alle direkten Nachfolger des uebergebenen Knotens in einer Liste zurueck.
	 * @param startOrt der Startknoten
	 */
	public List<Ort> getDirekteNachfolger(Ort startOrt) {
		List<Ort> nachfolger = new LinkedList<Ort>();

		Iterator<Strasse> it = strassen.iterator();
		Strasse s;
		while (it.hasNext()) {
			s = it.next();
			if (s.getStartOrt() == startOrt) {
				nachfolger.add(s.getZielOrt());
			} else if (s.getZielOrt() == startOrt && !s.isGerichtet()) {
				nachfolger.add(s.getStartOrt());
			}
		}

		return nachfolger;
	}


	/**
	 * Implementierung zu Aufgabe 1.b)
	 * Gibt alle direkten Vorgaenger des uebergebenen Knotens in einer Liste zurueck.
	 * @param zielOrt der Zielknoten
	 */
	public List<Ort> getDirekteVorgaenger(Ort zielOrt) {
		List<Ort> vorgaenger = new LinkedList<Ort>();

		Iterator<Strasse> it = strassen.iterator();
		Strasse s;
		while (it.hasNext()) {
			s = it.next();
			if (s.getZielOrt() == zielOrt) {
				vorgaenger.add(s.getStartOrt());
			} else if (s.getStartOrt() == zielOrt && !s.isGerichtet()) {
				vorgaenger.add(s.getZielOrt());
			}
		}

		return vorgaenger;
	}


	/**
	 * Berechnet die Adjazenzmatrix und speichert sie in dem privaten Attribut A
	 */
	private void calcAdjazenzmatrix() {
		int knotenzahl = orte.size();
		A = new boolean[knotenzahl][knotenzahl];
		for (int i = 0; i < knotenzahl; i++) {
			List<Ort> direkteNachfolger = getDirekteNachfolger(orte.get(i));
			Iterator<Ort> itNachfolger = direkteNachfolger.iterator();
			Ort nachfolger;
			while (itNachfolger.hasNext()) {
				nachfolger = itNachfolger.next();
				A[i][nachfolger.getNummer()-1] = true;
			}
			A[i][i] = true;
		}
		for (int j = 0; j < knotenzahl; j++) {
			for (int i = 0; i < knotenzahl; i++) {
				if (A[i][j]) {
					for (int k = 0; k < knotenzahl; k++) {
						if (A[j][k]) {
							A[i][k] = true;
						}
					}
				}
			}
		}
	}


	/**
	 * Implementierung zu Aufgabe 1.c)
	 * Gibt alle von dem uebergebenen Knoten erreichbaren Orte in einer Liste zurueck.
	 * @param startOrt der Startknoten
	 * @return alle erreichbaren Orte
	 */
	public List<Ort> getErreichbarOrte(Ort startOrt) {
		calcAdjazenzmatrix();

		List<Ort> erreichbareOrte = new LinkedList<Ort>();
		int ortnummer = startOrt.getNummer()-1;
		int knotenzahl = orte.size();
		for (int j = 0; j < knotenzahl; j++) {
			if (A[ortnummer][j]) {
				erreichbareOrte.add(orte.get(j));
			}
		}

		return erreichbareOrte;
	}
	
	
	/**
	 * Implementierung zu Aufgabe 1.d)
	 * Gibt zurueck, ob ein Weg von startOrt zu zielOrt existiert.
	 * @param startOrt der Startknoten
	 * @param zielOrt der Zielknoten
	 * @return ob ein Weg existiert
	 */
	public boolean existiertWeg(Ort startOrt, Ort zielOrt) {
		calcAdjazenzmatrix();
		return A[startOrt.getNummer()-1][zielOrt.getNummer()-1];
	}


	/**
	 * Gibt das Ergebnis der Tiefensuche von Knoten startOrt zurueck
	 * @param startOrt der Startknoten
	 * @return das Ergebnis der Tiefensuche
	 */
	private List<Ort> recTiefensuche(Ort startOrt) {
		List<Ort> rueckgabe = new LinkedList<Ort>();
		List<Ort> nachfolger = getDirekteNachfolger(startOrt);
		Iterator<Ort> it = nachfolger.iterator();

		bereitsBesuchteOrte.add(startOrt);
		rueckgabe.add(startOrt);
		Ort ort;
		while (it.hasNext()) {
			ort = it.next();
			if (!bereitsBesuchteOrte.contains(ort)) {
				rueckgabe.addAll(recTiefensuche(ort));
			}
		}

		return rueckgabe;
	}


	/**
	 * Implementierung zu Aufgabe 1.e)
	 * @param a
	 */
	public void tiefensuche(Ort a) {
		bereitsBesuchteOrte = new LinkedList<Ort>();
		List<Ort> DFS = recTiefensuche(a);

		System.out.println("Tiefensuche von Ort " + a + ":");
		Iterator<Ort> itDFS = DFS.iterator();
		while (itDFS.hasNext()) {
			System.out.println(itDFS.next());
		}
	}



	/**
	 * Main-Methode als Einstiegspunkt.
	 */
	public static void main(String[] args) {
		//Stadtplan erzeugen und aus Datei einlesen
		Stadtplan plan = new Stadtplan();
		plan.einlesen("luebeck_city.txt");

		/**
		 * Testen der zu implementierenden Methoden
		 */

		Ort ort9 = plan.getOrt(9);
		/**
		 * Aufgabe 1.a)
		 */
		List<Ort> direkteNachfolger = plan.getDirekteNachfolger(ort9);
		System.out.println("Direkte Nachfolger von " + ort9 + " sind:");
		Iterator<Ort> itNachfolger = direkteNachfolger.iterator();
		Ort nachfolger;
		while (itNachfolger.hasNext()) {
			nachfolger = itNachfolger.next();
			System.out.println(nachfolger);
		}
		/*
		 *  Direkte Nachfolger von Theater Combinale (9) sind:
		 *  Marke13 (42)
		 *  Hüx (18)
		 *  Sporthalle (47)
		 */

		System.out.println();
		/**
		 * Aufgabe 1.b)
		 */
		List<Ort> direkteVorgaenger = plan.getDirekteVorgaenger(ort9);
		System.out.println("Direkte Vorgaenger von " + ort9 + " sind:");
		Iterator<Ort> itVorgaenger = direkteVorgaenger.iterator();
		Ort vorgaenger;
		while (itVorgaenger.hasNext()) {
			vorgaenger = itVorgaenger.next();
			System.out.println(vorgaenger);
		}
		/*
		 * Direkte Vorgaenger von Theater Combinale (9) sind:
		 *  Hüx (18)
		 *  Cafe Calma (48)
		 */

		System.out.println();
		/**
		 * Aufgabe 1.c)
		 */
		List<Ort> erreichbarOrte = plan.getErreichbarOrte(ort9);
		System.out.println("Erreichbare Orte von " + ort9 + " sind:");
		Iterator<Ort> itErreichbar = erreichbarOrte.iterator();
		Ort ort;
		while (itErreichbar.hasNext()) {
			ort = itErreichbar.next();
			System.out.println(ort);
		}
		/*
		 * Erreichbare Orte von Theater Combinale (9) sind:
		 *  Theater Combinale (9)
		 *  Hauptpost (12)
		 *  Hüx (18)
		 *  Sternschnuppe (24)
		 *  Marke13 (42)
		 *  Sporthalle (47)
		 *  Marke18 (49)
		 *  Marke19 (50)
		 */

		System.out.println();
		/**
		 * Aufgabe 1.d)
		 */
		Ort ort49 = plan.getOrt(49);
		System.out.println("Existiert ein Weg von " + ort9 + " nach " + ort49 + ": " + plan.existiertWeg(ort9, ort49));

		Ort ort10 = plan.getOrt(10);
		Ort ort36 = plan.getOrt(36);
		System.out.println("Existiert ein Weg von " + ort10 + " nach " + ort36 + ": " + plan.existiertWeg(ort10, ort36));
		/*
		 * Existiert ein Weg von Theater Combinale (9) nach Marke18 (49): true
		 * Existiert ein Weg von Johannis-Kloster (10) nach Marke7 (36): false
		 */
		
		System.out.println();
		/**
		 * Aufgabe 1.e)
		 */
		plan.tiefensuche(ort10);
		/*
		 * Tiefensuche von Ort Johannis-Kloster (10):
		 *  Johannis-Kloster (10)
		 *  Marke19 (50)
		 *  Sternschnuppe (24)
		 *  Marke18 (49)
		 *  Hauptpost (12)
		 *  Ordnungsamt (11)
		 */
	}



	/**
	 * Die Methode liest die übergebene Definition eines Stadplanes ein und generiert
	 * Ort- und Strasse-Objekte. Die Datei muss existieren und ein gültiges Format
	 * besitzen.
	 * @param dateiname der Dateiname
	 */
	public void einlesen(String dateiname) {
		orte = new LinkedList<Ort>();
		strassen = new LinkedList<Strasse>();

		Eingabe def = Eingabe.oeffnen(dateiname);

		int anzOrte = Integer.parseInt(def.readString());		// Anzahl der Orte
		int anzStrassen = Integer.parseInt(def.readString());	// Anzahl der Strassen

		for (int i = 0; i < anzOrte; i++) {						// Schleife über alle Orte
			String zeile = def.readString();
			int semikolon = zeile.indexOf(';');					// Position des ersten Semikolons
			String nummer = zeile.substring(0, semikolon);		// Extraktion der Nummer
			String name = zeile.substring(semikolon + 1, zeile.length()); // Extraktion des Namens
			Ort ort = new Ort(Integer.parseInt(nummer), name);	// Ort generieren
			orte.add(ort);										// Ort in Liste einfügen
		}

		for (int j = 0; j < anzStrassen; j++) {
			String zeile = def.readString();
			int semikolon = zeile.indexOf(';');					// Position des ersten Semikolons
			String nummer = zeile.substring(0, semikolon);		// Extraktion der Nummer
			zeile = zeile.substring(semikolon + 1, zeile.length()); // Zeile verkürzen

			semikolon = zeile.indexOf(';');						// Position des ersten Semikolons
			String name = zeile.substring(0, semikolon);		// Extraktion des Namens
			zeile = zeile.substring(semikolon + 1, zeile.length()); // Zeile verkürzen

			semikolon = zeile.indexOf(';');						// Position des ersten Semikolons
			String start = zeile.substring(0, semikolon);		// Extraktion des Startortes
			zeile = zeile.substring(semikolon + 1, zeile.length()); // Zeile verkürzen

			semikolon = zeile.indexOf(';');						// Position des ersten Semikolons
			String ziel = zeile.substring(0, semikolon);		// Extraktion des Zielortes
			zeile = zeile.substring(semikolon + 1, zeile.length()); // Zeile verkürzen

			semikolon = zeile.indexOf(';');						// Position des ersten Semikolons
			String richtung = zeile.substring(0, semikolon);	// Extraktion der Richtung
			String gewicht = zeile.substring(semikolon + 1, zeile.length()); // Extraktion der Länge

			Strasse strasse = new Strasse(Integer.parseInt(nummer), name); // Strasse erzeugen
			int startOrtNr = Integer.parseInt(start);
			Ort startOrt = orte.get(startOrtNr - 1);			// Startort aus Liste holen
			strasse.setBeginn(startOrt);
			int zielOrtNr = Integer.parseInt(ziel);
			Ort zielOrt = orte.get(zielOrtNr - 1);				// Zielort aus Liste holen
			strasse.setZiel(zielOrt);

			strasse.setGerichtet(richtung.toLowerCase().equals("gerichtet")); // Richtung wird gesetzt

			strasse.setGewicht(Integer.parseInt(gewicht));

			strassen.add(strasse); // Strasse zu Liste hinzufügen
		}
	}

	/**
	 * liefert der Ort zu einer gegebenen Nummer zurück
	 * @param nummer die Nummer des Ortes
	 * @return der zugehörige Ort
	 */
	public Ort getOrt(int nummer) {
		return orte.get(nummer - 1);
	}

 
}