import java.util.*;


public class Graph implements Iterable<Integer> {

    private LinkedList<Edge>[] adjLists;
    private int vertexCount;

    /* Initializes a graph with NUMVERTICES vertices and no Edges. */
    public Graph(int numVertices) {
        adjLists = (LinkedList<Edge>[]) new LinkedList[numVertices];
        for (int k = 0; k < numVertices; k++) {
            adjLists[k] = new LinkedList<Edge>();
        }
        vertexCount = numVertices;
    }

    /* Adds a directed Edge (V1, V2) to the graph. That is, adds an edge
       in ONE directions, from v1 to v2. */
    public void addEdge(int v1, int v2) {
        addEdge(v1, v2, 0);
    }

    /* Adds an undirected Edge (V1, V2) to the graph. That is, adds an edge
       in BOTH directions, from v1 to v2 and from v2 to v1. */
    public void addUndirectedEdge(int v1, int v2) {
        addUndirectedEdge(v1, v2, 0);
    }

    /* Adds a directed Edge (V1, V2) to the graph with weight WEIGHT. If the
       Edge already exists, replaces the current Edge with a new Edge with
       weight WEIGHT. */
    public void addEdge(int v1, int v2, int weight) {
        // go through adjacent list and make sure edge
        for (Edge i : adjLists[v1]) {
            if (i.to == v2) {
                adjLists[v1].remove(i);
            }
        }
        Edge v2Edge = new Edge(v1, v2, weight);
        adjLists[v1].add(v2Edge);
    }

    /* Adds an undirected Edge (V1, V2) to the graph with weight WEIGHT. If the
       Edge already exists, replaces the current Edge with a new Edge with
       weight WEIGHT. */
    public void addUndirectedEdge(int v1, int v2, int weight) {
        for (Edge i : adjLists[v1]) {
            if (i.to == v2) {
                adjLists[v1].remove(i);
            }
        }
        for (Edge i : adjLists[v2]) {
            if (i.to == v1) {
                adjLists[v2].remove(i);
            }
        }
        Edge newEdge = new Edge(v1, v2, weight);
        Edge newEdge2 = new Edge(v2, v1, weight);
        adjLists[v1].add(newEdge);
        adjLists[v2].add(newEdge2);
    }

    /* Returns true if there exists an Edge from vertex FROM to vertex TO.
       Returns false otherwise. */
    public boolean isAdjacent(int from, int to) {
        for (Edge i : adjLists[from]) {
            if (i.to == to) {
                return true;
            }
        }
        return false;
    }

    /* Returns a list of all the vertices u such that the Edge (V, u)
       exists in the graph. */
    public List<Integer> neighbors(int v) {
        List<Integer> a = new ArrayList<>();
        for (Edge i : adjLists[v]) {
            a.add(i.to);
        }
        return a;
    }
    /* Returns the number of incoming Edges for vertex V. */
    public int inDegree(int v) {
        int count = 0;
        for (int i = 0; i < vertexCount; i++) {
            if (isAdjacent(i, v)) {
                count += 1;
            }
        }
        return count;
    }

    /* Returns an Iterator that outputs the vertices of the graph in topological
       sorted order. */
    public Iterator<Integer> iterator() {
        return new TopologicalIterator();
    }

    /**
     *  A class that iterates through the vertices of this graph,
     *  starting with a given vertex. Does not necessarily iterate
     *  through all vertices in the graph: if the iteration starts
     *  at a vertex v, and there is no path from v to a vertex w,
     *  then the iteration will not include w.
     */
    private class DFSIterator implements Iterator<Integer> {

        private Stack<Integer> fringe;
        private HashSet<Integer> visited;

        public DFSIterator(Integer start) {
            fringe = new Stack<>();
            visited = new HashSet<>();
            fringe.push(start);
        }

        public boolean hasNext() {
            if (!fringe.isEmpty()) {
                int i = fringe.pop();
                while (visited.contains(i)) {
                    if (fringe.isEmpty()) {
                        return false;
                    }
                    i = fringe.pop();
                }
                fringe.push(i);
                return true;
            }
            return false;
        }

        public Integer next() {
            int curr = fringe.pop();
            ArrayList<Integer> lst = new ArrayList<>();
            for (int i : neighbors(curr)) {
                lst.add(i);
            }
            lst.sort((Integer i1, Integer i2) -> -(i1 - i2));
            for (Integer e : lst) {
                fringe.push(e);
            }
            visited.add(curr);
            return curr;
        }

        //ignore this method
        public void remove() {
            throw new UnsupportedOperationException(
                    "vertex removal not implemented");
        }

    }

    /* Returns the collected result of performing a depth-first search on this
       graph's vertices starting from V. */
    public List<Integer> dfs(int v) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        Iterator<Integer> iter = new DFSIterator(v);

        while (iter.hasNext()) {
            result.add(iter.next());
        }
        return result;
    }

    /* Returns true iff there exists a path from START to STOP. Assumes both
       START and STOP are in this graph. If START == STOP, returns true. */
    public boolean pathExists(int start, int stop) {
        if (dfs(start).contains(stop)) {
            return true;
        }
        else {
            return false;
        }
    }


    /* Returns the path from START to STOP. If no path exists, returns an empty
       List. If START == STOP, returns a List with START. */
    public List<Integer> path(int start, int stop) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        ArrayList<Integer> path = new ArrayList<Integer>();
        ArrayList<Integer> finalPath = new ArrayList<Integer>();
        Iterator<Integer> iter = new DFSIterator(start);
        if (!pathExists(start, stop)) {
            return result;
        }
        while (iter.hasNext()) {
            int temp = iter.next();
            if (temp == stop) {
                result.add(temp);
                break;
            }
            result.add(temp);
        }
        int temp = result.get(result.size()-1);
        for(int j = result.size()-1; j >= 0; j--) {
            if(j == 0){
                break;
            }
            if (isAdjacent(temp, result.get(j - 1))) {
                path.add(result.get(j));
                temp = result.get(j - 1);
            }
        }
        for(int i = path.size()-1; i >= 0; i--){
            finalPath.add(result.get(i));
        }
        return finalPath;
    }

    public List<Integer> topologicalSort() {
        ArrayList<Integer> result = new ArrayList<Integer>();
        Iterator<Integer> iter = new TopologicalIterator();
        while (iter.hasNext()) {
            result.add(iter.next());
        }
        return result;
    }

    private class TopologicalIterator implements Iterator<Integer> {

        private Stack<Integer> fringe;

        private ArrayList<Integer> currentInDegree;

        private HashSet<Integer> visited;

        // TODO: Instance variables here!

        TopologicalIterator() {

            fringe = new Stack<Integer>();

            visited = new HashSet<>();

            currentInDegree  = new ArrayList<Integer>();

            for (int i = 0; i < adjLists.length ; i++) {
                 if (inDegree(i) == 0) {
                     fringe.push(i);
                 }
                currentInDegree.add(inDegree(i));
            }
        }

        public boolean hasNext() {
            if (!fringe.isEmpty()) {
                int i = fringe.pop();
                while (visited.contains(i)) {
                    if (fringe.isEmpty()) {
                        return false;
                    }
                    i = fringe.pop();
                }
                fringe.push(i);
                return true;
            }
            return false;
        }

        public Integer next() {
            int curr = fringe.pop();
            ArrayList<Integer> lst = new ArrayList<>();
            for (int i : neighbors(curr)) {
                int prevInd = currentInDegree.get(i);
                currentInDegree.set(i, prevInd - 1);
                lst.add(i);
            }
            for (Integer e : lst) {
                if (currentInDegree.get(e) == 0) {
                    fringe.push(e);
                }
            }
            visited.add(curr);
            return curr;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

    }

    public Edge getEdge(int u, int v) {
        for (Edge i : adjLists[u]) {
            if (i.to == v) {
                return i;
            }
        }
        return null;
    }
    public List<Integer> shortestPath(int start, int stop) {
        int[] DistTo = new int[vertexCount];
        int[] edgeTo = new int[vertexCount];
        Boolean[] visited = new Boolean[vertexCount];
        HashMap<Integer, Edge> neighbor = new HashMap<>();
        ArrayList<Integer> result = new ArrayList<>();
        PriorityQueue<Edge> fringePQ = new PriorityQueue<>();
        for (int i : neighbors(start)) {
            fringePQ.add(getEdge(start, i));
            neighbor.put(i, getEdge(start, i));
        }

        for (int i = 0; i < vertexCount; i++) {
            DistTo[i] = 2147483647;
            visited[i] = false;
        }

        while (fringePQ.peek().to != stop) {
            Edge currentVertex = fringePQ.poll();
            for (int i : neighbors(currentVertex.to)) {
                if (visited[i] == false) {
                    Edge newEdge = getEdge(currentVertex.to, i);
                    if (!neighbor.containsKey(i) || neighbor.get(i).weight > newEdge.weight + (neighbor.get(currentVertex.to).weight)) {
                        Edge newNewEdge = new Edge(currentVertex.to, i, newEdge.weight + (neighbor.get(currentVertex.to).weight));
                        fringePQ.add(newNewEdge);
                        neighbor.put(i, newNewEdge);
                        DistTo[i] = currentVertex.weight;
                        edgeTo[i] = currentVertex.from;

                    }
                    else {
                        fringePQ.add(newEdge);
                        neighbor.put(i, newEdge);
                        DistTo[i] = currentVertex.weight;
                        edgeTo[i] = currentVertex.from;
                    }
                }
            }
        }



        result.add(stop);
        int currentEdge = edgeTo[stop];
        for (int i = vertexCount; i < 0; i--) {
            if (i == currentEdge) {
                result.add(0, i);
                currentEdge = edgeTo[currentEdge];
            }
        }
        return result;
    }

    private class Edge implements Comparable {

        @Override
        public int compareTo(Object o) {
            Edge newEdge = (Edge) o;
            if (this.weight > newEdge.weight) {
                return 1;
            }
            else if (this.weight < newEdge.weight) {
                return -1;
            }
            else {
                return 0;
            }
        }

        private int from;
        private int to;
        private int weight;

        Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public String toString() {
            return "(" + from + ", " + to + ", weight = " + weight + ")";
        }

    }

    private void generateG1() {
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(0, 4);
        addEdge(1, 2);
        addEdge(2, 0);
        addEdge(2, 3);
        addEdge(4, 3);
    }

    private void generateG2() {
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(0, 4);
        addEdge(1, 2);
        addEdge(2, 3);
        addEdge(4, 3);
    }

    private void generateG3() {
        addUndirectedEdge(0, 2);
        addUndirectedEdge(0, 3);
        addUndirectedEdge(1, 4);
        addUndirectedEdge(1, 5);
        addUndirectedEdge(2, 3);
        addUndirectedEdge(2, 6);
        addUndirectedEdge(4, 5);
    }

    private void generateG4() {
        addEdge(0, 1);
        addEdge(1, 2);
        addEdge(2, 0);
        addEdge(2, 3);
        addEdge(4, 2);
    }

    private void printDFS(int start) {
        System.out.println("DFS traversal starting at " + start);
        List<Integer> result = dfs(start);
        Iterator<Integer> iter = result.iterator();
        while (iter.hasNext()) {
            System.out.println(iter.next() + " ");
        }
        System.out.println();
        System.out.println();
    }

    private void printPath(int start, int end) {
        System.out.println("Path from " + start + " to " + end);
        List<Integer> result = path(start, end);
        if (result.size() == 0) {
            System.out.println("No path from " + start + " to " + end);
            return;
        }
        Iterator<Integer> iter = result.iterator();
        while (iter.hasNext()) {
            System.out.println(iter.next() + " ");
        }
        System.out.println();
        System.out.println();
    }

    private void printTopologicalSort() {
        System.out.println("Topological sort");
        List<Integer> result = topologicalSort();
        Iterator<Integer> iter = result.iterator();
        while (iter.hasNext()) {
            System.out.println(iter.next() + " ");
        }
    }

    public static void main(String[] args) {
        Graph g1 = new Graph(5);
        g1.generateG1();
        g1.printDFS(0);
        g1.printDFS(2);
        g1.printDFS(3);
        g1.printDFS(4);

        g1.printPath(0, 3);
        g1.printPath(0, 4);
        g1.printPath(1, 3);
        g1.printPath(1, 4);
        g1.printPath(4, 0);

        Graph g2 = new Graph(5);
        g2.generateG2();
        g2.printTopologicalSort();
    }
}