static final class IndexedList2 extends AbstractList { new ArrayList l; MultiSet index = new MultiSet(false); // HashMap static bool debug; static int instances; *() { ++instances; } *(L 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 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 IndexedList2 ensureIndexed(L l) { ret l instanceof IndexedList2 ? (IndexedList2) l : new IndexedList2(l); } }