/**
 * Dynamic array IVector implementation.
 * @author Jeff Raab
 */
public class DynamicArrayVector implements IVector {

    /** Array used to store elements in this. */
    protected Object[] elements;
    
    /** Size of this. */
    protected int size = 0;
    
    /** Constructs a new dynamic array vector. */
    public DynamicArrayVector() {
        elements = new Object[4];
    }
    
    /**
     * Adds the given object to the end of this,
     * increasing the size of this by 1.
     * @param anObject object to add
     */
    public void add(Object anObject) {
        if (shouldGrow()) {
            grow();
        }
        
        elements[size] = anObject;
        size++;
    }
    
    /**
     * Inserts the given object into this
     * at the given rank, increasing the size of this by 1.
     * @param aRank rank at which to insert object
     * @param anObject object to insert
     */
    public void insertAtRank(int aRank, Object anObject) {
        if (aRank < 0 || aRank > size()) {
            throw new RuntimeException("Invalid rank");
        }
        
        if (shouldGrow()) {
            grow();
        }
        
        shiftRangeRight(aRank, size);
        
        elements[aRank] = anObject;
    }

    /**
     * Removes and returns the object at the given rank,
     * reducing the size of this by 1.
     * @param aRank rank from which to remove object
     */
    public Object removeAtRank(int aRank) {
        if (aRank < 0 || aRank > (size() - 1)) {
            throw new RuntimeException("Invalid rank");
        }
        
        Object removed = elements[aRank];
        
        shiftRangeLeft(aRank + 1, size);
        
        if (shouldShrink()) {
            shrink();
        }
        
        return removed;
    }
    
    /**
     * Returns the object at the given rank.
     * @param aRank rank of object to return
     */
    public Object elementAtRank(int aRank) {
        if (aRank < 0 || aRank > (size() - 1)) {
            throw new RuntimeException("Invalid rank");
        }
        
        return elements[aRank];
    }
    
    /**
     * Sets this to store the given object at the given rank,
     * and returns the object that was replaced at that rank.
     * @param aRank rank of object to store
     * @param anObject object to store
     */
    public Object replaceElement(int aRank, Object anObject) {
        if (aRank < 0 || aRank > (size() - 1)) {
            throw new RuntimeException("Invalid rank");
        }
        
        Object replaced = elements[aRank];

        elements[aRank] = anObject;

        return replaced;
    }
    
    /** Returns the number of elements in this. */
    public int size() {
        return size;
    }
    
    /** Returns whether or not this is empty. */
    public boolean isEmpty() {
        return (size == 0);
    }
    
    /** Returns whether or not this should grow. */
    protected boolean shouldGrow() {
        return (size == elements.length);
    }
    
    /** Returns whether or not this should shrink. */
    protected boolean shouldShrink() {
        if (size <= 4) {
            return false;
        }
        
        return (size < (elements.length / 3));
    }
    
    /** Doubles the length of the underlying array. */
    private void grow() {
        Object[] newArray = new Object[elements.length * 2];
        
        for (int i = 0; i < elements.length; i++) {
            newArray[i] = elements[i];
        }
        
        elements = newArray;
    }

    /** Halves the length of the underlying array. */
    private void shrink() {
        Object[] newArray = new Object[elements.length / 2];
        
        for (int i = 0; i < newArray.length; i++) {
            newArray[i] = elements[i];
        }
        
        elements = newArray;
    }
    
    /** 
     * Shifts the elements in the underlying array to the right 1 index,
     * in the given range [startIndex, endIndex),
     * growing the size of this by 1.
     * @param startIndex start of range of indices
     * @param endIndex end of range of indices (exclusive)
     */
    private void shiftRangeRight(int startIndex, int endIndex) {
        for (int i = endIndex - 1; i >= startIndex; i--) {
            elements[i + 1] = elements[i];
        }
        
        elements[startIndex] = null;
        
        size++;
    }

    /** 
     * Shifts the elements in the underlying array to the left 1 index,
     * in the given range [startIndex, endIndex),
     * shrinking the size of this by 1.
     * @param startIndex start of range of indices
     * @param endIndex end of range of indices (exclusive)
     */
    private void shiftRangeLeft(int startIndex, int endIndex) {
        for (int i = startIndex; i < endIndex; i++) {
            elements[i - 1] = elements[i];
        }
        
        elements[endIndex - 1] = null;
        
        size--;
    }
}