static final class IndexedList2<A> extends AbstractList<A> {
  new ArrayList<A> l;
  MultiSet<A> index = new MultiSet(false); // HashMap
  static bool debug;
  static int instances;
  
  *() {
    ++instances;
  }
  
  *(L<A> x) {
    this();
    l.ensureCapacity(l(x));
    addAll(x);
  }
  
  // required immutable list methods
  
  @Override
  public A get(int i) {
    ret l.get(i);
  }
  
  @Override
  public int size() {
    ret l.size();
  }
  
  // required mutable list methods
  
  @Override
  public A set(int i, A a) {
    A prev = l.get(i);
    if (prev != a) {
      index.remove(prev);
      index.add(a);
    }
    l.set(i, a);
    ret prev;
  }
  
  @Override
  public void add(int i, A a) {
    index.add(a);
    l.add(i, a);
  }
  
  @Override
  public A remove(int i) {
    A a = l.get(i);
    index.remove(a);
    l.remove(i);
    ret a;
  }
  
  // speed up methods

  @Override  
  protected void removeRange(int fromIndex, int toIndex) {
    for (int i = fromIndex; i < toIndex; i++)
      unindex(i);
    l.subList(fromIndex, toIndex).clear();
  }
  
  @Override
  public int indexOf(O a) {
    if (!contains(a)) ret -1;
    ret l.indexOf(a);
  }
  
  @Override
  public bool contains(O a) {
    bool b = index.contains((A) a);
    if (debug) print("IndexedList2.contains " + a + " => " + b);
    ret b;
  }
  
  @Override
  public void clear() {
    index.clear();
    l.clear();
  }
  
  @Override
  public bool addAll(int i, Collection<? extends A> c) {
    index.addAll((Collection) c);
    ret l.addAll(i, c);
  }
  
  // indexing methods
  
  void unindex(int i) {
    index.remove(l.get(i));
  }
  
  void index(int i) {
    index.add(l.get(i));
  }
  
  // static methods
  
  static <A> IndexedList2<A> ensureIndexed(L<A> l) {
    ret l instanceof IndexedList2 ? (IndexedList2) l : new IndexedList2(l);
  }
}