// CSE 143
// This class provides a binarySearch method for searching a sorted array of ints.
// You do NOT need to use this file unless you have an older Mac and are not able
// to successfully upgrade it to Java v1.6.  We strongly recommend that you try
// upgrading your Java to v1.6 by following the Mac JDK download link on the
// course web site before using this file.
//
// NOTE: Even if you use this file, you will still need to import java.util.*;
// in your SortedIntList program.  If you do not, you may lose points because
// your program may not compile when we run it on our testing server.
//
// author: Stuart Reges, 1/11/08   (minor modifications by Marty Stepp 1/11/09)

public class Arrays {
    static {
        String javaVersion = System.getProperty("java.version");
        if (javaVersion != null && javaVersion.length() >= 3) {
            try {
                double version = Double.parseDouble(javaVersion.substring(0, 3));
                if (version >= 1.6) {
                    throw new RuntimeException("You should not use this Arrays.java file! " +
                            "It is needed only for Java v1.5 or older. " +
                            "Please remove it from your project and recompile.");
                }
            } catch (NumberFormatException nfe) {}
        }
    }
    
    private Arrays() {}  // cannot be instantiated

    // Returns the index of the given key in the list within the given array;
    // returns (-(insertion point) - 1) otherwise.  The insertion point is
    // defined as the point at which the key would be inserted into the
    // array: the index of the first element in the range greater than
    // the key, or toIndex if all elements in the range are less than the
    // specified key.  Note that this guarantees that the return value
    // will be >= 0 if and only if the key is found.  If the list
    // contains multiple copies of the key in the given range, there is
    // no guarantee which index is returned.
    //
    // Precondition: elements are in sorted (nondecreasing) order
    public static int binarySearch(int[] list, int key) {
        return binarySearch(list, 0, list.length, key);
    }
    
    // Returns the index of the given key in the list within the range
    // fromIndex (inclusive) through toIndex (exclusive); returns
    // (-(insertion point) - 1) otherwise.  The insertion point is
    // defined as the point at which the key would be inserted into the
    // array: the index of the first element in the range greater than
    // the key, or toIndex if all elements in the range are less than the
    // specified key.  Note that this guarantees that the return value
    // will be >= 0 if and only if the key is found.  If the list
    // contains multiple copies of the key in the given range, there is
    // no guarantee which index is returned.
    //
    // Precondition: elements in indexes fromIndex (inclusive)
    // to toIndex (exclusive) are in sorted (nondecreasing) order
    public static int binarySearch(int[] list, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
    
        while (low <= high) {
            int mid = (low + high) / 2;
            int midVal = list[mid];
    
            if (midVal < key) {
                low = mid + 1;
            } else if (midVal > key) {
                high = mid - 1;
            } else {
                return mid;  // key found
            }
        }
        return -(low + 1);   // key not found
    }

    // Returns a resized copy of the given array with the given new length.
    public static int[] copyOf(int[] list, int length) {
        int[] list2 = new int[length];
        System.arraycopy(list, 0, list2, 0, Math.min(length, list.length));
        return list2;
    }

    // Returns a resized copy of the given array with the given new length.
    @SuppressWarnings("unchecked")
    public static <T> T[] copyOf(T[] list, int length) {
        T[] list2 = (T[]) (new Object[length]);
        System.arraycopy(list, 0, list2, 0, Math.min(length, list.length));
        return list2;
    }
    
    // Sets each element in the given array to store the given value.
    public static void fill(int[] list, int value) {
        for (int i = 0; i < list.length; i++) {
            list[i] = value;
        }
    }

    // Returns a String representation of the given array.
    public static String toString(int[] elements) {
        return java.util.Arrays.toString(elements);
    }
    
    // Returns a String representation of the given array.
    public static <T> String toString(T[] elements) {
        return java.util.Arrays.toString(elements);
    }
    
    // Returns true if the given two arrays contain the same elements.
    public static boolean equals(int[] a1, int[] a2) {
        return java.util.Arrays.equals(a1, a2);
    }
    
    // Returns true if the given two arrays contain the same elements.
    public static <T> boolean equals(T[] a1, T[] a2) {
        return java.util.Arrays.equals(a1, a2);
    }
}