Libraryless. Click here for Pure Java version (2260L/14K).
// optimized for search - O(1) for searching for a token // set is O(m) with m = number of occurrences of token // This could be improved to O(log m) by using a TreeSet instead of the L in the index final sclass TokenIndexedList2 extends RandomAccessAbstractList<S> { new Map<S, L<Token>> index; // tokens are in order new L<Token> list; sclass Token { int i; // index in list S s; // actual token } *() {} *(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.i = size(); list.add(t); addToIdx(t); true; } public void add(int i, S s) { ++modCount; new Token t; t.s = s; t.i = i; list.add(i, t); reorder(i+1); addToIdx(t); } 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) { int n = size(); for (int i = fromIdx; i < n; i++) list.get(i).i = i; } void removeFromIdx(Token t) { L<Token> idx = index.get(t.s); int i = Collections.binarySearch(idx, t, comparator()); idx.remove(i); if (empty(idx)) index.remove(t.s); } void addToIdx(Token t) { L<Token> idx = index.get(t.s); if (idx == null) index.put(t.s, idx = new L); int i = -1-Collections.binarySearch(idx, t, comparator()); idx.add(i, t); } Comparator<Token> comparator() { ret (Comparator<Token>) (a, b) -> b.i-a.i; } public int indexOf(S s) { L<Token> l = index.get(s); ret l == null ? -1 : l.get(0).i; } 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; // TODO: this can be optimized for (int i = fromIndex; i < toIndex; i++) removeFromIdx(list.get(i)); list.subList(fromIndex, toIndex).clear(); reorder(fromIndex); } }
Began life as a copy of #1025480
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: | #1025481 |
Snippet name: | TokenIndexedList2 [OK but usually not fast. use TokenIndexedList3 instead] |
Eternal ID of this version: | #1025481/23 |
Text MD5: | 087fdd028073c70b764bd130ddc53f96 |
Transpilation MD5: | 0c26db5b0c5a4ae3724d3383d9b0875b |
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-01 18:39:36 |
Source code size: | 2454 bytes / 109 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 269 / 762 |
Version history: | 22 change(s) |
Referenced in: | #1025510 - TokenIndexedList3 [using treeset in index, OK] #1034167 - Standard Classes + Interfaces (LIVE, continuation of #1003674) |