// Backtracking-enabled stacks (BStacks) are very useful for AI
// computation because they allow inserting a branching point anywhere
// in a computation, even deep inside nested function calls and loops.
//
// BStacks normally operate serially, always exploring the main branch first
// and then optionally backtracking afterwards.
//
// However, the only thing preventing a BStack from backtracking in
// parallel to the main computation is the use of external mutable
// objects. With sufficient cloning of these objects at a branch point
// and/or the use of immutable data structures, there is no obstacle to
// parallelizing.
//
// A further evolution of BStacks are PStacks. In PStacks, at any point
// in time, every ongoing or potential computation is listed with a
// probability value p (usually 0 < p <= 1).
//
// This "table of possible computations or continuations of computations"
// constantly sorts itself by decreasing probability, so computations
// with higher probability can be pursued first.
//
// The code in this class is based on BStack_v3.
//
// PStack doesn't support undos because those only make sense in
// serial execution.

sclass PStack<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;
  
  *() {}
  *(Computable<A> computation) { push(computation); }
  *(Iterable<Computable> l) { pushAll(l); }
  
  selfType cloneStack() {
    new selfType s;
    s.snapshot = snapshot;
    s.options = options;
    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 <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 {
    // 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 {}
}