import java.util.*;

/**
 * Simple Array List implementation for CSE143 demonstration Wi05
 * The interface is a subset of java.util.ArrayList.
 * 
 * @author Hal Perkins
 * @version 11/09/03, 2/11/05
 */
public class SimpleArrayList {
  
  // instance variables
  private Object[] items;          // items in this list are stored in
  private int size;                 // items[0..size-1]
  
  // default capacity of a new SimpleArrayList if none is specified
  private static final int defaultCapacity = 5;
  
  /**
   * Construct a new SimpleArrayList with a default capacity
   */
  public SimpleArrayList() {
    this(defaultCapacity);
  }
  
  /**
   * Construct a new SimpleArrayList with the specified capacity
   * @param initialCapacity The initial size of this SimpleArrayList
   */
  public SimpleArrayList(int initialCapacity) {
    items = new Object[initialCapacity];
    size = 0;
  }
  
  // Basic query functions
  
  /**
   * Return the current size of this SimpleArrayList
   * @return the number of items currently in this SimpleArrayList
   */
  public int size() {
    return size;
  }
  
  /**
   * Return whether this SimpleArrayList is empty or not
   * @return true if this SimpleArrayList contains no items, otherwise false
   */
  public boolean isEmpty() {
    return size() == 0;
  }
  
  /**
   * Return the location of an item in the list
   * @param obj The object we are looking for
   * @return The first location of obj in the list if found, otherwise -1
   */
  public int indexOf(Object obj) {
    for (int k = 0; k < size(); k++) {
      if (items[k].equals(obj)) {
        return k;
      }
    }
    return -1;
  }
  
  /**
   * Return whether this list contains a given object
   * @param obj The object we are looking for
   * @return true if obj is in the list, otherwise false
   */
  public boolean contains(Object obj) {
    return indexOf(obj) != -1;
  }
  
  // Add elements to this SimpleArrayList
  
  /**
   * Add the given object to the end of this SimpleArrayList if there is room
   * @param obj the object to be added
   * @return true if obj was successfully added to this SimpleArrayList, otherwise false
   */
  public boolean add(Object obj) {
    ensureSpareCapacity(1);
    items[size] = obj;
    size++;
    return true;
  }
  
  // ensure there's at least nrequested empty slots in the array
  private void ensureSpareCapacity(int nrequested) {
    if (size()+nrequested <= items.length) {
      return;
    }
    Object[] newItems = new Object[items.length*2 + nrequested];
    for (int k = 0; k < size(); k++) {
      newItems[k] = items[k];
    }
    items = newItems;
  }
  
  // clear the list
  
    
  /**
   * Remove all objects from this SimpleArrayList
   */
  public void clear() {
    for (int k = 0; k < size; k++) {
      items[k] = null;
    }
    size = 0;
  }
 
  
  // set and get items from this list
  
  private void checkPosition(int pos) {
    if (pos < 0 || pos >= size()) {
      throw new IndexOutOfBoundsException();
    }
  }
  
  /**
   * Return the element at the specified position in the list
   * @param pos  the position of the element to return
   * @return the element at the specified position
   * @throws IndexOutOfBoundsException if the position is out of range (<0 or >=size())
   */
  public Object get(int pos) {
    checkPosition(pos);
    return items[pos];
  }
  
  /**
   * Replace the element at the specified position with the specified element
   * @param pos the position of the element to be replaced
   * @param obj the new element to be stored at that position
   * @return the element that was previously stored at that position
   * @throws IndexOutOfBoundsException if the position is out of range (<0 or >=size())
   */
  public Object set(int pos, Object obj) {
    checkPosition(pos);
    Object result = items[pos];
    items[pos] = obj;
    return result;
  }
  
  /**
   * Remove the item at position k
   * @param pos the position of the element to remove
   * @return the element that was removed
   * @throws IndexOutOfBoundsException if the position is out of range
   */
  public Object remove(int pos) {
    checkPosition(pos);
    Object result = items[pos];
    size--;
    // shift to the left
    for (int k = pos; k < size; k++) {
      items[k] = items[k+1];
    }
    items[size] = null;
    return result;
  }
  
  
  /**
   * Return true if this list is equal to another one
   * @param obj the other object to compare this list to
   * @return true if obj is another SimpleArrayList and its eleemnts
   *          are pairwise equal to the elements of this list,
   *          otherwise return false
   */
  public boolean equals(Object obj) {
    //TODO
    return false;  // placeholder
  }
  
  /**
   * Return a new Iterator for this SimpleArrayList
   * @return a new initialized iterator
   */
  public Iterator iterator() {
    //TODO
    return null;  // placeholder
  }
  
}