// Last edited on 2000-09-03 06:11:09 by stolfi

import java.util.*;
import java.io.*;
import Esquina;
import Trecho;
import Planta;
import Nodo;
import NodoTrecho;
import NodoServico;
import MonteDeNodos;
import CriterioDeParada;

public class GrafoImpl extends Grafo
  {
    // Construtor 

    public GrafoImpl(Planta pl) 
      // Cria o grafo para a planta "pl".
      { // Cria os nós associados a trechos:
        Trecho[] tr = pl.trechos();   int nt = tr.length;
        trIni = new Nodo[nt];
        trMei = new Nodo[nt];
        trFim = new Nodo[nt];
        for (int i = 0; i < nt; i++) 
          { trIni[i] = new NodoTrechoInicio(this, tr[i]);
            trMei[i] = new NodoTrechoMeio  (this, tr[i]);
            trFim[i] = new NodoTrechoFim   (this, tr[i]);
          }
        
        // Cria os nós associados a serviços
        Servico[] sv = pl.servicos(); int ns = sv.length;
        svEnt  = new Nodo[ns];
        svSai  = new Nodo[ns];
        for (int i = 0; i < ns; i++) 
          { svEnt[i] = new NodoServicoEntrada(this, sv[i]);
            svSai[i] = new NodoServicoSaida  (this, sv[i]);
         }
      }

    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 = trIni.length;
        for (int i = 0; i < nt; i++) 
          { trIni[i].prev = null; trIni[i].indice = -1;
            trMei[i].prev = null; trMei[i].indice = -1;
            trFim[i].prev = null; trFim[i].indice = -1;
          }
        int ns = svEnt.length;
        for (int i = 0; i < ns; i++) 
          { svEnt[i].prev = null; svEnt[i].indice = -1;
            svSai[i].prev = null; svSai[i].indice = -1;
         }
      }
  }