import java.util.*;


/**
 * UndoableList is a class with a single member head.  head is a reference
 * to the first node in the array, and reference to null if the list is 
 * empty.
 */
public class UndoableListSolution {
  private static final int MAX_VERSION = 10;

  // versions is an array of MAX_VERSION elements, each elements is a head
  // to an UndoableList.  
  
  private Node versions[];

  // Members current, latest and earliest are all indices into
  // versions[].  versions[current] is always the current version.  
  // versions[latest] is the latest version, and versions[earliest] 
  // is the earliest version.  Similar to array implementation of queues 
  // (lab 4), current, latest and earliest can "wrap around" the array.  
  // Therefore, we use modulo arithmatic (%) when increasing or decreasing 
  // the version numbers.

  private int earliest;
  private int current;
  private int latest;

  public UndoableListSolution() {
    versions = new Node[MAX_VERSION];
    earliest = current = latest = 0;
  }

  public Node getHead() {
    return versions[current];
  }

  /**
   * Inserts a new node with value v into this linked list, maintaining
   * the sorted order of the list.
   */
  public void insert(int v) {
    Node head = versions[current];
    versions[nextVersion()] = insert(head, v);
  }

  /**
   * Deletes the node with value v from this linked list.  If v does not
   * exist in the list, do nothing.
   */
  public void delete(int v) {
    Node head = versions[current];
    versions[nextVersion()] = delete(head, v);
  }

  /**
   * Returns true if a node with value v exists in this linked list. Returns 
   * false otherwise.
   */
  public boolean find(int v) {
    Node head = versions[current];
    return find(head, v);
  }

  /**
   * If current version is the earliest, cannot undo.  Just return.  
   * Otherwise, points current to the previous version of the list.
   */
  public void undo() {
    if (current != earliest)
    {
      current--;
      if (current < 0)
      {
        current = versions.length - 1;
      }
    }
  }

  /**
   * If current is the latest version, cannot redo.  Just return.  
   * Otherwise, points current to the next version of the list.
   */
  public void redo() {
    if (current != latest)
    {
      current = (current + 1) % versions.length;
    }
  }

  /**
   * Returns a string containing the values in the list for printing.
   */
  public String toString()
  {
    Node head = versions[current];
    if (head == null)
      return "[ ]";
    else
      return "[" + toString(head) + "]";
  }

  /**
   * Update current to the next version, and set the current to be the
   * latest version.  If we currently stored MAX_VERSION already, then
   * latest == earliest.  In this case, we throw away the oldest version
   * by pointing earliest to the 2nd oldest version.
   */
  private int nextVersion()
  {
    current = (current + 1) % versions.length;
    latest = current;
    if (latest == earliest)
    {
      earliest = (earliest + 1) % versions.length;
    }
    return current;
  }

  /**
   * Returns the head of the new list after inserting v into the list that 
   * begins at n.
   */
  private Node insert(Node n, int v) {
    if (n == null)
      return new Node(v);
    else {
      Node m;
      int x = n.getValue();
      if (x > v) {
        m = new Node(v);
        m.setNext(n);
        return m;
      } else {
        m = insert(n.getNext(), v);
        // Insertion has happened somewhere down the list. Clone self.
        if (m != n.getNext())
        {
          Node p = new Node(x);
          p.setNext(m);
          return p;
        }
        else
        {
          return n;
        }
      }
    }
  }

  /**
   * Returns the head of the new list after deleting v from the list that 
   * begins at n.
   */
  private Node delete(Node n, int v) {
    if (n == null)
      return null;
    else {
      int x = n.getValue();
      if (x == v) {
        return n.getNext();
      } else if (x > v) {
        return n;
      } else {
        Node m = delete(n.getNext(), v);
        if (m != n.getNext())
        {
          // Deletion has happened somewhere down the list. Clone self.
          Node p = new Node(x);
          p.setNext(m);
          return p;
        }
        else
        {
          return n;
        }
      }
    }
  }

  /**
   * Returns true if value v exists in the list that begins at n.
   */
  private boolean find(Node n, int v) {
    if (n == null)
      return false;
    if (n.getValue() == v)
      return true;
    else 
      return find(n.getNext(), v);
  }

  /**
   * Returns a string containing values from the list starting at 
   * node n.
   */
  private String toString(Node n) {
    if (n == null)
      return "";
    else
      if (n.getNext() == null)
        return "" + n.getValue() + ":" + n.nodeId;
      else
        return "" + n.getValue() + ":" + n.nodeId +", "+toString(n.getNext());
  }
}


/**
 * A Node represents a node in a linked list.  It has two members: (i) value, 
 * which is an int, is the data stored inside the node, and (ii) next, which 
 * is a reference to the next node in the list.  next is null if it is the 
 * last node.
 */
class Node {
  public static int lastId = 0;
  public int value;
  public int nodeId; // unique id to identify a node.
  public Node next;

  public Node(int v) {
	value = v;
	next  = null;
    nodeId = lastId++;
  }

  public int getValue() {
	return value;
  }

  public Node getNext() {
	return next;
  }

  public void setValue(int v) {
	value = v;
  }

  public void setNext(Node n) {
	next = n;
  }
}