// 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

  bool dirty;

  *() {}

  *(Iterable<LS> toks) { addAll(toks); }

  void addAll(Iterable<LS> toks) {

    fOr (LS tok : toks)

      add(tok);

  }

  void add(LS tok) {

    for (int i = 1; i < l(tok); i += 2) {

      LL<S> idx = listGetOrCreate_List(sorts, i/2);

      idx.add(tok);

    }

    set dirty;

  }

  private void sort {

    for i over sorts: {

      int j = i*2+1;

      sortInPlaceByCalculatedFieldIC(sorts.get(i),

        func(LS tok) -> S { tok.get(j) });

    }

    dirty = false;

  }

  // return all tokenizations with token t in position i

  // may return null

  LLS byToken(int i, S t) {

    clean();

    LLS list = get(sorts, i);

    if (list == null) null;

    int start = binarySearchForStart(list, i, t);

    if (start < 0) null;

    int end = binarySearchForEnd(list, i, t, start);

    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 (mid == 0 || !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;

  }

  private int binarySearchForEnd(LLS list, int position, S t, int start) {

    int low = start+1, high = list.size()-1;

    while (low <= high) {

      int mid = (low + high) >>> 1;

      S token = list.get(mid).get(position*2+1);

      if (eqic(token, t))

        low = mid + 1; // still in target range, go lower

      else // we found a different token, now check if we're at the end

        if (mid-1 == start || eqic(list.get(mid-1).get(position*2+1), t))

          ret mid; // yep, it's the end

        else

          high = mid - 1; // continue to search higher up

    }

    ret low;

  }

  LLS fullList() { ret first(sorts); }

  // if you want to sort it ahead of time

  void clean() {

    if (dirty) sort();

  }

}