package Q1;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class convexHull
{
    protected List<Position> domain;
    protected int xMax;
    protected int yMax;
    private int points;
    private Position a = new Position(true);
    private Position b = new Position(false);


    convexHull()
    {
        domain = new ArrayList<Position>();
        xMax = 40;
        yMax = 40;
        points = 15;
    }

    private void generatePoints(List<Position> domain)
    {
        for (int i = 0; i < points; i++){
            domain.add(new Position(xMax, yMax));
        }
    }

    private void generateShape(List<Position> a, int xmin, int xmax, int ymin, int ymax)
    {
        for (int i = 0; i < points; i++)
        {
            a.add(new Position(xmin, xmax, ymin, ymax));
            //a.get(i) = new Position(xmin, xmax, ymin, ymax);
        }

    }

    private void printArr(List<Position> domain){
        System.out.print("LIST:");
        for (Position obj : domain)
        {
            System.out.print("("+obj.x + "," + obj.y + ")");
        }
        System.out.println("\n" + "Done");
    }

    private int isLeft(Position a, Position b, Position c)
    {
        if ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) >= 0)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }

    public void sortByX(List<Position> domain){
        Position temp;
        for (int i = 0; i < domain.size()-1; i++){
            for (int j = 0; j < domain.size()-1; j++){
                if (domain.get(j).x > domain.get(j+1).x){
                    temp = domain.get(j);
                    domain.set(j, domain.get(j+1));
                    domain.set(j+1, temp);
                }
            }
        }
    }

    private List<Position> findConvex(List<Position> points){

        if (points.size() < 4){
            formClockwise(points);
            return points;
        }

        else{
            List<Position> L1 = points.subList(0, points.size()/2);
            List<Position> L2 = points.subList(points.size()/2, points.size());
            return merge(L1, L2);
        }

    }

    private List<Position> merge(List<Position> L1, List<Position> L2){
        L1 = findConvex(L1);
        L2 = findConvex(L2);
        boolean go = true;
        int p1 = highlowx(L1, true); //fins inner point for L1
        int p2 = highlowx(L2, false); //find inner point for L2
        int p3 = p2;
        int p4 = p1;
        int runlimit2 = L2.size()-1;
        int runlimit1 = L1.size()-1;
        bridge line = new bridge(p1,p2);
        bridge line2 = new bridge(p1,p2);
        while (0 <= p4 && go)
        {
            while (p3 <= runlimit2)
            {
                if (isLeft(L2.get(line.i2),L1.get(line.i1),L2.get(p3)) == 0 ){ //ahhh
                    line.sp2(p3);
                }
                p3++;
            }
            p4--;
            if (p4 >= 0){
                if (isLeft(L1.get(line.i1),L2.get(line.i2), L1.get(p4)) == 1 ){
                    line.sp1(p4);
                    p3 = p2;
                }
                else{
                    go = false;
                }
            }
        }
        p3 = p2;
        p4 = p1;
        go = true;
        while (0 <= p4 && p4 <= runlimit1 && go){
            while (p3 <= runlimit2){
                if (isLeft(L2.get(line2.i2), L1.get(line2.i1), L2.get(p3)) == 1 ){ //ahhh
                    line2.sp2(p3);
                }
                p3++;
            }
            p4++;
            if (p4 >= 0 && p4 <= runlimit1){
                if (isLeft(L1.get(line2.i1),L2.get(line2.i2), L1.get(p4)) == 0 ){
                    line2.sp1(p4);
                    p3 = p2;
                }
                else{
                    p3 = p2;
                }
        }
        }
        List<Position> merged = new ArrayList<Position>();
        int countback = line.i1;
        int k = 0;
        for (int i = 0; i <= countback; i++){
            merged.add(L1.get(i));
        }
        k = 0;

        for (int i = line.i2; i <= line2.i2; i++){
            k++;
            merged.add(L2.get(i));
        }
        if (k == 0 && line.i2 > line2.i2){
            merged.add(L2.get(line.i2));
            merged.add(L2.get(line2.i2));
        }
        if (line2.i1 != 0){
            for (int i = line2.i1; i <= L1.size()-1; i++){
                merged.add(L1.get(i));
            }
        }

        if (merged.size() == 4 && line2.i1 < line.i1){
            merged.remove(0);
            merged.add(L1.get(line2.i1));
        }
        return merged;
    }

    private int highlowx(List<Position> points2, boolean b){
        int bestindex = 0;
        Iterator<Position> it = points2.iterator();
        Position p;
        int counter = 0;

        if (b){
            while (it.hasNext()){
                p = it.next();
                if (p.x > points2.get(bestindex).x){
                    bestindex = counter;
                }
                counter++;
            }
        }
        else{
            while (it.hasNext()){
                p = it.next();
                if (p.x < points2.get(bestindex).x){
                    bestindex = counter;
                }
                counter++;
            }
        }
        return bestindex;
    }

    private List<Position> formClockwise(List<Position> points)
    {
        Position temp;
        if (points.size() == 2){
            return points;
        }
        else{
            if (isLeft(points.get(1), points.get(0), points.get(2)) == 0){
                temp = points.get(1);
                points.set(1, points.get(2));
                points.set(2, temp);
                return points;
            }
        }
        return points;
    }

    public boolean endcheck()
    {
        int counter = 0;
            for (Position p : domain)
            {
                if (p.x == 40)
                {
                    counter++;
                    break;
                }
        }
        if (counter > 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public boolean endcheck(List<Position> domain, int x1, int y1)
    {
        int counter = 0;
            for (Position p : domain)
            {
                if (p.x == x1 && p.y == y1){
                    counter++;
                    break;
                }
        }
        if (counter > 0){
            return true;
        }
        else {
            return false;
        }
    }

    public void execute(){
        boolean check = false;
        List<Position> domainCopy = new ArrayList<Position>();
        while (check == false)
        {
            generatePoints(domain); //fills domain with points
            domain.add(a); //adds starting point
            domain.add(b); //adds end point
            sortByX(domain); //sorts domain by x
            domainCopy = domain;
            domain = findConvex(domain);
            check = endcheck();
        }
        System.out.println("Sorted by X:");
        printArr(domainCopy);
        System.out.println("Complete Hull:");
        printArr(domain);
    }

    public static void main(String [] args)
    {
        convexHull c = new convexHull();
        c.execute(); //for question 1
    }
}