import java.util.ArrayList;
import java.util.Iterator;
import java.util.Random;
/**
 * Vernetzungsprobleme sammelt einige Algorithmen zur Bearbeitung von Graphen
 * Variante zum Messen der Komplexitaet.
 * 
 * @author MB
 * @version MAR 2019           
 */
public class Vernetzungsprobleme
{
    private static long counter = 0;
    private static int[] id;
    private static Random r = new Random();
    
    /**
     * Ueberprueft anhand einer Eingabe von Knoten (dargestellt von Zahlen), ob in einem Array, diese Knoten
     * transitiv miteinander verbunden sind. Neue Verbindungen werden auf der Konsole angezeigt.
     * Dieser Algorithmus findet schnell heraus, ob zwei Knoten verbunden sind. Die transitive Vereinigung
     * erfordert allerdings insgesamt quadratischen Aufwand, da bei allen Objekten die Identitaet der Menge
     * neu gesetzt wird (der Feldinhalt wird entsprechend geaendert).
     * @param anzahl - Groesse des Arrays
     * @param zahlen - die Liste der verbundenen Paare
     * @return - Anzahl der Initialisierungs-, Such- und Vereinigungsoperationen
     */
    private static long quickFindConnection(int anzahl, ArrayList<String> zahlen){
        int p = 0, q = 0, t = 0;
        counter = 0;
        // Initialisierung des Inputs: dieser muss aus einer Folge von Indices bestehen
        Iterator<String> it = zahlen.iterator();
        while(it.hasNext()){
            p = (new Integer(it.next())).intValue();
            if (it.hasNext()){ // testen, ob die Anzahl der eingegebenen Zahlen wirklich gerade war
                q = (new Integer(it.next())).intValue();
            }
            else{
                continue; // Abbruch
            }
            if (true){ // urspruengliche Testbedingung hat sich hier eruebrigt
                t = id[p];
                if (t == id[q]){    // das Paar ist schon verbunden
                    continue;
                }
                for(int i = 0; i < anzahl; i++){
                    if(id[i] == t){
                        id[i] = id[q];  // alle, die schon mit p verbunden waren, werden mit q verbunden,
                                        // indem die Feldinhalte gleich gesetzt werden
                    }
                    counter++;
                }
            }
            counter++;
        }
        return counter;
    }
           
    /**
     * Ueberprueft anhand einer Eingabe von Knoten (dargestellt von Zahlen), ob in einem Array, diese Knoten
     * transitiv miteinander verbunden sind. Neue Verbindungen werden auf der Konsole angezeigt.
     * Dieser Algorithmus sucht laenger, ob zwei Knoten verbunden sind. Die transitive Vereinigung
     * erfordert allerdings insgesamt weniger Aufwand, denn es werden nicht alle Feldinhalte geaendert, sondern
     * nur der oberste Feldinhalt, der bisher dem obersten Verweisungsindex entsprach, wird auf den neuen obersten
     * Verweisungsindex gesetzt.
     * @param anzahl - Groesse des Arrays
     * @param zahlen - die Liste der verbundenen Paare
     * @return - Anzahl der Initialisierungs-, Such- und Vereinigungsoperationen
     */
    private static long quickUnionConnection(int anzahl, ArrayList<String> zahlen){
        int p = 0, q = 0, i = 0, j = 0;
        counter = 0;
        // Initialisierung des Inputs: dieser muss aus einer Folge von Indices bestehen
        Iterator<String> it = zahlen.iterator();
        while(it.hasNext()){
            p = (new Integer(it.next())).intValue();
            if (it.hasNext()){ // testen, ob die Anzahl der eingegebenen Zahlen wirklich gerade war
                q = (new Integer(it.next())).intValue();
            }
            else{
                continue; // Abbruch
            }
            if (true){
                for(i = p; i != id[i]; i = id[i]){ // suche die Wurzel zum Teilbaum
                    counter++;    
                } 
                for(j = q; j != id[j]; j = id[j]){
                    counter++;
                } 
                if (i == j){
                    continue;   // die beiden verweisen schon aufeinander
                }
                id[i] = j; // neuer Verweis
            }
            counter++;
        }
        return counter;
    }
    
     /**
     * Ueberprueft anhand einer Eingabe von Knoten (dargestellt von Zahlen), ob in einem Array, diese Knoten
     * transitiv miteinander verbunden sind. Neue Verbindungen werden auf der Konsole angezeigt.
     * Dieser Algorithmus sucht laenger, ob zwei Knoten verbunden sind. Die transitive Vereinigung
     * erfordert allerdings insgesamt weniger Aufwand. In dieser Variante wird die Vereinigung von der
     * kleineren Menge (dem kleineren Teilbaum) aus vollzogen. Die Suche wird dadurch logarithmisch relativ
     * zur H�he des Baums.
     * @param anzahl - Groesse des Arrays
     * @param zahlen - die Liste der verbundenen Paare
     * @return - Anzahl der Initialisierungs-, Such- und Vereinigungsoperationen
     */
    private static long weightedQuickUnionConnection(int anzahl, ArrayList<String> zahlen){
        int p = 0, q = 0, i = 0, j = 0;
        counter = 0;
        int[] size = new int[anzahl];
        for(i = 0; i < anzahl; i++){   // diese Schleife wird im counter nicht mitgezaelt, da sie normalerweise
                                      // zusammen mit der Initialisierung des Arrays id[] erfolgt
            size[i] = 1;    // am Anfang verweist jeder Knoten nur auf sich
        }
        // Initialisierung des Inputs: dieser muss aus einer Folge von Indices bestehen
        Iterator<String> it = zahlen.iterator();
        while(it.hasNext()){
            p = (new Integer(it.next())).intValue();
            if (it.hasNext()){ // testen, ob die Anzahl der eingegebenen Zahlen wirklich gerade war
                q = (new Integer(it.next())).intValue();
            }
            else{
                continue; // Abbruch
            }
            if (true){
                for(i = p; i != id[i]; i = id[i]){
                    counter++;
                } 
                for(j = q; j != id[j]; j = id[j]){
                    counter++;
                }
                if (i == j){
                    continue;   // die beiden verweisen schon aufeinander
                }
                // jetzt spielt die Groesse der Teilmengen eine Rolle
                if(size[i] < size[j]){
                    id[i] = j; // neuer Verweis
                    size[j] += size[i];
                }
                else {
                    id[j] = i;
                    size[i] += size[j];
                }
            }
            counter++;
        }
        return counter;
    }
    
    /**
     * Ueberprueft anhand einer Eingabe von Knoten (dargestellt von Zahlen), ob in einem Array, diese Knoten
     * transitiv miteinander verbunden sind. Neue Verbindungen werden auf der Konsole angezeigt.
     * Dieser Algorithmus sucht laenger, ob zwei Knoten verbunden sind. Die transitive Vereinigung
     * erfordert allerdings insgesamt weniger Aufwand. In dieser Variante wird die Vereinigung von der
     * kleineren Menge (dem kleineren Teilbaum) aus vollzogen. Die Suche wird dadurch logarithmisch relativ
     * zur Hoehe des Baums. Ausserdem wird jeweils der Pfad eines Knoten relativ zu seiner zunaechst vorliegenden
     * Laenge halbiert. Insgesamt ergibt sich eine fast lineare Laufzeit.
     * @param anzahl - Groesse des Arrays
     * @param zahlen - die Liste der verbundenen Paare
     * @return - Anzahl der Initialisierungs-, Such- und Vereinigungsoperationen
     */
    private static long weightedQuickUnionConnectionWithPathDivision(int anzahl, ArrayList<String> zahlen){
        int p = 0, q = 0, i = 0, j = 0;
        counter = 0;
        int[] size = new int[anzahl];
        for(i = 0; i < anzahl; i++){  // diese Schleife wird im counter nicht mitgezaelt, da sie normalerweise
                                      // zusammen mit der Initialisierung des Arrays id[] erfolgt
            size[i] = 1;    // am Anfang verweist jeder Knoten nur auf sich
        }
        // Initialisierung des Inputs: dieser muss aus einer Folge von Indices bestehen
        Iterator<String> it = zahlen.iterator();
        while(it.hasNext()){
            p = (new Integer(it.next())).intValue();
            if (it.hasNext()){ // testen, ob die Anzahl der eingegebenen Zahlen wirklich gerade war
                q = (new Integer(it.next())).intValue();
            }
            else{
                continue; // Abbruch
            }
            if (true){
                for(i = p; i != id[i]; i = id[i]){ // gesucht wird die Menge zu p
                    id[i] = id[id[i]];  // dabei wird der Pfad halbiert
                    counter++;
                } 
                for(j = q; j != id[j]; j = id[j]){
                    id[j] = id[id[j]];
                    counter++;
                } 
                if (i == j){
                    continue;   // die beiden verweisen schon aufeinander
                }
                // jetzt spielt die Groesse der Teilmengen eine Rolle
                if(size[i] < size[j]){
                    id[i] = j; // neuer Verweis
                    size[j] += size[i];
                }
                else {
                    id[j] = i;
                    size[i] += size[j];
                }
            }
            counter++;
        }
        return counter;
    }
    
    /**
     * Testmethode zum Laufzeitvergleich und Vergleich der benoetigten Schritte.
     * Die Vorteile der Gewichtung zeigen sich erst bei grosser Anzahl der zu betrachteten Objekte.
     * Die Vorteile der Pfadhalbierung fallen i.d.R. kaum ins Gewicht.
     * @param - Anzahl der zu betrachtenden Objekte
     */
    public static void vergleichVernetzungsalgorithmen(int anzahl){
        ArrayList<String> eingabe = new ArrayList<String>();
        String s = "";
        id = new int[anzahl];
        System.out.println("Erstellen der Eingabe bei Array-Laenge " + anzahl);
        // die Anzahl der Informationen (Paare) wird hier auf einen zufaelligen Standard gesetzt
        int faktor = r.nextInt(5)+1;
        for(int i = 0; i < anzahl*faktor; i++){
           s = "" + r.nextInt(anzahl); // hier wird auch Speicher und Zeit verbraucht!
           eingabe.add(s);
        }
        System.out.println("Laenge der Eingabe: " + eingabe.size());
        System.out.println("Beginn des Vergleiches.");
        // erste Befuellung des Array
        for(int i = 0; i < anzahl; i++){   // die Indices repraesentieren die Knoten, die Feldinhalte werden
                                           // verwendet, um eine Verbindung durch Gleichheit des Inhalts zu markieren 
            id[i] = i;  // am Anfang ist jedes Objekt nur mit sich selbst verbunden
        }
        Timer.start(false);
        System.out.println("quickFindConnection benoetigt " + quickFindConnection(anzahl, eingabe) + " Schritte.");
        System.out.println(Timer.stop());
        // Array zuruecksetzen!
        for(int i = 0; i < anzahl; i++){   // die Indices repraesentieren die Knoten, die Feldinhalte werden
                                           // verwendet, um eine Verbindung durch Gleichheit des Inhalts zu markieren 
            id[i] = i;  // am Anfang ist jedes Objekt nur mit sich selbst verbunden
        }
        // Die sleep-Phasen sollen eine Verzerrung im Millisekundenbereich beseitigen, die mit dem Algorithmus nicht zusammenhaengt
        try{
            Thread.sleep(2000);
        }
        catch(Exception e){
            System.err.println(e.toString());
        }
        Timer.start(false);
        System.out.println("quickUnionConnection benoetigt " + quickUnionConnection(anzahl, eingabe) + " Schritte.");
        System.out.println(Timer.stop());
        // Array zuruecksetzen!
        for(int i = 0; i < anzahl; i++){   // die Indices repraesentieren die Knoten, die Feldinhalte werden
                                           // verwendet, um eine Verbindung durch Gleichheit des Inhalts zu markieren 
            id[i] = i;  // am Anfang ist jedes Objekt nur mit sich selbst verbunden
        }
        try{
            Thread.sleep(2000);
        }
        catch(Exception e){
            System.err.println(e.toString());
        }
        Timer.start(false);
        System.out.println("weightedQuickUnionConnection benoetigt " + weightedQuickUnionConnection(anzahl, eingabe) + " Schritte.");
        System.out.println(Timer.stop());
        // Array zuruecksetzen!
        for(int i = 0; i < anzahl; i++){   // die Indices repraesentieren die Knoten, die Feldinhalte werden
                                           // verwendet, um eine Verbindung durch Gleichheit des Inhalts zu markieren 
            id[i] = i;  // am Anfang ist jedes Objekt nur mit sich selbst verbunden
        }
        try{
            Thread.sleep(2000);
        }
        catch(Exception e){
            System.err.println(e.toString());
        }
        Timer.start(false);
        System.out.println("weightedQuickUnionConnectionWithPathDivision benoetigt " + weightedQuickUnionConnectionWithPathDivision(anzahl, eingabe) + " Schritte.");
        System.out.println(Timer.stop());
        System.out.println("Ende");
    }
        
}
/**
 *  Timer misst die Laufzeit von Vorgaengen.
 * 
 */
class Timer
{
    private static long  dauer = 0;

    /**
     * Startet den Timer mit der Systemzeit in Millisekunden, meldet den Start
     * 
     */
    public static void start()
    {
        dauer = System.currentTimeMillis();
        System.out.println("Stoppuhr gestartet.");
    }
    
    /**
     * Startet den Timer mit der Systemzeit in Millisekunden, meldet den Start
     * nur, wenn Eingabeparameter auf "true" steht
     * @param ausgabe - wenn "true" dann Ausgabe
     */
    public static void start(boolean ausgabe)
    {
        dauer = System.currentTimeMillis();
        if (ausgabe){
           System.out.println("Stoppuhr gestartet.");
        }

    }
    
    /**
     *  Stoppt den Timer und gibt die benoetigte Zeit formatiert zurueck
     *  @return - die Zeit in entsprechenden Einheiten
     */
    
    public static String stop()
    {
        String out = "";
        dauer -= System.currentTimeMillis();
        dauer = -1 * dauer;
        String time = "";
        if (dauer > 60000){
            dauer = dauer/60000;
            if (dauer == 1){
                time = "Minute";
            }
            else {
                time = "Minuten";
            }
        }
        else if (dauer > 1000){
            dauer = dauer/1000;
            if (dauer == 1){
                time = "Sekunde";
            }
            else {
                time = "Sekunden";
            }
        }
        else {
            time = "Millisekunden";
        }
        out = "Dauer: " + dauer + " " + time + " .";
        return out;
    }
    
    /**
     *  Stoppt den Time und gibt die benoetigte Zeit als positiven Wert in Millisekunden zurueck
     *  
     *  @return dauer - Wert der gemessenen Millisekunden
     */
    
    public static long stopWert()
    {
       
        dauer -= System.currentTimeMillis();
        dauer = -1 * dauer;
        return dauer;
    }
}