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;

}