[AuD]Stadtplan

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);
    }


}