// optimized for search - O(1) for searching for a token
// set & add are worse than ArrayList - O(m) with m = number of occurrences of token
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 S set(int i, S s) {
    Token t = list.get(i);
    S old = t.s;
    if (eq(old, s)) ret old;
    
    // remove from index
    removeFromIdx(t);
      
    // change token, add to chain
    t.s = s;
    addToIdx(t);
    ret old;
  }
  
  public bool add(S s) {
    new Token t;
    t.s = s;
    t.i = size();
    list.add(t);
    addToIdx(t);
  }
  
  public void add(int i, S s) {
    new Token t;
    t.s = s;
    t.i = i;
    list.add(i, t);
    reorder(i+1);
    addToIdx(t);
    true;
  }
  
  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);
    if (idx == null) ret;
    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;
  }
}