// optimized for search - O(1) for searching for a certain element // set is O(log m) with m = number of occurrences of element final sclass CalculatedFieldIndexedList extends RandomAccessAbstractList { new Map>> index; // elements by calculated field, sorted by index final new ArrayList> list; IF1 f; // element to "key" (calculated field) final sclass Elem extends HasIndex { A s; // actual element toString { ret "Elem " + quote(s) + "@" + idx; } } *(IF1 *f) {} *(IF1 *f, Map>> *index) {} // use different type of index (e.g. ciMap) *(IF1 *f, Cl l) { addAll(l); } public A get(int i) { ret list.get(i).s; } public int size() { ret list.size(); } public A set(int i, A s) { Elem t = list.get(i); A old = t.s; if (eq(old, s)) ret old; removeFromIdx(t); t.s = s; addToIdx(t); ret old; } public bool add(A s) { ++modCount; new Elem t; t.s = s; t.idx = size(); list.add(t); addToIdx(t); true; } public void add(int i, A s) { ++modCount; new Elem t; t.s = s; t.idx = i; list.add(i, t); reorder(i+1); addToIdx(t); } public bool addAll(int i, Collection l) { int n = l.size(); if (n == 0) false; ++modCount; L> l2 = emptyList(n); int j = i; for (A s : l) { new Elem t; t.s = s; t.idx = j++; l2.add(t); } list.addAll(i, l2); reorder(i+n); for (Elem t : l2) addToIdx(t); true; } public A remove(int i) { ++modCount; Elem t = list.get(i); removeFromIdx(t); list.remove(i); reorder(i); ret t.s; } void reorder(int fromIdx) { int n = size(); for (int i = fromIdx; i < n; i++) list.get(i).idx = i; } void removeFromIdx(Elem t) { B key = calc(t); var idx = index.get(key); idx.remove(t); if (idx.isEmpty()) index.remove(key); } void addToIdx(Elem t) { B key = calc(t); var idx = index.get(key); if (idx == null) index.put(key, idx = new TreeSet); idx.add(t); } public A getByKey(B key) { var l = index.get(key); ret l == null ?: first(l).s; } // doesn't return null public L getAllByKey(B key) { var l = index.get(key); ret l == null ? emptyList() : map(l, x -> x.s); } public int indexOfKey(B key) { var l = index.get(key); ret l == null ? -1 : first(l).idx; } @Override public int lastIndexOf(O s) { TreeSet> l = index.get(s); ret l == null ? -1 : last(l).idx; } @Override public bool contains(O s) { ret index.containsKey(s); } public void clear() { ++modCount; index.clear(); list.clear(); } protected void removeRange(int fromIndex, int toIndex) { if (fromIndex == toIndex) ret; ++modCount; for (int i = fromIndex; i < toIndex; i++) removeFromIdx(list.get(i)); list.subList(fromIndex, toIndex).clear(); reorder(fromIndex); } public int[] indicesOfKey(B o) { TreeSet> idx = index.get(o); if (idx == null) ret emptyIntArray(); int[] a = new int[idx.size()]; int i = 0; for (Elem t : idx) a[i++] = t.idx; ret a; } B calc(A a) { ret f.get(a); } B calc(Elem a) { ret f.get(a.s); } }