package djw1005;

import java.util.ArrayList;
import java.util.Random;

public class Graph {

    static class Vertex implements FibHeap.Storable<Vertex> {
        ArrayList<Edge> neighbours = new ArrayList<Edge>();
        double distance = Double.POSITIVE_INFINITY;
        //
        // Provide the infrastructure to allow a Vertex to be storable in a FibHeap
        public double key() { return this.distance; }
        public FibHeap.Node asFibNode() {
            // lazy -- no need to create a FibHeap.Node if we never end up using it!
            if (this.fhn == null) this.fhn = new FibHeap.Node<>();
            return this.fhn;
        }
        FibHeap.Node<Vertex> fhn = null;
        //
        // OPTIONAL: For printing, it's nice to have a toString method.
        Vertex(String Id) { this.Id = Id; }
        String Id = "";
        @Override
        public String toString() { return Id; }
    }
    static class Edge {
        final Vertex end; final double edgecost;
        Edge(Vertex end, double edgecost) { this.end=end; this.edgecost=edgecost; }
    };

    // Graph class, stored in the AdjancencyList style.
    // The Graph has a list of vertices, and each vertex has
    // a list of its neighbours.
    ArrayList<Vertex> vertices = new ArrayList<Vertex>();

    public void disjktra(Vertex s) {
        for (Vertex v : vertices)
            v.distance = Double.POSITIVE_INFINITY;
        s.distance = 0;
        FibHeap<Vertex> toExplore = new FibHeap<Vertex>();
        toExplore.push(s);
        while (!toExplore.isEmpty()) {
            System.out.println(toExplore);
            Vertex v = toExplore.popmin();
            System.out.println("Visit " + v);
            System.out.println(toExplore);
            for (Edge e : v.neighbours) {
                Vertex w = e.end;
                double dist_w = v.distance + e.edgecost;
                if (dist_w < w.distance) {
                    w.distance = dist_w;
                    System.out.println("-> " + w + " distance " + w.distance);
                    if (toExplore.contains(w))
                        toExplore.decreaseKey(w);
                    else
                        toExplore.push(w);
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        // Create a random graph with <= 40 edges
        String[] vs = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k"};
        for (String c : vs)
            g.vertices.add(new Vertex(c));
        Random random = new Random(16180339887L);
        addingEdges:
        for (int i=0; i<40; i++) {
            Vertex u = g.vertices.get(random.nextInt(g.vertices.size()));
            Vertex v = g.vertices.get(random.nextInt(g.vertices.size()));
            if (u==v) continue;
            for (Edge e : u.neighbours) if (e.end == v) continue addingEdges;
            u.neighbours.add(new Edge(v, random.nextInt(10)));
        }
        // Run Dijkstra's algorithm
        g.disjktra(g.vertices.get(0));
    }

}