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
  }
  
  public S get(int i) { ret list.get(i).s; }
  public int size() { ret list.size(); }
  
  public void set(int i, S s) {
    Token t = list.get(i);
    if (eq(t.s, s)) ret;
    
    // remove from index
    removeFromIdx(token);
      
    // change token, add to chain
    t.s = s;
    addToIdx(token);
  }
  
  void removeFromIdx(Token t) {
    L<Token> idx = index.get(t.s);
    if (idx == null) ret;
    idx.remove(t); // TODO: binary search
    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;
  }
}