import java.util.*;

public class MST {
  public static DirectedGraph minimumSpanningTree(DirectedGraph g) {
    
    HashMap<Object, TreeThread> treeThreads = new HashMap<Object, TreeThread>();
    int i = 0;
    Iterator<Object> it = g.getNodes().iterator();
    while (it.hasNext()) {
      Object n = it.next();
    	treeThreads.put(n, new TreeThread(n, g, i++, treeThreads));
    }
    
    Collection<TreeThread> ts = treeThreads.values();
    Iterator<TreeThread> it2 = ts.iterator();
    while (it2.hasNext()) {
    	Thread t = it2.next();
    	System.out.println(t);
    	if (t.getState() == Thread.State.NEW)	t.start();
    }
    	
    it2 = ts.iterator();
    while (it2.hasNext())
    	try{
    		it2.next().join();
    	}
    	catch (InterruptedException e) { /* ignore */}
 
    return treeThreads.values().iterator().next().myTree;
  }
   
  
  public static void main(String[] args) {
		String a = "A";
		String b = "B";
		String c = "C";
		String d = "D";
		String e = "E";
		Graph x = new Graph();
		x.addNode(a);
		x.addNode(b);
		x.addNode(c);
		x.addNode(d);
		x.addNode(e);
		x.addEdge(a, b, 5.0);
		x.addEdge(b, a, 5.0);
		x.addEdge(b, c, 8.0);
		x.addEdge(c, b, 8.0);
		x.addEdge(c, d, 7.0);
		x.addEdge(d, c, 7.0);
		x.addEdge(d, e, 6.0);
		x.addEdge(e, d, 6.0);
		x.addEdge(e, a, 4.0);
		x.addEdge(a, e, 4.0);
		x.addEdge(c, a, 5.0);
		x.addEdge(a, c, 5.0);
		x.addEdge(d, b, 2.0);
		x.addEdge(b, d, 2.0);
		x.addEdge(a, d, 2.0);
		x.addEdge(d, a, 2.0);
		
		System.out.println("Eingabe:");
		printGraph(x);

		
		DirectedGraph t = minimumSpanningTree(x);
		
		System.out.println("Ausgabe:");
		printGraph(t);

  }
  
  public static void printGraph(DirectedGraph g) {
		Set n = g.getNodes();
		Set s;
		for (Object node : n) {
			System.out.print(node);
			System.out.print("->");
			s = g.getSuccNodes(node);
			for (Object suc : s) {

				System.out.print(suc.toString());
				System.out.print("(" + g.getEdgeWeight(node, suc) + ")");
				System.out.print(",");
			}
			System.out.println("");
		}
	}
}


class TreeThread extends Thread {
	private final int id;
	private final DirectedGraph graph;
	private final HashMap<Object, TreeThread> trees;
	DirectedGraph myTree = new Graph();
	
	public TreeThread (Object myNode, DirectedGraph originalGraph, int id, HashMap<Object, TreeThread> trees) {
		this.graph = originalGraph;
		this.id = id;
		this.trees = trees;
		myTree.addNode(myNode);
	}
	
	
	public DirectedGraph getTree() {
		return myTree;
	}
	
	public void run() {
		
  	while (true) {
  		System.out.println(this+" sleeps");
  			try {
  				Thread.currentThread().sleep((int) Math.random() * 1);
  			} catch (InterruptedException e) {/* ignore */}
  			System.out.println(this+" awakes");
			
			//teste, ob ich gemergt wurde
			if (trees.get(myTree.getNodes().iterator().next()) != this) {
				System.out.println(this+" has been merged and dies");
				return;
			}
			
			
			//Bestimme Kandidaten für kleinste ausgehende Kante
			Object minFromNode = null, minToNode = null;
			double minWeight = Double.MAX_VALUE;
			for (Object from : myTree.getNodes())
				for (Object to : graph.getSuccNodes(from))
					if (trees.get(from).id != trees.get(to).id) {
						double w = graph.getEdgeWeight(from, to);
						if (w < minWeight) {
							minWeight = w;
							minFromNode = from;
							minToNode = to;
						}
					}
			
			//Abbruch, falls keine ausgehenden Kanten
			if (minFromNode == null) {
				System.out.println(this+" finds no outgoing edges and dies");
				return;
			}
			
			//Bäume verschmelzen
			TreeThread fromTree = trees.get(minFromNode);
			TreeThread toTree = trees.get(minToNode);
			synchronized(fromTree.id < toTree.id ? fromTree : toTree) {
				synchronized(fromTree.id < toTree.id ? toTree : fromTree) {
					if (trees.get(minFromNode) == fromTree && trees.get(minToNode) == toTree) {
						
						if (fromTree.id != toTree.id) {
							System.out.println(this+" merges with "+toTree);
							for (Object n : toTree.myTree.getNodes()) 
								fromTree.myTree.addNode(n);
							
							for (Object n : toTree.myTree.getNodes()) {
								for (Object m : toTree.myTree.getSuccNodes(n))
							  	fromTree.myTree.addEdge(n, m, toTree.myTree.getEdgeWeight(n, m));
							  
							  trees.put(n, fromTree);
							}
							
							fromTree.myTree.addEdge(minFromNode, minToNode, graph.getEdgeWeight(minFromNode, minToNode));
							fromTree.myTree.addEdge(minToNode, minFromNode, graph.getEdgeWeight(minToNode, minFromNode));
							System.out.println(this+" finishes merging");
						}
					}
					else System.out.println(this+" discards merge with "+toTree);
				}
			}
		}
	}
}