// A represents the return type of the backtrackable main computation

sclass BStack<A> extends VStack is IBStack<A> {

  static int idCounter;

  int stackID = ++idCounter; // for debugging

  // alternative to backtrack to

  BStack<A> alternative;

  // steps to undo before switching to the alternative

  L<AutoCloseable> undos;

  *() {}

  *(Computable<A> computation) { push(computation); }

  *(Iterable<Computable> l) { pushAll(l); }

  sclass NoOptionsException extends RuntimeException {}

  BStack<A> cloneStack() {

    new BStack<A> s;

    s.alternative = alternative;

    s.undos = undos;

    undos = null;

    s.stack = shallowCloneElements(stack);

    ret s;

  }

  public void addUndo(AutoCloseable undo) {

    if (undo == null) ret;

    if (undos == null) undos = new L;

    undos.add(undo);

  }

  public <B extends VStack.Computable> void options(B function,

    IVF1<B>... options) {

    options(function, asList(options));

  }

  public <B extends VStack.Computable> void options(B function, Iterable<IVF1<B>> options) {

    L<IVF1<B>> optionsList = nonNulls(options);

    if (empty(optionsList))

      throw new NoOptionsException;

    // All options except first are stored as alternatives

    // in cloned stacks.

    for (int i = l(optionsList)-1; i > 0; i--)

      setAlternative(optionsList.get(i));

    // Execute the first option

    first(optionsList).get(function);

  }

  srecord noeq ExecuteOption(IVF1 option) is VStack.Computable {

    public void step(VStack stack, O subComputationResult) {

      O target = stack.caller();

      stack.return();

      option.get(target);

    }

  }

  void setAlternative(IVF1 option) {

    alternative = cloneStack();

    alternative.push(new ExecuteOption(option));

  }

  // Try to backtrack one step and return a new stack

  // Returns null if no backtracking possible

  public BStack<A> backtrack() ctex {

    // Apply undos in reverse order

    for (int i = l(undos)-1; i >= 0; i--)

      undos.get(i).close();

    ret alternative;

  }

  public A nextResult() {

    stepAll(this);

    return (A) latestResult;

  }

  // calculate next result and print stack at every step

  public A nextResultWithPrintStruct(long maxSteps) {

    stepMaxWithPrintIndentedStruct(this, maxSteps);

    return (A) latestResult;

  }

}