package graph;

import java.util.*;

public final class AdjListGraphMatrix extends AbstractGraph implements GraphAlgorithms.TopSort, GraphAlgorithms.DFS {

    private Knoten [] vertices;
    private int [][] verticesWeight;

    public AdjListGraph() { // default constructor
        this(false);
    }

    public AdjListGraph(boolean directed) {
        super(directed);
        vertices = new Knoten[0];
        verticesWeight = new int[0][0];
        
        for (int i=0; i<verticesWeight.length; i++)
        {
            vertices[i] = new Knoten();
            for (int j=0; j<verticesWeight.length; j++)
                verticesWeight[i][j] = 0;
        }
    }

    public AdjListGraph(AdjListGraph orig) { 
        super(orig.isDirected());
        vertices = new Knoten [orig.vertices.length];
        verticesWeight = new int[orig.verticesWeight.length][orig.verticesWeight.length];
        
        // Clone vertices
        for (int i=0; i<verticesWeight.length; i++)
        {
            vertices[i] = new Knoten();
            vertices[i].data = orig.vertices[i].data;
            for (int j=0; j<verticesWeight.length; j++)
                verticesWeight[i][j] = orig.verticesWeight[i][j];
        }
    }

    public boolean addVertex(Object vertex) {
        // Objekt darf nicht schon in der Knoten sein

        for (int i=0; i<vertices.length; i++)
            if (vertices[i].data.equals(vertex))
                    return false;

        Knoten [] newVertices = new Knoten [vertices.length+1];
        int [][] newVerticesWeight = new int [verticesWeight.length+1][verticesWeight.length+1];
        for (int i=0; i<newVerticesWeight.length-1; i++)
        {
            newVertices[i] = new Knoten();
            newVertices[i].data = vertices[i].data;
            for (int j=0; j<newVerticesWeight.length-1; j++)
                newVerticesWeight[i][j] = verticesWeight[i][j];
        }
        
        newVertices[vertices.length] = new Knoten();
        newVertices[vertices.length].data = vertex;
        
        vertices = newVertices;
        verticesWeight = newVerticesWeight;
        
        return true;
    }

    public boolean addEdge(Object from, Object to) {
        int fromPos = findVertex(from);
        int toPos = findVertex(to);
        
        if (fromPos == -1 || toPos == -1)
            return false;
        else
        {
            verticesWeight[fromPos][toPos] = 1;
            if (!isDirected())
                verticesWeight[toPos][fromPos] = 1;
            
            return true;
        }
    }

    public boolean removeEdge(Object from, Object to) {
        int fromPos = findVertex(from);
        int toPos = findVertex(to);

        if (fromPos == -1 || toPos == -1)
            return false;
        else
        {
            verticesWeight[fromPos][toPos] = 0;
            if (!isDirected())
                verticesWeight[toPos][fromPos] = 0;
            
            return true;
        }
    }

    public int getNofVertices() {
        return vertices.length;
    }

    public int getNofEdges() {
        int count = 0;
        
        for (int i=0; i<verticesWeight.length-1; i++)
            for (int j=0; j<verticesWeight.length-1; j++)
                if (verticesWeight[i][j] != 0)
                    count++;
            
        return count;
    }

    public Set getVertices() {
        Set set = new TreeSet();

        for (int i=0; i<vertices.length; i++)
            set.add(vertices[i].data);
            
        return set;
    }

    public Set getAdjacentVertices(Object vertex) {
        Set set = new TreeSet();

        int pos = findVertex(vertex);
        
        for (int i=0; i<verticesWeight[pos].length; i++)
            if (verticesWeight[pos][i] != 0)
                set.add(vertices[i].data);

        return set;
    }

    public Object clone() {
        return new AdjListGraph(this);
    }
    
    public void sort() {
        System.out.print("Top-Sort: ");
        
        for (int i=0; i<vertices.length; i++) // Anfangszustand herstellen
            vertices[i].visited = false;
        
        // VerbindunsKnoten kopieren
        int [][] tempVerticesWeight = new int [verticesWeight.length][verticesWeight.length];
        for (int i=0; i<verticesWeight.length; i++)
            for (int j=0; j<verticesWeight.length; j++)
                tempVerticesWeight[i][j] = verticesWeight[i][j];
        
        for (int i=0; i<vertices.length; i++) { // Durchsuche ganzen Graph
            Knoten knoten = searchVertex(tempVerticesWeight); // Suche nach Vertex ohne Abhängigkeiten
            
            if (knoten==null) {
                System.out.println("\nError: Graph hat einen Zyklus");
                return;
            }
           
            System.out.print(knoten.data + " ");

            knoten.visited=true;
            
            // Nachbarn aktualisieren
            int pos = findVertex(knoten.data);
            for (int j=0; j<tempVerticesWeight.length; j++)
                tempVerticesWeight[pos][j] = 0;
        }
        
        System.out.println("");
    }

    private Knoten searchVertex(int [][] verbindungsKnoten)
    {
        int count;
        for (int i=0; i<verbindungsKnoten.length; i++) { // Suche geeigneten Vertex im Graphen
            count = 0;
            if (!vertices[i].visited) {
                for (int j=0; j<verbindungsKnoten.length; j++) {
                    if (verbindungsKnoten[j][i] == 1)
                        count++;
                }
                if (count == 0)
                    return vertices[i];
            }
        }
                
        return null;
    }

    public Graph traverse(Object startVertex) {
        //Graph für Spannungtree
        Graph spanningGraph = new AdjListGraph(true);
        
        for (int i=0; i<vertices.length; i++) // Anfangszustand herstellen
            vertices[i].visited = false;
        
        System.out.print("DFS: ");
        spanningGraph.addVertex(vertices[findVertex(startVertex)].data);
        dfs(findVertex(startVertex), spanningGraph);
        System.out.println("");
        
        return spanningGraph;
    }

    private void dfs(int v, Graph spanningGraph) {
        if (!vertices[v].visited) {
            System.out.print(vertices[v].data + " ");
            vertices[v].visited=true;
            
            for (int w=0; w<verticesWeight.length; w++) { // Nachbarknoten besuchen
                if (!vertices[w].visited && verticesWeight[v][w] == 1)  {
                    spanningGraph.addVertex(vertices[w].data);
                    spanningGraph.addEdge(vertices[v].data, vertices[w].data);
                    dfs(w, spanningGraph);
                }
            }
        }
    }
    
    private int findVertex(Object vertex)
    {
        for (int i=0; i<vertices.length; i++) // Suche From
            if (vertices[i].data.equals(vertex))
                return i;
            
         return -1;
    }
}

class Knoten {
    Object data;
    boolean visited;
}