package SortTest;

import java.util.Arrays;

public class Search {
	private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException(
                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException(fromIndex);
        }
        if (toIndex > arrayLength) {
            throw new ArrayIndexOutOfBoundsException(toIndex);
        }
    }
	
    public static int biasedBSearch(double[] a, double key) {
        //System.out.println(key);
        return biasedBSearch0(a, 0, a.length, key);
    }

    public static int biasedBSearch(double[] a, int fromIndex, int toIndex,
                                   double key) {
        rangeCheck(a.length, fromIndex, toIndex);
        return biasedBSearch0(a, fromIndex, toIndex, key);
    }

    // Like public version, but without range checks.
    private static int biasedBSearch0(double[] a, int fromIndex, int toIndex,
                                     double key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (3*low + high) >>> 2;
            double midVal = a[mid];

            if (midVal < key)
                low = mid + 1;  // Neither val is NaN, thisVal is smaller
            else if (midVal > key)
                high = mid - 1; // Neither val is NaN, thisVal is larger
            else {
                long midBits = Double.doubleToLongBits(midVal);
                long keyBits = Double.doubleToLongBits(key);
                if (midBits == keyBits)     // Values are equal
                    return mid;             // Key found
                else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
                    low = mid + 1;
                else                        // (0.0, -0.0) or (NaN, !NaN)
                    high = mid - 1;
            }
        }
        return -(low + 1);  // key not found.
    }



	public static int skewSearch(double[] a, double key) {
        return skewSearch0(a, 0, a.length, key);
    }

    public static int skewSearch(double[] a, int fromIndex, int toIndex,
                                   double key) {
        rangeCheck(a.length, fromIndex, toIndex);
        return skewSearch0(a, fromIndex, toIndex, key);
    }
    

    // Like public version, but without range checks.
    private static int skewSearch0(double[] a, int fromIndex, int toIndex,
                                     double key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
        	int mid = (3*low + high) >>> 2;
            double midVal = a[mid];

            if (midVal > key)
                high = mid-1;  // Neither val is NaN, thisVal is smaller
            else{
	            int mid2 = (mid + high) >>> 1;
	            double mid2Val = a[mid2];
	
	            if (mid2Val < key)
	                low = mid2 + 1;  // Neither val is NaN, thisVal is smaller
	            else if (mid2Val > key){
	            	low = mid;
	                high = mid2 - 1; // Neither val is NaN, thisVal is larger
	            }
	            else {
	                long mid2Bits = Double.doubleToLongBits(mid2Val);
	                long keyBits = Double.doubleToLongBits(key);
	                if (mid2Bits == keyBits)     // Values are equal
	                    return mid2;             // Key found
	                else if (mid2Bits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
	                    low = mid2 + 1;
	                else{                        // (0.0, -0.0) or (NaN, !NaN)
	                	low = mid;
	                	high = mid2 - 1;
	                }
	            }
            }
        }
        return -(low + 1);  // key not found.
    }
    
    public static int bSearch(double[] a, double key) {
    	//System.out.println(key);
        return bSearch0(a, 0, a.length, key);
    }

    public static int bSearch(double[] a, int fromIndex, int toIndex,
                                   double key) {
        rangeCheck(a.length, fromIndex, toIndex);
        return bSearch0(a, fromIndex, toIndex, key);
    }

    // Like public version, but without range checks.
    private static int bSearch0(double[] a, int fromIndex, int toIndex,
                                     double key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            double midVal = a[mid];

            if (midVal < key)
                low = mid + 1;  // Neither val is NaN, thisVal is smaller
            else if (midVal > key)
                high = mid - 1; // Neither val is NaN, thisVal is larger
            else {
                long midBits = Double.doubleToLongBits(midVal);
                long keyBits = Double.doubleToLongBits(key);
                if (midBits == keyBits)     // Values are equal
                    return mid;             // Key found
                else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
                    low = mid + 1;
                else                        // (0.0, -0.0) or (NaN, !NaN)
                    high = mid - 1;
            }
        }
        return -(low + 1);  // key not found.
    }


    public static int superSkewSearch(double[] a, double key) {
        return superSkewSearch0(a, 0, a.length, key);
    }

    public static int superSkewSearch(double[] a, int fromIndex, int toIndex,
                                   double key) {
        rangeCheck(a.length, fromIndex, toIndex);
        return superSkewSearch0(a, fromIndex, toIndex, key);
    }
    

    // Like public version, but without range checks.
    private static int superSkewSearch0(double[] a, int fromIndex, int toIndex,
                                     double key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (3*low + high) >>> 2;
            double midVal = a[mid];

            if (midVal > key)
                high = mid-1;  // Neither val is NaN, thisVal is smaller
            else{
                int mid2 = (low + high) >>> 1;
                double mid2Val = a[mid2];
    
                if (mid2Val < key)
                    low = mid2 + 1;  // Neither val is NaN, thisVal is smaller
                else if (mid2Val > key){
                    low = mid;
                    high = mid2 - 1; // Neither val is NaN, thisVal is larger
                }
                else {
                    long mid2Bits = Double.doubleToLongBits(mid2Val);
                    long keyBits = Double.doubleToLongBits(key);
                    if (mid2Bits == keyBits)     // Values are equal
                        return mid2;             // Key found
                    else if (mid2Bits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
                        low = mid2 + 1;
                    else{                        // (0.0, -0.0) or (NaN, !NaN)
                        low = mid;
                        high = mid2 - 1;
                    }
                }
            }
        }
        return -(low + 1);  // key not found.
    }
}