package sort;

/** A growable class for storing <b><tt>int</b></tt>s. */
public class IntVector implements Cloneable {

    // The underlying storage for this.
    private int[] elems;

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

    /** Creates an <b><tt>IntVector</b></tt> with the given initial 
     *  capacity. 
     *  @param capacity the initial capacity of <b><tt>this</b></tt> 
     */
    public IntVector(int capacity) {
	this.elems = new int[capacity];
	this.size = 0;
    }

    /** Creates an <b><tt>IntVector</b></tt> with the given array and size.
     *  <br><b>WARNING</b>: This does not copy the given array but uses it
     *  directly, so the internal data is left unprotected. Use carefully.
     *  @param nums the array to use as the underlying array of 
     *  <b><tt>this</b></tt>
     *  @param size the initial size (not capacity) of <b><tt>this</b></tt>
     */
    protected IntVector(int[] nums, int size) {
	this.elems = nums;
	this.size = size;
    }

    /** Creates an <b><tt>IntVector</b></tt> with the default capacity 
     *  (10). 
     */
    public IntVector() {
	this(10);
    }

    /** Adds the given element to the end of <b><tt>this</b></tt>.
     *  @param the element to insert into <b><tt>this</b></tt>
     */
    public void addElement(int x) {
	if (size >= elems.length) {
	    doubleCapacity();
	    addElement(x);
	} else {
	    elems[size++] = x;
	}
    }

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

    /** Adds elements from the given array to the end of 
     *  <b><tt>this</b></tt>, in order.
     *  @param nums the array 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) {
	while (elems.length - size < length) {
	    doubleCapacity();
	}
	System.arraycopy(nums, offset, elems, size, length);
	size += length;
    }

    // Doubles the capacity of this (linear operation)
    private void doubleCapacity() {
	int[] tmp = new int[elems.length * 2 + 1];
	System.arraycopy(elems, 0, tmp, 0, elems.length);
	elems = tmp;
    }

    /** Adds all elements in the given <b><tt>IntVector</b></tt> to 
     *  <b><tt>this</b></tt>.
     *  @param iv the <b><tt>IntVector</b></tt> from which to insert elements
     */
    public void concat(IntVector iv) {
	if (size + iv.size > elems.length) {
	    int[] tmp = new int[2 * (size + iv.size) + 1];
	    System.arraycopy(elems, 0, tmp, 0, size);
	    System.arraycopy(iv.elems, 0, tmp, size, iv.size);
	    elems = tmp;
	} else {
	    System.arraycopy(iv.elems, 0, elems, size, iv.size);
	}
	size += iv.size;
    }

    /** Clears <b><tt>this</b></tt> of any elements. */
    public void clear() {
	size = 0;
    }

    /** Copies as many elements as can fit from <b><tt>this</b></tt> into
     *  the target array.
     *  @param target the array to copy elements into
     *  @param offset the position in the destination at which to start 
     *  	copying
     *  @return the number of elements copied
     */
    public int copyElements(int[] target, int offset) {
	int num = Math.min(size, target.length - offset);
	System.arraycopy(elems, 0, target, offset, num);
	return num;
    }

    /** Creates a deep copy of <b><tt>this</b></tt>.
     *  @return a deep copy of <b><tt>this</b></tt>
     */
    public Object clone() {
	IntVector iv = new IntVector(elems.length);
	System.arraycopy(elems, 0, iv.elems, 0, size);
	iv.size = size;
	return iv;
    }

    /** Tests if <b><tt>this</b></tt> is equal to the given 
     *  <b><tt>Object</b></tt>.
     *  @param obj the <b><tt>Object</b></tt> to compare <b><tt>this</b></tt>
     *  	to
     *  @return whether or not <b><tt>this</b></tt> is equal to the argument
     */
    public boolean equals(Object obj) {
	if (obj instanceof IntVector) {
	    IntVector iv = (IntVector) obj;
	    return iv.size() == size() && 
		Util.compare(iv.elems, 0, elems, 0, size());
	} else {
	    return false;
	}
    }

    /** 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("------ IntVector: " + size + " elements ------");
	for (int i = 0; i < size; i++) {
	    ps.println(elems[i]);
	}
	ps.println("------------------------");
    }

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

    // Tests the insertion methods of this class.
    private static boolean insertTest() {
	System.out.println("=> running insert tests...");
	int[] nums = new int[1000];
	int[] nums2 = new int[nums.length];
	int off, len;
	IntVector iv = new IntVector();
	for (int i = 0; i < nums.length; i++) {
	    nums[i] = Util.random();
	    nums2[i] = Util.random();
	    iv.addElement(nums[i]);
	}
	if (iv.size() != nums.length || 
	    !Util.compare(nums, 0, iv.elems, 0, nums.length)) {
	}
	iv.clear();
	if (iv.size() != 0) {
	    return fail("insert tests (#1)");
	}
	iv.addAll(nums2, 0, nums2.length);
	if (iv.size() != nums2.length || 
	    !Util.compare(nums2, 0, iv.elems, 0, nums2.length)) {
	    return fail("insert tests (#2)");
	}
	iv.clear();
	off = 24;
	len = nums.length - off - nums.length / 3;
	iv.addAll(nums, off, len);
	if (iv.size() != len ||
	    !Util.compare(nums, off, iv.elems, 0, len)) {
	    return fail("insert tests (#3)");
	}
	System.out.println("=> insert tests passed.");
	return true;
    }

    // Tests the concatenation method of this class.
    private static boolean concatTest() {
	System.out.println("=> running concat tests...");
	int[] nums = new int[1000];
	int off2 = nums.length / 2;
	int len2 = nums.length - nums.length / 2;
	IntVector iv, iv2;
	for (int i = 0; i < nums.length; i++) {
	    nums[i] = Util.random();
	}
	iv = new IntVector();
	iv.addAll(nums, 0, off2);
	iv2 = new IntVector();
	iv2.addAll(nums, off2, len2);
	iv.concat(iv2);
	if (iv2.size() != len2 || iv.size() != nums.length || 
	    !Util.compare(nums, 0, iv.elems, 0, nums.length)) {
	    return fail("concat tests (#1)");
	}
	iv = new IntVector();
	iv.addAll(nums, 0, off2);
	iv2 = new IntVector();
	iv2.addAll(nums, off2, len2);
	iv2.concat(iv);
	if (iv.size() != off2 || iv2.size() != nums.length || 
	    !Util.compare(nums, off2, iv2.elems, 0, len2) || 
	    !Util.compare(nums, 0, iv2.elems, len2, off2)) {
	    return fail("concat tests (#2)");
	}
	System.out.println("=> concat tests passed.");
	return true;
    }

    // Tests the clone method of this class.
    private static boolean cloneTest() {
	System.out.println("=> running clone tests...");
	IntVector iv = new IntVector(), iv2;
	int num = 1000;
	for (int i = 0; i < num; i++) {
	    iv.addElement(Util.random());
	}
	iv2 = (IntVector) iv.clone();
	if (iv == iv2 || iv.elems == iv2.elems || !iv.equals(iv2)) {
	    return fail("clone tests (#1)");
	}
	System.out.println("=> clone tests passed.");
	return true;
    }

    // Tests the element copy method of this class.
    private static boolean copyTest() {
	System.out.println("=> running copy tests...");
	int num = 1000, x;
	int[] nums;
	IntVector iv = new IntVector();
	for (int i = 0; i < num; i++) {
	    iv.addElement(Util.random());
	}
	nums = new int[iv.size()];
	x = iv.copyElements(nums, 0);
	if (x != iv.size() || 
	    !Util.compare(nums, 0, iv.elems, 0, iv.size())) {
	    return fail("copy tests (#1)");
	}
	x = iv.copyElements(nums, nums.length - 100);
	if (x != 100 ||
	    !Util.compare(iv.elems, 0, nums, nums.length - 100, 
			  100)) {
	    return fail("copy tests (#2)");
	}
	nums = new int[100];
	x = iv.copyElements(nums, 0);
	if (x != 100 ||
	    !Util.compare(nums, 0, iv.elems, 0, 100)) {
	    return fail("copy tests (#3)");
	}
	x = iv.copyElements(nums, nums.length - 50);
	if (x != 50 ||
	    !Util.compare(iv.elems, 0, nums, nums.length - 50, 
			  50)) {
	    return fail("copy tests (#4)");
	}
	nums = new int[2 * iv.size()];
	x = iv.copyElements(nums, 0);
	if (x != iv.size() || 
	    !Util.compare(nums, 0, iv.elems, 0, iv.size())) {
	    return fail("copy tests (#5)");
	}
	x = iv.copyElements(nums, nums.length - 100);
	if (x != 100 ||
	    !Util.compare(iv.elems, 0, nums, nums.length - 100, 
			  100)) {
	    return fail("copy tests (#6)");
	}
	System.out.println("=> copy tests passed.");
	return true;
    }

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

}