// 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).

// This allows O(1) front insertion, front removal and back insertion

// (not removal at the back though) which is fine for what I need this

// for (event queues).

//

// Stefan Reich, Oct 21

sclass AppendableChain<A> extends MinimalChain<A> is Iterable<A>, IntSize {

  MinimalChain<A> last; // pointer to last element in chain (which may be us)

  gettable int size; // total length of chain

  *() {} // only used internally

  *(A *element) { size = 1; last = this; }

  // intermediate constructor called by itemPlusChain()

  *(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()); }

  // append at the end

  bool add(A a) {

    MinimalChain newLast = new MinimalChain(a);

    last.next = newLast;

    last = newLast;

    ++size;

    true;

  }

  // drop first element

  AppendableChain<A> popFirst() {

    if (next == null) null;

    element = next.element;

    if (last == next) last = this;

    next = next.next;

    --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;

  }

  //public Iterator<A> iterator() { ret toList().iterator(); }

  class ACIt > ItIt<A> {

    MinimalChain<A> c = AppendableChain.this;

    public bool hasNext() {

      ret c != null;

    }

    public A next() {

      var a = c.element;

      c = c.next;

      ret a;

    }

  }

  public ItIt<A> iterator() {

    ret new ACIt;

  }

}