package graph;


import partition.ListPartition;
import partition.Partition;
import position.NodePositionList;
import position.PositionList;
import priorityqueue.Entry;
import priorityqueue.PriorityQueue;
import priorityqueue.heap.HeapPriorityQueue;

import java.security.InvalidKeyException;

public class Kruskal<V, E> {
    protected Graph<V, E> graph;
    protected Object WEIGHT;
    protected PositionList<Edge<E>> EList;

    protected PriorityQueue<Double, Edge<E>> Q;

    public Iterable<Edge<E>> execute(Graph<V, E> g, Object w) throws InvalidKeyException{
	graph = g;
	WEIGHT = w;
	Q = new HeapPriorityQueue<Double, Edge<E>>();
	EList = new NodePositionList<Edge<E>>();
	KruskalAlg();
	return EList;
    }

    protected void KruskalAlg() throws InvalidKeyException{
	Partition<Vertex<V>> P = new ListPartition<Vertex<V>>();

	for (Vertex<V> w : graph.vertices())
	    P.makeSet(w);

	for (Edge<E> e : graph.edges())
	    Q.insert((Double) e.get(WEIGHT), e);

	while (EList.size() < graph.numVertices() - 1) {
	    Entry<Double, Edge<E>> e_entry = Q.removeMin();
	    Edge<E> e = e_entry.getValue();
	    Vertex<V> endV[] = graph.endVertices(e);
	    Vertex<V> u = endV[0];
	    Vertex<V> v = endV[1];

	    if (P.find(u) != P.find(v)) {
		P.union(P.find(u), P.find(v));
		EList.addLast(e);
	    }
	}
    }
}