import it.uniupo.graphLib.Edge;
import it.uniupo.graphLib.GraphInterface;
import it.uniupo.graphLib.UndirectedGraph;

import java.util.*;

public
class BFSAndDFSApp {
    private GraphInterface myGraph;
    private BFS bfs;
    private DFS dfs;

    private boolean[] scoperti;
    private int[] fathers;
    GraphInterface treeDFS;

    public BFSAndDFSApp(GraphInterface g) {
        myGraph = g;
        BFS bfs = new BFS(g);
        DFS dfs = new DFS(g);
        this.scoperti = new boolean[myGraph.getOrder()];
        this.treeDFS = this.myGraph.create();
        this.fathers = new int[myGraph.getOrder()];
        Arrays.fill(this.fathers, -1);
    }

    private boolean visitaDFS(int sorg) {
        if (sorg >= this.myGraph.getOrder() || sorg < 0) {
            throw new IllegalArgumentException("Sorgente non presenten nel grafo");
        }
        scoperti[sorg] = true;
        for (int node : this.myGraph.getNeighbors(sorg)) {
            if (!scoperti[node]) {
                fathers[node] = node;
                treeDFS.addEdge(sorg, node);
                return visitaDFS(node);
            } else if (node != fathers[node]) {
                return true;
            }
        }
        return false;
    }

    private void visitaBFS(int sorg) {
        scoperti[sorg] = true;
        Queue<Integer> q = new LinkedList<>();
        q.add(sorg);
        while (!q.isEmpty()) {
            int node = q.remove();
            for (Integer neighbour : this.myGraph.getNeighbors(node)) {
                if (!scoperti[neighbour]) {
                    scoperti[neighbour] = true;
                    q.add(neighbour);
                    fathers[neighbour] = node;
                }
            }
        }
    }


    public boolean hasUndirectedCycle() {
        for (int nodo = 0; nodo < this.myGraph.getOrder(); nodo++) {
            if (visitaDFS(nodo)) {
                return true;
            }
        }
        return false;
    }

    private void visitaDFSPostVisit(int sorg, ArrayList<Integer> orderPostVisit) {
        if (sorg >= this.myGraph.getOrder() || sorg < 0) {
            throw new IllegalArgumentException("Sorgente non presenten nel grafo");
        }
        scoperti[sorg] = true;
        for (int node : this.myGraph.getNeighbors(sorg)) {
            if (!scoperti[node]) {
                visitaDFSPostVisit(node, orderPostVisit);
            }
        }
        orderPostVisit.add(sorg);
    }

    public ArrayList<Integer> getNodesInOrderPostVisit(int sorg) {
        ArrayList<Integer> orderPostVisit = new ArrayList<>();
        visitaDFSPostVisit(sorg, orderPostVisit);
        return orderPostVisit;
    }

    private boolean hasDirCycleImpl(int sorg) {
        scoperti[sorg] = true;
        for (Integer node : myGraph.getNeighbors(sorg)) {
            if (!scoperti[node]) {
                fathers[node] = sorg;
                if (hasDirCycleImpl(node)) {
                    return true;
                }
            } else if (fathers[sorg] != -1 && node != fathers[sorg]) {
                return true;
            }
        }
        return false;
    }

    public boolean hasDirCycle() {
        if (myGraph instanceof UndirectedGraph) {
            throw new IllegalArgumentException("Impossibile usare hasDirCycle su un grafo non orientato");
        }
        for (int i = 0; i < myGraph.getOrder(); i++) {
            fathers = new int[myGraph.getOrder()];
            Arrays.fill(fathers, -1);
            scoperti = new boolean[myGraph.getOrder()];
            Arrays.fill(scoperti, false);
            if (hasDirCycleImpl(i)) {
                return true;
            }
        }
        return false;
    }


    public ArrayList<Edge> getShortestPath(int sorg, int dest) {
        ArrayList<Edge> path = new ArrayList<>();
        visitaBFS(sorg);
        int tmp = dest;
        while (fathers[tmp] != -1) {
            int x = tmp;
            tmp = fathers[tmp];
            path.add(new Edge(tmp, x));
        }
        //path.add(new Edge(sorg, tmp));
        Collections.reverse(path);
        return path;
    }
}