package graph.spath;

import javax.swing.JTextArea;

import graph.*;
import heap.MinimumHeap;

/*
 * Created on 09/06/2003
 */
/**
 * @author André Santanchè
 */
public class Dijkstra
{
  Graph g;
  Vertex s;
  MinimumHeap q;
  JTextArea output = null;
  
  public Dijkstra(Graph g, Vertex s, MinimumHeap q)
  {
    this.g = g;
    this.s = s;
    this.q = q;
  }

  protected void initializeSingleSource(Vertex s)
  {
    Vertex v[] = g.getVertexList();
    for (int i = 0; i < v.length; i++) {
      v[i].setD(Integer.MAX_VALUE);
      v[i].setPi(null);
    }
    s.setD(0);
  }
  
  protected void relax(Edge e)
  {
    Vertex u = e.getOrigin(),
           v = e.getDestination();

    String out = "relax(" + u + ", " + v + "; d[v]=" + v.getD() +
                 "; d[u]+w(u,v)=" + u.getD() + e.getWeight() + ")";
    if (output == null)
      System.out.println(out);
    else
      output.append(out + "\n");

    if (v.getD() > u.getD() + e.getWeight()) {
      q.decreaseKey(v, u.getD() + e.getWeight());
      v.setPi(u);
    }
  }
  
  public Graph shortestPath()
  {
    if (output != null)
      output.append("\nExecução Dijkstra\n-----------------\n");
      
    initializeSingleSource(s);
    Graph gs = new Graph();
    
    q.buildMinHeap(g.getVertexList());
    while (!q.isEmpty())
    {
      Vertex u = (Vertex) q.heapExtractMin();
      gs.addVertex(u);
      Edge e[] = u.getEdges();
      if (e != null)
        for (int i = 0; i < e.length; i++)
          relax(e[i]);
    }
    return shortestPathGraph(gs);
  }
  
  private Graph shortestPathGraph(Graph gs)
  {
    Graph spg = new Graph();
    Vertex vl[] = gs.getVertexList();
    Vertex root = null;
    attachNodes(spg, s);
    return spg;
  }
  
  public Vertex attachNodes(Graph spg, Vertex sroot)
  {
    Vertex newSRoot = new Vertex(sroot.getLabel());
    newSRoot.setPi(sroot.getPi());
    newSRoot.setD(sroot.getD());
    spg.addVertex(newSRoot);
    Edge le[] = sroot.getEdges();
    if (le != null && le.length > 0)
    {
      for (int i = 0; i < le.length; i++)
      {
        Vertex sr = le[i].getDestination();
        System.out.println(sr + " pai " + sr.getPi() + " root " + sroot);
        if (sr.getPi() == sroot)
          newSRoot.addEdge(
            new Edge(newSRoot, attachNodes(spg, sr), le[i].getWeight()));
      }
    }
    return newSRoot;
  }
  
  public void setOutput(JTextArea output)
  {
    this.output = output;
  }
}