static final class IndexedList2<A> extends ArrayList<A> {

  final new HashMap<A, Int> index;

  static int instances;

  *() { ++instances; }

  *(L<A> x) {

    this();

    ensureCapacity(l(x));

    addAll(x);

  }

  @Override

  public A set(int i, A a) {

    A prev = get(i);

    if (prev != a) {

      indexRemove(prev);

      indexAdd(a);

      super.set(i, a);

    }

    ret prev;

  }

  @Override

  public void add(int i, A a) {

    indexAdd(a);

    super.add(i, a);

  }

  @Override

  public bool add(A a) {

    indexAdd(a);

    ret super.add(a);

  }

  @Override

  public A remove(int i) {

    A a = get(i);

    indexRemove(a);

    super.remove(i);

    ret a;

  }

  public bool remove(O a) {

    int i = indexOf(a);

    if (i < 0) false;

    ret true with remove(i);

  }

  // speed up methods

  @Override  

  protected void removeRange(int fromIndex, int toIndex) {

    for (int i = fromIndex; i < toIndex; i++)

      unindex(i);

    super.removeRange(fromIndex, toIndex);

  }

  @Override

  public int indexOf(O a) {

    if (!contains(a)) ret -1;

    ret super.indexOf(a);

  }

  @Override

  public bool contains(O a) {

    ret index.containsKey(a);

  }

  @Override

  public void clear() {

    index.clear();

    super.clear();

  }

  @Override

  public bool addAll(int i, Collection<? extends A> c) {

    for (A a : c) indexAdd(a);

    ret super.addAll(i, c);

  }

  // indexing methods

  void unindex(int i) {

    indexRemove(get(i));

  }

  void indexAdd(A a) {

    Int i = index.get(a);

    index.put(a, i == null ? 1 : i+1);

  }

  void indexRemove(A a) {

    Int i = index.get(a);

    if (i != null && i > 1)

      index.put(a, i-1);

    else

      index.remove(a);

  }

  // static methods

  static <A> IndexedList2<A> ensureIndexed(L<A> l) {

    ret l instanceof IndexedList2 ? (IndexedList2) l : new IndexedList2(l);

  }

}