// Prim's algorithm with a priority queue (binary heap)
//
// Author: Rahul Simha
// Date: Oct, 2001.

import edu.gwu.algtest.*;
import edu.gwu.util.*;
import edu.gwu.debug.*;

import java.util.*;
import java.io.*;

/**
 * Class <code>FastPrim</code> implements Prim's algorithm but with
 * the customary priority-queue. The queue is a standard implementation
 * of a binary heap with the decreaseKey operation.
 *
 * @see SpanningTreeAlgorithm
 */

public class FastPrim implements SpanningTreeAlgorithm {

  // Debugging for internal use.
  private static final boolean debug = true;
  
  int algID;                         // Given by test-environment.
  PropertyExtractor props;           // Properties file.

  int numVertices;                   // Number of vertices (when initialized).

  boolean useMatrix;                 // Adjacency matrix or list?
  
  double[][] adjMatrix;              // The adjacency matrix (given as input).
  GraphVertex[] adjList;             // The adjacency list (given as input).

  int[] predecessor;                 // Store predecessors to build MST.
  double[] predecessorEdgeWeight;    // Store edge weights as well.

  double[][] treeMatrix;             // The MST, if required in matrix form.
  GraphVertex[] treeList;            // The MST, if required in list form.

  double treeWeight;                 // Total weight of tree.

  
  //---------------- Algorithm interface ------------------------------------

  public String getName ()
  {
    return "FastPrim";
  }


  public void setPropertyExtractor (int algID, PropertyExtractor props)
  {
    this.algID = algID;
    this.props = props;
  }


  //---------------- SpanningTreeAlgorithm interface -------------------------

  public void initialize (int numVertices)
  {
    this.numVertices = numVertices;
    predecessor = new int [numVertices];
    predecessorEdgeWeight = new double [numVertices];
  }



  public double[][] minimumSpanningTree (double[][] adjMatrix)
  {
    // Consistency check:
    if (numVertices != adjMatrix.length) {
      System.out.println ("ERROR: adjMatrix length not equal to numVertices");
      return null;
    }

    // We are using an adjacency matrix.
    useMatrix = true;


    // Create heap. Note: BinaryHeap implements the PriorityQueueAlgorithm
    // interface (that has insert, extractMin and decreaseKey operations.

    PriorityQueueAlgorithm priorityQueue = new BinaryHeap (numVertices);
    priorityQueue.initialize (numVertices);
    

    // Since we are given an adjacency matrix, we need to build vertices
    // to use in the priority queue. GraphVertex is a class that holds
    // the vertex id and also can hold an edge-list (Therefore, it's
    // used for the adjacency-list representation.
    // NOTE: most importantly, GraphVertex implements the PriorityQueueNode
    // interface that allows the priority queue to store indices inside the node.

    GraphVertex[] vertices = new GraphVertex [numVertices];

    // Place vertices in priority queue.
    for (int i=0; i<numVertices; i++) {
      vertices[i] = new GraphVertex (i);

      if (i != 0) {
        // All vertices except 0 have "infinity" as initial priority.
        vertices[i].setKey (Double.MAX_VALUE);
        predecessor[i] = -1;
      }
      else {
        // Vertex 0 has 0 as priority.
        vertices[i].setKey (0);
        predecessor[i] = i;
      }

      priorityQueue.insert (vertices[i]);
    }

    
    // Now process vertices one by one in order of priority (which changes
    // during the course of the iteration.

    while (! priorityQueue.isEmpty() ) {

      // Extract vertex with smallest priority value.
      GraphVertex vertex = (GraphVertex) priorityQueue.extractMin ();

      // For readability we'll use these shortcuts.
      int v = vertex.vertexID;
      double v_key = vertex.getKey();

      // Scan neighbors in adjMatrix.
      for (int i=0; i<numVertices; i++) {

        // Look at row adjMatrix[v][i].
        if ( (v != i) && (adjMatrix[v][i] > 0) ) {

          // We have found a neighbor: explore the edge (v,i).
          double w = adjMatrix[v][i];

          // If the current priority is higher, lower it via edge (v,i).
          if (vertices[i].getKey() > w) {

            // decreaseKey operation.
            priorityQueue.decreaseKey (vertices[i], w);

            // Record predecessor and weight for building MST later.
            predecessor[i] = v;
            predecessorEdgeWeight[i] = w;

          }

        }

      } // endfor
      
    } // endwhile
    

    // Create space for tree.
    treeMatrix = new double [numVertices][];
    for (int i=0; i<numVertices; i++) {
      treeMatrix[i] = new double [numVertices];
      // Already initialized to zero.
    }
    
    treeWeight = 0;


    // Now build tree using pred edges. Note: we start from "1"
    // since "0" is its own predecessor (the root of the tree).

    for (int i=1; i<numVertices; i++) {
      // (i, pred[i]) has to be an edge.
      int j = predecessor[i];
      treeMatrix[i][j] = treeMatrix[j][i] = predecessorEdgeWeight[i];
      treeWeight += predecessorEdgeWeight[i];
    }

    return treeMatrix;

  }

  public GraphVertex[] minimumSpanningTree (GraphVertex[] adjList)
  {
    // ... (not shown) ...
    return null;
  }

  public double getTreeWeight ()
  {
    return treeWeight;
  }
  

  
}