package utils;

import java.awt.Point;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
import java.util.Vector;

import business.Arista;
import business.Grafo;
import business.Vertice;
import core.PanelEdicion;


public class Utilidades {

	public static void algoritmoDijkstra(Vertice verticeOrigen, HashMap<Integer,Vertice> resultado, Grafo grafo) {
		ArrayList<Vertice> vertices = grafo.getVertices();
		for(Vertice v : vertices) {	 //Le pone a todos los vertices del grafo: (padre=-1) y si no es el origen (distancia=infinito)
			v.setPadre(-1);
			if(v.getId().equals(verticeOrigen.getId())) {
				v.setDistancia(0);
			} else {
				v.setDistancia(Constantes.INFINITO);
			}
			v.setRecorrido(false);
		}

		boolean continua = true;
		while(continua) {
			Vertice verticeAux = obtenerVerticeDistanciaMinima(vertices);
			continua = verticeAux.getId() != -1;
			if(continua) {
				verticeAux.setRecorrido(true);
				ArrayList<Vertice> verticesAdyacentes = verticeAux.getAdyacentes();
				for(Vertice vAdy : verticesAdyacentes) {
					Arista arista = grafo.obtenerAristaPorVertices(verticeAux.getId(), vAdy.getId());
					if(arista.getId() != -1) {
						if(vAdy.getDistancia() > verticeAux.getDistancia() + 1) {
							for(Vertice v : vertices) {
								if(v.getId() == vAdy.getId())
									break;
							}
							vAdy.setDistancia(verticeAux.getDistancia() + 1);
							vAdy.setPadre(verticeAux.getId());
							resultado.put(vAdy.getId(), vAdy);
						}
					}
				}
			}
		}
	}

	private static Vertice obtenerVerticeDistanciaMinima(ArrayList<Vertice> vertices) {
		int distanciaMinima = Constantes.INFINITO;
		Vertice verticeMinimo = new Vertice(new Point(0, 0), -1, false);
		for(Vertice v : vertices) {
			if(!v.isRecorrido() && v.getDistancia() < distanciaMinima)	{
				verticeMinimo = v;
				distanciaMinima = v.getDistancia();
			}
		}
		return verticeMinimo;
	}

	public static void CalcularMatriz(int matrizDistancias[][], Grafo grafo) {
		HashMap<Integer,Vertice> camino = new HashMap<Integer,Vertice>();
		ArrayList<Vertice> vertices = grafo.getVertices();
		int i = 0;
		for(Vertice v : vertices) {
			camino.clear();
			algoritmoDijkstra(v, camino, grafo);
			Set<Integer> keys = camino.keySet();
			for(Integer key : keys) {
				v = camino.get(key);
				matrizDistancias[i][vertices.indexOf(v)] = v.getDistancia();
			}
			i++;
		}
	}

	public static boolean existeCiclo(Grafo grafo) {
		for(int i = 0; i < grafo.getVertices().size(); i++) {
			if(existeCicloDesdeVertice(grafo, i)) {
				return true;
			}
		}
		return false;
	}

	private static boolean existeCicloDesdeVertice(Grafo grafo, int origen) {
		boolean ciclo = false;
		class VerticeDistancia {
			public Vertice v;
			public int d;
			VerticeDistancia() {
				v = null;
				d = 0;
			}
		}
		Stack<VerticeDistancia> abiertos = new Stack<VerticeDistancia>();
		Stack<Vertice> cerrados = new Stack<Vertice>();
		Vertice verticeOrigen = grafo.getVertices().get(origen);
		int original = verticeOrigen.getId();
		cerrados.add(verticeOrigen);
		ArrayList<Vertice> adyacentes = verticeOrigen.getAdyacentes();
		for(Vertice v : adyacentes) {
			VerticeDistancia vDist = new VerticeDistancia();
			vDist.v = v;
			vDist.d++;
			abiertos.add(vDist);
		}
		VerticeDistancia vDistAux = new VerticeDistancia();
		for(; !abiertos.empty() && !ciclo; cerrados.push(vDistAux.v)) {
			vDistAux = abiertos.pop();
			adyacentes = vDistAux.v.getAdyacentes();
			for(Vertice v : adyacentes) {
				VerticeDistancia nodoDist = new VerticeDistancia();
				verticeOrigen = v;
				if(verticeOrigen.getId() != original) {
					if(!cerrados.contains(verticeOrigen)) {
						nodoDist.d = vDistAux.d + 1;
						nodoDist.v = verticeOrigen;
						abiertos.add(nodoDist);
					}
				} else if (vDistAux.d > 1) {
					return true;
				}
			}
		}
		return ciclo;
	}

	public static Integer[] obtenerDistanciasResolutivas(int indiceVertice, ArrayList<Integer> verticesIds, PanelEdicion pEdicion, int matrizDistancias[][]) {
		Integer distancias[] = new Integer[verticesIds.size()];
		for(int i = 0; i < verticesIds.size(); i++) {
			Integer indiceV = pEdicion.getGrafo().obtenerIndiceVerticePorId(verticesIds.get(i));
			Integer dist = matrizDistancias[indiceVertice][indiceV];
			distancias[i] = dist;
		}
		return distancias;
	}

	public static boolean hayRepetidos(ArrayList<Integer[]> distancias) {
		boolean repetidos = false;
		for(int i=0; !repetidos && i<distancias.size(); i++) {
			Integer veces = apariciones(distancias.get(i), distancias);
			if(veces == 2)
				repetidos = true;
		}
		return repetidos;
	}

	private static Integer apariciones(Integer d[], ArrayList<Integer[]> distancias) {
		int contador = 0;
		for(int i=0; i<distancias.size() && contador<2; i++) {
			boolean iguales = true;
			for(int j=0; iguales && j<d.length; j++) {
				iguales = iguales && d[j] == distancias.get(i)[j];
			}
			if(iguales)
				contador++;
		}
		return contador;
	}

	public static boolean contiene(ArrayList<ArrayList<Integer>> listaConjuntos, ArrayList<Integer> conjunto) {
		for(ArrayList<Integer> subconjunto : listaConjuntos) {
			if(sonIguales(conjunto, subconjunto))
				return true;
		}
		return false;
	}

	private static boolean sonIguales(ArrayList<Integer> conjunto, ArrayList<Integer> subconjunto) {
		boolean igual = false;
		if(conjunto.size() == subconjunto.size()) {
			int max = conjunto.size();
			for(int i = 0; i < max; i++) {
				igual = subconjunto.contains(conjunto.get(i));
				if(!igual || igual && i == max - 1)
					break;
			}
		}
		return igual;
	}

	public static Boolean esGrafoCiclo(Grafo grafo) {
		Boolean esCiclo = true;
		ArrayList<Vertice> vertices = grafo.getVertices();
		ArrayList<Integer> mirados = new ArrayList<Integer>();
		Vertice v = vertices.get(0);
		while (esCiclo && vertices.size() != mirados.size()) {
			mirados.add(v.getId());
			ArrayList<Vertice> adyacentes = v.getAdyacentes();
			if(adyacentes.size() != 2) {
				esCiclo = false;
			} else if(!mirados.contains(adyacentes.get(0).getId())) {
				v = adyacentes.get(0);
			} else if(!mirados.contains(adyacentes.get(1).getId())) {
				v = adyacentes.get(1);
			} else if(vertices.size() != mirados.size()){
				esCiclo = false;
			}
		}
		return esCiclo;
	}

	public static String sonGemelos(Vertice v1, Vertice v2) {
		String res = "GEMELOSNO";
		ArrayList<Vertice> ady1 = v1.getAdyacentes();
		ArrayList<Vertice> ady2 = v2.getAdyacentes();
		if(ady1.size() == ady2.size()) {
			for(Vertice e : ady1) {
				if(v2.equals(e)) {
					res= "GEMELOSAD";
				} else if(!ady2.contains(e)) {
					return "NADA";
				}
			}
		} else {
			res = "NADA";
		}
		return res;
	}

	public static Boolean estaDentroRegion(Point vertice, Point extremo1, Point extremo2, Double zoom) {
		Double x1 = extremo1.getX() / zoom;
		Double y1 = extremo1.getY() / zoom;
		Double x2 = extremo2.getX() / zoom;
		Double y2 = extremo2.getY() / zoom;
		return vertice.x > Math.min(x1, x2) && vertice.x < Math.max(x1, x2) && vertice.y > Math.min(y1, y2) && vertice.y < Math.max(y1, y2);
	}

	public static Boolean esVaciaONula(ArrayList<?> lista) {
		return lista == null || lista.isEmpty();
	}

	public static Boolean esVaciaONula(HashSet<Arista> conjunto) {
		return conjunto == null || conjunto.isEmpty();
	}

	public static Boolean esVaciaONula(Vector<?> vector) {
		return vector == null || vector.isEmpty();
	}

	public static String calcularExtensionArchivo(String nombre) {
		int longitud = nombre.length();
		return nombre.substring(longitud - 3, longitud);
	}

	public static Integer calcularMaximoNumeroAristas(Integer numeroVertices) {
		return (numeroVertices*(numeroVertices-1))/2;
	}
}