/**
  Solutions for programming assignment 1.

  Data structures and algorithms, CS 305 & 503
  Spring 2010.
 */

public class
LinkList<E>
implements LinkedSequence<E> {

  /**
     Insert a new value after an existing value in this linked list.

     @param e The existing value in this linked list after which the new value
     will be inserted.  If e is null, the new value is inserted after the head.
     If e occurrs more than once, the new value is inserted after the leftmost
     (closest to the head) value.

     @param v The new value to insert.

     @return true iff the new value was inserted.
   */

  private boolean 
  addAfter(E e, E v) {
    if (e == null) {
      head = new Link<E>(v, head)
      animator.unlink(null, head.next)
      animator.link(head, head.next)
      animator.link(null, head)
      return true
      }

    Link<E> link = find(e)
    if (link == null)
      return false

    link.next = new Link<E>(v, link.next)

    animator.unlink(link, link.next.next)
    animator.link(link, link.next)
    animator.link(link.next, link.next.next)

    return true
    }


  /**
     Determine if this linked list contains a value.

     @param v a value.

     @return a reference to a link containing v, or null if there's no such
     link.
   */

  private Link<E>
  find(E v) {
    for (Link<E> link = head; link != null; link = link.next)
      if (link.hasValue(v))
	return link
    return null
    }


  /**
     Determine if this linked list contains a value.

     @param v a value.

     @return true iff this linked list contains v.
   */

  public boolean 
  has(E v) {
    return find(v) != null
    }


  /**
     Insert a new value after an existing value in this linked list.

     @param e The existing value in this linked list after which the new value
     will be inserted.  If e is null, the new value is inserted after the head.
     If e occurrs more than once, the new value is inserted after the leftmost
     (closest to the head) value.

     @param v The new value to insert.

     @return true iff the new value was inserted.
   */

  public boolean 
  insertAfter(E e, E v) {

    if (!addAfter(e, v))
      return false

    count++

    return true
    }


  /**
     Determine if this linked list contains any values.

     @return true iff this linked list contains no values.
   */

  public boolean 
  isEmpty() {
    return head == null
    }


  /**
     Create a new empty linked list.
   */

  public LinkList() {
    head = null
    count = 0
    }


  /**
     Run some tests.  Call it with 

       $ java -ea -classpath public/pa1.jar:. LinkList
   */

  public static void
  main(String args[]) {
    LinkList<Integer> l = new LinkList<Integer>()
    l.setAnimator(new NullLSA())

    assert l.isEmpty() : "l.isEmpty() failed"
    assert l.insertAfter(null, 0) : "l.insertAfter(null, 0) failed."
    assert !l.isEmpty() : "!l.isEmpty() failed"
    assert l.see() == 0 : "l.see() == 0 failed"
    assert l.has(0): "l.has(0) failed"

    assert l.insertAfter(null, 1) : "l.insertAfter(null, 1) failed."
    assert l.see() == 1 : "l.see() == 1 failed"
    assert l.has(0): "l.has(0) failed"
    assert l.has(1): "l.has(1) failed"
    assert l.remove(1) : "l.remove(1) failed"
    assert l.see() == 0 : "l.see() == 0 failed"
    assert l.remove(0) : "l.remove(0) failed"
    assert l.isEmpty() : "l.isEmpty() failed"
    }


  /**
     Remove a value from this linked list.

     @param e The value to remove.

     @return true if e was removed from the list, false if e wasn't in the
     list.
   */

   public boolean 
   remove(E v) {
 
     if (isEmpty())
       return false
 
     if (head.hasValue(v)) {
       animator.unlink(null, head)
       animator.unlink(head, head.next)
       animator.link(null, head.next)
       head = head.next
       count--
       return true
       }
 
     for (Link<E> l = head; l.next != null; l = l.next)
       if (l.next.hasValue(v)) {
         animator.unlink(l, l.next)
	 animator.unlink(l.next, l.next.next)
	 animator.link(l, l.next.next)
         l.next = l.next.next
	 count--
       return true
         }
 
     return false
     }
 
 
  /**
     Return the value at this linked list's head.

     @return the value at this linked list's head, or null if the list is empty
     (note the ambiguity if the value at the list's head is null).
   */

  public E
  see() {
    return isEmpty() ? null : head.value
    }
  

  /**
     Set this linked list's animataion engine.

     @param animator The animator to use in further animations.
   */

  public void 
  setAnimator(LinkedSequenceAnimator animator) {
    this.animator = animator
    }


  /**
     Determine the number of values in this linked list.

     @return the number of values in this linked list.
   */

  public int
  size() {
    return count
    }


  /**
     The links in the stack.
   */

  private static class 
  Link<E> {

    /**
       Create a new link.

       @param v The new link's value.
       @param n The link following the new link (or null).
     */

    Link(E v, Link<E> n) { 
      value = v
      next = n; 
      }


    /**
       Determine if this link holds a particular value.

       @param v The value of interest.

       @return true iff this link holds the given value.
     */

    boolean 
    hasValue(E v) {
      if (value == null)
	return v == null
      return value.equals(v)
      }


    /**
       The value held in this link. 
     */

    final E value


    /**
       This link's successor, or null if there's no successor.
     */

    Link<E> next
    }


  /**
     This linked list's head.

     Invariant: count == 0 iff head == null
   */

  private Link<E> head


  /**
     This linked list's animation engine.

     invariant: animator != null
   */

  LinkedSequenceAnimator animator


  /**
     The number of values in the linked list.

     invariant:  count > -1
   */

  private int count
  }


/**
 */

public class 
LinkQueue<E>
implements LinkedSequence<E> {


  /**
     Determine if this queue contains a value.

     @param v a value.

     @return true iff this queue contains v.
   */

  public boolean 
  has(E v) {
    for (Link<E> link = head; link != null; link = link.next)
      if (link.hasValue(v))
	return true

    return false
    }


  /**
     Insert a new value into this queue.

     @param e Should be null or the value currently at the tail.

     @param v The value to insert.

     @return true if v was inserted, false if e wasn't null and wasn't the
     value stored at the tail (if any).
   */

  public boolean 
  insertAfter(E e, E v) {

    if ((e != null) && ((tail == null) || !tail.hasValue(e)))
      return false

    final Link<E> newTail = new Link<E>(v, null)

    animator.link(tail, newTail)
    if (tail != null)
      tail.next = newTail
    else
      head = newTail
    tail = newTail

    ++count

    return true
    }


  /**
     Determine if this queue contains any values.

     @return true iff this queue contains no values.
   */

  public boolean 
  isEmpty() {
    return head == null
    }


  /**
     Create a new empty queue.
   */

  public LinkQueue() {
    head = tail = null
    count = 0
    }


  /**
     Run some tests.  Call it with 

       $ java -ea -classpath public/pa1.jar:. LinkQueue
   */

  public static void
  main(String args[]) {

    LinkQueue<Integer> q = new LinkQueue<Integer>()
    q.setAnimator(new NullLSA())

    assert q.isEmpty() : "q.isEmpty() failed"
    assert q.insertAfter(null, 0) : "q.insertAfter(null, 0) failed."
    assert !q.isEmpty() : "!q.isEmpty() failed"
    assert q.see() == 0 : "q.see() == 0 failed"

    assert q.insertAfter(null, 1) : "q.insertAfter(null, 1) failed."
    assert q.see() == 0 : "q.see() == 0 failed"
    assert q.remove(0) : "q.remove(0) failed"
    assert q.see() == 1 : "q.see() == 1 failed"
    assert q.remove(1) : "q.remove(1) failed"
    assert q.isEmpty() : "q.isEmpty() failed"
    }


  /**
     Remove a value from this queue.

     @param e The value to remove.

     @return true if e was removed from this queue, or false if e wasn't the
     value at the queue head.
   */

  public boolean 
  remove(E e) {

    if (isEmpty() || !head.hasValue(e))
      return false

    animator.unlink(null, head)
    animator.unlink(head, head.next)
    animator.link(null, head.next)

    head = head.next
    if (--count == 0)
      tail = null

    return true
    }


  /**
     Return without removing the value at this queue's head.

     @return the value at this queue's, or null if the queue is empty.
   */

  public E
  see() {

    if (isEmpty())
      return null

    return head.value
    }
  

  /**
     Set this queue's animataion engine.

     @param animator The animator to use in further animations.
   */

  public void 
  setAnimator(LinkedSequenceAnimator animator) {
    this.animator = animator
    }


  /**
     Determine the number of values in this queue.

     @return the number of values in this queue.
   */

  public int
  size() {
    return count
    }


  /**
     The links in the stack.
   */

  private static class 
  Link<E> {

    // See LinkList.Link<E> for details.

    }


  /**
     The queue.

     invariants: 
       count == 0 iff head == null
       head == null iff tail == null
   */

  private Link<E> head, tail


  /**
     The number of values in the queue.

     invariant: count > -1
   */

  private int count


  /**
     This queue's animation engine.

     invariant: animator != null
   */

  private LinkedSequenceAnimator animator
  }


/**

 */

public class 
LinkStack<E>
implements LinkedSequence<E> {

  /**
     Determine if this stack contains a value.

     @param v a value.

     @return true iff this stack contains v.
   */

  public boolean 
  has(E v) {
    for (Link<E> link = head; link != null; link = link.next)
      if (link.hasValue(v))
	return true
    return false
    }


  /**
     Insert a new value into this stack.

     @param e Should be null.

     @param v The value to insert.

     @return true if v was inserted, false if e wasn't null.
   */

  public boolean 
  insertAfter(E e, E v) {
    if (e != null)
      return false

    if (head != null)
      animator.unlink(null, head)

    head = new Link<E>(v, head)
    count++

    if (head.next != null)
      animator.link(head.next, head.next.next)

    animator.link(null, head)

    return true
    }


  /**
     Determine if this stack contains any values.

     @return true iff this stack contains no values.
   */

  public boolean 
  isEmpty() {
    return head == null
    }


  /**
     Create a new empty stack.
   */

  public LinkStack() {
    head = null
    count = 0
    }


  /**
     Run some tests.  Call it with 

       $ java -ea -classpath public/pa1.jar:. LinkStack
   */

  public static void
  main(String args[]) {

    LinkStack<Integer> s = new LinkStack<Integer>()
    s.setAnimator(new NullLSA())

    assert s != null : "s is null"
    assert s.isEmpty() : "s.isEmpty() failed"
    assert s.insertAfter(null, 0) : "s.insertAfter(null, 0) failed."
    assert !s.isEmpty() : "!s.isEmpty() failed"
    assert s.see() == 0 : "s.see() == 0 failed"

    assert s.insertAfter(null, 1) : "s.insertAfter(null, 1) failed."
    assert s.see() == 1 : "s.see() == 1 failed"
    assert s.remove(1) : "s.remove(1) failed"
    assert s.see() == 0 : "s.see() == 0 failed"
    assert s.remove(0) : "s.remove(0) failed"
    assert s.isEmpty() : "s.isEmpty() failed"
    }


  /**
     Remove a value from the stack.

     @param e The value to remove.

     @return true e was the stack top, false otherwise.
   */

  public boolean 
  remove(E v) {
    if (isEmpty() || !head.hasValue(v))
      return false

    animator.unlink(head, head.next)
    animator.unlink(null, head)
    animator.link(null, head.next)

    head = head.next
    count--

    return true
    }


  /**
     Return the value at this stack's top.

     @return the value at this stack's top, or null if this stack is empty
     (note the ambiguity).
   */

  public E
  see() {
    return isEmpty() ? null : head.value
    }
  

  /**
     Set this stack's animataion engine.

     @param animator The animator to use in further animations.
   */

  public void 
  setAnimator(LinkedSequenceAnimator animator) {
    this.animator = animator
    }


  /**
     Determine the number of values in this stack.

     @return the number of values in this stack.
   */

  public int
  size() {
    return count
    }


  /**
     The links in the stack.
   */

  private static class 
  Link<E> {

    // See LinkList.Link<E> for details.

    }


  /**
     The values pushed into this stack.

     invariant: count == 0 iff head == null
   */

  private Link<E> head


  /**
     This stack's animation engine.

     invariant: animator != null
   */

  LinkedSequenceAnimator animator


  /**
     The number of values in the stack.

     invariant: count > -1
   */

  private int count
  }