/**
 * Linked-list based class for storing a list of strings.
 * Demonstration program for CSE 143.
 * Also illustrates use of interfaces to specify classes
 * @author Hal Perkins
 * @version 0.1, 4/17/06
 */
public class LinkedStringList implements StringList {
  
  // List state
  private StringLink first;   // first link in the list, or null if
                              //   the list is empty
  private StringLink last;    // last link in the list, or null if
                              //   the list is empty
  private int size;           // number of items in the list
  
  // Note on method comments: JavaDoc automatically picks up the text
  // of comments in interfaces and uses them to document the corresponding
  // methods in implementing classes if no local JavaDoc comments are
  // provided.  This file takes advantage of that by providing succinct
  // comments here to make the file easier to read, while not duplicating
  // all of the text in the interface's JavaDoc comments.
  
  // constructors
  
  // Construct a new, empty StringList
  public LinkedStringList() {
    first = null;
    last  = null;
    size  = 0;
  }
  
  // private methods used by other operations
  
  // Verify that pos is valid (0 <= pos < size).
  // Throw an IndexOutOfBoundsException if it is not, otherwise
  // return silently.
  private void checkIndex(int pos) {
    if (pos < 0 || pos >= size) {
      throw new IndexOutOfBoundsException();
    }
  }
  
  // Return a reference to the link at position pos in the list.
  // pre: pos is valid (i.e., 0 <= pos < size)
  private StringLink getLinkAt(int pos) {
    int k = 0;
    StringLink p = first;
    while (k < pos) {
      p = p.next;
      k++;
    }
    return p;
  }
  
  // query functions
  
  // return the size of this list
  public int size() {
    return size;
  }
  
  // return true if this list is empty, otherwise false
  public boolean isEmpty() {
    return size() == 0;
  }
  
  // return the location of s in this list, or -1 if not present
  public int indexOf(String s) {
    StringLink p = first;
    int pos = 0;
    while (p != null) {
      if (p.item.equals(s)) {
        return pos;
      }
      p = p.next;
      pos++;
    }
    // not found
    return -1;
  }
  
  // return true if this list contains s, otherwise return false
  public boolean contains(String s) {
    return indexOf(s) != -1;
  }
  
  // return the list element at a given position in this list
  // pre: 0 <= pos < size
  public String get(int pos) {
    checkIndex(pos);
    return getLinkAt(pos).item;
  }
  
  
  // list modifications
  
  // change the item at a given position to a new value
  // pre: 0 <= pos < size
  public void set(int pos, String s) {
    checkIndex(pos);
    getLinkAt(pos).item = s;
  }
  
  // add s to the end of this list
  public void add(String s) {
    if (first == null) {
      // special case - adding first item to empty list
      first = new StringLink(s);
      last  = first;
    } else {
      // add new node to non-empty list
      last.next = new StringLink(s);
      last = last.next;
    }
    size++;
  }
  
  // add s to this list at a position pos
  // pre: 0 <= pos < size
  public void add(int pos, String s) {
    checkIndex(pos);
    if (pos == 0) {
      // special case - this is the new first node
      first = new StringLink(s, first);
    } else {
      // add after node at location pos-1
      StringLink prev = getLinkAt(pos-1);
      prev.next = new StringLink(s, prev.next);
    }
    size++;
  }

  // remove the item at the specified position from this list
  // pre: 0 <= pos < size
  public void remove(int pos) {
    checkIndex(pos);
    if (pos == 0) {
      // removing first link
      first = first.next;
      if (first == null) {
        last = null;
      }
    } else {
      // update next field of previous node to next field of victim
      StringLink prev = getLinkAt(pos-1);
      if (prev.next == last) {
        last = prev;
      }
      prev.next = prev.next.next;
    }
    size--;
  }
  
  // toString
  
  // return a string representation of this StringList
  public String toString() {
    String result = "[";
    if (first != null) {
      result = result + first.item;
      StringLink p = first.next;
      while (p != null) {
        result = result + "," + p.item;
        p = p.next;
      }
    }
    result = result + "]";
    return result;
  }
}