package com.example.unodtantos.appqueology2.modelo;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;


/**
 * Created by unodtantos on 03/04/2015.
 */
public class Estructura implements Serializable {

    /*--------------------------------------------------------------------------------------------*/

    // <editor-fold defaultstate="collapsed" desc="Atributos de la clase">

    private LinkedList lista_vertices;
    private LinkedList lista_aristas;
    private Vertice v_inicio;
    private int cv = 0;
    private int ce = 0;
    private Vertice Vertis = null;
    private Vertice comparar = null;

    // </editor-fold>

    /*--------------------------------------------------------------------------------------------*/

    // <editor-fold defaultstate="collapsed" desc="Constructor de la clase">

    /**
     * Constructor de la clase.
     */
    public Estructura() {
        this.lista_vertices = new LinkedList();
        this.lista_aristas = new LinkedList();
        this.v_inicio = agregarVertice("Inicio");
    }

    // </editor-fold>

    /*--------------------------------------------------------------------------------------------*/

    // <editor-fold defaultstate="collapsed" desc="Agregar relación">

    /**
     * Método que permite agregar una relación a la estructura.
     * @param nom_ue_relacion
     */
    public void agregarNodoRelacion(String nom_ue_relacion) {
        Vertice v = agregarVertice(nom_ue_relacion);
        agregarArista(this.getV_inicio(), v, nom_ue_relacion);
    }

    // </editor-fold>

    /*--------------------------------------------------------------------------------------------*/

    // <editor-fold defaultstate="collapsed" desc="Agregar arista, vertice">

    /**
     * Método que permite agregar una arista a la estructura.
     * @param v_padre
     * @param v_hijo
     * @param obj_nom_ue
     * @return
     */
    public Arista agregarArista(Vertice v_padre, Vertice v_hijo, Object obj_nom_ue){
        Arista arista = new Arista(v_padre, v_hijo, obj_nom_ue);
        lista_aristas.add(ce++, arista);

        return arista;
    }

    /**
     * Método que permite agregar un vértice a la estructura.
     * @param O
     * @return
     */
    public Vertice agregarVertice(Object O) {
        Vertice v = new Vertice(O);
        lista_vertices.add(cv++, v);

        return v;
    }

    // </editor-fold>

    /*--------------------------------------------------------------------------------------------*/

    // <editor-fold defaultstate="collapsed" desc="Eliminar arista, vertice">

    /**
     * Método que permite eliminar una arista de la estructura.
     * @param a
     * @return
     */
    public boolean borrarArista(Arista a) {

        for (int i = 0; i <= lista_aristas.size(); i++) {
            Arista arista = (Arista) lista_aristas.get(i);

            if (a == arista) {
                lista_aristas.remove(i);
                ce--;
                return true;
            }
        }
        return false;
    }

    /**
     * Método que permite eliminar un vértice de la estructura.
     * @param v
     * @return
     */
    public boolean borrarVertice(Vertice v) {

        for (int i = 0; i <= lista_vertices.size(); i++) {
            Vertice vertice = (Vertice) lista_vertices.get(i);
            if (v == vertice) {
                lista_vertices.remove(i);
                cv--;

                return true;
            }
        }
        return false;
    }

    // </editor-fold>

    /*--------------------------------------------------------------------------------------------*/

    // <editor-fold defaultstate="collapsed" desc="Obtener información de la Estructura">

    /**
     * Método que permite buscar un vértice en la estructura.
     * @param O
     * @return
     */
    public Vertice buscarVertice(Object O) {

        for (int i = 0; i < lista_vertices.size(); i++) {
            Vertice v = (Vertice) lista_vertices.get(i);
            Object s = v.getElemento();

            if (s.equals(O)) {
                return (Vertice) lista_vertices.get(i);
            }
        }
        return null;
    }



    /**
     * Método que devuevle un LinkedList con todos los vertices adyacentes del recibido por parámetro.
     * @param V
     * @return
     */
    public LinkedList adyacentesVertice(Vertice V) {

        LinkedList L = new LinkedList();
        int c = 0;
        for (int i = 0; i < lista_aristas.size(); i++) {
            Arista a = (Arista) lista_aristas.get(i);
            Vertice V1 = a.getV1();
            Vertice V2 = a.getV2();

            if (V1 == V) {
                L.add(c++, V2);
            }
            if (V2 == V) {
                L.add(c++, V1);
            }
        }
        return L;
    }

    /**
     * Método que devuelve un LinkedList de los hijos de un vértice.
     * @param v
     * @return
     */
    public LinkedList adyacentesHijos(Vertice v) {
        LinkedList L = new LinkedList();
        int c = 0;
        for (int i = 0; i < lista_aristas.size(); i++) {
            Arista a = (Arista) lista_aristas.get(i);
            Vertice V1 = a.getV1();
            Vertice V2 = a.getV2();

            if (V1 == v) {
                L.add(c++, V2);
            }
        }

        return L;
    }

    /**
     * Método que devuelve un LinkedList con los padres de un vértice.
     * @param v
     * @return
     */
    public LinkedList adyacentesPadres(Vertice v) {
        LinkedList L = new LinkedList();
        int c = 0;
        for (int i = 0; i < lista_aristas.size(); i++) {
            Arista a = (Arista) lista_aristas.get(i);
            Vertice V1 = a.getV1();
            Vertice V2 = a.getV2();

            if (V2 == v) {
                L.add(c++, V1);
            }
        }

        return L;
    }

    /**
     * Método que devuelve un vértice hijo no visitado de un vértice.
     * @param v
     * @return
     */
    public Vertice adyacentesHijosNoVisitados(Vertice v) {

        for (int i = 0; i < lista_aristas.size(); i++) {
            Arista a = (Arista) lista_aristas.get(i);
            Vertice V1 = a.getV1();
            Vertice V2 = a.getV2();

            if (V1 == v) {
                if (V2.getState() == 0) {

                    return V2;
                }
            }
        }

        return null;
    }

    /**
     * Método que devuelve un vértice hijo no visitado desde un vértice concreto.
     * @param v
     * @return
     */
    public Vertice adyacentesHijosNoVisitadosDesdeVertice(Vertice v) {

        for (int i = 0; i < lista_aristas.size(); i++) {
            Arista a = (Arista) lista_aristas.get(i);
            Vertice V1 = a.getV1();
            Vertice V2 = a.getV2();

            if (V1 == v) {
                ArrayList<String> visit = v.getVisitados();
                Boolean encontrado = false;
                for(int j=0;j<visit.size();j++){
                    if(visit.get(j).equals(V2.getElemento().toString())){
                        encontrado = true;
                    }
                }
                if(!encontrado){
                    marcarHijosVerticeNoVisitados(V2);
                    return V2;
                }
            }
        }

        return null;
    }

    /**
     * Método que te devuelve un ArrayList con los nombres de todos los hijos hasta las hojas de una
     * UE concreta.
     * @param nombre_ue
     * @return
     */
    public ArrayList<String> obtenerTodosHijos(String nombre_ue) {

        Vertice v = buscarVertice(nombre_ue);

        ArrayList<String> todos_hijos = new ArrayList<>();

        for (int i = 0; i < lista_vertices.size(); i++) {
            Vertice w = (Vertice) lista_vertices.get(i);
            w.setCiclo(0);
        }

        LinkedList l = adyacentesHijos(v);
        for (int i = 0; i < l.size(); i++) {
            Vertice w = (Vertice) l.get(i);
            if (w.getCiclo() == 0) {
                w.setCiclo(1);
                todos_hijos.add(w.getElemento().toString());

                LinkedList l2 = adyacentesHijos(w);
                for (int j = 0; j < l2.size(); j++) {
                    Vertice w2 = (Vertice) l2.get(j);
                    l.addLast(w2);
                }
            }
        }

        return todos_hijos;
    }

    /**
     * Método que devuelve un ArrayList con los nombres de todos los padres hasta el vértice raíz
     * de una UE concreata.
     * @param nombre_ue
     * @return
     */
    public ArrayList<String> obtenerTodosPadres(String nombre_ue) {

        Vertice v = buscarVertice(nombre_ue);

        ArrayList<String> todos_padres = new ArrayList<>();

        for (int i = 0; i < lista_vertices.size(); i++) {
            Vertice w = (Vertice) lista_vertices.get(i);
            w.setCiclo(0);
        }

        LinkedList l = adyacentesPadres(v);
        for (int i = 0; i < l.size(); i++) {
            Vertice w = (Vertice) l.get(i);
            if (w.getCiclo() == 0) {
                w.setCiclo(1);
                todos_padres.add(w.getElemento().toString());

                LinkedList l2 = adyacentesPadres(w);
                for (int j = 0; j < l2.size(); j++) {
                    Vertice w2 = (Vertice) l2.get(j);
                    l.addLast(w2);
                }
            }
        }

        return todos_padres;
    }

    /**
     * Método que permite saber el nivel en que se encuentra un vértice dentro de la estructura.
     * @param v
     * @return
     */
    public int encontrarGrado(Vertice v) {

        if (v.getElemento().equals(this.v_inicio.getElemento())) {
            return 0;
        }

        for (int i = 0; i < lista_vertices.size(); i++) {
            Vertice w = (Vertice) lista_vertices.get(i);
            w.setState(0);
        }

        Stack stack = new Stack();
        Boolean encontrado = false;
        int grado = 0;

        stack.push(this.v_inicio);
        v_inicio.setState(1);

        while (!stack.isEmpty() || !encontrado) {

            Vertice vv = (Vertice) stack.peek();
            Vertice hijo = adyacentesHijosNoVisitados(vv);

            if (hijo != null) {
                if (v.getElemento().equals(hijo.getElemento())) {
                    grado++;
                    encontrado = true;
                    return grado;
                } else {
                    hijo.setState(2);
                    stack.push(hijo);

                    grado++;
                }
            } else {
                stack.pop();
                grado--;
            }
        }

        return grado;
    }

    // </editor-fold>

    /*--------------------------------------------------------------------------------------------*/

    // <editor-fold defaultstate="collapsed" desc="Nueva relación crea un ciclo?">

    /**
     * Metodo que permite saber si una nueva relación crea un ciclo.
     * @param v
     * @return
     */
    public ArrayList isCycle(Vertice v) {

        ArrayList result = new ArrayList();
        ArrayList implicados = new ArrayList();

        for (int i = 0; i < lista_vertices.size(); i++) {
            Vertice w = (Vertice) lista_vertices.get(i);
            w.setCiclo(0);
        }
        LinkedList l = adyacentesHijos(v);

        for (int i = 0; i < l.size(); i++) {
            Vertice w = (Vertice) l.get(i);

            if (w.getCiclo() == 0) {
                w.setCiclo(1);
                implicados.add(w.getElemento().toString());
                if (v.getElemento().toString().equals(w.getElemento().toString())) {
                    result.add(true);
                    result.add(implicados);

                    return result;
                } else {
                    LinkedList l2 = adyacentesHijos(w);
                    for (int j = 0; j < l2.size(); j++) {
                        Vertice w2 = (Vertice) l2.get(j);
                        l.addLast(w2);
                    }
                }
            }
        }
        result.add(false);
        result.add(implicados);
        return result;

    }

    // </editor-fold>

    /*--------------------------------------------------------------------------------------------*/

    // <editor-fold defaultstate="collapsed" desc="Recorrido de la estructura mediante (Bfs y Dfs)">

    /**
     * Método que se encarga de hacer un recorrido de la estructura a lo ancho.
     * @return
     */
    public String bfs() {
        for (int i = 0; i < lista_vertices.size(); i++) {
            Vertice w = (Vertice) lista_vertices.get(i);
            w.setState(0);
        }
        LinkedList L = new LinkedList();
        LinkedList L2 = new LinkedList();
        int c = 0;
        Vertice w = (Vertice) lista_vertices.get(0);
        L.add(c++, w);
        w.setState(1);
        String r = "";
        while (L.size() != 0) {
            w = (Vertice) L.getFirst();
            r = r + "-" + w.getElemento();
            w.setState(3);
            c--;
            L.removeFirst();
            L2 = adyacentesVertice(w);
            for (int i = 0; i < L2.size(); i++) {
                Vertice y = (Vertice) L2.get(i);
                if (y.getState() == 0) {
                    L.add(c++, y);
                    y.setState(2);
                }
            }
        }
        return r;
    }

    /**
     * Método que se encarga de recorrer la estructura en profundidad.
     * @return
     */
    public String dfs() {
        for (int i = 0; i < lista_vertices.size(); i++) {
            Vertice w = (Vertice) lista_vertices.get(i);
            w.setState(0);
        }

        Stack stack = new Stack();
        String r = "";

        stack.push(this.v_inicio);
        v_inicio.setState(1);
        r = String.valueOf(this.v_inicio.getElemento());

        while (!stack.isEmpty()) {
            Vertice v = (Vertice) stack.peek();
            Vertice vv = adyacentesHijosNoVisitados(v);
            if (vv != null) {
                vv.setState(2);
                r = r + " - " + vv.getElemento();
                stack.push(vv);
            } else {
                stack.pop();
            }
        }
        return r;
    }

    // </editor-fold>

    /*--------------------------------------------------------------------------------------------*/

    // <editor-fold defaultstate="collapsed" desc="Marcar hijos como no visitados">

    /**
     * Método que permite marcar un hijo como no visitado desde un vértice concreto.
     * @param v
     */
    public void marcarHijosVerticeNoVisitados(Vertice v){

        for (int i = 0; i < lista_aristas.size(); i++) {
            Arista a = (Arista) lista_aristas.get(i);
            Vertice V1 = a.getV1();
            Vertice V2 = a.getV2();

            if (V1 == v) {
                for (int j = 0; j < V1.getVisitados().size(); j++) {
                    if (V1.getVisitados().get(j).equals(V2.getElemento().toString())) {
                        V1.getVisitados().remove(j);
                    }
                }
            }
        }
    }

    // </editor-fold>

    /*--------------------------------------------------------------------------------------------*/

    // <editor-fold defaultstate="collapsed" desc="Getters and Setters">

    public Vertice getV_inicio() {
        return v_inicio;
    }

    public void setV_inicio(Vertice v_inicio) {
        this.v_inicio = v_inicio;
    }

    public int getCv() {
        return cv;
    }

    public void setCv(int cv) {
        this.cv = cv;
    }

    public int getCe() {
        return ce;
    }

    public void setCe(int ce) {
        this.ce = ce;
    }

    public LinkedList getVertices() {
        return lista_vertices;
    }

    public LinkedList getAristas() {
        return lista_aristas;
    }

    // </editor-fold>

    /*--------------------------------------------------------------------------------------------*/
}