sbool groupUsingWordTree_debug;
sbool groupUsingWordTree_printReplacements;

sS groupUsingWordTree(S input, Map<S, O> tree) {  
  ret join(groupUsingWordTree(javaTok(input), tree));
}
  
static L<S> groupUsingWordTree(L<S> tok, Map<S, O> tree) {  
  for (int i = 1; i < l(tok); )
    i = groupUsingWordTree_scanFrom(tok, i, tree);
  ret tok;
}
      
// returns index of first unreplaced token
// every replacement ends up as a single token plus some ""
static int groupUsingWordTree_scanFrom(L<S> tok, int i, Map<S, O> tree) {
  int j = i;
  S best = null; // best replacement found
  int bestIndex = 0; // till where to replace
  
  while true {
    if (j > i) { // no default in root!
      S def = cast tree.get("<default>");
      if (def != null) {
        best = join(subList(tok, i, j+1)); bestIndex = j;
        //print("best solution: " + sfu(bestSolution));
      }
    }
   
    if (j >= l(tok)) break;
    
    O t = tree.get(tok.get(j));
    if (groupUsingWordTree_debug)
      print(i + "-" + j + " / " + joinSubList(tok, i, j+1) + " => " + sfu(t));
    if (t == null) break;
    if (!t instanceof Map) {
      int k = j+2;
      
      // skip if already grouped
      if (!(eqGet(tok, i-2, "{") && eqGet(tok, k, "}"))) {
        LS subList = subList(tok, i, k-1);
        S replacement = curly(join(subList));
        if (groupUsingWordTree_printReplacements)
          print("groupUsingWordTree: replacing " + sfu(subList) + " with " + quote(replacement));
        replaceTokens(tok, i, k-1, replacement);
      }
      ret k;
    }
    tree = (Map) t;
    j += 2;
  }
  
  if (best != null) {
    int k = bestIndex;
    replaceTokens(tok, i, k-1, best);
    ret k;
  }
  ret i+2;
}