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

/**
 * @author Joel
 * @author Cristian
 */

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

public class AlgoritmoBR {

    /**
     * @param args the command line arguments
     */
    ArrayList<vertice> VGi = new ArrayList<> ();
    ArrayList<vertice> VGe = new ArrayList<> ();
    ArrayList<arista> E_no_VGe = new ArrayList<> ();
    ArrayList<arista> E_no_VGi = new ArrayList<> ();
    ArrayList<rectaDual> arrangement = new ArrayList<> ();
    public long tiempoEjecucion=0, inicio, fin, tiempoParte1=0, tiempoParte2=0, tiempoParte3=0, tiempoParte4=0, tiempoParte5=0;
    
    /**
     * Este método permite reportar a todos los segmentos de un grafo (B) que se intersecan por lo menos con algun segmento de un grafo distinto (R) en complejidad de tiempo O(n^2)
     * @param R - Grafo Rojo (RED)
     * @param B - Grafo Azul (BLUE)
     */
    public void BR(Grafo R, Grafo B) {
        
            
        
        //Grafos en consulta
        Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+"\n"+R.toString()+"\n");
        Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+"\n"+B.toString()+"\n");
        
        //Parte 1
        inicio=System.nanoTime();
        
        ArrayList<vertice> ConvexHull = new ArrayList<vertice>();
        ConvexHull = R.GrahamScan();
        
        setV(ConvexHull, B.vertices);
        
        fin=System.nanoTime();
        
        tiempoParte1=fin-inicio;
        
        Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+"\nCH(R):\n"+ConvexHull.toString()+" ");
        Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+"\n\n\nV(Gi):\n"+VGi.toString());
        Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+"\n\nV(Ge):\n"+VGe.toString());
        Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+"\n\ntiempo: "+tiempoParte1+" ns");
        
        
        //Parte 2
        // (a)
        if(!VGe.isEmpty())
        {
            
            inicio=System.nanoTime();
            
            ArrayList<tangente> tngt = new ArrayList();
            tngt = tangentes(VGe, ConvexHull);

            tngt = OrdenRotacional(tngt);
            
            // (b)
            E_no_VGe=obtenerEGVe(tngt,ConvexHull,B);
            
            
            fin=System.nanoTime();
            
            tiempoParte2=fin-inicio;

            
            Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+"\n\nvértices tangentes (Der-Izq):\n");
            for(int i=0; i<VGe.size(); i++)
                    Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+tngt.get(i).toString()+"\n");

            Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+"\n\nOrden Rotacional:\n");
            for(int i=0; i<tngt.size(); i++)
                Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+tngt.get(i).toString("Orden Rotacional")+"\n");

            Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+"\n\nLos Segmentos que atraviesan a R: "+E_no_VGe.toString());
        }

        /*System.out.println("\n\nEl arrangement creado es el siguiente: \n");
        for(int i=0; i<R.vertices.size(); i++)
            System.out.println("y = "+R.vertices.get(i).getX()+"x + ("+R.vertices.get(i).getY()+")\n");
        for(int i=0; i<VGi.size(); i++)
            System.out.println("y = "+VGi.get(i).getX()+"x + ("+VGi.get(i).getY()+")\n");
        crearArrangement(R.vertices, VGi);
        for(int i=0; i<arrangement.size(); i++){
            System.out.println(arrangement.get(i).toString()+"\n");
        }*/
        
        
        
        // Parte 3
        inicio=System.nanoTime();
        
        obtenerEGi(R.vertices, VGi, ConvexHull);
        
        fin=System.nanoTime();
        
        tiempoParte3=fin-inicio;
        
        
        
        // Parte 4
        
        
        
        
        
        tiempoEjecucion= tiempoParte1+tiempoParte2+tiempoParte3+tiempoParte4;
        
        Interfaz.jTextArea1.setText(Interfaz.jTextArea1.getText()+"\n\nTiempo de Ejecución Total: \t"+tiempoEjecucion+"ns\nTiempo Parte 1: \t"+tiempoParte1+" ns\nTiempo Parte 2: \t"+tiempoParte2+" ns\nTiempo Parte 3: \t"+tiempoParte3+" ns\nTiempo Parte 4: \t"+tiempoParte4+"ns\n");
        
    }
       
    /**
     * Método que busca los puntos azules que están dentro y fuera del cierre convexo (VGi y VGe, respectivamente)
     * @param poligono
     * @param puntos 
     */
    public void setV(ArrayList<vertice> poligono, ArrayList<vertice> puntos){
        for(int i=0; i<puntos.size(); i++){
            if(estaDentro(poligono, puntos.get(i)))
                this.VGi.add(puntos.get(i));
            else
                this.VGe.add(puntos.get(i));
        }
    }
    
    
    /**
     * Método para verificar si un punto se encuentra dentro de un polígono.
     * @param poligono
     * @param punto
     * @return true si el punto está dentro del polígono, false si no lo está.
     */
    public boolean estaDentro(ArrayList<vertice> poligono, vertice punto)
    {
        int counter = 0;
        int i;
        int n=poligono.size();
        double xinters;
        vertice p1,p2;
        p1 = poligono.get(0);
        for (i=1;i<=n;i++) {
            p2 = poligono.get(i%n);
            if (punto.getY() > Math.min(p1.getY(),p2.getY())) {
                if (punto.getY() <= Math.max(p1.getY(),p2.getY())) {
                    if (punto.getX() <= Math.max(p1.getX(),p2.getX())) {
                        if (p1.getY() != p2.getY()) {
                            xinters = (punto.getY()-p1.getY())*(p2.getX()-p1.getX())/(p2.getY()-p1.getY())+p1.getX();
                            //OBS: Si los puntos en linea se cuentan dentro, se hace < xinters
                            if (p1.getX() == p2.getX() || punto.getX() <= xinters)
                                counter++;
                        }
                    }
                }
            }
            p1 = p2;
        }
        if (counter % 2 == 0)
            return false;
        else
            return true;
    }    
    
   // para paso 2
   /**
    * método de ordenamiento optimizado, modificado para almacenar el contenido del ordenamiento en una Lista de indices
    * @param data - Lista de datos
    * @param origin - Lista de datos originales
    * @param first - indice del primer elemento de la lista
    * @param n - tamaño de la Lista
    * @param indice - Lista de indices resultante
    */
    public void mergesort(ArrayList<vertice> data, ArrayList<vertice> origin, int first, int n, ArrayList<Integer> indice)
   {
      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,origin, first, n1, indice);      // Sort data[first] through data[first+n1-1]
         mergesort(data,origin, first + n1, n2, indice); // Sort data[first+n1] to the end

         // Merge the two sorted halves.
         merge(data,origin, first, n1, n2, indice);
      }
   } 
  /**
   * método de ordenamiento de apoyo al método mergesort
   * @param data - Lista de datos
   * @param origin - Lista de datos Originales
   * @param first - el primero de la Lista
   * @param n1 - el inicio del segmento
   * @param n2 - el final del segmento
   * @param indice - la lista de los indices resultantes
   */
   private void merge(ArrayList<vertice> data, ArrayList<vertice> origin, int first, int n1, int n2, ArrayList<Integer> indice)
   {
      ArrayList<vertice> temp = new ArrayList(); // Allocate the temporary array
      ArrayList<Integer> tempI = 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 (data.get(first + copied1).getX() < data.get(first + n1 + copied2).getX()) 
         {
             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));
         indice.set(first + i, origin.indexOf(temp.get(i)));
      }
      
   }
   
   /**
        * Consulta si un vertice dado está o no a la izquierda de una recta
        * @param A - primer vertice de la recta
        * @param B - segundo vertice de la recta
        * @param C - vertice a consulta
        * @return true si está a la izquierda, false si no lo está.
   */
   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;
    }

   
   /**
    * Calcula los vertices tangententes del conjunto VGe con respecto a CH.
    * @param VGe - Lista del conjunto de vertices VGe
    * @param CH - Lista de vertices que componen el CH
    * @return la Lista de tangentes izquierdas y derechas de VGe con repecto a CH.
    */
   private ArrayList<tangente> tangentes(ArrayList<vertice> VGe, ArrayList<vertice> CH)
   {
       
       ArrayList<tangente> tngt = new ArrayList();
       
       int fila=0;       
       int i,j,k;
       
       ArrayList<Integer> indices = new ArrayList();
       
       for( i=0; i<CH.size();i++)
           indices.add(i);
       
       for(i=0; i<VGe.size();i++)
           tngt.add(new tangente());
       
       mergesort((ArrayList<vertice>) CH.clone(),CH,0,CH.size(),indices);
       //indices con las posiciones de los puntos ordenados por el eje X
       double suma=0;
       for(i=0; i<CH.size();i++)
           suma=suma+CH.get(indices.get(i)).getX();
       suma=suma/i;
       
       for(int p=0; p<VGe.size();p++)
       {
           //resguardos para los indices ordenados por eje X
        if(VGe.get(p).getX() <= suma) 
        {
            for( i=0; i< CH.size(); i++)
            {
                //resguardos para hacer los calculos en el array lineal
                if(indices.get(i)==0){
                    j=CH.size();
                    k=indices.get(i);
                }else{
                    if(indices.get(i)==CH.size()-1){
                        j=indices.get(i);
                        k=-1;
                    }else{
                        j=indices.get(i);
                        k=indices.get(i);
                    }
                }
            
            
                if(estaIzquierda(CH.get(j-1), CH.get(indices.get(i)), VGe.get(p)) && !estaIzquierda(CH.get(indices.get(i)), CH.get(k+1), VGe.get(p))){
                   tngt.get(fila).setP(VGe.get(p));
                   tngt.get(fila).setTan_der(CH.get(indices.get(i)));
                }else{
                   if(!estaIzquierda(CH.get(j-1), CH.get(indices.get(i)), VGe.get(p)) && estaIzquierda(CH.get(indices.get(i)), CH.get(k+1), VGe.get(p))){
                        tngt.get(fila).setP(VGe.get(p));
                        tngt.get(fila).setTan_izq(CH.get(indices.get(i)));
                   }
                }
                if(tngt.get(fila).estaCompleto()) i=CH.size();
              }
            }
       else
        {
            for( i=CH.size()-1; i>=0; i--)
            {
                //resguardos para hacer los calculos en el array lineal
                if(indices.get(i)==0){
                    j=CH.size();
                    k=indices.get(i);
                }else{
                    if(indices.get(i)==CH.size()-1){
                        j=indices.get(i);
                        k=-1;
                    }else{
                        j=indices.get(i);
                        k=indices.get(i);
                    }
                }
                
                if(estaIzquierda(CH.get(j-1), CH.get(indices.get(i)), VGe.get(p)) && !estaIzquierda(CH.get(indices.get(i)), CH.get(k+1), VGe.get(p))){
                   tngt.get(fila).setP(VGe.get(p));
                   tngt.get(fila).setTan_der(CH.get(indices.get(i)));
                }else{
                   if(!estaIzquierda(CH.get(j-1), CH.get(indices.get(i)), VGe.get(p)) && estaIzquierda(CH.get(indices.get(i)), CH.get(k+1), VGe.get(p))){
                        tngt.get(fila).setP(VGe.get(p));
                        tngt.get(fila).setTan_izq(CH.get(indices.get(i)));
                   }
                }
                
                if(tngt.get(fila).estaCompleto()) i=-1;
             }
        }
                if(tngt.get(fila).estaCompleto()) fila++;
                
       }
       return tngt;
   }

   
   /**
    * Método de ordenamiento optimizado, modificado para ordenar una lista de tangentes
    * @param data - Lista de datos
    * @param first - el indice del primer elemento
    * @param n - cantidad de elementos de la Lista
    */
   public void mergesort(ArrayList<tangente> data, int first, int n)
   {
      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);      // Sort data[first] through data[first+n1-1]
         mergesort(data, first + n1, n2); // Sort data[first+n1] to the end

         // Merge the two sorted halves.
         merge(data, first, n1, n2);
      }
   } 
  
   /**
    * Método de Ordenamiento Optimizado de apoyo a mergesort
    * @param data - Lista de datos
    * @param first - el primer elemento de la Lista
    * @param n1 - indice de inicio del segmento
    * @param n2 - indice de termino del segmento
    */
   private void merge(ArrayList<tangente> data, int first, int n1, int n2)
   {
      ArrayList<tangente> 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 (data.get(first + copied1).getM() < data.get(first + n1 + copied2).getM()) 
         {
             if(data.get(first + copied1).getM()==0 && data.get(first + copied1).esInfinita())
                temp.add(copied++, data.get(first + n1  + (copied2++)));  
             else
                temp.add(copied++, data.get(first + (copied1++)));
         }
         else
         {    
             if(data.get(first + n1 + copied2).getM()==0 && data.get(first + n1 + copied2).esInfinita())
                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));
      }
      
   }
   
   /**
    * Método que obtiene el orden rotacional de VGe con respecto a CH, en concreto
    * @param origen
    * @return 
    */
   private ArrayList<tangente> OrdenRotacional(ArrayList<tangente> origen)
   {
       //acomodo de los datos del arreglo
       int n=origen.size();
       for(int i=0; i<n ;i++)
       {
           tangente a = new tangente();
           a.setP(origen.get(i).getP());
           a.setTan_izq(origen.get(i).getTan_der());
           origen.add(i+n,a);
       }
       //ordenamientos
        mergesort(origen,0,origen.size());
       
       //reacomodo de lista (a partir de cero)
        n=origen.size();
        while(origen.get(0).getM()<0 )
        {
            origen.add(n,origen.get(0));
            origen.remove(0);
        }
        
       return origen;
   }
   
   /**
    * Este método realiza una comparación de los puntos externos con la cerradura convexa para determinar los segmentos azules que intersecan a la cerradura convexa.
    * para ello utiliza un cáliper Rotatorio que gira bajo el orden rotacional dado determinando los puntos que estan de un lado al otro dentro de las líneas paralelas de soporte del Cáliper Rotatorio.
    * @param OR Orden Rotacional de los Puntos Azules Externos con respecto a CH(R)
    * @param CH la Cerradura Convexa del Grafo Rojo
    * @param B El Grafo Azul.
    * @return Un Arreglo de los segmentos azules externos que atraviesan a CH(R).
    */
   public ArrayList<arista> obtenerEGVe(ArrayList<tangente> OR, ArrayList<vertice> CH, Grafo B)
   {
       ArrayList<arista> EGVe = new ArrayList();
       boolean mediaVuelta=false;
       
       CaliperRotatorio CR = new CaliperRotatorio();
       //busca caliper horizontal
       CR.buscarAntipodal(CH.get(0), CH);
       
       for(int i=0; i<OR.size() ;i++)
       {
           CR.ingresa(OR.get(i).getP());
           
           //mover caliper
           CR.girar(OR.get(i),CH);
           
               for(int k=0; k < CR.elementosDentro()-1 ; k++)
               {
                   
                   if(CR.estaDentro(CR.getElementoDentro(k), OR.get(i)))
                   {
                       arista aIntersectar = B.esArista(CR.getElementoDentro(k),CR.getElementoDentro(CR.elementosDentro()-1));
                       if(aIntersectar != null)
                       {
                           if(CR.intersectaCon(aIntersectar))
                           {
                               if(!EGVe.contains(aIntersectar))
                                   EGVe.add(aIntersectar);
                           }
                       }
                   }
                   else
                   {
                       CR.saleDentro(k);
                       k--;
                   }
               }
               
               if(i==OR.size()-1 && mediaVuelta==false)
               {
                   i=-1;
                   mediaVuelta=true;
               }
       }
       return EGVe;
   }

   public void obtenerEGi(ArrayList<vertice> R, ArrayList<vertice> VGi, ArrayList<vertice> CH){
       int current=-1;
       ArrayList<Splits> C = new ArrayList<>();
       C.add(new Splits());
       C.get(0).crearRegion(CH);
       C.get(0).addPoint(VGi.get(0), 0);
       //(a)
       crearArrangement(R, VGi);
       //(b)
       for(int k=1; k<2/*VGi.size()*/; k++){
           //(i)
           current=regionActual(VGi.get(k), C.get(k-1).Regiones);
           //(ii)
           if(C.get(k-1).Regiones.get(current).esVacia()){
               C.add(new Splits());
               C.get(k).Regiones = C.get(k-1).Regiones;
               C.get(k).Regiones.get(current).puntos.add(VGi.get(k));
           }
           else{
               //(A)
               ArrayList<dualRojo> OR = new ArrayList<>();
               //System.out.println("\nPrueba de OR "+k+"\n");
               OR=getOR(arrangement.get(indexA(C.get(k-1).Regiones.get(current).puntos.get(0))).getRojo(), arrangement.get(indexA(VGi.get(k))).getRojo());
               //System.out.println(OR.toString());
               //(B)
               
               
           }
       }
   }
   
   public ArrayList<dualRojo> getOR(ArrayList<dualRojo> bj, ArrayList<dualRojo> bk){
       ArrayList<dualRojo> OR = new ArrayList<>();
       ArrayList<dualRojo> Pos = new ArrayList<>();
       ArrayList<dualRojo> Neg = new ArrayList<>();
       ArrayList<dualRojo> IP = new ArrayList<>();
       ArrayList<dualRojo> IN = new ArrayList<>();
       for(int i=0; i<bj.size(); i++){
           if(bj.get(i).interAzul.getX()<0){
               if(bj.get(i).interAzul.getX()== Double.NEGATIVE_INFINITY)
                   IN.add(bj.get(i));
               else
                   Neg.add(bj.get(i));
           }
           else{
               if(bj.get(i).interAzul.getX()== Double.POSITIVE_INFINITY)
                   IP.add(bj.get(i));
               else
                   Pos.add(bj.get(i));
           }
       }
       for(int i=0; i<bk.size(); i++){
           if(bk.get(i).interAzul.getX()<0){
               if(bk.get(i).interAzul.getX()== Double.NEGATIVE_INFINITY)
                   IN.add(bk.get(i));
               else
                   Neg.add(bk.get(i));
           }
           else{
               if(bk.get(i).interAzul.getX()== Double.POSITIVE_INFINITY)
                   IP.add(bk.get(i));
               else
                   Pos.add(bk.get(i));
           }
       }
       mergesort2(Pos, 0, Pos.size());
       mergesort2(Neg, 0, Neg.size());
       OR.addAll(Pos);
       OR.addAll(IP);
       OR.addAll(IN);
       OR.addAll(Neg);
       //Ordenar OR
       return OR; 
   }
   
   public int regionActual(vertice pto, ArrayList<regionConvexa> regiones){
       int posActual=0;
       for(int i=0; i<regiones.size(); i++){
           if(regiones.get(i).estaDentro(pto)){
               posActual=i;
               break;
           }
       }
       return posActual;
   }
   /**
    * Método que crea un arreglo dual de líneas a partir de los puntos rojos y VGi
    * @param R
    * @param VGi 
    */
   public void crearArrangement(ArrayList<vertice> R, ArrayList<vertice> VGi){
       
       for(int i=0; i<VGi.size(); i++){
           rectaDual aux = new rectaDual(VGi.get(i), R);
           arrangement.add(aux);
       }
   }
   
   public int indexA(vertice v){
       int pos=-1;
       for(int i=0; i<arrangement.size(); i++){
           if(arrangement.get(i).getAzul()==v)
               pos=i;
       }
       return pos;
   }
   
   public void mergesort2(ArrayList<dualRojo> data, int first, int n)
   {
      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;

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

         // Merge the two sorted halves.
         merge2(data, first, n1, n2);
      }
   } 
  
   private void merge2(ArrayList<dualRojo> data, int first, int n1, int n2)
   {
      ArrayList<dualRojo> 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 ((data.get(first + copied1).getInter().getX() < data.get(first + n1 + copied2).getInter().getX())||((data.get(first + copied1).getInter().getX() == data.get(first + n1 + copied2).getInter().getX())&&(data.get(first + copied1).getInter().getY() < data.get(first + n1 + copied2).getInter().getY())))
            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));
   }
   
}
