// optimized for search - O(1) for searching for a token
// set is O(log m) with m = number of occurrences of token
final sclass TokenIndexedList3 extends RandomAccessAbstractList<S> implements IContentsIndexedList<S>, IContentsIndexedList2<S> {
  final new HashMap<S, TreeSet<Token>> index; // tokens by contents, sorted by index
  final new ArrayList<Token> list;
  int reorderFrom = 0;

  final sclass Token extends HasIndex {
    S s; // actual token
    
    toString { ret "Token " + quote(s) + "@" + idx; }
  }
  
  *() {}
  *(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.idx = size();
    list.add(t);
    addToIdx(t);
    true;
  }
  
  public void add(int i, S s) {
    ++modCount;
    new Token t;
    t.s = s;
    t.idx = i;
    list.add(i, t);
    reorder(i+1);
    addToIdx(t);
  }
  
  public bool addAll(int i, Collection<? extends S> l) {
    int n = l.size();
    if (n == 0) false;
    ++modCount;
    L<Token> l2 = emptyList(n);
    int j = i;
    for (S s : l) {
      new Token t;
      t.s = s;
      t.idx = j++;
      l2.add(t);
    }
    list.addAll(i, l2);
    reorder(i+n);
    for (Token t : l2)
      addToIdx(t);
    true;
  }
  
  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) {
    if (reorderFrom < 0 || reorderFrom < fromIdx) reorderFrom = fromIdx;
  }
  
  void ensureReordered {
    ensureReorderedTo(size()-1);
  }
  
  // to = inclusive
  void ensureReorderedTo(int to) {
    if (reorderFrom > to) ret;
    for (int i = reorderFrom; i <= to; i++)
      list.get(i).idx = i;
    reorderFrom = to;
  }
  
  void removeFromIdx(Token t) {
    TreeSet<Token> idx = index.get(t.s);
    idx.remove(t);
    if (idx.isEmpty()) index.remove(t.s);
  }
  
  void addToIdx(Token t) {
    TreeSet<Token> idx = index.get(t.s);
    if (idx == null)
      index.put(t.s, idx = new TreeSet);
    idx.add(t);
  }
  
  @Override
  public int indexOf(O s) {
    TreeSet<Token> l = index.get(s);
    if (l == null) ret -1;
    Token t = first(l);
    ensureReorderedTo(t.idx);
    ret t.idx;
  }
  
  @Override
  public int lastIndexOf(O s) {
    TreeSet<Token> l = index.get(s);
    ret l == null ? -1 : last(l).idx;
  }
  
  @Override
  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;
    
    for (int i = fromIndex; i < toIndex; i++)
      removeFromIdx(list.get(i));
      
    list.subList(fromIndex, toIndex).clear();
    reorder(fromIndex);
  }
  
  public int[] indicesOf(O o) {
    TreeSet<Token> idx = index.get(o);
    if (idx == null) ret emptyIntArray();
    int[] a = new int[idx.size()];
    int i = 0;
    for (Token t : idx) a[i++] = t.idx;
    ret a;
  }
  
  public TreeSet<HasIndex> indicesOf_treeSetOfHasIndex(O o) {
    ret (TreeSet) index.get(o);
  }
}