static class IndexedList extends AbstractList { new ArrayList l; MultiMap index; static bool debug; *() {} *(L x) { 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) { unindex(i); A prev = l.get(i); l.set(i, a); index(i); ret prev; } @Override public void add(int i, A a) { if (i != l.size()) { l.add(i, a); index = null; } else { l.add(i, a); index(i); } } @Override public A remove(int i) { A a = l.get(i); l.remove(i); index = null; ret a; } // speed up methods @Override protected void removeRange(int fromIndex, int toIndex) { l.subList(fromIndex, toIndex).clear(); index = null; } public int indexOf(O a) { ensureIndexed(); L positions = index.get((A) a); int n = l(positions); int min = -1; if (n != 0) { min = positions.get(0); for (int i = 1; i < n; i++) { int p = positions.get(i); if (p < min) min = p; } } if (debug) print("IndexedList.indexOf " + a + " => " + min); ret min; } @Override public bool contains(O a) { ensureIndexed(); bool b = index.containsKey((A) a); if (debug) print("IndexedList.contains " + a + " => " + b); ret b; } // indexing methods void unindex(int i) { if (index != null) index.remove(l.get(i), i); } void index(int i) { if (index == null) ensureIndexed(); else index.put(l.get(i), i); } void ensureIndexed() { if (index == null) { index = new MultiMap; int n = size(); for (int i = 0; i < n; i++) index.put(l.get(i), i); } } }