package PracticaSiete;

import PracticaCuatro.ListaEnlazada;

public class Mapa {

    GrafoPesado<String> MapaCiudades;

    public Mapa() {
        MapaCiudades = new GrafoPesado<String>();
    }

    public void setMapa(GrafoPesado<String> M) {
        MapaCiudades = M;
    }


    Vertice<String> getVertice(String c) {
        // obtiene el vertice que corresponde a c
        for (Vertice<String> v: MapaCiudades.vertices) {
            if (v.getDato().equals(c)) return v;
        }
        return null;
    }

    private boolean existeCamino(boolean[] visit,Vertice<String> v, String f){
        // seteamos como visitado
        visit[v.getPosicion()] = true;
        boolean ok = false;

        //para cada adyacente
        ListaEnlazada<Arista<String>> adyacentes = v.getAdyacentes();
        adyacentes.comenzar();
        while(!(adyacentes.fin())) {
            Arista<String> a = adyacentes.elemento();
            if(a.getDestino().getDato().equals(f)) {
                // si es el destino, terminamos
                ok = true;
            } else {
                if(!(visit[a.getDestino().getPosicion()])) {
                    // sino está visitado, volvemos a lazar el método.
                    ok = existeCamino(visit,a.getDestino(), f);
                }
            }
            adyacentes.proximo();
        }
        return ok;
    }




    private ListaEnlazada<String> devolverCamino(boolean[] visit, Vertice<String> v, String f, ListaEnlazada<String> l) {
        //agregamos el dato a la lista y lo seteamos como visitado
        l.agrega(v.getDato());
        visit[v.getPosicion()] = true;

        //para cada adyacente...
        ListaEnlazada<Arista<String>> ady = v.getAdyacentes();
        ady.comenzar();
        while(!(ady.fin())) {
            Arista<String> a = ady.elemento();
            // si es el destino, terminamos.
            if(a.getDestino().getDato().equals(f)) {
                l.agrega(a.getDestino().getDato());
                return l;
            } else {
                // si no está visitado...
                if(!(visit[a.getDestino().getPosicion()])) {
                    Vertice<String> aux = a.getDestino();
                    boolean[] v1 = visit.clone();
                    // y, lleva al destino...
                    if (existeCamino(v1,aux,f)) {
                        // seguimos
                        l = devolverCamino(visit,a.getDestino(), f, l);
                    }
                }
            }
            ady.proximo();
        }
        if ((v.getDato() != f)&&( l.tamano() == 1)) return null;
        else return l;
    }

    public boolean existeCamino (String ciudad1, String ciudad2) {
        // si origen = destino, no hay nada que hacer.
        if (ciudad1 != ciudad2) {
            // creamos el arreglo de visitados
            boolean[] visitados = new boolean[this.MapaCiudades.cantVertices];
            for (int i=0; i < MapaCiudades.cantVertices; i++) {
                visitados[i]= false;
            }
            // si existe la ciudad de origen...
            Vertice<String> v = getVertice(ciudad1);
            if (v != null){
                //empieza el recorrido
                return existeCamino(visitados,getVertice(ciudad1),ciudad2);
            }
            return false;
        }else{
            return true;
        }
    }

    public ListaEnlazada<String> devolverCamino (String ciudad1, String ciudad2){
        boolean[] visitados = new boolean[this.MapaCiudades.cantVertices];
        for (int i=0; i < MapaCiudades.cantVertices; i++) {
            visitados[i]= false;
        }
        // creamos la lista para contener el camino
        // y se busca el vertice que corresponde a esa ciudad
        ListaEnlazada<String> l = new ListaEnlazada<String>();
        Vertice<String> v = getVertice(ciudad1);
        if(!(v == null)){
            l = devolverCamino(visitados,v, ciudad2, l);
        }
        return l;
    }

    public ListaEnlazada<String> devolverCaminoExceptuando (String ciudad1, String ciudad2, ListaEnlazada<String> ciudades) {
        ListaEnlazada<String> l = new ListaEnlazada<String>();
        boolean[] visitados = new boolean[this.MapaCiudades.cantVertices];

        for (int i=0; i < MapaCiudades.cantVertices; i++) {
            if (ciudades.incluye(MapaCiudades.vertices[i].getDato())){
                visitados[i] = true;
            }
            else visitados[i]= false;
        }
        // una vez "visitadas", se esquivaran en el dfs que devuelve el camino
        // o una lista vacía en caso de que no exista.
        Vertice<String> v = getVertice(ciudad1);
        if(!(v == null)){
            l = devolverCamino(visitados,v, ciudad2, l);
        }
        return l;
    }


    public ListaEnlazada<String> caminoMasCorto(String ciudad1, String ciudad2) {
        return null;
    }

    public ListaEnlazada<String> caminoMasCortoCargandoCombustible (String ciudad1, String ciudad2){
        return null;
    }
}