import java.util.*;

/**
 * Simple Array List implementation for CSE143 demonstration Au03
 * The interface is a subset of java.util.ArrayList.
 * 
 * @author Hal Perkins
 * @version 11/08/04
 */
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;  // placeholder
  }
  
  /**
   * 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;
  }
  
  private void ensureSpareCapacity(int howMuch) {
    if (size() + howMuch <= items.length) {
      return;
    } else {
      Object[] newItems = new Object[items.length * 2 + howMuch];
      for (int k = 0; k < size(); k++){
        newItems[k] = items[k];
      }
      items = newItems;
    }
  }
  
  /** 
   * Add the given object to the list at the given position, moving
   * items at higher positions to the right
   * @param pos position to add object
   * @param obj the object to be added
   * @return true if object successfully added to this list, otherwise false
   */
  public boolean add(int pos, Object obj) {
    ensureSpareCapacity(1);
    checkPos(pos);
    
    for (int k = size; k > pos; k--) {
      items[k] = items[k-1];
    }
    items[pos] = obj;
    size++;
    return true;
  }
  
  // remove items from the list
  
    
  /**
   * Remove all objects from this SimpleArrayList
   */
  public void clear() {
    for (int k = 0; k < size; k++) {
      items[k] = null;
    }
    size = 0;
  }
  
  /**
   * Remove the object at the given position
   */
  public void remove(int pos) {
    //TODO
  }
  
  /**
   * Remove the first copy of an object from the list
   * @param obj the object to be removed
   */
  public void remove(Object obj) {
    //TODO
  }
 
  
  // set and get items from this list
  
  private void checkPos(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 pos < 0 or pos >= size()
   */
  public Object get(int pos) {
    checkPos(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) {
    checkPos(pos);
    Object result = items[pos];
    items[pos] = obj;
    return result;
  }
  
  /** Check whether this list is equal to another one
   * @param obj the other object to compare to
   * @return true if obj is also a SimpleArrayList and its elements
   *          are pairwise equal to the element of this list; otherwise
   *          return false.
   */
  public boolean equals(Object obj) {
    if (obj instanceof SimpleArrayList) {
      SimpleArrayList other = (SimpleArrayList)obj;
      if (size() != other.size()) {
        return false;
      }
      for (int k = 0; k < size(); k++) {
        if (!get(k).equals(other.get(k))) {
          return false;
        }
      }
      return true;
    } else {
      return false;
    }
    
  }
  
  /** 
   * Return a new Iterator for this SimpleArrayList
   * @returns A new Iterator object
   */
  public Iterator iterator() {
    return new SimpleArrayListIterator();
  }
  
  private class SimpleArrayListIterator implements Iterator {
    
    private int pos;     // position of next item to return
    
    public SimpleArrayListIterator() {
      pos = 0;
    }
    
    public boolean hasNext() {
      return pos < size();
    }
    
    public Object next() throws NoSuchElementException {
      if (pos >= size) {
        throw new NoSuchElementException();
      } else {
        pos++;
        return items[pos-1];
      }
    }
    
    public void remove() {}
  }
  
}