package memory.jolden.mst;

import java.io.*;

/**
 * A Java implementation of the <tt>mst</tt> Olden benchmark.  The Olden
 * benchmark computes the minimum spanning tree of a graph using
 * Bentley's algorithm.
 * <p><cite>
 * J. Bentley. "A Parallel Algorithm for Constructing Minimum Spanning Trees"
 * J. of Algorithms, 1:51-59, 1980.
 * </cite>
 * <p>
 * As with the original C version, this one uses its own implementation
 * of hashtable.
 **/
public class MST
{
  /**
   * The number of vertices in the graph.
   **/
  private static int vertices = 0;
  /**
   * Set to true to print the final result.
   **/
  private static boolean printResult = false;
  /**
   * Set to true to print information messages and timing values
   **/
  private static boolean printMsgs = false;

    public static void main(String[] args){
 	main(10);
    }


    public static void main(int vertices){
	// parseCmdLine(args);
	Graph graph = new Graph(vertices);
	int dist = computeMST(graph, vertices);
    }
    
  /**
   * The method to compute the minimum spanning tree.
   * @param graph the graph data structure 
   * @param numvert the number of vertices in the graph
   * @return the minimum spanning tree cost
   **/
  static int computeMST(Graph graph, int numvert)
  {
    int cost=0;

    // Insert first node
    Vertex inserted = graph.firstNode();
    Vertex tmp = inserted.next();
    MyVertexList = tmp;
    numvert--;

    // Annonunce insertion and find next one
    while (numvert > 0) {
      BlueReturn br = doAllBlueRule(inserted);
      inserted = br.vert();
      int dist = br.dist();
      br = null;
      System.out.println("numvert= " +numvert);
      numvert--;
      cost += dist;
    }
    return cost;
  }

  private static BlueReturn BlueRule(Vertex inserted, Vertex vlist)
  {
    BlueReturn retval = new BlueReturn();
    
    if (vlist == null) {
      retval.setDist(999999);
      return retval;
    }

    Vertex prev = vlist;
    retval.setVert(vlist);
    retval.setDist(vlist.mindist());
    Hashtable hash = vlist.neighbors();
    Object o = hash.get(inserted);
    if (o != null) {
      int dist = ((Integer)o).intValue();
      if (dist < retval.dist()) {
	vlist.setMindist(dist);
	retval.setDist(dist);
      }
    } else 
      System.out.println("Not found");
    
    int count = 0;
    // We are guaranteed that inserted is not first in list
    for (Vertex tmp = vlist.next(); tmp != null; prev = tmp, tmp = tmp.next()) {
      count++;
      if (tmp == inserted) {
	Vertex next = tmp.next();
	prev.setNext(next);
      }	else {
	hash = tmp.neighbors();
	int dist2 = tmp.mindist();
	o = hash.get(inserted);
	if (o != null) {
	  int dist = ((Integer)o).intValue();
	  if (dist < dist2) {
	    tmp.setMindist(dist);
	    dist2 = dist;
	  }
	} else 
	  System.out.println("Not found");

	if (dist2 < retval.dist()) {
	  retval.setVert(tmp);
	  retval.setDist(dist2);
	}
      } // else
    } // for
    return retval;
    
  }
		
  private static Vertex MyVertexList = null;

  private static BlueReturn doAllBlueRule(Vertex inserted)
  {
    if (inserted == MyVertexList)
      MyVertexList = MyVertexList.next();
    return BlueRule(inserted, MyVertexList);
  }

  /**
   * Parse the command line options.
   * @param args the command line options.
   **/
  private static final void parseCmdLine(String args[])
  {
    int i = 0;
    String arg;

    while (i < args.length && args[i].startsWith("-")) {
      arg = args[i++];

      if (arg.equals("-v")) {
	if (i < args.length) {
	  vertices = new Integer(args[i++]).intValue();
	} else throw new RuntimeException("-v requires the number of vertices");
      } else if (arg.equals("-p")) {
	printResult = true;
      } else if (arg.equals("-m")) {
	printMsgs = true;
      } else if (arg.equals("-h")) {
	usage();
      }
    }
    if (vertices == 0) usage();
  }

  /**
   * The usage routine which describes the program options.
   **/
  private static final void usage()
  {
    System.err.println("usage: java MST -v <levels> [-p] [-m] [-h]");
    System.err.println("    -v the number of vertices in the graph");
    System.err.println("    -p (print the result>)");
    System.err.println("    -m (print informative messages)");
    System.err.println("    -h (this message)");
    System.exit(0);
  }

}

/**
 * Not really sure what this is for?
 **/
class BlueReturn
{
  private Vertex vert;
  private int dist;
  
  public Vertex vert()
    {
      return vert;
    }
  
  public void setVert(Vertex v)
    {
      vert = v;
    }

  public int dist()
    {
      return dist;
    }
  
  public void setDist(int d)
    {
      dist = d;
    }

}