cmodule AModule {
  switchable S input = "STATICALAFLATTENLISTOFPAIRSLPAIRALLAOUTEMPTYLISTLLFORPAIRAPUNNULLLOUTADDPAOUTADDPBRETOUT";
  switchable S words = "ret ll ls static out list pair null";
  
  // basically immutable (we make a new copy for every step)
  // to allow evaluating states in parallel and in any order
  class GreedySplitIntoWordsCI_Multi implements IF0<Either<Iterable<GreedySplitIntoWordsCI_Multi>, LS>> {
    S s; // the input to be split
    TreeSet<S> wordsSet;
    Map<Int> longestMatchMap;
    int i = 0, last = 0;
    ReverseChain<S> out;
    
    *() {}
    *(S *s, Cl<S> words) {
      wordsSet = asCISet(words);
      longestMatchMap = AutoMap(i -> lengthOfLongestPrefixInCISet(substring(s, i), wordsSet));
    }
      
    // either we return some choices or a final result
    Either<Iterable<GreedySplitIntoWordsCI_Multi>, LS> get() {
      if (i >= l(s)) ret done(); // done with input
      
      int longestMatch = longestMatchMap.get(i);
      print("longestMatch at " + i + ": " + longestMatch);
      
      ret eitherA(listPlus(mapNonNulls(countBackwardsTo1(longestMatch), matchLength -> {
        if (!contains(wordsSet, substring(s, i, i+matchLength))) null;
        GreedySplitIntoWordsCI_Multi clone = shallowClone(this, new GreedySplitIntoWordsCI_Multi);
        clone.i = clone.last = i+longestMatch;
        clone.out = revChainPlus(out, substring(s, i, clone.i));
        ret clone;
      }), getVar(() -> {
        GreedySplitIntoWordsCI_Multi clone = shallowClone(this, new GreedySplitIntoWordsCI_Multi);
        clone.i++;
        ret clone;
      })));
    }

    Either<Iterable<GreedySplitIntoWordsCI_Multi>, LS> done() {
      flush();
      ret eitherB(asList(out));
    }

    void flush {
      if (i > last) {
        // modifying this object in spite of convention
        out = revChainPlus(out, substring(s, last, i));
        last = i;
      }
    }
    
    toString { ret out + ", " + i + "/" + l(s); }
  }
  
  visual jDynamicTree(
    new GreedySplitIntoWordsCI_Multi(input, splitAtSpace(words))!,
    x -> getVars(eitherAOpt(x)));
}