/*
  This example has been modified to include
  1. A static class variable num_cons
  2. ListException
  3. Mmmmmm ...
  */

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() {
    return data;
  }

  public List tail() {
    return next;
  }


 public String toString() {
    return "(" + RestOfString() + ")";
  }

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

  public int length() {
    if (isEmpty())
      return 0;
    else return 1 + tail().length();
  }

  
  public List append(List l2) {
    if (isEmpty())
      return l2;
    else return new List(head(),tail().append(l2));
  }


  public List insert(Object e, Comparator c) {
    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) {
    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 */

  public List delete(Object e) {
    if (isEmpty())
      return this;
    else if (head().equals(e))
      return tail();
    else return new List(head(),tail().delete(e));
  }
        
  
  private List rev(List temp) {
    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
  }
}