import java.util.Arrays;

public class ArrayUtils {

    public static void main(String[] args) {

        double EPSILON = 0.001;

        // Testing average
        double[] values1 = {1,2,3,4,5};
        assert Math.abs(average(values1) - 3) < EPSILON: "test average(values1)";

        // Testing stdDeviation
        assert Math.abs(stdDeviation(values1) - Math.sqrt(2.5)) < EPSILON: "test stdDeviation(values1)";

        // Testing removeDuplicates
        int[] values2 = {1,1,1,2,2,3,2,3,2,1};
        int[] valuesNub = {1,2,3};
        assert Arrays.equals(removeDuplicates(values2) , valuesNub): "test removeDuplicates(values2)";

        // Testing binarySearch
        int[] values3 = {0,1,1,2,3,3,3,3,5,7,8,9,9,11,15};
        assert binarySearch(values3, 2) == true: "test binarySearch(values2, 2)";
        assert binarySearch(values3, 4) == false: "test binarySearch(values2, 4)";
    }

    public static double sum(double[] values) {

        int result = 0;
        for (double value : values) {
            result += value;
        }
        return result;

    }

    // Computes the average of an array of doubles
    // Precondition: values.length > 0
    public static double average(double[] values) {

        double theSum = sum(values);

        return theSum/values.length;
    }

    // Computes the standard deviation of an array
    // Precondition: values.length > 1
    public static double stdDeviation(double[] values) {

        double avg = average(values);

        double result = 0;
        for (double value : values) {
            result = result + Math.pow((value-avg), 2);
        }

        return Math.sqrt(result / (values.length - 1));
    }

    static boolean search(int[] list, int x) {
        boolean found = false;
        for (int element : list) {
            if (element == x) {
                found = true;
            }
        }
        return found;
    }

    public static boolean haveSeenAlready(int x, int[] values, int i) {
        for (int j = 0; j < i; j++) {
            if (x == values[j]) {
                return true;
            }
        }
        return false;
    }

    public static int nbDifferentElements(int[] values) {

        int count = 0;

        for (int i = 0; i < values.length; i++) {

            if ( !haveSeenAlready(values[i], values, i) ) {
                count++;
            }

        }

        return count;

    }

    // Constructs a new array which contains the same elements
    // as the given array but with the duplicates removed
    // Precondition: values != null
    public static int[] removeDuplicates(int[] values) {

        int[] valuesNoDup = new int[nbDifferentElements(values)];

        int counter = 0;

        for (int i = 0; i < values.length; i++) {
            if (!haveSeenAlready(values[i], values, i)) {
                valuesNoDup[counter] = values[i];
                counter++;
            }
        }

        return valuesNoDup; // TODO
    }

    // Returns true if x is in the list of values, and false
    // otherwise
    // Precondition: values != null, values is sorted
    public static boolean binarySearch(int[] values, int x) {

        int start = 0;
        int end = values.length-1;

        boolean found = false;

        while (!found) {

            if (end - start <= 1) {
                return (values[start] == x || values[end] == x);
            }

            int i = (start + end)/2;
            if (values[i] == x) {
                found = true;
            } else if (values[i] < x) {
                // x is somewhere between start and i
                start = i;
            } else {
                // x is somewhere between i and end
                end = i;
            }

        }

        return found;
    }


}