package sort;

/** Maps elements to buckets according to splitters. */
public class SplitBucketizer implements Bucketizer {

    // The splitters to use in computing which bucket an element goes into.
    private int[] splitters;

    /** Creates a <b><tt>SplitBucketizer</b></tt> that uses the given 
     *  splitters. The splitters must be in sorted order, otherwise
     *  behavior is undefined.
     *  @param splitters the splitters to use
     */
    public SplitBucketizer(int[] splitters) {
	this.splitters = splitters;
    }

    /** Computes the bucket into which the given element should be placed. */
    public int getPos(int x) {
	if (splitters.length == 0 || x > splitters[splitters.length - 1]) {
	    return splitters.length;
	} else {
	    int low = 0, high = splitters.length - 1;
	    int mid = 0;
	    while (low < high) {
		mid = (low + high) / 2;
		if (splitters[mid] > x) {
		    high = mid;
		} else {
		    low = mid + 1;
		}
	    }
	    return low;
	}
    }

    /** Tests this class. */
    protected static boolean test() {
	System.out.println("Running SplitBucketizer tests...");
	int[] nums = new int[1000];
	int[] splitters = new int[nums.length / 100];
	int pos;
	SplitBucketizer sb;
	for (int i = 0; i < nums.length; i++) {
	    nums[i] = Util.random(Integer.MAX_VALUE);
	}
	for (int i = 0; i < splitters.length; i++) {
	    splitters[i] = nums[Util.random(nums.length)];
	}
	Util.sort(splitters);
	sb = new SplitBucketizer(splitters);
	for (int i = 0; i < nums.length; i++) {
	    pos = sb.getPos(nums[i]);
	    if (pos < 0 || pos > splitters.length) {
		return fail(1, nums[i], pos, splitters);
	    }
	    if (pos != 0 && nums[i] < splitters[pos - 1]) {
		return fail(2, nums[i], pos, splitters);
	    } if (pos != splitters.length && 
		  nums[i] > splitters[pos]) {
		return fail(3, nums[i], pos, splitters);
	    }
	}
	System.out.println("SplitBucketizer tests passed.");
	return true;
    }

    // Prints an error message and returns false.
    private static boolean fail(int id, int num, int pos, 
				int[] splitters) {
	System.out.println("SplitBucketizer tests " + "(#" + id + 
			   ") (" + Util.toHexString(num) + ", " + pos +
			   ", " + Util.toHexString(splitters) + 
			   " failed!");
	return false;
    }
}