import java.awt.*;
import java.io.*;
import java.util.*;
import java.net.*;

public class GraphMST {
	
	static final String current_n_s = "From Node ";
	static final String current_n_e = " To Node ";
	static final String current_e = "Edge Cost ";
	static final String focus = " Next Cheapest Edge: ";
	static final String c_cycle = " Completes a Cycle - skip it";
	static final String does_not = " Does not generate a Cycle - so add it";
	static final String done = "Minimum Spanning Tree Found";
	static final String cost_e = ", Cost = ";
	String sentence;
	AlgThread alg;
	Graph graph;
	int cnt = 1;
	
	public GraphMST( AlgThread alg, Graph graph ) {
		this.alg = alg;
		this.graph = graph;
		Minimum_Spanning_Tree();
		}

/*------------------------------------------------*/
	public void Minimum_Spanning_Tree( ) {
		int pivot = 0; /*-*/ alg.frame.Highlight(1);
		Edge trial_edge;
		Forest mst;
		PriorityQueue PQ;
 
		PQ = new PriorityQueue( graph.edge_cnt ); /*-*/ alg.frame.Highlight(6);
		PQ = Initialize( PQ ); /*-*/ alg.frame.Highlight(7);
		PQ.Sort( pivot, graph.edge_cnt ); /*-*/ alg.frame.Highlight(8);
		/*-*/ PQ.Print_Val( ); alg.frame.setText(1, "Initialization");
		/*-*/ alg.frame.waitStep();
 
		mst = new Forest( graph.edge_cnt ); /*-*/ alg.frame.Highlight(11);
		while ( mst.Num_Edges( )	< graph.node_cnt-1 ) { /*-*/ alg.frame.Highlight(12);
 			trial_edge = (Edge)(PQ.Extract_First_Element_MST( )); /*-*/ alg.drawingPanel.Highlight_Edge_Focus(trial_edge); alg.frame.Highlight(12);
			if (!Cycle( trial_edge, mst )) { /*-*/ alg.frame.Highlight(13); sentence = does_not;
				/*-*/ alg.drawingPanel.Highlight_Edge_Final( trial_edge );
				mst.Add( trial_edge ); /*-*/ alg.frame.Highlight(14);
				}
			/*-*/ else { sentence = c_cycle; } alg.frame.setText(2, sentence); alg.frame.waitStep(); System.out.println( sentence );
		}		
	// Finished /*-*/ mst.Print_Val(); alg.frame.Highlight(20); 
	/*-*/ alg.frame.setText(2, done); System.out.println(done); 
	}

//-------
	private PriorityQueue Initialize( PriorityQueue PQ ) {
		int i;
		Node neg_one;
 
		neg_one = new Node(-1, 0, 0);
		for (i = 0; i < graph.edge_cnt; i ++) {
			graph.edges[i].Set_Rep( neg_one );
			PQ.Add( (Object)graph.edges[i] );
			}
		return PQ;
		}
 
	private boolean Cycle( Edge te, Forest T ) {
			sentence = new String(
						focus+current_n_s+te.start.Get_ID()+current_n_e+te.end.Get_ID()+
						cost_e+te.Cost());
			System.out.println(sentence+" ");
			/*-*/ alg.frame.setText(1, sentence); alg.frame.setText(2, "" );
			/*-*/alg.frame.waitStep();
			if ( te.New( ) ) {
				//new tree
				T.New( te );
				return false;
				}
			else if ( te.Is_From( ) || te.Is_To( ) ) {
				//add to existing tree
				T.Existing( te );
				return false;
				}
			else if ( te.Join( ) ) {
				//combine trees
				T.Combine( te );
				return false;
				}
			else {
				//exclude this edge
				/*-*/ alg.drawingPanel.Highlight_Edge_Ori(te);
				/*-*/ sentence = new String(focus+c_cycle);
				/*-*/ System.out.println(sentence+" ");
				/*-*/ alg.frame.setText(2, sentence);
				/*-*/ alg.frame.waitStep();
				return true;
				}
			}
 
}