sbool translateUsingWordTreeC_debug;

sbool translateUsingWordTreeC_printReplacements;

static L<S> translateUsingWordTreeC(L<S> tok, Map<S, O> tree) {  

  for (int i = 0; i < l(tok); )

    i = translateUsingWordTreeC_scanFrom(tok, i, tree);

  ret tok;

}

// returns index of first unreplaced token

// every replacement ends up as a single token plus some ""

static int translateUsingWordTreeC_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 (translateUsingWordTreeC_debug)

      print(i + "-" + j + " / " + joinWithSpace(subList(tok, i, j+1)) + " => " + sfu(t));

    if (t == null) break;

    if (t instanceof S) {

      int k = j+1;

      if (translateUsingWordTreeC_printReplacements)

        print("translateUsingWordTreeC: replacing " + sfu(subList(tok, i, k-1) + " with " + quote(t));

      replaceTokens(tok, i, k, (S) t);

      ret k;

    }

    tree = (Map) t;

    j++;

  }

  if (best != null) {

    int k = bestIndex;

    if (translateUsingWordTreeC_printReplacements)

      print("translateUsingWordTreeC: replacing " + sfu(subList(tok, i, k) + " with " + quote(best));

    replaceTokens(tok, i, k, best);

    ret k;

  }

  ret i+1;

}