/** The functional list type defined by List<T> := EmptyList<>() + ConsList(T, List<T>) */
interface List {

  /** Visitor hooks */
  abstract public Object visit(ListVisitor v); 
                                                           
  /** Returns the empty list of type T, which is unique across all types. */
  default public EmptyList empty() { return EmptyList.ONLY; }
  
  /** Adds i to the front of this. */
  default public ConsList cons(Object o) { return new ConsList(o, this); }
  
  /* Overriding equals to implement structural equality */
  abstract public boolean equals(Object other);
    
  /* The List composite type overrides toString to provide a List-like string represenation. */
  
  /** A help function for producing a Lisp-like representation for List. Called by toString() and toStringHelp() */
  abstract String toStringHelp();
  
  /* Interpreter pattern implementations of reverse, insert, insertSort, merge, partition, and mergeSort. */
  
  /** returns the elements of this in reverse order. */
  abstract List reverse();
  /** helper method used to implement reverse() */
  abstract List reverseHelp(List accum);
  
  /** Assuming that this is a list of elements of type T supporting Comparable<T>, returns this collection of elements
    * in ascending (non-descending) order */
  public abstract List insert(Comparable elt);
  
  /** Assuming that this is a list of elements of type T supporting Comparable<T>, mergeSort() returns a list 
    * containing exactly the same collection of elements in ascending (non-descending) order. */
  public abstract List insertSort();
  
  /** Assuming that this and right are both ascending (non-descending) lists of elements of type T supporting Comparable<T>,
    * merge(right) merges the two lists, i.e. returns the list containing the same collection of elements as this and right
    * in ascending order. */  
  public abstract List merge(List right);
  
  /** Paritions this by returning a pair (left, right) such that this and union(left,right) [generalized to multi-sets]
    * contain the same multi-sets of elements and the length [size] of left and right differ by at most 1. */
  public abstract Pair partition();
  
  /** Assuming that this is a list of elements of type T supporting Comparable<T>, mergeSort() returns a list 
    * containg exactly the same collection of elements in ascending (non-descending) order. */
  public abstract List mergeSort();
}
 
/** Concrete empty list structure containing nothing. */
class EmptyList implements List {
  public static final EmptyList ONLY = new EmptyList();
    
  /* private constructor */
  private EmptyList() { }
  
  /** Visitor hooks */
  public Object visit(ListVisitor v) { return v.forEmptyList(this); }
  
  public boolean equals(Object o) { return o == ONLY; }
  
  /** Constructs a Lisp-like String representation. */
  public String toString() { return "()"; }
  /** Helper method for toString() that outputs the final closing paren of the Lisp string representation. */
  public String toStringHelp() { return ")"; }
  
  public List reverse() { return ONLY; }
  public List reverseHelp(List accum) { return accum; }
  
  public List insert(Comparable elt) { /* Your code goes here instead of: */ return null; } 
  
  public List insertSort() { /* Your code goes here instead of: */ return null; } 

  public List merge(List right) { /* Your code goes here instead of: */ return null; } 
  
  public Pair partition() { /* Your code goes here instead of: */ return null; } 
  
  public List mergeSort() { /* Your code goes here instead of: */ return null; } 
}   
  
/** Concrete non-empty list structure containing an element of T, called first, and a List<T> called rest. */
class ConsList implements List {
  
  /** Cons node fields */
  Object first;
  List rest;
  
  /** Data constructor for ConsList */
  ConsList(Object f, List r) { first = f; rest = r; }
  
  /** Accessors */
  public Object first() { return first; }
  public List rest() { return rest; }
  
  /** Visitor hooks */
  public Object visit(ListVisitor v) { return v.forConsList(this); }
  
  public boolean equals(Object o) { 
    if (o.getClass() != ConsList.class) return false;
    ConsList other = (ConsList) o;  // never fails
//    return (other.first().equals(first)) && (other.rest().equals(rest));
    /* Imperative replacement for preceding line to avoid stack overflow.  The second
     * call on equals in a tail call but Java does not optimize it.  
     * Java type checking forces ugly code, even by imperative C standards. */
    ConsList thisList = this;
    do {
      if (! other.first.equals(thisList.first)) return false;
      
      // Address case where either other.rest or thisList.rest is empty
      if (other.rest instanceof EmptyList) return thisList.rest instanceof EmptyList;
      if (thisList.rest instanceof EmptyList) return false;
      
      other = (ConsList) other.rest;       // never fails
      thisList = (ConsList) thisList.rest; // never fails
    } while (true);
  }
  
  /** Constructs a Lisp-like String representation. */
  public String toString() { return "(" + first + rest.toStringHelp(); }
  /** Help function for toString that formats every element with a preceding space */
  public String toStringHelp() { return " " + first + rest.toStringHelp(); }
    
  public List reverse() { return reverseHelp(EmptyList.ONLY); }
  
  public List reverseHelp(List accum) { return rest.reverseHelp(accum.cons(first)); }
  
  public List insert(Comparable elt) { /* Your code goes here instead of: */ return null; }
  
  public List insertSort() { /* Your code goes here instead of: */ return null; } 
  
  public List merge(List right) { /* Your code goes here instead of: */ return null; }
    
  public List mergeHelp(ConsList other) { /* Your code goes here instead of: */ return null; }
  
  public Pair partition() { /* Your code goes here instead of: */ return null; } 
  
  public Pair partitionHelp(List left, List right) {/* Your code goes here instead of: */ return null; } 
  
  public List mergeSort() { /* Your code goes here instead of: */ return null; }
}