// optimized for search - O(1) for searching for a token // set is O(log m) with m = number of occurrences of token final sclass TokenIndexedList3 extends RandomAccessAbstractList<S> implements IContentsIndexedList<S>, IContentsIndexedList2<S> { final new HashMap<S, TreeSet<Token>> index; // tokens by contents, sorted by index final new ArrayList<Token> list; int reorderFrom = 0; final sclass Token extends HasIndex { S s; // actual token toString { ret "Token " + quote(s) + "@" + idx; } } *() {} *(Collection<S> l) { addAll(l); } public S get(int i) { ret list.get(i).s; } public int size() { ret list.size(); } public S set(int i, S s) { Token t = list.get(i); S old = t.s; if (eq(old, s)) ret old; removeFromIdx(t); t.s = s; addToIdx(t); ret old; } public bool add(S s) { ++modCount; new Token t; t.s = s; t.idx = size(); list.add(t); addToIdx(t); true; } public void add(int i, S s) { ++modCount; new Token t; t.s = s; t.idx = i; list.add(i, t); reorder(i+1); addToIdx(t); } public bool addAll(int i, Collection<? extends S> l) { int n = l.size(); if (n == 0) false; ++modCount; L<Token> l2 = emptyList(n); int j = i; for (S s : l) { new Token t; t.s = s; t.idx = j++; l2.add(t); } list.addAll(i, l2); reorder(i+n); for (Token t : l2) addToIdx(t); true; } public S remove(int i) { ++modCount; Token t = list.get(i); removeFromIdx(t); list.remove(i); reorder(i); ret t.s; } void reorder(int fromIdx) { if (reorderFrom < 0 || reorderFrom < fromIdx) reorderFrom = fromIdx; } void ensureReordered { ensureReorderedTo(size()-1); } // to = inclusive void ensureReorderedTo(int to) { if (reorderFrom > to) ret; for (int i = reorderFrom; i <= to; i++) list.get(i).idx = i; reorderFrom = to; } void removeFromIdx(Token t) { TreeSet<Token> idx = index.get(t.s); idx.remove(t); if (idx.isEmpty()) index.remove(t.s); } void addToIdx(Token t) { TreeSet<Token> idx = index.get(t.s); if (idx == null) index.put(t.s, idx = new TreeSet); idx.add(t); } @Override public int indexOf(O s) { TreeSet<Token> l = index.get(s); if (l == null) ret -1; Token t = first(l); ensureReorderedTo(t.idx); ret t.idx; } @Override public int lastIndexOf(O s) { TreeSet<Token> 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[] indicesOf(O o) { TreeSet<Token> idx = index.get(o); if (idx == null) ret emptyIntArray(); int[] a = new int[idx.size()]; int i = 0; for (Token t : idx) a[i++] = t.idx; ret a; } public TreeSet<HasIndex> indicesOf_treeSetOfHasIndex(O o) { ret (TreeSet) index.get(o); } }
Began life as a copy of #1025510
download show line numbers debug dex old transpilations
Travelled to 6 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt
No comments. add comment
Snippet ID: | #1025805 |
Snippet name: | TokenIndexedList3 with lazy reordering [dev. - probably the idea doesn't help much] |
Eternal ID of this version: | #1025805/10 |
Text MD5: | c54974be1b49ebe1ff9db5e57101599f |
Author: | stefan |
Category: | javax / image analysis |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2019-10-22 12:18:23 |
Source code size: | 3517 bytes / 156 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 205 / 266 |
Version history: | 9 change(s) |
Referenced in: | [show references] |