package net.datastructures;
/** Realization of a vector by means of an array.  The array has
  * initial length 16 and is doubled when the size of the vector
  * exceeds the capacity of the array.  No shrinking of the array is
  * performed.
  *
  * @author Roberto Tamassia
  */
public class ArrayVector implements Vector {
  private Object[] A;		// array storing the elements of the vector
  private int capacity = 16;	// initial length of array A
  private int size = 0;		// number of elements stored in the vector
  /** Creates the vector with initial capacity 16. */
  public ArrayVector() { 
    A = new Object[capacity];
  }
  /** Returns the number of elements in the vector. */
  public int size() {
    return size;
  }
  /** Returns whether the vector is empty. */
  public boolean isEmpty() {
    return size() == 0; 
  }
  /** Returns the element stored at the given rank. */
  public Object elemAtRank(int r) 
    throws BoundaryViolationException {
    checkRank(r, size());
    return A[r]; 
  }
  /** Replaces the element stored at the given rank. */
  public Object replaceAtRank(int r, Object e) 
    throws BoundaryViolationException {
    checkRank(r, size());
    Object temp = A[r];
    A[r] = e;
    return temp;
  }
  /** Inserts an element at the given rank. */
  public void insertAtRank(int r, Object e) 
    throws BoundaryViolationException {
    checkRank(r, size() + 1);
    if (size == capacity) {		// an overflow
      capacity *= 2;
      Object[] B = new Object[capacity];
      for (int i=0; i<size; i++) 
	B[i] = A[i];
      A = B;
    }
    for (int i=size-1; i>=r; i--)	// shift elements up
      A[i+1] = A[i];
    A[r] = e;
    size++;
  }
  /** Removes the element stored at the given rank. */
  public Object removeAtRank(int r) 
    throws BoundaryViolationException {
    checkRank(r, size());
    Object temp = A[r];
    for (int i=r; i<size-1; i++)	// shift elements down
      A[i] = A[i+1];
    size--;
    return temp;
  }
  /** Checks whether the given rank is in the range [0, n - 1] */
  protected void checkRank(int r, int n) 
    throws BoundaryViolationException {
    if (r < 0 || r >= n)
      throw new BoundaryViolationException("Illegal vector index: " + r);
  }
}