package iterator.listfour;
import java.util.NoSuchElementException;
import java.util.ConcurrentModificationException;

/* public */
interface MutList {
  public Iterator newIterator();
  public void insert(int i); // insert i at head of list
  public void delete(int i); // delete first occurence of i in the list
}

/* public */
interface Iterator {
  public boolean hasNext();
  public int next();
}

/* public */
class MutListF {
  private MutListF() {}
  public static final MutList newI() {
    return new MutListObj();
  }
}

class MutListObj implements MutList, Changeable {
  private List l = ListF.nil;
  private int changeCount = 0;
  public int changeCount() { return changeCount; }
  public Iterator newIterator() { return l.newIterator(this); }
  public String toString() { return l.toString(); }
  public void insert(int i) {
    changeCount++;
    l = l.insert(i);
  }
  public void delete(int i) {
    changeCount++;
    l = l.delete(i);
  }
}

/*
 *************************************************************************
 * Immutable List classes.
 *************************************************************************
 */
interface Changeable {
  public int changeCount();
}

interface List {
  public Iterator newIterator(Changeable parent);
  public List insert(int i);
  public List delete(int i);
}

class ListF {
  private ListF() {}
  public static final List nil = new Nil(); /* Singleton */
  public static final List cons(int hd, List tl) /* Factory */ {
    return new Cons(hd, tl);
  }
}

class Nil implements List {
  Nil() {}
  public String toString() { return "nil"; }
  public Iterator newIterator(Changeable parent) {
    return new NullIterator();
  }
  public List insert(int i) {
    return ListF.cons(i, this);
  }
  public List delete(int i) {
    throw new NoSuchElementException();
  }
}

class Cons implements List {
  final int hd;
  final List tl;
  Cons(int hd, List tl) { this.hd = hd; this.tl = tl; }
  public String toString() { return hd + "::" + tl.toString(); }
  public Iterator newIterator(Changeable parent) {
    return new ListIterator(this, parent);
  }
  public List insert(int i) {
    return ListF.cons(i, this);
  }
  public List delete(int i) {
    if (hd == i) {
      return tl;
    } else {
      List new_tl = tl.delete(i);
      return ListF.cons(hd, new_tl);
    }
  }
}

class NullIterator implements Iterator {
  NullIterator() { }
  public boolean hasNext() { return false; }
  public int next() { throw new NoSuchElementException(); }
}

class ListIterator implements Iterator {
  private List node;
  private Changeable parent;
  private int changeCount;
  ListIterator(List node, Changeable parent) {
    this.node = node;
    this.parent = parent;
    this.changeCount = parent.changeCount();
  }
  public boolean hasNext() {
    if (changeCount != parent.changeCount())
      throw new ConcurrentModificationException();
    return node != ListF.nil;
  }
  public int next() {
    if (changeCount != parent.changeCount())
      throw new ConcurrentModificationException();
    if (! hasNext())
      throw new NoSuchElementException();
    int result = ((Cons)node).hd;
    node = ((Cons)node).tl;
    return result;
  }
}

/*
 *************************************************************************
 * A test case.
 *************************************************************************
 */
public class Main {
  public static void main(String[] args) {
    MutList test = MutListF.newI();
    test.insert(3);
    test.insert(2);
    test.insert(1);
    System.out.println(test);

    int sum=0;
    for (Iterator i = test.newIterator(); i.hasNext(); )
      sum += i.next();
    System.out.println(sum);

    List rev=ListF.nil;
    for (Iterator i = test.newIterator(); i.hasNext(); )
      rev = ListF.cons(i.next(),rev);
    System.out.println(rev);

    for (Iterator i = test.newIterator(); i.hasNext(); )
      test.insert(4);
  }
}