sbool translateUsingWordTree_debug;
sbool translateUsingWordTree_printReplacements;

sS translateUsingWordTree(S input, Map<S, O> tree) {  
  ret empty(input) ? input : join(translateUsingWordTree(javaTok(input), tree));
}
  
static L<S> translateUsingWordTree(L<S> tok, Map<S, O> tree) {  
  for (int i = 1; i < l(tok); )
    i = translateUsingWordTree_scanFrom(tok, i, tree);
  ret tok;
}
      
// returns index of first unreplaced token
// every replacement ends up as a single token plus some ""
static int translateUsingWordTree_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 = def; bestIndex = j;
        //print("best solution: " + sfu(bestSolution));
      }
    }
   
    if (j >= l(tok)) break;
    
    O t = tree.get(tok.get(j));
    if (translateUsingWordTree_debug)
      print(i + "-" + j + " / " + joinSubList(tok, i, j+1) + " => " + sfu(t));
    if (t == null) break;
    if (t instanceof S) {
      int k = j+2;
      if (translateUsingWordTree_printReplacements)
        print("translateUsingWordTree: replacing " + sfu(subList(tok, i, k-1) + " with " + quote(t));
      replaceTokens(tok, i, k-1, (S) t);
      ret k;
    }
    tree = (Map) t;
    j += 2;
  }
  
  if (best != null) {
    int k = bestIndex;
    replaceTokens(tok, i, k-1, best);
    ret k;
  }
  ret i+2;
}



sS translateUsingWordTree(Map<S, O> tree, S input) {
  ret translateUsingWordTree(input, tree);
}