package Practica01;

import java.io.*;
import java.util.*;
import java.*;


/**
 * Clase Skyline
 * @author Juan Miguel Gabarron Segura y Javier Imbernon Molina
 * @version 1.0
 */
public class Skyline {

    private ArrayList<Punto> skyline;
    private ArrayList<Edificio> edificios;
    private String archivoEntrada;
    private String archivoSalida;

    /**
     * Constructor por defecto
     */
    public Skyline(String archivoEntrada, String archivoSalida)
    {
        this.skyline = new ArrayList<Punto>();
        this.edificios=new ArrayList<Edificio>();
        this.archivoEntrada=archivoEntrada;
        this.archivoSalida=archivoSalida;
        cargarArchivoEdificios();
        generarSkyline();
        guardarArchivoSalida();
    }



	private void cargarArchivoEdificios() {

    	StringTokenizer token;
    	String entrada;
    	int numElementos;
    	int x,y,z;
    	Edificio e=null;

    	skyline = new ArrayList<Punto>();
    	edificios = new ArrayList<Edificio>();

    	try{
    		File f = new File(archivoEntrada);
    		FileReader fr = new FileReader(f);
    		BufferedReader br = new BufferedReader(fr);

    		numElementos = Integer.parseInt(br.readLine());
    		for(int i=0; i<numElementos; i++){
    			entrada=br.readLine();
    			token = new StringTokenizer(entrada,", ");
	    		try{
	    			x=Integer.parseInt(token.nextToken());
	    			y=Integer.parseInt(token.nextToken());
	    			z=Integer.parseInt(token.nextToken());
	    			e = new Edificio(x,y,z);
	    			edificios.add(e);
	    		}catch(NumberFormatException ex){
	    			System.out.println("Formato de entrada no valido \n");
	    		}

    		}
    		br.close();
    	}catch(Exception exception){
    		exception.printStackTrace();
    	}
	}

	/**
     * <B>Metodo getSkyline.</B>
     * Metodo observador de la clase Skyline
     * @return nos devuelve el Skyline
     */
    public void guardarArchivoSalida()
    {
        try
        {
            Punto p = new Punto();
            PrintWriter fileOut = new PrintWriter (new FileWriter(archivoSalida));

            fileOut.println(skyline.size());

            for(int i=0; i<skyline.size(); i++)
            {
                p=(skyline.get(i));

                fileOut.write(p.getX()+","+p.getY()+"\n");

            }
            fileOut.close();
        }
        catch(Exception e){

        	e.printStackTrace();

        }
    }

    private void generarSkyline() {

    	int pi = 0;                      	//Punto de Inicio del Skyline
        int pd = (edificios.size()-1);    	//Punto de Destino del Skyline

        skyline=doSkyline(pi, pd);

	}


    public ArrayList<Punto> doSkyline(int pi, int pd) 	// Metodo de Divide y Venceras
    {
        ArrayList<Punto> puntos = new ArrayList<Punto>();

        Punto p1 = new Punto();         	// Punto donde se guardara la variable X y Y del pi
        Punto p2 = new Punto();        		// Punto donde se guardara la variable X y Y del pi, siendo la Y = 0
        Edificio ed = new Edificio();  		// Variable donde guardaremos el edificio

        if(pi==pd) 							// caso base, la ciudad tiene un unico edificio
        {
            ed = edificios.get(pi); 		// cogemos el edificio de la posicion pi
            p1.setX(ed.getInicio());        // en la X del p1 guardamos la X de Inicio del Edificio
            p1.setY(ed.getAltura());        // en la Y del p1 guardamos la Altura del Edificio
            p2.setX(ed.getFin());       	// en la X del p2 guardamos la X de Fin del Edificio
            p2.setY(0);              		// La Altura final del Edificio es 0
            puntos.add(p1);     			// agregamos los puntos al Skyline de puntos
            puntos.add(p2);
        }

        else												 		 // Separamos en 2 los Skyline
        {
            int medio=(pi+pd)/2;

            ArrayList<Punto>izq = this.doSkyline(pi,medio);   		// Skyline desde pi hasta medio
            ArrayList<Punto>der = this.doSkyline(medio+1,pd); 		// Skyline desde medio hasta pd
            puntos = skylineFussion(izq,der);            			// Unimos los Skylines
        }

        return puntos;
    }

    public ArrayList<Punto> skylineFussion(ArrayList<Punto> sk1, ArrayList<Punto> sk2)
    {

    	int sk1Y= -1, sk2Y= -1, prev= -1;    				// "sk1Y" Altura del Skyline 1, "sk2Y" Altura del SkyLine 2, "prev" altura previa del anterior Skyline

    	ArrayList<Punto> salida = new ArrayList<Punto>();	// Skyline de salida

    	Punto pAux;                    						// punto auxiliar, lo usaremos para hacer la "mezcla de puntos"
        Punto p1 = new Punto();         					// punto donde guardaremos el primer punto del skyline sk1
        Punto p2 = new Punto();         					// punto donde guardaremos el primer punto del skyline sk2

        while ((!sk1.isEmpty()) && (!sk2.isEmpty())) 			// el bucle se realiza hasta que sk1 o sk2 se quede sin elementos
        {
            pAux = new Punto();  							// Inicializamos la variable pAux
            p1 = sk1.get(0); 								// guardamos el primer elemento de sk1
            p2 = sk2.get(0); 								// guardamos el primer elemento de sk2

            if (p1.getX() < p2.getX()) 						// Si X del sk1 es menor que la X del sk2
            {
                pAux.setX(p1.getX());                		// Guardamos en pAux la X de p1
                pAux.setY(Math.max(p1.getY(), sk2Y)); 		// Hacemos que el maximo entre la Y del sk1 y la altura previa del sk2 sea la altura Y de pAux

                if (pAux.getY()!=prev) 						// Si este maximo no es igual al del segmento anterior
                {
                    salida.add(pAux); 						// Agregamos el punto al Skyline de salida
                    prev = pAux.getY();    					// Actualizamos prev
                }
                sk1Y = p1.getY();   						// Actualizamos la altura sk1Y
                sk1.remove(0); 								// Eliminamos el punto del sk1
            }

            else if (p1.getX() > p2.getX()) 				// si X del sk1 es mayor que la X del sk2
            {
                pAux.setX(p2.getX());                		// Guardamos en pAux la X de p2
                pAux.setY(Math.max(p2.getY(), sk1Y)); 		// Hacemos que el maximo entre la Y del sk2 y la altura previa del sk1 sea la altura Y de pAux

                if (pAux.getY()!=prev) 						// Si este maximo no es igual al del segmento anterior
                {
                    salida.add(pAux); 						// Agregamos el punto al Skyline de salida
                    prev = pAux.getY();    					// Atualizamos prev
                }
                sk2Y = p2.getY();   						// Actualizamos la altura sk2Y
                sk2.remove(0); 								// Eliminamos el punto del sk2
            }


            else 														// si la X del s1 es igual a la X del s2
            {
                if ((p1.getY() > p2.getY()) && (p1.getY()!=prev)) 		// Guardaremos el punto que tenga la altura mas alta
                {
                    salida.add(p1);
                    prev = p1.getY();
                }
                if ((p1.getY() <= p2.getY()) && (p2.getY()!=prev))
                {
                    salida.add(p2);
                    prev = p2.getY();
                }
                sk1Y = p1.getY();   									// Actualizamos sk1Y e sk2Y
                sk2Y = p2.getY();
                sk1.remove(0); 											// Eliminamos el punto del sk1 y del sk2
                sk2.remove(0);
            }
        }
        while ((!sk1.isEmpty())) 										// Mientras sk1 no este vacio
        {
            pAux=sk1.get(0); 											// Guardamos en pAux el primer punto

            if (pAux.getY()!=prev) 										// Si pAux no tiene la misma altura del segmento previo
            {
                salida.add(pAux); 										// Agregamos pAux al Skyline de salida
                prev = pAux.getY();    									// Actualizamos prev
            }
            sk1.remove(0); 												// Eliminamos el punto de sk1
        }
        while((!sk2.isEmpty())) 										// Mientras sk2 no este vacio
        {
            pAux=sk2.get(0); 											// Guardamos en pAux el primer punto

            if (pAux.getY()!=prev) 										// Si pAux no tiene la misma altura del segmento previo
            {
                salida.add(pAux); 										// Agregamos pAux al Skyline de salida
                prev = pAux.getY();    									// Actualizamos prev
            }
            sk2.remove(0); 												// Eliminamos el punto de sk2
        }
        return salida;
    }


}