package sort;

/** A class to represent a set of buckets, used in bucket and other sorts. */
public class Buckets {

    // The number of buckets in this.
    private int numBuckets;

    // The number of elements in this.
    private int size;

    // The underlying storage for this.
    private IntVector[] buckets;

    // The mapping from elements to buckets.
    private Bucketizer bucketizer;

    /** Creates a <b><tt>Buckets</b></tt> object with the given number of 
     *  buckets and the given mapping from elements to buckets. The mapping 
     *  should have a range of {0, ... , <b><tt>num</b></tt> - 1}. Any value 
     *  returned outside of this range will be mapped into this range by 
     *  taking its modulus with <b><tt>num</b></tt>.
     *  @param num the number of buckets
     *  @param bz the mapping from elements to buckets
     */
    public Buckets(int num, Bucketizer bz) {
	buckets = new IntVector[num];
	for (int i = 0; i < buckets.length; i++) {
	    buckets[i] = new IntVector();
	}
	size = 0;
	bucketizer = bz;
	numBuckets = num;
    }

    /** Inserts the given element into <b><tt>this</b></tt> in the 
     *  appropriate bucket.
     *  @param x the element to insert
     */
    public void addElement(int x) {
	int pos = bucketizer.getPos(x) % numBuckets;
	buckets[pos].addElement(x);
	size++;
    }

    /** Inserts elements from an array into <b><tt>this</b></tt> in the 
     *  appropriate buckets.
     *  @param nums the element from which to insert elements
     *  @param offset the position from which to start inserting
     *  @param length the number of elements to insert
     */
    public void addAll(int[] nums, int offset, int length) {
	int tmp[] = new int[length]; // why? to speed up global adding
	System.arraycopy(nums, offset, tmp, 0, length);
	for (int i = 0; i < length; i++) {
	    addElement(tmp[i]);
	}
    }

    /** Clears <b><tt>this</b></tt> of all elements. */
    public void clear() {
	for (int i = 0; i < buckets.length; i++) {
	    buckets[i].clear();
	}
	size = 0;
    }

    /** Returns the number of elements in <b><tt>this</b></tt>.
     *  @return the number of elements in <b><tt>this</b></tt>
     */
    public int size() {
	return size;
    }

    /** Adds all elements from the given <b><tt>Buckets</b></tt> to 
     *  <b><tt>this</b></tt>.
     *  @param bucks the <b><tt>Buckets</b></tt> from which to insert elements
     */
    public void combine(Buckets bucks) {
	for (int i = 0; i < buckets.length; i++) {
	    buckets[i].concat(bucks.buckets[i]);
	}
	size += bucks.size;
    }

    /** Copies all elements from <b><tt>this</b></tt> into the target array. 
     *  The target array must be of sufficient size. Copying starts at 
     *  index 0. The order of the elements in the destination array is as
     *  follows:
     *  <ul>
     *  <li> for elements <i>x</i> and <i>y</i> in buckets <i>i</i> and
     *  <i>j</i>, respectively, the position of <i>x</i> is less than
     *  the position of <i>y</i> if <i>i</i> < <i>j</i>
     *  <li> for elements <i>x</i> and <i>y</i> in the same bucket, the
     *  position of <i>x</i> is less than the position of <i>y</i> iff
     *  the position of <i>x</i> in the bucket is less than the position
     *  of <i>y</i> in the bucket
     *  </ul>
     *  @param target the destination array
     *  @return the number of elements copied
     */
    public int copyElements(int[] target) {
	int offset = 0;
	for (int i = 0; i < buckets.length; i++) {
	    offset += buckets[i].copyElements(target, offset);
	}
	return offset;
    }

    /** Copies elements from the given bucket into the target array.
     *  This call has the same effect as (though is faster than) the
     *  call <b><tt>getBucket(bucket).copyElements(target, offset)</b>
     *  </tt>.
     *  @param bucket the bucket to copy elements from
     *  @param target the array to copy elements into
     *  @param offset the position at which to start copying elements
     *  @return the number of elements copied
     */
    public int copyBucket(int bucket, int[] target, int offset) {
	return buckets[bucket].copyElements(target, offset);
    }

    /** Returns a copy of the given bucket.
     *  @param bucket the bucket to be retrieved
     *  @return a copy of the retrieved bucket
     */
    public IntVector getBucket(int bucket) {
	return (IntVector) buckets[bucket].clone();
    }

    /** Prints the elements in <b><tt>this</b></tt> to the given 
     *  <b><tt>PrintStream</b></tt>, one per line.
     *  @param ps the target <b><tt>PrintStream</b></tt>
     */
    protected void print(java.io.PrintStream ps) {
	ps.println("====== Buckets: " + buckets.length + " buckets, " +
		   size + " elements ======");
	for (int i = 0; i < buckets.length; i++) {
	    ps.println("bucket " + i + ":");
	    buckets[i].print(ps);
	}
	ps.println("========================");
    }

    /** Tests this class */
    protected static boolean test() {
	System.out.println("Testing Buckets...");
	boolean res = insertTest();
	res &= combineTest();
	res &= copyTest();
	if (res) {
	    System.out.println("Buckets tests passed.");
	} else {
	    System.out.println("Buckets tests failed!");
	}
	return res;
    }

    // Tests the insertion methods of this class.
    private static boolean insertTest() {
	System.out.println("=> running insertion tests...");
	int[] nums = new int[1000];
	int res;
	Buckets bucks = new Buckets(40, new RadixBucketizer(5));
	for (int i = 0; i < nums.length; i++) {
	    nums[i] = Util.random(Integer.MAX_VALUE);
	    bucks.addElement(nums[i]);
	}
	if ((res = insertTestHelper(nums, 0, nums.length, 
				    bucks)) != 0) {
	    return fail("insert tests (#" + res + ")");
	}
	bucks.clear();
	if (bucks.size() != 0) {
	    return fail("insert tests (#4)");
	}
	bucks.addAll(nums, 100, nums.length / 2 - 100);
	if ((res = insertTestHelper(nums, 100, nums.length / 2 - 100,
				    bucks)) != 0) {
	    return fail("insert tests (#" + (res + 4) + ")");
	}
	System.out.println("=> insertion tests passed.");
	return true;
    }

    // Helper method for insertTest(). Tests if the given array elements
    // were correctly inserted into the destination. Does not individually
    // test if each element was inserted into the proper bucket, but does
    // test that each bucket is of the expected size. The return value is
    // 0 for a successful test, nonzero otherwise.
    private static int insertTestHelper(int[] src, int off, int len,
					Buckets dst) {
	int[] nums1, nums2, counts;
	int start;
	nums1 = new int[len];
	nums2 = new int[len];
	System.arraycopy(src, off, nums1, 0, len);
	start = 0;
	for (int i = 0; i < dst.numBuckets; i++) {
	    start += dst.buckets[i].copyElements(nums2, start);
	}
	if (dst.size() != len || start != dst.size()) {
	    return 1;
	}
	Util.sort(nums1);
	Util.sort(nums2);
	if (!Util.compare(nums1, 0, nums2, 0, nums1.length)) {
	    return 2;
	}
	counts = new int[dst.numBuckets];
	for (int i = 0; i < len; i++) {
	    counts[dst.bucketizer.getPos(src[off + i])]++;
	}
	for (int i = 0; i < counts.length; i++) {
	    if (counts[i] != dst.buckets[i].size()) {
		return 3;
	    }
	}
	return 0;
    }

    // Tests the combine method of this class.
    private static boolean combineTest() {
	System.out.println("=> running combine tests...");
	int[] nums = new int[2000];
	Buckets b1, b2;
	int res;
	for (int i = 0; i < nums.length; i++) {
	    nums[i] = Util.random(Integer.MAX_VALUE);
	}
	b1 = new Buckets(64, new RadixBucketizer(6));
	b2 = new Buckets(64, new RadixBucketizer(6));
	b1.addAll(nums, 0, nums.length / 2);
	b2.addAll(nums, nums.length / 2, nums.length - nums.length / 2);
	b1.combine(b2);
	if ((res = insertTestHelper(nums, 0, nums.length, b1)) != 0) {
	    return fail("combine tests (#" + res + ")");
	} else if ((res = insertTestHelper(nums, nums.length / 2,
					   nums.length - nums.length / 2,
					   b2)) != 0) {
	    return fail("combine tests (#" + (res + 3) + ")");
	}
	b1.clear();
	b2.clear();
	b1.addAll(nums, 0, nums.length / 2);
	b2.addAll(nums, nums.length / 2, nums.length - nums.length / 2);
	b2.combine(b1);
	if ((res = insertTestHelper(nums, 0, nums.length, b2)) != 0) {
	    return fail("combine tests (#" + (res + 6) + ")");
	} else if ((res = insertTestHelper(nums, 0, nums.length / 2,
					   b1)) != 0) {
	    return fail("combine tests (#" + (res + 9) + ")");
	}
	System.out.println("=> combine tests passed.");
	return true;
    }

    // Tests the copy methods of this class. (Does not test if elements in
    // each bucket retain original relative order.)
    private static boolean copyTest() {
	System.out.println("=> running copy tests...");
	int[] nums = new int[1000];
	int[] dst = new int[nums.length];
	int[] sorted = new int[dst.length];
	int crntBucket, nextBucket;
	RadixBucketizer rb = new RadixBucketizer(4);
	Buckets bucks = new Buckets(16, rb);
	for (int i = 0; i < nums.length; i++) {
	    nums[i] = Util.random(Integer.MAX_VALUE);
	}
	bucks.addAll(nums, 0, nums.length);
	bucks.copyElements(dst);
	System.arraycopy(dst, 0, sorted, 0, nums.length);
	Util.sort(nums);
	Util.sort(sorted);
	if (!Util.compare(nums, 0, sorted, 0, nums.length)) {
	    return fail("copy tests (#1)");
	}
	crntBucket = 0;
	// Test if buckets are contiguous and in correct order.
	for (int i = 0; i < nums.length; i++) {
	    if ((nextBucket = rb.getPos(dst[i])) - crntBucket < 0) {
		return fail("copy tests (#2)");
	    }
	    nextBucket = crntBucket;
	}
	System.out.println("=> copy tests passed.");
	return true;
    }

    // Prints an error message and returns false.
    private static boolean fail(String msg) {
	System.out.println("Error in Buckets: " + msg + " failed.");
	return false;
    }

}