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);

}