// Last edited on Tue Jun 19 22:33:52 BRT 2001 
// Grupo:
//
// Gabriel Araujo 983728
// Joao Porto     981389
// Joao Guilherme 981374
// Joyce Ynoue    981414
// Mateus Polastro 981787

package pckGerador;
import java.util.*;
import java.io.*;
import pckMapa.Mapa;

public class GrafoImpl extends Grafo
  {
    // Construtor

    public GrafoImpl(Mapa mp) {
      // Cria o grafo para o mapa mp
       // Cria os nós associados a trechos:
        Trecho[] trechos = Mapa.getTrechos();   
        Conexao[] conexoes = Mapa.getConexoes();
        int MAXTRECHO = trechos.length;
        int MAXCONEXAO = conexoes.length;
     
        for (int i = 0; i < MAXTRECHO; i++)
            nMei[i] = new NodoMeio(this, trechos[i]);
        

        for (int i = 0; i < MAXCONEXAO; i++)
            nCon[i] = new NodoConexao(this, conexoes[i]);
         


    } //fim

public final Nodo[] dijkstra(Nodo[] ini, CriterioDeParada cr) {

        // Vetor de resultados
        Vector res = new Vector();

        // Vetor de nodos já processados
        Vector done = new Vector();

        // O "heap" de nós já alcançados mas ainda não otimizados:
        MonteDeNodos monte = new MonteDeNodos(numNodos());

        // Inicializa o heap com os nós de partida.
        for (int i = 0; i < ini.length; i++)
          { Nodo u = ini[i];
            u.custoTot = 0.0;
            u.prev = null;
            monte.insere(u);
          }
        // Processa os nós em ordem de distância crescente:
        while ((monte.tamanho() > 0) && (! cr.satisfeito()))
          {
            // Retira o nó mais barato ainda não processado:
            Nodo u = monte.remove();
            // System.out.println("Processando " + u);

            // Marca esse nó como tendo sido processado:
            u.indice = done.size(); done.addElement(u);

            // Verifica se ele é um dos nós procurados:
            if (cr.aceitavel(u))
              { res.addElement(u);
                System.out.println("Achou nodo aceitável: " + u);
              }
            // Examina os vizinhos:
            Nodo[] prox = u.prox();
            double[] custo = u.custo();
            for(int i = 0; i < prox.length; i++)
              { Nodo v = prox[i];
                int iv = v.indice;
                if ((iv < 0) || (iv >= done.size()) || (v != done.elementAt(iv)))
                  { // Este vizinho ainda não foi processado.
                    double custoNovo = u.custoTot + custo[i];
                    // System.out.print("  vizinho " + v + " custo = " + custoNovo);
                    if (custoNovo < 0.0) { throw new Error("custo negativo"); }
                    if (! monte.possui(v))
                      { // System.out.println(" (nodo novo)");
                        // if (v.prev != null) { throw new Error("prev dirty"); }
                        // if (v.indice != -1) { throw new Error("indice dirty"); }
                        v.custoTot = custoNovo;
                        v.prev = u;
                        monte.insere(v);
                      }
                    else if (custoNovo < v.custoTot)
                      { // System.out.println(" (melhorou)");
                        v.custoTot = custoNovo;
                        v.prev = u;
                        monte.ajusta(v);
                      }
                    else
                      { // System.out.println(" (não melhorou)");
                      }
                  }
              }
            //  monte.debuga("Dijkstra");
          }
        System.out.println("Processou " + done.size() + " nodos.");
        System.out.println("Encontrou " + res.size() + " nodos aceitáveis.");

        // Recolhe os resultados:
        int nr = res.size();
        Nodo[] r = new Nodo[nr];
        for (int i = 0; i < nr; i++) { r[i] = (Nodo) res.elementAt(i); }
        return r;
      }


    private void limpaNodos()
      // Limpa os campos "prev" e "indice" de todos os nodos.
      // Útil para debugagens.
      {
        int nt = trechos.length; 
        for (int i = 0; i < nt; i++)
          { trCon[i].prev = null; trCon[i].indice = -1;
            trMei[i].prev = null; trMei[i].indice = -1;
          }
      }
  }