// 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);
  }
}