package pgdp.arrays;

public class ProbabilisticSearch extends MiniJava {
    /**
     * Binary Search aus der Vorlesung leicht abgewandelt
     */
    public static int[] find(int[] a, int x) {
        return find0(a, x, 0, a.length - 1, 1);
    }

    public static int[] find0(int[] a, int x, int n1, int n2, int numberOfSteps) {
        int t = (n1 + n2) / 2;
        if (a[t] == x)
            return new int[]{t, numberOfSteps};
        else if (n1 >= n2)
            return new int[]{-1, numberOfSteps};
        else if (x > a[t])
            return find0(a, x, t + 1, n2, numberOfSteps + 1);
        else if (n1 < t)
            return find0(a, x, n1, t - 1, numberOfSteps + 1);
        else return new int[]{-1, numberOfSteps};
    }

    public static int[] probalisticSearch(int[] arr, int value) {
        return probalisticSearch0(arr, value, 0, arr.length - 1, 1);
    }

    public static int[] probalisticSearch0(int[] a, int x, int min, int max, int numberOfSteps) {
        int t = calculatePosition(a, x, min, max);

        if (a[t] == x)
            return new int[]{t, numberOfSteps};
        if (a[t] > x) {
            if (a[t - (int) Math.pow(2, numberOfSteps - 1)] < x) {
                if (a[t - (int) Math.pow(2, numberOfSteps - 1)+1] >= x)
                    return find0(a, x, t - (int) Math.pow(2, numberOfSteps - 1), max, numberOfSteps + 1);
                else {
                    numberOfSteps++;
                }
            } else {
                return probalisticSearch0(a, x, min, t - (int) Math.pow(2, numberOfSteps - 1), numberOfSteps + 1);
            }
        }
//        if(a[t] < x)
//            return find0(a, x, t, max, numberOfSteps+1);
        return new int[]{-1, numberOfSteps};
    }

    private static int calculatePosition(int[] a, int x, int min, int max) {
        int position;
        double outcome, denominatorTop, denominatorBottom, numerator;

        numerator = x - a[min];
        denominatorTop = a[max] - a[min];
        denominatorBottom = max;

        outcome = (numerator / ((denominatorTop) / (denominatorBottom)));
        position = (int) Math.round(outcome);

        return position;
    }

//    public static int[] probalisticSearch(int[] arr, int value) {
//        //int position = probSearch(arr, value);
//        int steps = 1, a = 0;
//
//        if (arr[position] == value) {
//            return new int[]{position, steps};
//        }
//        if (arr[position] > value) {
//            for (int i = 0; i < arr.length; i++) {
//                a = 2 ^ i;
//                steps++;
//                if (arr[position - a] == value) {
//                    return new int[]{position - a, steps};
//                } else if (arr[position - a] < value) {
//
//                }
//            }
//        }
//        if (arr[position] < value) {
//
//        }
//        return new int[]{};
//    }

    public static void compareApproaches(int[] arr, int min, int max) {
        // TODO
    }

    public static void main(String[] args) {
        // Not part of the exercise but can be helpful for debugging purposes
        int[] exampleArray = new int[]{6, 20, 22, 35, 51, 54, 59, 74, 77, 80, 87, 94, 97};

        int[] result = probalisticSearch(exampleArray, 22);
        write(result[0] + ", " + result[1]);
    }
}