package dll;

/**
 * An implementation of general lists with linked nodes.
 *
 * @author Samuel A. Rebelsky
 * @author CSC153 2004S
 * @version 1.0 of April 2004
 */
public class LinkedList
  implements GeneralList
{
  // +--------+------------------------------------------------------------
  // | Fields |
  // +--------+

  /**
   * The front of the list.  Set to null if the list is empty.
   */
  ListNode front;

  /**
   * The length of the list.  Included to make the length() operation
   * more efficient.
   */
  int length;

  // +--------------+------------------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Build a new, empty, list.
   */
  public LinkedList()
  {
    front = null;
  } // LinkedList()


  // +-----------+---------------------------------------------------------
  // | Observers |
  // +-----------+

  /**
   * Determine if the list is empty.
   */
  public boolean isEmpty() {
    return null == front;
  } // isEmpty()

  /**
   * Determine the length of the list.
   */
  public int length() {
    return this.length;
  } // length()

  /**
   * Get the object at a particular position in the list.
   *
   * Pre:
   *   (1) The position is valid.
   *   (2) The position is associated with this list.
   */
  public Object get(Position pos) {
    return ((ListNode) pos).contents;
  } // get(Position)

  /**
   * Get the first position in the list.
   *
   * Pre:
   *   (1) The list is nonempty.
   */
  public Position first() {
    return this.front;
  } // first()

  /**
   * Get the last position in the list.
   *
   * Pre:
   *   (1) The list is nonempty.
   */
  public Position last() {
    ListNode pos = this.front;
    while (pos.next != null)
      pos = pos.next;
    return pos;
    // Alternately: Keep track of the last element, too
  } // first()

  /**
   * Determine if a position is the first position in this list.
   *
   * Pre:
   *   (1) The position is valid.
   *   (2) The position is associated with this list.
   */
  public boolean isFirst(Position pos) {
    return pos == this.front;
  } // isFirst(Position)

  /**
   * Determine if a position is the last position in this list.
   *
   * Pre:
   *   (1) pos is valid.
   *   (2) pos is associated with this list.
   */
  public boolean isLast(Position pos) {
    return pos == this.last();
  } // isFirst(Position)

  /**
   * Get the next position in this list.
   *
   * Pre:
   *   (1) pos is valid.
   *   (2) pos is associated with this list.
   *   (3) pos is not the last position in this list.
   */
  public Position next(Position pos) {
    return ((ListNode) pos).next;
  } // next(Position)

  /**
   * Get the previous position in this list.
   *
   * Pre:
   *   (1) pos is valid.
   *   (2) pos is associated with this list.
   *   (3) pos is not the first position in this list.
   */
  public Position prev(Position pos) {
    // STUB
    return this.front;
  } // next(Position)

  /**
   * Determine if a position is a associated with this list.
   */
  public boolean belongs(Position pos) {
    // STUB
    return true;
  } // belongs(Position)


  // +----------+----------------------------------------------------------
  // | Mutators |
  // +----------+

  /**
   * Add an element to the list.
   *
   * Post: 
   *   (1) The length of the list has increased by 1.
   *   (2) The list now contains another instance of newelt.
   *   (3) All positions previously associated with this list
   *       are now invalid.
   */
  public void add(Object newelt) {
    ++this.length;
    this.front = new ListNode(newelt, this.front);
  } // add(Object)

  /**
   * Remove all elements from the list.
   *
   * Post: 
   *   (1) The list contains no elements.
   *   (2) All positions previously associated with this list 
   *       are now invalid.
   */
  public void clear() {
    this.length = 0;
    this.front = null;
  } // clear()

  /**
   * Remove an element at a specified position from the list.
   *
   * Pre:
   *   (1) The position is valid.
   *   (2) The position is associated with this list.
   *   (3) get(pos) returns obj.
   * Post:
   *   (1) The length of the list has decreased by 1.
   *   (2) The list contains one fewer instance of obj.
   *   (3) All positions previously associated with this list 
   *       are now invalid.
   *   (4) The value returned is obj.
   */
  public Object remove(Position pos) {
    --this.length;
    if (pos == this.front) {
      this.front = this.front.next;
    }
    else {
      ListNode tmp = this.front;
      while (tmp.next != pos)
        tmp = tmp.next;
      tmp.next = tmp.next.next;
    }
    ListNode node = ((ListNode) pos);
    Object returnme = node.contents;
    node.contents = null;
    node.next = null;
    return returnme;
  } // remove(Position)

  /**
   * Replace the element at a specified position in the list.
   *
   * Pre:
   *   (1) The position is valid.
   *   (2) The position is associated with this list.
   *   (3) get(pos) returns oldobj.
   * Post:
   *   (1) get(pos) now returns newobj.
   *   (2) The value returned is oldobj.
   */
  public Object replace(Position pos, Object newobj) {
    // STUB
    return null;
  } // replace(Position, Object)

} // class LinkedList