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

  }

}