package ad1.ss16.pa;
import java.util.*;
import java.util.logging.Level;
import java.util.logging.Logger;

public class Network implements Cloneable{

    int currNodes = 0;
    Node[] nodes;
    boolean[] discovered; //ob Knoten schon entdeckt ist
    int distances [];

    /* Konstruktor
       Benoetigte Instanzvariablen initialisieren
    */

    public Network(Network net) {
        this.nodes = net.nodes;
        this.discovered = net.discovered;
        this.distances = net.distances;
        this.numberOfComp = net.numberOfComp;
        this.critical = net.critical;
        this.countChild = net.countChild;
    }


    public Network(int n) {
        this.nodes = new Node[n];
        for (int i = 0; i < this.nodes.length; i++) {
            this.nodes[i] = new Node();
        }

        this.distances = new int[nodes.length];
        this.discovered = new boolean[nodes.length];
        this.critical = new LinkedList <Integer>();
    }

    //einfach die Laenge zurueckgeben
    public int numberOfNodes() {
        return this.nodes.length;
    }

    /*
        Die Groesse der Adjazenzlisten addieren
        Jede Connetions ist zwei Mal enthalten. Dadurch vor dem Zurueckgeben durch zwei addieren
        Dies ergebit die Anzahl der Connections
    */
    public int numberOfConnections() {
        int help = 0;
        for (int i = 0; i < this.nodes.length; i++)
            help = help + this.nodes[i].adjazenzList.size();

        help = help/2;
        return help;
    }

    /*
        Parameter v und w darf natuerlich nicht gleich sein
        Dann ueberpruefen ob die Connection eventuell schon besteht
        Danach den jeweiligen Knoten in die jeweilige Adjazenzliste einfuegen
    */
    public void addConnection(int v, int w) {
        if (v != w) {
            if (!this.nodes[v].adjazenzList.contains(w)) {
                this.nodes[v].adjazenzList.add(w);
                this.nodes[w].adjazenzList.add(v);
            }
        }
    }
    /*
        Nimmt addConnection (int v, intw) zur Hilfe
    */
    public void addAllConnections(int v) {
        for (int i = 0; i < this.nodes.length; i++) {
            this.addConnection (v, i);
        }
    }

    /*
        Connection loeschen
        Einfach in beiden Adjazenzlisten den jeweiligen Knoten entfernen
    */
    public void deleteConnection(int v, int w) {
        this.nodes[v].adjazenzList.remove(w);
        this.nodes[w].adjazenzList.remove(v);
    }

    /*
        Loescht so lange Knoten bis peek() null liefert
        Zur Hilfe wird deleteConnection (int v, int w) genutzt
    */
    public void deleteAllConnections(int v) {
        while (nodes[v].adjazenzList.peek() != null) {
           this.deleteConnection(v, this.nodes[v].adjazenzList.peek());
        }
    }


    /*

    */
    int numberOfComp;

    public int numberOfComponents() {
        Arrays.fill(this.discovered, false);

        this.numberOfComp =0;

        for (int i=0; i<this.nodes.length; i++){
            if (!discovered[i]) {
                this.numberOfComp++;
                this.numberOfComponents(i);
            }
        }

        return this.numberOfComp;

    }


    private void numberOfComponents(int z) {
        this.discovered[z]=true;

        for (int n : this.nodes[z].adjazenzList) {
            if (!this.discovered[n])
                this.numberOfComponents(n);
        }
    }

    /*
        Wenn die Anzahl der Knoten kleiner sind als die Connections, muss ein Kreis existieren
    */
    public boolean hasCycle() {
        int standalones = 0;

        for (Node n : this.nodes) {
            if (n.adjazenzList.isEmpty() && n.adjazenzList != null)
                standalones ++;
        }

        if (this.numberOfConnections() != 0 || !(this.numberOfComponents() >= this.numberOfNodes())) {
            if ((this.numberOfNodes() - standalones - (this.numberOfComponents()-standalones-1)) <= this.numberOfConnections())
                return true;
        }
        return false;
    }

    public int minimalNumberOfConnections(int start, int end) {
        // Wenn Startknoten gleich Endknoten ist, dann ist die Reichweite = 0
        if (start == end) {
            return 0;
        }

        return this.shortestPath(0, -1, start, end);


    }

    /*
        Tarjan Algorithmus verwendet
    */

    public List<Integer> criticalNodes() {

        this.critical = new LinkedList<Integer>();
        Arrays.fill(this.discovered, false);
        for (int i = 0; i < nodes.length; i++) {
            if (!this.discovered[i]) {
                this.calculateCritical(i);
            }
        }
        return this.critical;
    }

    LinkedList<Integer> critical;
    int time;

    public void calculateCritical(int start) {
        this.time = 0;
        this.nodes[start].parent = -1;
        this.countChild = 0;
        this.DFS(start);
    }

    /*
    LinkedList <Integer> critical;
     public List<Integer> criticalNodes(){
         int actualComponents = this.numberOfComponents();
         critical = new LinkedList <Integer>();

         Network clone = new Network (this);


         for (Node n : this.nodes) {
             for (int s : n.adjazenzList) {
                 clone.deleteAllConnections(s);
                 if(actualComponents+2 <= clone.numberOfComponents())
                     critical.add(s);
             }
         }




         return critical;
     }
*/

    /*
       ***************************************************************************
       *                        HELPER SECTION                                   *
       ***************************************************************************
    */


/*
    Stack<Integer> tempstack;
    Stack<Integer> auxStack;

    private void newDFS(int actualnode) {
        this.tempstack = new Stack<Integer>();
        this.discovered[actualnode] = true;
        tempstack.push(actualnode);

        while (!tempstack.isEmpty()) {
            int v = tempstack.pop();
            if (!this.discovered[v]) {
                this.discovered[v] = true;

                this.auxStack = new Stack<Integer>();
                for (int w : this.nodes[v].adjazenzList) {
                    if (!this.discovered[w]) {
                        this.auxStack.push(w);
                    }
                }
                while (!auxStack.isEmpty()) {
                    tempstack.push(auxStack.pop());
                }
            }
        }

    }*/


    int countChild;

    private void DFS(int actualnode) {

        this.discovered[actualnode] = true;
        this.nodes[actualnode].ltime = time++;
        this.nodes[actualnode].time = time;

        if (this.nodes[actualnode].parent == -1) {
            this.countChild = 0;
        }
        this.nodes[actualnode].isAP = false;

        Iterator tempIT = nodes[actualnode].adjazenzList.iterator();
        while (tempIT.hasNext()) {
            int adjazenz = (Integer) tempIT.next();

            if (adjazenz == this.nodes[actualnode].parent) {
                continue;
            }

            if (!this.discovered[adjazenz]) {
                this.nodes[adjazenz].parent = actualnode;
                if (this.nodes[actualnode].parent == -1) {
                    this.countChild++;
                }

                this.DFS(adjazenz);

                if (this.nodes[actualnode].time <= nodes[adjazenz].ltime) {
                    this.nodes[actualnode].isAP = true;
                } else {
                    this.nodes[actualnode].ltime = Math.min(nodes[actualnode].ltime, nodes[adjazenz].ltime);
                }
            } else {
                this.nodes[actualnode].ltime = Math.min(nodes[actualnode].ltime, nodes[adjazenz].time);
            }
        }

        if (this.nodes[actualnode].parent == -1 && this.countChild >= 2 || this.nodes[actualnode].parent != -1 && this.nodes[actualnode].isAP) {
            this.critical.add(actualnode);
        }
    }



    public int shortestPath(int level, int nextlevel, int start, int end) {
        Arrays.fill(this.discovered, false);

        this.discovered[start] = true;

        Queue<Integer> q = new LinkedList<Integer>();

        q.offer(start);

        while (!q.isEmpty()) {
            int help = q.poll();

            if (help == nextlevel) {
                nextlevel = -1;
                level++;
            }

            if (help == end) {
                return level;
            }

            for (int node : this.nodes[help].adjazenzList) {
                if (!discovered[node]) {
                    discovered[node] = true;
                    q.offer(node);

                    if (nextlevel == -1) {
                        nextlevel = node;
                    }
                }
            }
        }

        return -1;
    }

    /*
        Node Klasse - stellt ein Blatt dar.
    */
private class Node {

        public Queue<Integer> adjazenzList;
        int time;
        int ltime;
        int parent;
        boolean isAP;

        public Node() {
            this.adjazenzList = new PriorityQueue<Integer>();
        }

        public void clone (Node n) {
            this.adjazenzList = n.adjazenzList;
            this.time = n.time;
            this.ltime= n.ltime;
            this.parent=n.parent;
            this.isAP=n.isAP;
        }

    }
}