import java.util.*;

/**
 * Simple Linked List implementation for CSE143 demonstration Au03, Wi05
 * The interface is a subset of java.util.List.
 * 
 * @author Hal Perkins
 * @version 11/08/04, 2/13/05
 */
public class SimpleLinkedList {
  
  // inner class - representation of list nodes
  private class Node {
    public Object item;       // the item this node refers to
    public Node next;         // next list node or null if this
                                //   is the last node in the list
    
    /** construct a new Node */
    public Node(Object item, Node next) {
      this.item = item;
      this.next = next;
    }
  }
  
  // instance variables
  private Node first;       // first node in list or null if list is empty
  private Node last;        // last node in list or null if list is empty
  private int  size;        // # of items in this list
  
  /**
   * Construct a new empty SimpleLinkedList
   */
  public SimpleLinkedList() {
    first = null;
    last  = null;
    size  = 0;
  }
  
  // Basic query functions
  
  /**
   * Return the current size of this SimpleLinkedList
   * @return the number of items currently in this SimpleLinkedList
   */
  public int size() {
    return size;
  }
  
  /**
   * Return whether this SimpleLinkedList is empty or not
   * @return true if this SimpleLinkedList 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) {
    Node p = first;
    int loc = 0;
    while (p != null) {
      if (p.item.equals(obj)) {
        return loc;
      }
      p = p.next;
      loc++;
    }
    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 SimpleLinkedList
  
  /**
   * Add the given object to the end of this SimpleLinkedList if there is room
   * @param obj the object to be added; must not be null
   * @return true if obj was successfully added to this SimpleLinkedList, otherwise false
   * @throws IllegalArgumentException if obj is null
   */
  public boolean add(Object obj) {
    if (obj == null) {
      throw new IllegalArgumentException();
    }
    Node newNode = new Node(obj, null);
    if (first == null) {
      first = newNode;
      last = first;
    } else {
      last.next = newNode;
      last = newNode;
    }
    size++;
    return true;
  }
  
  
  /** 
   * Add the given object to the list at the given position
   * @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) {
    //TODO
    return false;  // placeholder
  }
  
  // remove items from the list
 
  /**
   * Remove all objects from this SimpleLinkedList
   */
  public void clear() {
    first = null;
    last  = 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);
    Node p = first;
    int loc = 0;
    while (loc < pos) {
      p = p.next;
      loc++;
    }
    return p.item;
  }
  
  /**
   * 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);
    return null;  //placeholder
  }
  
  /** Check whether this list is equal to another one
   * @param obj the other object to compare to
   * @return true if obj is also a SimpleLinkedList and its elements
   *          are pairwise equal to the element of this list; otherwise
   *          return false.
   */
  public boolean equals(Object obj) {
    if (obj instanceof SimpleLinkedList) {
      SimpleLinkedList other = (SimpleLinkedList)obj;
      if (this.size() != other.size()) {
        return false;
      }
      Node p = this.first;
      Node q = other.first;
      while (p != null) {
        if (!p.item.equals(q.item)) {
          return false;
        }
        p = p.next;
        q = q.next;
      }
      return true;
    }
    return false;  // placeholder
  }
  
  /** 
   * Return a new Iterator for this SimpleLinkedList
   * @returns A new Iterator object
   */
  public Iterator iterator() {
    return new SimpleLinkedListIterator();
  }
  
  private class SimpleLinkedListIterator implements Iterator {
    
    // Insert state here
    Node nextNode;     // next unvisited node in the list
    
    public SimpleLinkedListIterator() {
      nextNode = first;
    }
    
    public boolean hasNext() {
      return nextNode != null;
    }
    
    public Object next() throws NoSuchElementException {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      Object item = nextNode.item;
      nextNode = nextNode.next;
      return item;
    }
    
    public void remove() {} // Not implemented
  }
  

  
}