sclass ProbabilisticMachine<A extends ProbabilisticMachine.State> {

  transient TreeSetWithDuplicates<A> doneStates = new(byProbability());

  transient TreeSetWithDuplicates<A> states = new(byProbability());

  transient TreeSetWithDuplicates<A> steppableStates = new(byProbability());

  transient TreeSetWithDuplicates<A> droppedStates = new(byProbability());

  transient int stateCount;

  bool verbose;

  double cutoffPercentage = 50;

  Comparator<A> byProbability() { ret (a, b) -> cmp(b.probability, a.probability); }

  abstract sclass State {

    ProbabilisticMachine machine;

    int number;

    State prev;

    double probability = 100;

    BasicLogicRule remainingRule;

    toString {

      ret toStringWithFields(this, "number", "probability") + stringIf(done(), " (done)";

    }

    bool done() { ret remainingRule == null; }

    O action() { ret remainingRule == null ? null : remainingRule.lhs; }

    void step { if (!done()) runAction(action()); }

    abstract void runAction(O action);

    abstract State emptyClone();

    State prepareClone() {

      State s = emptyClone();

      copyFields(this, s, 'machine, 'probability);

      s.prev = this;

      s.remainingRule = optCast BasicLogicRule(remainingRule.rhs);

      ret s;

    }

  }

  void addState(A s) {

    if (verbose) print("Adding state to machine " + this + ": " + s);

    s.machine = this;

    if (s.number == 0) s.number = ++stateCount;

    if (s.probability < cutoffPercentage) ret with droppedStates.add(s);

    addToCollections(s, states, steppableStates);

    if (s.done()) doneStates.add(s);

    if (verbose) printStats();

  }

  bool stepFirstUnstepped() {

    A s = popFirst(steppableStates), ret false if null;

    ret true with s.step();

  }

  void reset {

    clearAll(doneStates, states, steppableStates, droppedStates);

    stateCount = 0;

  }

  void think {

    while ping (stepFirstUnstepped()) {}

  }

  L<A> bestStates(int n) {

    ret takeFirst(n, doneStates);

  }

  void printStats() {

    print("States: " + stats(states) + ", done: " + stats(doneStates) + ", steppable: " + stats(steppableStates) + ", dropped: " + stats(droppedStates));

  }

  S stats(TreeSetWithDuplicates<A> ts) {

    ret l(ts) + (empty(ts) ? "" : " (best: " + iround(first(ts).probability) + ")");

  }

}