// optimized for search - O(1) for searching for a token

// set is O(m) with m = number of occurrences of token

// This could be improved to O(log m) by using a TreeSet instead of the L in the index

final sclass TokenIndexedList2 extends RandomAccessAbstractList<S> {

  new Map<S, L<Token>> index; // tokens are in order

  new L<Token> list;

  sclass Token {

    int i; // index in list

    S s; // actual token

  }

  *() {}

  *(Collection<S> l) { addAll(l); }

  public S get(int i) { ret list.get(i).s; }

  public int size() { ret list.size(); }

  public S set(int i, S s) {

    Token t = list.get(i);

    S old = t.s;

    if (eq(old, s)) ret old;

    removeFromIdx(t);

    t.s = s;

    addToIdx(t);

    ret old;

  }

  public bool add(S s) {

    ++modCount;

    new Token t;

    t.s = s;

    t.i = size();

    list.add(t);

    addToIdx(t);

    true;

  }

  public void add(int i, S s) {

    ++modCount;

    new Token t;

    t.s = s;

    t.i = i;

    list.add(i, t);

    reorder(i+1);

    addToIdx(t);

  }

  public S remove(int i) {

    ++modCount;

    Token t = list.get(i);

    removeFromIdx(t);

    list.remove(i);

    reorder(i);

    ret t.s;

  }

  void reorder(int fromIdx) {

    int n = size();

    for (int i = fromIdx; i < n; i++)

      list.get(i).i = i;

  }

  void removeFromIdx(Token t) {

    L<Token> idx = index.get(t.s);

    int i = Collections.binarySearch(idx, t, comparator());

    idx.remove(i);

    if (empty(idx)) index.remove(t.s);

  }

  void addToIdx(Token t) {

    L<Token> idx = index.get(t.s);

    if (idx == null)

      index.put(t.s, idx = new L);

    int i = -1-Collections.binarySearch(idx, t, comparator());

    idx.add(i, t);

  }

  Comparator<Token> comparator() {

    ret (Comparator<Token>) (a, b) -> b.i-a.i;

  }

  public int indexOf(S s) {

    L<Token> l = index.get(s);

    ret l == null ? -1 : l.get(0).i;

  }

  public bool contains(O s) {

    ret index.containsKey(s);

  }

  public void clear() {

    ++modCount;

    index.clear();

    list.clear();

  }

  protected void removeRange(int fromIndex, int toIndex) {

    if (fromIndex == toIndex) ret;

    ++modCount;

    // TODO: this can be optimized

    for (int i = fromIndex; i < toIndex; i++)

      removeFromIdx(list.get(i));

    list.subList(fromIndex, toIndex).clear();

    reorder(fromIndex);

  }

}