// A represents the return type of the backtrackable main computation
sclass BStack<A> extends VStack {
  static int idCounter;
  int stackID = ++idCounter; // for debugging
  
  // alternative to backtrack to
  BStack alternative;
  
  // steps to undo before switching to the alternative
  L<AutoCloseable> undos;
  
  *() {}
  *(Computable<A> computation) { push(computation); }
  *(Iterable<Computable> l) { pushAll(l); }
  
  BStack cloneStack() {
    new BStack s;
    s.stack = shallowCloneElements(stack);
    ret s;
  }
  
  void addUndo(AutoCloseable undo) {
    if (undo == null) ret;
    if (undos == null) undos = new L;
    undos.add(undo);
  }
  
  <A extends VStack.Computable> void options(A function,
    IVF1<A>... options) {
    // Check if there is more than one option
    if (l(options) > 1) {
      // Then remember this option in a cloned stack
      IVF1<A> option2 = second(options);
      saveAlternative(clonedStack -> {
        A clonedFunction = (A) nextToLast(clonedStack.stack);
        option2.get(clonedFunction);
      });
    }

    // Execute the first option
    first(options).get(function);
  }
  
  record noeq ExecuteOption(IVF1<BStack<A>> option) is VStack.Computable {
    public void step(VStack stack, O subComputationResult) {
      option.get((BStack) stack);
      stack.return();
    }
  }
  
  void saveAlternative(IVF1<BStack<A>> option) {
    alternative = cloneStack();
    alternative.push(new ExecuteOption(option));
  }
  
  // Try to backtrack one step and return a new stack
  // Returns null if no backtracking possible
  BStack backtrack() ctex {
    if (undos != null)
      for (undo : reversed(getAndClearList(undos)))
        undo.close();
        
    ret alternative;
  }
  
  A nextResult() {
    stepAll(this);
    return (A) latestResult;
  }
  
  // calculate next result and print stack at every step
  A nextResultWithPrintStruct(long maxSteps) {
    stepMaxWithPrintStruct(this, maxSteps);
    return (A) latestResult;
  }
}