import java.util.*;
import edu.bethel.mathcs.util.*;

public class LinkedMutableContainer<E> extends AbstractMutableContainer<E> {

  int size = 0;
  LinkedMutableContainer.Node<E> head = null;

  public String toString() {
    if (this.head == null)
      return "()";
    else
      return this.head.toString();
  }

  public boolean isEmpty() {
    return this.head == null;
  }

  public int size() {
    return this.size;
  }

  public void clear() {
    this.head = null;
    this.size = 0;
  }

  public boolean add(E t) {
    this.head = new Node<E>(t, this.head);
    this.size++;
    return true;
  }

  public boolean delete(E t) {
    if (t == null)
      return false;
    try {
      this.head = this.head.deleteSpecial(t);
      this.size--;
      return true;
    } catch (NoSuchElementException e) {
      return false;
    }
  }

  private static class Node<E> implements Cloneable {

    E userObject;

    Node<E> next;

    /**
     * @return the number of nodes in the linked list beginning at the
     * receiver.
     */
    public int length() {
      if (this.next == null) {
        return 1;
      } else {
        return 1 + this.next.length();
      }
    }

    public int lengthIter() {
      Node<E> current = this;
      int i = 1;
      for (; current.next != null; i++, current = current.next);
      return i;
    }

    // returns a string consisting of a comma-separated list of the
    // elements of the linked list starting at the receiver surrounded
    // by parens.
    public String toString() {
      StringBuilder sb = new StringBuilder("(");
      this.toStringHelper(sb);
      sb.append(")");
      return sb.toString();
    }

    // this appends to sb, the receiver's userObject, followed by a
    // comma and the rest of the elements if there are any.
    private void toStringHelper(StringBuilder sb) {
      sb.append(this.userObject);
      if (this.next != null) {
        sb.append(", ");
        this.next.toStringHelper(sb);
      }
    }

    // returns a linked list of nodes that contains the same elements as
    // the receiver but one occurrence of t is deleted.  The return
    // value shares structure with the receiver and modifies it.
    /** @throws NullPointerException if <code>t</code> is null. */
    public Node delete(E t) {
      if (t.equals(this.userObject)) {
        return this.next;
      } else if (this.next == null) {
        return this;
      } else {
        this.next = this.next.delete(t);
        return this;
      }
    }

    // returns a linked list of nodes that contains the same elements as
    // the receiver but one occurrence of t is deleted.  The return
    // value shares structure with the receiver and modifies it.
    /** @throws NullPointerException if <code>t</code> is null.
     * @throws NoSuchElementException if it doesn't find t.
     */
    private Node deleteSpecial(E t) {
      if (t.equals(this.userObject)) {
        return this.next;
      } else if (this.next == null) {
        throw new NoSuchElementException();
      } else {
        this.next = this.next.delete(t);
        return this;
      }
    }

    public Node deleteIter(E t) {
      if (this.next == null) {
        return t.equals(this.userObject) ? null : this;
      } else if (this.userObject.equals(t)) {
        return this.next;
      } else {
        Node current = this;
        do {
          // ASSERTION: I know that current.next is not null
          // ASSERTION: I know that t does not occur in the linked list
          // starting at the receiver and ending at current.
          if (current.next.userObject.equals(t)) {
            current.next = current.next.next;
            return this;
          }
          current = current.next;
          // ASSERTION: I know that current is not null
          // ASSERTION: I know that t does not occur in the linked list
          // starting at the receiver and ending at current.
        } while (current.next != null);
        // ASSERTION: I know that t does not occur in the linked list
        // starting at the receiver and ending at current.
        // ASSERTION: current is the last node in the list.
        return this;
      }
    }

    // returns true if and only if the linked list starting at the
    // receiver contains t.
    public boolean contains(E t) {
      if (t == null)
        return false;
      return this.containsHelper(t);
    }

    private boolean containsHelper(E t) {
      if (this.userObject.equals(t)) {
        return true;
      } else if (this.next == null) {
        return false;
      } else {
        return this.next.containsHelper(t);
      }
    }

    // returns a linked list of nodes with the same elements as the
    // linked list of nodes starting at the receiver only in the reverse
    // order.  This modifies the receiver and the return value shares
    // structure with the receiver.
    public Node reverse() {
      if (this.next == null) {
        return this;
      } else {
        Node value = this.next.reverse();
        this.next.next = this;
        this.next = null;
        return value;
      }
    }

    public boolean equals(Object o) {
      if (o instanceof Node) {
        return this.equalsHelper((Node) o);
      } else
        return false;
    }

    // returns true if and only if the linked list starting at the
    // receiver contains the same elements in the same order as the
    // linked list starting at the argument.

    // PRECONDITION: n is not null
    private boolean equalsHelper(Node n) {
      if (!this.userObject.equals(n.userObject)) {
        return false;
      } else if (this.next == null) {
        return n.next == null;
      } else if (n.next == null) {
        return false;
      } else {
        return this.next.equalsHelper(n.next);
      }
    }

    public Node<E> clone() {
      try {
        Node<E> value = (Node<E>) super.clone();
        if (this.next == null)
          return value;
        else {
          value.next = this.next.clone();
          return value;
        }
      } catch (CloneNotSupportedException o) {
        throw new AssertionError("Seriously, this can't happen.");
      }
    }

    public Node(E elt) {
      this(elt, null);
    }

    public Node(E elt, Node<E> next) {
      if (elt == null)
        throw new NullPointerException();
      this.userObject = elt;
      this.next = next;
    }

    public static void main(String[] args) {
      Node test = new Node("1", new Node("2", new Node("3")));
      Node test1 = test.clone();
      System.out.println(test.equals(test1));
      System.out.println(test);
      System.out.println(test = test.reverse());
      test.delete("2");
      System.out.println(test);
      System.out.println(test1);
      System.out.println(test.equals(test1));

//    test.next = test;
//    System.out.println(test.length());
    }
  }
}