import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;



public class Toit2 {
	public Point l1[] = {new Point(1,10), new Point(5,6), new Point(8,0), new Point(10,8), new Point(12,0)};
	public Point l2[] = {new Point(2,12), new Point(7,0), new Point(9,4), new Point(11,2), new Point(14,0)};

	Im[] listImmeuble;

	public Toit2() {

	}

	public List<Point> fusion(List<Point> l1, List<Point> l2) {
		List<Point> result = new ArrayList<Point>();

		int l1_length = l1.size();
		int l2_length = l2.size();
		int j = 0;
		int i = 0;

		//tant que ligne1 et ligne2 n'ont pas été complétement parcourus tout les 2
		while(i != l1_length || j != l2_length){
			//si un des 2 est fini, alors on rajoute tout le 2eme a la liste des points
			if(i == l1_length && j != l2_length){
				result.add(l2.get(j));
				j++;
			} else if(i != l1_length && j == l2_length){
				result.add(l1.get(i));
				i++;
			}
			//si l1.get(i) est entre l2.get(j) et [j+1] ( et que j+1 existe donc ) ou l1.get(i).x == l2.get(j).x
			else if(j+1 < l2_length && i < l1_length && l2.get(j).x <= l1.get(i).x && l1.get(i).x < l2.get(j+1).x){
				//si la hauteur de l1 est inférieur a l2 on ajoute l2 et incrémente j et i (sans ajouter i)
				if(l1.get(i).y < l2.get(j).y){
					if(j-1 >= 0 &&l2.get(j-1).y > l2.get(j).y){
						//on créer un nouveau point
						result.add(new Point(l1.get(i).x, l2.get(j).y));
					//on ajoute juste l2.get(j)
					} else {
						result.add(l2.get(j));
					}
					j++;
					i++;
				}else if(l2.get(j).y !=0 && l1.get(i).y > l2.get(j).y){
					result.add(l2.get(j));
					result.add(l1.get(i));
					i++;
				}else if(j-1 >= 0){
					//si le point avant j est plus grand alors l2.get(j) vas vers le bas (ligne verticale)
					if(l2.get(j-1).y > l2.get(j).y){
						//ici on sais deja qu'on ajout l1.get(i)
						//on check si on crer un autre point
						if(l1.get(i-1).y > l2.get(j).y){
							result.add(new Point(l2.get(j).x, l1.get(i-1).y));
						}
						result.add(l1.get(i));
						i++;
						j++;

					}else{
						System.out.println(" CAS NON TRAITE ! l1["+i+"] = " + l1.get(i) + " l2.get(j) = "+l2.get(j)+" et l2.get(j+1)= " + l2.get(j+1));
					}
				} else {
					//ici on ajoute l'un des deux, ils sont égaux
					if(l1.get(i).x == l2.get(j).x && l1.get(i).y == l2.get(j).y){
						result.add(l1.get(i));
						i++;
					//si un des deux sont égaux
					}else if(l1.get(i).x == l2.get(j).x || l1.get(i).y == l2.get(j).y){
						result.add(new Point(Math.min(l1.get(i).x,l2.get(j).x),Math.max(l1.get(i).y,l2.get(j).y)));
						i++;
					}
				}
			//si ce n'est pas entre les 2
			}else{
				if(i < l1_length && l1.get(i).x < l2.get(j).x){
					result.add(l1.get(i));
					i++;
				} else if(j + 1 < l2_length && i < l1_length && l1.get(i).x > l2.get(j+1).x){
					j++;
				} else if(j == l2_length-1 && i != l1_length-1){
					result.add(new Point(l2.get(j).x, l1.get(i).y));
					i++;
				//ici on ajoute l'un des deux, ils sont égaux
				} else if(l1.get(i).x == l2.get(j).x && l1.get(i).y == l2.get(j).y){
						result.add(l1.get(i));
						i++;
				//si un des deux sont égaux
				}else if(l1.get(i).x == l2.get(j).x || l1.get(i).y == l2.get(j).y){
						result.add(new Point(Math.min(l1.get(i).x,l2.get(j).x),Math.max(l1.get(i).y,l2.get(j).y)));
						i++;
				} else {
					break;
				}
			}
		}

		return result;
	}

	public List<Point> createRoofline(Im[] listImmeuble){

		if (listImmeuble.length <= 1) {

			List<Point> p = new ArrayList<Point>();
			p.add(new Point(listImmeuble[0].p1));
			p.add(new Point(listImmeuble[0].p2));
            return p;
		}

		Im[] first = new Im[listImmeuble.length / 2];
		Im[] second = new Im[listImmeuble.length - first.length];

	    System.arraycopy(listImmeuble, 0, first, 0, first.length);
	    System.arraycopy(listImmeuble, first.length, second, 0, second.length);

	    return fusion(createRoofline(first), createRoofline(second));

	}

	public static void main (String[] args){
		Toit2 t = new Toit2();

		/*//test
		Point l3[] = {new Point(2,2), new Point(4,0), new Point(5,2), new Point(7,0), new Point(8,2), new Point(10,0)};
		Point l4[] = {new Point(1,3), new Point(11,0), new Point(12,1), new Point(13,0), new Point(14,1), new Point(15,0)};

		Point l5[] = {new Point(1,2), new Point(8,0), new Point(9,2), new Point(10,0)};
		Point l6[] = {new Point(1,3), new Point(4,0), new Point(5,6), new Point(7,0)};

		List<Point> p = t.fusion(t.l1, t.l2);
		System.out.println("WE HAVE : ");
		for(Point point : p){
			System.out.print("(" + point.x + "," + point.y+")");
		}
		System.out.println("\nWE WANT :");
		Point l[] = {new Point(1,10), new Point(2,12), new Point(7,6), new Point(8,0), new Point(9,4), new Point(10,8), new Point(12,2), new Point(14,0)};

		//test
		Point ll[] = {new Point(1,3), new Point(11,0), new Point(12,1), new Point(13,0), new Point(14,1), new Point(15,0)};
		Point lll[] = {new Point(1,3), new Point(4,2), new Point(5,6), new Point(7,2), new Point(8,0), new Point(9,2), new Point(10,0)};
		for(Point point : l){
			System.out.print("(" + point.x + "," + point.y+")");
		}

		System.out.println("\nListe triée : :");

		Point list[] = {new Point(7,0), new Point(14,0), new Point(5,6), new Point(8,0), new Point(2,12), new Point(11,2), new Point(10,8), new Point(12,0), new Point(1,10), new Point(9,4)};
		List<Point> p2 = t.tri(list) ;
		for(Point point : p2){
			System.out.print("(" + point.x + "," + point.y+")");
		}*/

		//notre liste d'immeuble
		Im[] listImmeuble = {new Im(1,10,5,0), new Im(5,6,8,0), new Im(10,8,12,0), new Im(2,12,7,0), new Im(9,4,11,0), new Im(11,2,14,0)};
		List<Point> p100 =t.createRoofline(listImmeuble);

		for(Point point : p100){
			System.out.print("(" + point.x + "," + point.y+")");
		}

		System.out.println("\nWE WANT :");
		Point l[] = {new Point(1,10), new Point(2,12), new Point(7,6), new Point(8,0), new Point(9,4), new Point(10,8), new Point(12,2), new Point(14,0)};
		for(Point point : l){
			System.out.print("(" + point.x + "," + point.y+")");
		}
	}





}