/*
  This example has been modified to include
  1. A static class variable num_cons
  2. ListException
  3. Catch/throw
  4. Some exercises
  */

public class List {
  private boolean eol;              // (1)
  private Object data;              // (2)
  private List next;                // (3)
  private static int num_cons = 0;  // (4)

  /* A list is an element with data, followed by a list
     or is empty. 
     Because of the peculiarities of OOP wee cannot actually have null as
     the empty list as we would then have to have instance variables and
     methods associated with null. So a work round is to have a list element
     marked as empty at the end of every list. 
     (1) eol is true if this is an end of list marker, otherwise it is false
     (2) the data in the list element (an object)
     (3) next is the next list element (and may be the end of list element)
     (4) a class variable (not instance) counting number of elements
         I've just put this here as a wee test. Note that whenever we construct
         a List object this class variable is incremented. So, we can find out
         just how many times we have used the constructor. Interesting to 
         see. Look what happens when we insert something into a list,
         creating possibly many new List objects.
     */

  public List() {
    eol = true;
    data = null;
    next = null;
    num_cons++;
  }

  public List(Object e) {
    eol = false;                     // (1)
    data = e;                        // (2) 
    next = new List();               // (3)
    num_cons++;
  }
  /* create a single element list with e as data
     (1) it is NOT the end of list
     (2) data is set to be e
     (3) the next element is an end of list element
   */

  public List(Object e, List tail) {
    eol = false;                    // (1)
    data = e;                       // (2)
    next = tail;                    // (3)
    num_cons++;
  }    
  /* create me a new list element with e as the data and tail as the rest
     of the list, where tail is a List
     (1) it is NOT an end of list 
     (2) e is the data
     (3) tail is the net of the list
     */

  public List add(Object e) {
    return new List(e,this);
  }
  /* add e onto the list. Similar to function cons in scheme and lisp
   */

  public boolean isEmpty() {
    return eol;    
  }

  public Object head() throws ListException {
    if (isEmpty())
      throw new ListException("head of empty list");
    else return data;
  }/* Because head() throws an exception most everything must also 
      throw or catch. Same for tail() below */

  public List tail() throws ListException {
    if (isEmpty())
      throw new ListException("tail of empty list");
    else return next;
  }

 public String toString() {
   String s = "";
   try {
    s = RestOfString();
   } catch (ListException e) {System.out.println("Yikes!");}
   return "(" + s + ")";
  }

  private String RestOfString() throws ListException {
    if (isEmpty())
      return "";
    else return head().toString() + " " + tail().RestOfString();
  }

  public int length() throws ListException {
    if (isEmpty())
      return 0;
    else return 1 + tail().length();
  }
  
  public List append(List l2) throws ListException {
    if (isEmpty())
      return l2;
    else return new List(head(),tail().append(l2));
  }

  public List insert(Object e, Comparator c) throws ListException{
    if (isEmpty())
      return new List(e);
    else if (c.compare(e,head()) < 0)
      return new List(e,this);
    else return new List(head(),tail().insert(e,c));
  }

 public boolean isPresent(Predicate p) throws ListException{
    if (isEmpty())
      return false;
    else return (p.predicate(head())) || tail().isPresent(p);
  }/* Takes a Predicate P and tests to see if some object
      in the list satisfies that predicate.
      NOTE: || is OR, so if first test delivers true second
            test is not evaluated! We get the recursive call
	    made conditionally. */

  public List delete(Predicate p) throws ListException{
    if (isEmpty())
      return this;
    else if (p.predicate(head()))
      return tail();
    else return new List(head(),tail().delete(p));
  }        
  
  private List rev(List temp) throws ListException{
    if (isEmpty())
      return temp;
    else return tail().rev(new List(head(),temp));
  }

  public List reverse() throws ListException {
    if (isEmpty())
      throw new ListException("Reverse of empty list");
    else return rev(new List());
  }

  public int cons() {
    return List.num_cons; // shows number of times constructor has been used
  }
}


/*
  Exercises
  1. Write a method nth(i) to deliver the nth item
     in the list. Throw a ListException if List is empty
  2. Write a method find(p), to deliver a list of objects
     that satisfy predicate p.
  3. Use 1 and 2 to extend Test.java, such that we can show the 
     nth ToDo item or show all items of a given priority
     */