// This backtracking-enabled stack (BStack) postpones cloning stack

// frames as long as possible.

// More specifically, only the current top frame is actually mutable.

// Some stack frames below (from 0 up to clonePointer) may not be

// cloned yet, and are cloned (=made mutable) by the pop() function.

// The tests (test_BStack_v3) pass, but they might not test the lazy

// cloning. So for safety, stick with BStack_v2 until there are more

// tests for BStack_v3.

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

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

  static int idCounter;

  int stackID = ++idCounter; // for debugging

  // elements at this index and below must be cloned before use

  int clonePointer = -1;

  // cloned version made at last branch point

  selfType snapshot;

  // remaining options at last branch point

  Iterator<IVF1> options;

  // steps to undo before switching to the alternative

  L<AutoCloseable> undos;

  *() {}

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

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

  selfType cloneStack() {

    new selfType s;

    s.snapshot = snapshot;

    s.options = options;

    s.undos = undos;

    undos = null;

    s.stack = cloneList(stack);

    // Directly clone current function, clone older stack entries

    // lazily.

    replaceLast(s.stack, shallowClone(last(stack)));

    clonePointer = l(stack)-2;

    ret s;

  }

  public void addUndo(AutoCloseable undo) {

    if (undo == null || snapshot == 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, arrayIterator(options));

  }

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

    Iterator<IVF1<B>> iterator = nonNullIterator(iterator(options));

    if (!iterator.hasNext())

      throw new NoOptionsException;

    IVF1<B> firstOption = iterator.next();

    // All options except first are stored as alternatives

    // in cloned stacks.

    setOptions(iterator);

    // Execute the first option

    firstOption.get(function);

  }

  <B> void setOptions(Iterator<IVF1<B>> options) {

    snapshot = cloneStack();

    this.options = (Iterator) options;

  }

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

  // Returns null if no backtracking possible

  public selfType backtrack() ctex {

    // Apply undos in reverse order

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

      undos.get(i).close();

    // no more options? done

    if (options == null || !options.hasNext()) null;

    // get snapshot and option to execute

    selfType nextStack = snapshot;

    var option = options.next();

    // If there are more options in the list, make another clone

    // of the snapshot

    bool moreOptions = options.hasNext();

    if (moreOptions) {

      nextStack = new selfType;

      nextStack.stack = shallowCloneElements(snapshot.stack);

      nextStack.snapshot = snapshot;

      nextStack.options = options;

    }

    nextStack.push(new ExecuteOption(option));

    ret nextStack;

  }

  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;

  }

  protected void pop :: after {

    int idx = l(stack)-1;

    // Clone the new top stack frame if necessary

    if (idx >= 0 && idx == clonePointer) {

      stack.set(idx, shallowClone(stack.get(idx)));

      --clonePointer;

    }

  }

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

    public void step(VStack stack, O subComputationResult) {

      O target = stack.caller();

      stack.return();

      option.get(target);

    }

  }

  sclass NoOptionsException extends RuntimeException {}

}