interface Seq {
  Seq empty();
  // returns Seq that is empty

  Seq cons(Object newElt);
  // returns the Seq with elts newElt, s[0], ..., s[n]

  Object first();       // returns the element s[0]
  Seq rest();           // returns a Seq representing s[1], ..., s[n]
  Object eltAt(int i);  // returns the element s[i]
  boolean isEmpty();    // returns n == 0  

  public Object execute(SeqVisitor host);  // applies the visitor code host
}

interface SeqVisitor {
  Object forEmpty(Seq host);
  Object forCons(Seq host);
}

interface MutSeq extends Seq {
  void setFirst(Object f);         // changes this.first = f 
  void setRest(MutSeq r);          // changes this.rest = r
  void set(MutSeq m);              // changes this = m
  void setEltAt(int i, Object val);     // changes this[i] = val
  void insert(Object o);           // changes this.first,this.rest = o,this
  void remove();                   // changes this = this.rest
  Object execute(MutSeqVisitor m); // applies visitor operation m to this
}

interface MutSeqVisitor {
  Object forEmpty(MutSeq host);
  Object forCons(MutSeq host);
}

class QuasiList implements MutSeq {

  private List value;

  /* constructor */
  QuasiList() { value = new Empty(); }
  private QuasiList(List v) { value = v; }

  /* visible methods */
  public Seq empty() { return new QuasiList(); }
  public Seq cons(Object newElt) { return new QuasiList(value.cons(newElt)); }
  public Object first() { return value.first(); }
  public MutSeq rest() { return value.rest(); }
  // rest returns a MutSeq (QuasiList) but the Seq interface mandates
  //   the weaker type!

  public Object eltAt(int i) { return value.eltAt(i); }
  public boolean isEmpty() { return value.isEmpty(); }
  public void insert(Object o) { value = new Cons(o, new QuasiList(value)); }

  public String toString() { return value.toString(); }

  public void setFirst(Object o) { value = value.updateFirst(o); }

  public void setRest(MutSeq m) { value = value.updateRest(m); }

  public void set(MutSeq m) { value = m.value; }

  public void setEltAt(int i, final Object val) {  
    /* inner class */
    class UpdateEltAt implements MutSeqVisitor {
      /* fields */
      final int index;       // index of element to be updated

      /* constructor */
      UpdateEltAt(int i) { index = i; }

      /* visit methods */
      Object forEmpty(MutSeq host) { throw
        new IllegalArgumentException("out-of-bounds index in UpdateEltAt");
      }
      Object forCons(MutSeq host) {
        if (index == 0) return host.setFirst(val);
        else return host.rest().execute(new UpdateEltAt(index-1));
      }
    }
    execute(new UpdateEltAt(i));  
  }

  public void remove() { value = value.rest(); }

  public Object execute(SeqVisitor v) { return value.execute(v); }
  // apply visitor v to value and return result; value is UNCHANGED

  public Object execute(MutSeqVisitor v) { return value.execute(v,this); }
  // apply visitor v to value and return result; value may be CHANGED

  /* inner classes */
  private interface List {
    abstract String toStringHelp();
    // List -> String without any parentheses and leading blanks
  }

  private class Empty extends List {

    /* constructor */
    private Empty() {}  

    /* methods */
    Object first() { 
    throw new IllegalArgumentException("first() applied to empty list");
    }
    MutSeq rest() { 
    throw new IllegalArgumentException("rest() applied to empty list");
    }
    Object eltAt(int i) { 
      throw new IllegalArgumentException("out-of-bounds index in List.eltAt"); 
    }
    Object execute(SeqVisitor v) { return v.forEmpty(this); }
    Object execute(MutSeqVisitor v) { return v.forEmpty(QuasiList.this); }
    public String toString() { return "()"; }
    public String toStringHelp() { return ""; }
  }

  private class Cons extends List {

    /* fields */
    private final Object first;
    private final MutSeq rest;

    /* constructor */
    Cons(Object f, List r) {
      first = f;
      rest = r;
    }

    /* functional methods */
    Object first() { return first; }
    Seq rest() { return rest; }
    /* MutSeq is the correct output type but Java does not support it */

    Object eltAt(int i) { 
      if (0 == i) return first;
      else return rest.eltAt(i-1);
    }

    /* mutator methods */
    void setFirst(Object o) { first = o; }

    Object execute(SeqVisitor v) { v.forCons(this); }
    Object execute(MutSeqVisitor v) { v.forCons(QuasiList.this); }

    public String toString() { 
      return "(" + first + rest.toStringHelp() + ")"; }
    String toStringHelp() { return " " + first + rest.toStringHelp(); }
  } 

}