import structure5.*;
import java.util.Iterator;

public class OrderedVector<T extends Comparable<T>> extends AbstractStructure<T> implements OrderedStructure<T> {
    protected Vector<T> v;

    public OrderedVector() 
    {
        v = new Vector<T>();
    }

    public Iterator<T> iterator() {
        return v.iterator();
    }

    /**
     * Locate a value in the current vector.  If the vector
     * does not contain the value, the method returns the
     * location where the value _should_ be.
     * This is *almost* the same binary search algorithm
     * we looked at earlier.
     * pre: value is not null.
     * post: ideal location of value in vector.
     */
    protected int locate(T value) {
        int lo  = 0;
        int hi  = v.size() - 1;
        return searchHelper(value, lo, hi);
    }

    private int searchHelper(T elem, int lo, int hi) {
        // base case #1: not found; return where it *should* be
        if (lo > hi) {
            return lo;
        }

        // calculate the midpoint
        int mid = (hi - lo) / 2 + lo;

        // is the midpoint the element we are looking for?
        int cmp = elem.compareTo(v.get(mid)); // do a comparison

        // base case #2: found
        if (cmp == 0) {
            return mid;
        // recursive case #1: elem is to the left of mid
        } else if (cmp < 0) {
            return searchHelper(elem, lo, mid - 1);
        // recursive case #2: elem is to the right of mid
        } else {
            return searchHelper(elem, mid + 1, hi);
        }
    }
    
    /**
     * Inserts value.
     * pre: value is not null.
     * post: inserts a value, leaving Vector v in order.
     */
    public void add(T value) {
        // use magic locate method
        int pos = locate(value);
        // now that we know where it should go, insert it
        v.add(pos, value);
    }

    /**
     * Check that structure contains value.
     * pre: value is not null.
     * post: returns true iff structure contains value.
     */
    public boolean contains(T value) {
        int pos = locate(value);
        return (pos < size()) &&
            v.get(pos).equals(value);
    }
    
    /**
     * Removes value.
     * pre: value is not null and Vector actually contains v.
     * post: removes instance of a value, leaving Vector v in order.
     */
    public T remove(T value) {
        if (contains(value)) {
            int pos = locate(value);
            T found = v.get(pos);
            v.remove(pos);
            return found;
        }
        return null;
    }

    /**
     * Returns the size of the structure.
     */
    public int size() {
        return v.size();
    }

    /**
     * Clears the vector.
     */
    public void clear() {
        v.clear();
    }

    /**
     * Returns the element at the given index.
     */
    public T get(int index) {
	    return v.get(index);
    }

    public String toString() {
        return v.toString();
    }
}