/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package algoritmobr;

import interfaz.Interfaz;
import java.io.*;
import java.util.ArrayList;
import java.util.Stack;
import javax.swing.JOptionPane;

/**
 *
 * @author Joel
 * @author Cristian
 */
public class Grafo {
    
    public ArrayList<vertice> vertices;
    public ArrayList<arista> aristas;
    String nombre;

    /**
     * Constructor de un Grafo, da memoria a los arrayList de vertices y aristas y un nombre al grafo.
     */
    public Grafo() {
        this.vertices = new ArrayList<>();
        this.aristas = new ArrayList<>();
        this.nombre = "AUX";
    }
    
    /**
     * Constructor de un Grafo, da memoria a los arrayList de vertices y aristas y un dado por el método nombre al grafo.
     * @param nombre 
     */
    public Grafo(String nombre) 
    {
        this.vertices = new ArrayList<>();
        this.aristas = new ArrayList<>();
        this.nombre = nombre;
    }
    
    /**
     * Añade un vertice al grafo
     * @param x - Coordenada X
     * @param y - Coordenada Y
     */
    public void addVertice(Double x, Double y)
    {
        vertice a = new vertice(x,y);
        vertices.add(a);
    }
    
    /**
     * Añade una Arista al Grafo a traves de las referencias a de dos vertices (arista adireccional)
     * @param desde - primer vertice
     * @param hasta - segundo vertice
     */
    public void addArista(vertice desde, vertice hasta)
    {
        int flag=0;
        
        for(int i=0; i<aristas.size();i++){
            if(aristas.get(i).getDesde().equals(desde) && aristas.get(i).getHasta().equals(hasta)){
                flag++;
            }}
        
        if(flag==0){
        arista a = new arista(desde,hasta);
        aristas.add(a);
        }
    }
    
    /**
     * Añade una arista al Grafo a traves de indices de los vertices involucrados
     * @param desde - Indice del primer vertice
     * @param hasta - Indice del segundo vertice
     */
    public void addAristaIndice(int desde, int hasta)
    {
        int flag=0;
        
        for(int i=0; i<aristas.size();i++){
            if(vertices.indexOf(aristas.get(i).getDesde())==desde && vertices.indexOf(aristas.get(i).getHasta())==hasta){
                flag++;
            }}
        
        if(flag == 0){
            arista a = new arista(vertices.get(desde),vertices.get(hasta));
            aristas.add(a);
        }
        
    }
    
    
    public boolean esVacio()
    {
        if(vertices.isEmpty())
            return true;
        else
            return false;
    }
    
    //métodos
    //Graham Scan O(n log n)
    public ArrayList<vertice> GrahamScan(){
        ArrayList <vertice> Ch = new ArrayList(); 
        Stack<vertice> P=CH();
        while(!P.empty())
            Ch.add(0,P.pop());
        return Ch;
    }
    
    public Stack <vertice> CH(){
        ArrayList<vertice> puntos = new ArrayList<>();
        Stack <vertice> P = new Stack <vertice>();
        vertice min;
        puntos=(ArrayList<vertice>) vertices.clone();
        min = PuntoMenorOrdenada(puntos);
        puntos = OrdenarAngularmente(puntos, min);
        P.push(puntos.get(0));
        P.push(puntos.get(1));
        P.push(puntos.get(2));
        int i = 3;
        while(i<puntos.size()){
            vertice t= new vertice();
            t = P.pop();
            if(estaIzquierda(P.peek(), t, puntos.get(i)))
            {
                P.push(t);
                P.push(puntos.get(i));
                i++;
            }
        }
        return P;
    }
    //O(n)
    public vertice PuntoMenorOrdenada(ArrayList <vertice> puntos){
        vertice menor;
        menor=puntos.get(0);
        for(int i=1; i<puntos.size(); i++){
            if(puntos.get(i).getY()<menor.getY()||((puntos.get(i).getY()==menor.getY())&&(puntos.get(i).getX()>menor.getX())))
                menor=puntos.get(i);
        }
        return menor;
    }
    
    //Cambiar el método de ordenamiento a MERGE SORT  O(n log n)
    public ArrayList<vertice> OrdenarAngularmente(ArrayList<vertice> S, vertice m){
            //Ordenamiento angular
            S.remove(S.indexOf(m));
            mergesort(S, 0, S.size(), m);
            S.add(0, m);
            return S;
    }
    
    public void mergesort(ArrayList<vertice> data, int first, int n, vertice m)
   {
      int n1; // Size of the first half of the array
      int n2; // Size of the second half of the array

      if (n > 1)
      {
         // Compute sizes of the two halves
         n1 = n / 2;
         n2 = n - n1;

         mergesort(data, first, n1, m);      // Sort data[first] through data[first+n1-1]
         mergesort(data, first + n1, n2, m); // Sort data[first+n1] to the end

         // Merge the two sorted halves.
         merge(data, first, n1, n2, m);
      }
   } 
  
   private void merge(ArrayList<vertice> data, int first, int n1, int n2, vertice m)
   {
      ArrayList<vertice> temp = new ArrayList(); // Allocate the temporary array
      int copied  = 0; // Number of elements copied from data to temp
      int copied1 = 0; // Number copied from the first half of data
      int copied2 = 0; // Number copied from the second half of data
      int i;           // Array index to copy from temp back into data

      // Merge elements, copying from two halves of data to the temporary array.
      while ((copied1 < n1) && (copied2 < n2))
      {
         if (Angulo(m,data.get(first + copied1)) < Angulo(m, data.get(first + n1 + copied2)))
            temp.add(copied++,data.get(first + (copied1++)));
         else
            temp.add(copied++,data.get(first + n1 + (copied2++)));
      }
      // Copy any remaining entries in the left and right subarrays.
      while (copied1 < n1)
         temp.add(copied++,data.get(first + (copied1++)));
      while (copied2 < n2)
         temp.add(copied++,data.get(first + n1 + (copied2++)));

      // Copy from temp back to the data array.
      for (i = 0; i < n1+n2; i++)
         data.set(first + i, temp.get(i));
   }
   
   public double Angulo(vertice A, vertice B){
        double my, mx, mb, angulo;
        my = B.getY()-A.getY();
        mx = B.getX()-A.getX();
        if(mx==0){
            if(my>0) return 90;
            else if(my<0) return 270;
            else {
                return 0;
            }
        }
        else if(my==0){
            if(mx>0) return 0;
            else return 180;
        }
        else{
            mb=my/mx;
            angulo=Math.atan(mb)*(180/Math.PI);
            if(mx>0){
                if(my<0) return angulo + 360;
                else return angulo;
            }
            else return angulo + 180;
        }
    }
   public boolean estaIzquierda(vertice A, vertice B, vertice C){
        if((((B.getX()-A.getX())*(C.getY()-A.getY()))-((B.getY()-A.getY())*(C.getX()-A.getX())))>0)
            return true;
        else return false;
    }
   
   
   /**
    * Consulta si los vertices involucrados forman una arista registrada en el grafo
    * @param a - primer vertice
    * @param b - segundo vertice
    * @return la arista consultada o null si no está registrada
    */
   public arista esArista(vertice a, vertice b)
   {
       for(int i=0; i< aristas.size();i++)
       {
           if(aristas.get(i).getDesde().equals(a) && aristas.get(i).getHasta().equals(b))
               return aristas.get(i);
           if(aristas.get(i).getDesde().equals(b) && aristas.get(i).getHasta().equals(a))
               return aristas.get(i);
       }
        return null;
   }
   
    
    
    /**
     * Lee los datos de vértices y aristas del Grafo mediante la lectura de un archivo.
     * @param archivo - nombre del archivo al cual se debe acceder para la lectura.
     */
    public void LeerGrafo(String archivo)
    {
        File gf = null;
        FileReader fr = null;
        BufferedReader br = null;

        try {
           // Apertura del fichero y creacion de BufferedReader para poder
           // hacer una lectura comoda (disponer del metodo readLine()).
           gf = new File (archivo);
           fr = new FileReader (gf);
           br = new BufferedReader(fr);

           // Lectura del fichero
           String linea;
           double x, y;
           int d, h;
           while((linea=br.readLine())!=null)
           {
               if("<vertices>".equals(linea)){
                   linea=br.readLine();
                   
                   while(! "<\\vertices>".equals(linea)){
                       
                       x=Double.parseDouble(linea.substring(0, linea.indexOf(" ")));
                       y=Double.parseDouble(linea.substring(linea.indexOf(" ")));
                       
                       addVertice(x,y);
                       linea=br.readLine();
                   }
               }
               
               if("<aristas>".equals(linea)){
                   linea=br.readLine();
                   
                   while(! "<\\aristas>".equals(linea)){
                       
                       d=(int) Double.parseDouble(linea.substring(0, linea.indexOf(" ")));
                       h=(int) Double.parseDouble(linea.substring(linea.indexOf(" ")));
                       
                       addAristaIndice(d,h);
                       linea=br.readLine();
                   }
               }
               
           }           
        }
        catch(Exception e){
           //e.printStackTrace();
                JOptionPane.showMessageDialog(null, "ERROR, NO es posible abrir el archivo: "+archivo);
        }finally{
           // En el finally cerramos el fichero, para asegurarnos
           // que se cierra tanto si todo va bien como si salta 
           // una excepcion.
           try{                    
              if( null != fr ){   
                 fr.close();     
              }                  
           }catch (Exception e2){ 
              //e2.printStackTrace();
                JOptionPane.showMessageDialog(null, "ERROR, NO es posible abrir el archivo: "+archivo);
           }
        }
    }
    
    public void exportar(String ruta) {
        File fichero = new File(ruta, this.nombre + ".gr");
        
       // File fichero1 = new File(ruta+"/B.gr");
        //File fichero2 = new File(ruta+"/R.gr");
        if(fichero.exists())
        //if(fichero1.exists() || fichero2.exists())
        {
            int respuesta=JOptionPane.showConfirmDialog(null, "EL ARCHIVO "+this.nombre+" QUE INTENTA GUARDAR YA EXISTE\n"
           + "¿DESEA SOBREESCRIBIRLO?");
            if(respuesta==JOptionPane.YES_OPTION){
                fichero.delete();
                //fichero1.delete();
                //fichero2.delete();
            }
        
        }

        try {
            // A partir del objeto File creamos el fichero físicamente
            if (fichero.createNewFile()) {
                JOptionPane.showMessageDialog(null, "El fichero se ha creado correctamente");
                FileWriter file = null;
                PrintWriter pw = null;
                
                file= new FileWriter(ruta+"/"+this.nombre+".gr");
                pw = new PrintWriter(file);
                
                //Para los Vértices
                pw.println("<vertices>");
                
                for(int i=0; i<this.vertices.size();i++)
                    pw.println(this.vertices.get(i).getX() + " " + this.vertices.get(i).getY());
                
                pw.println("<\\vertices>");
                
                
                //Para las Aristas
                pw.println("<aristas>");
                
                for(int i=0; i<this.aristas.size();i++)
                    pw.println(this.vertices.indexOf(this.aristas.get(i).getDesde()) + " " + this.vertices.indexOf(this.aristas.get(i).getHasta()));
                
                pw.println("<\\aristas>");
                               
                
                file.close();
                
            } else {
                JOptionPane.showMessageDialog(null,"ERROR, No ha podido ser creado el fichero");
            }
        } catch (IOException ioe) {
            ioe.printStackTrace();
        }
    }
    
    /**
     * Se creará un grafo con coordenadas aleatorias, sólo se pide un 
     */
    public void aletorio(int N)
    {
        try{
        int i, d,h;
        Double x,y;
        for(i=0;i<N;i++)
        {
            do{
               x=Math.random()*620;
               y=Math.random()*420;
            }while(vertices.contains(new vertice(x,y)));
            addVertice(x,y); 
        }
        int dim = (int)(Math.random()*(((N*(N-1))/2)-(N-1)))+(N-1);

        for(i=0; i<N-1; i++)
            this.addAristaIndice(i, i+1);
        for(i=N-1;i<dim;i++)
        {
            do{
                d=(int) (Math.random()*(N-1))+0;
                h=(int) (Math.random()*(N-1))+0;
                
                if(d==h || esArista((vertice) vertices.get(d), (vertice) vertices.get(h))!=null)
                    d++;
                //System.out.println("hola "+d+" "+h);
            }while(d==h || esArista((vertice) vertices.get(d), (vertice) vertices.get(h))!=null);
            addAristaIndice(d,h);
        }
        
    }catch (Exception ex) {
                JOptionPane.showMessageDialog(null,"ERROR, Cantidad máxima Excedida");
            }
    }
    
    public void eliminarNodo(vertice v){
        for(int i=0; i<this.vertices.size(); i++){
            if(this.vertices.get(i).equals(v)){
                for(int j=0; j<this.aristas.size(); j++){
                    if(this.aristas.get(j).getDesde().equals(v)||this.aristas.get(j).getHasta().equals(v)){
                        this.eliminarArista(this.aristas.get(j));
                    }
                }
                this.vertices.remove(i);
            }
        }
    }
    
    public void eliminarArista(arista a){
        arista aux = this.esArista(a.getDesde(), a.getHasta());
        if(aux!=null){
            this.aristas.remove(a);
        }        
    }
    
   
    /**
     * se encarga de mostrar el contenido del grafo
     * @return un String con la información del Grafo
     */
    public String toString()
    {
        StringBuilder msn = new StringBuilder();
        msn.append("Grafo "+nombre+": \n vertices:"+vertices.toString()+"\n aristas:"+aristas.toString());
        return msn.toString();
    }
}
