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