import java.util.ArrayDeque;

public class LazyPrimMST {

    private boolean[] isVertexInMST;
    private ArrayDeque<Edge> mstEdges;
    private MinPQ<Edge> crossingEdgesPQ; // crossing (and ineligible) edges

    public LazyPrimMST(WeightedGraph g) {
        crossingEdgesPQ = new MinPQ<Edge>();
        mstEdges = new ArrayDeque<Edge>();
        isVertexInMST = new boolean[g.numVertices()];
        visit(g, 0);

        while (!crossingEdgesPQ.isEmpty()) {

            Edge e = crossingEdgesPQ.delMin(); // select smallest weight edge adjacent to tree
                                              // it might be ineligible though...
            int v = e.either();
            int w = e.other(v);
            
            // it may be that as additional vertices get added to MST, 
            // some edges already on crossingEdgesPQ may become ineligble, so...

            if (isVertexInMST[v] && isVertexInMST[w])
                continue;   // edge v-w was ineligible,
                            // it was just removed from the PQ
                            // so if we simply "continue" bypassing
                            // the rest of the body of this loop
                            // it just goes away...
                            // so we lazily just now get around to removing ineligible edge

            mstEdges.add(e);

            // if we make it this far, the edge was not ineligible, thus
            // one of its vertices is not in the mst. Add it, and update crossingEdges
            // accordingly...  (this is what visit does)
            if (!isVertexInMST[v]) {
                visit(g, v);
            }
            if (!isVertexInMST[w]) {
                visit(g, w);
            }
        }
    }

    private void visit(WeightedGraph g, int v) {
        isVertexInMST[v] = true;                  // add v to the mst

        for (Edge e : g.adj(v)) {                 // for every edge adjacent to v,
            if (!isVertexInMST[e.other(v)]) {     // if the other end of the edge is not in the mst
                crossingEdgesPQ.insert(e);        // it is a crossing edge, so add it the crossing edges
            }                                     
        }
    }

    public Iterable<Edge> mst() {
        return mstEdges;
    }

    public double weight() {
        double totalWeight = 0;
        for (Edge e : mst()) {
            totalWeight += e.weight();
        }
        return totalWeight;
    }

    public static void main(String[] args) {
        WeightedGraph g = new WeightedGraph("/Users/pauloser/Desktop/tinyEWG.txt");
        LazyPrimMST lazyPrim = new LazyPrimMST(g);
        for (Edge e : lazyPrim.mst()) {
            System.out.println(e);
        }
    }
}