// clever index of tokenized strings
// maintaining one CI-sorted list per token position
sclass PositionalTokenIndex {
  L<LLS> sorts = new L; // token index -> entries sorted by token at index
  
  *() {}
  *(Iterable<LS> toks) { addAll(toks); }
  
  void addAll(Iterable<LS> toks) {
    if (empty(toks)) ret;
    for (LS tok : toks)
      for (int i = 1; i < l(tok); i += 2) {
        LL<S> idx = listGetOrCreate_List(sorts, i/2);
        idx.add(tok);
      }
    sort();
  }
  
  private void sort {
    for i over sorts: {
      int j = i*2+1;
      sortInPlaceByCalculatedFieldIC(sorts.get(i),
        func(LS tok) -> S { tok.get(j) });
    }
  }
  
  // return all tokenizations with token t in position i
  // may return null
  LLS byToken(int i, S t) {
    LLS list = get(sorts, i);
    if (list == null) null;
    
    int start = binarySearchForStart(list, i, t);
    if (start < 0) null;
    
    // TODO: do more binary search here
    int end = mid+1;
    int l = l(list);
    while (end < l && eqic(list.get(end).get(i*2+1), t)) ++end;
    ret subList(list, start, end);
  }
  
  private int binarySearchForStart(LLS list, int position, S t) {
    int low = 0, high = list.size()-1;
    while (low <= high) {
      int mid = (low + high) >>> 1;
      S token = list.get(mid).get(position*2+1);
      int cmp = compareIC(token, t);

      if (cmp < 0)
        low = mid + 1;
      else if (cmp > 0)
        high = mid - 1;
      else // we found the target token, now check if we're at start
        if (!eqic(list.get(mid-1).get(position*2+1), t))
          ret mid; // yep, it's the start
        else
          high = mid - 1; // continue to search higher up
    }
    ret -1;
  }
}