// AppendableChain has one "smart" head element (with size counter
// and pointer to the chain's last element), all the other nodes are
// maximally simple (MinimalChain).
sclass AppendableChain<A> {
  A element;
  MinimalChain<A> next;
  MinimalChain<A> last; // pointer to last element in chain (null if we are is the last element)
  int size; // total length of chain

  *() {} // only used internally
  *(A *element) { size = 1; last = this; }
  
  *(A *element, AppendableChain<A> *next) {
    if (next == null) ret;
    
    new MinimalChain<A> b;
    b.element = next.element;
    b.next = next.next;
    this.next = b;
    last = next.last;
    size = next.size+1;
  }
  
  toString { ret str(toList()); }
  
  bool add(A a) {
    MinimalChain newLast = new MinimalChain(a, null);
    last.next = newLast;
    last = newLast;
    ++size;
    true;
  }
  
  AppendableChain<A> popFirst() {
    if (next == null) null;
    var copyingFrom = next;
    element = copyingFrom.element;
    next = copyingFrom.next;
    if (last == copyingFrom) last = this;
    --size;
    this;
  }
  
  ArrayList<A> toList() {
    ArrayList<A> l = emptyList(size);
    MinimalChain<A> c = this;
    while (c != null) {
      l.add(c.element);
      c = c.next;
    }
    ret l;
  }
  
  // TODO: optimize
  public Iterator<A> iterator() { ret toList().iterator(); }
}