Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

144
LINES

< > BotCompany Repo | #1025510 // TokenIndexedList3 [using treeset in index, OK]

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (4771L/27K).

1  
// A version of ContentsIndexedList specialized for tokens
2  
3  
// optimized for search - O(1) for searching for a token
4  
// set is O(log m) with m = number of occurrences of token
5  
final sclass TokenIndexedList3 extends RandomAccessAbstractList<S> implements IContentsIndexedList<S>, IContentsIndexedList2<S> {
6  
  final new HashMap<S, TreeSet<Token>> index; // tokens by contents, sorted by index
7  
  final new ArrayList<Token> list;
8  
9  
  final sclass Token extends HasIndex {
10  
    S s; // actual token
11  
    
12  
    toString { ret "Token " + quote(s) + "@" + idx; }
13  
  }
14  
  
15  
  *() {}
16  
  *(Collection<S> l) { addAll(l); }
17  
  
18  
  public S get(int i) { ret list.get(i).s; }
19  
  public int size() { ret list.size(); }
20  
  
21  
  public S set(int i, S s) {
22  
    Token t = list.get(i);
23  
    S old = t.s;
24  
    if (eq(old, s)) ret old;
25  
    removeFromIdx(t);
26  
    t.s = s;
27  
    addToIdx(t);
28  
    ret old;
29  
  }
30  
  
31  
  public bool add(S s) {
32  
    ++modCount;
33  
    new Token t;
34  
    t.s = s;
35  
    t.idx = size();
36  
    list.add(t);
37  
    addToIdx(t);
38  
    true;
39  
  }
40  
  
41  
  public void add(int i, S s) {
42  
    ++modCount;
43  
    new Token t;
44  
    t.s = s;
45  
    t.idx = i;
46  
    list.add(i, t);
47  
    reorder(i+1);
48  
    addToIdx(t);
49  
  }
50  
  
51  
  public bool addAll(int i, Collection<? extends S> l) {
52  
    int n = l.size();
53  
    if (n == 0) false;
54  
    ++modCount;
55  
    L<Token> l2 = emptyList(n);
56  
    int j = i;
57  
    for (S s : l) {
58  
      new Token t;
59  
      t.s = s;
60  
      t.idx = j++;
61  
      l2.add(t);
62  
    }
63  
    list.addAll(i, l2);
64  
    reorder(i+n);
65  
    for (Token t : l2)
66  
      addToIdx(t);
67  
    true;
68  
  }
69  
  
70  
  public S remove(int i) {
71  
    ++modCount;
72  
    Token t = list.get(i);
73  
    removeFromIdx(t);
74  
    list.remove(i);
75  
    reorder(i);
76  
    ret t.s;
77  
  }
78  
  
79  
  void reorder(int fromIdx) {
80  
    int n = size();
81  
    for (int i = fromIdx; i < n; i++)
82  
      list.get(i).idx = i;
83  
  }
84  
  
85  
  void removeFromIdx(Token t) {
86  
    TreeSet<Token> idx = index.get(t.s);
87  
    idx.remove(t);
88  
    if (idx.isEmpty()) index.remove(t.s);
89  
  }
90  
  
91  
  void addToIdx(Token t) {
92  
    TreeSet<Token> idx = index.get(t.s);
93  
    if (idx == null)
94  
      index.put(t.s, idx = new TreeSet);
95  
    idx.add(t);
96  
  }
97  
  
98  
  @Override
99  
  public int indexOf(O s) {
100  
    TreeSet<Token> l = index.get(s);
101  
    ret l == null ? -1 : first(l).idx;
102  
  }
103  
  
104  
  @Override
105  
  public int lastIndexOf(O s) {
106  
    TreeSet<Token> l = index.get(s);
107  
    ret l == null ? -1 : last(l).idx;
108  
  }
109  
  
110  
  @Override
111  
  public bool contains(O s) {
112  
    ret index.containsKey(s);
113  
  }
114  
  
115  
  public void clear() {
116  
    ++modCount;
117  
    index.clear();
118  
    list.clear();
119  
  }
120  
  
121  
  protected void removeRange(int fromIndex, int toIndex) {
122  
    if (fromIndex == toIndex) ret;
123  
    ++modCount;
124  
    
125  
    for (int i = fromIndex; i < toIndex; i++)
126  
      removeFromIdx(list.get(i));
127  
      
128  
    list.subList(fromIndex, toIndex).clear();
129  
    reorder(fromIndex);
130  
  }
131  
  
132  
  public int[] indicesOf(S o) {
133  
    TreeSet<Token> idx = index.get(o);
134  
    if (idx == null) ret emptyIntArray();
135  
    int[] a = new int[idx.size()];
136  
    int i = 0;
137  
    for (Token t : idx) a[i++] = t.idx;
138  
    ret a;
139  
  }
140  
  
141  
  public TreeSet<HasIndex> indicesOf_treeSetOfHasIndex(S o) {
142  
    ret (TreeSet) index.get(o);
143  
  }
144  
}

Author comment

Began life as a copy of #1025481

download  show line numbers  debug dex  old transpilations   

Travelled to 7 computer(s): bhatertpkbcr, mqqgnosmbjvj, onxytkatvevr, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt

No comments. add comment

Snippet ID: #1025510
Snippet name: TokenIndexedList3 [using treeset in index, OK]
Eternal ID of this version: #1025510/25
Text MD5: 25446ecdadde5cdaa0d7501f3d252420
Transpilation MD5: 011d6894c23c0092f0e7b773a773b73f
Author: stefan
Category: javax / image analysis
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2022-01-15 01:45:09
Source code size: 3246 bytes / 144 lines
Pitched / IR pitched: No / No
Views / Downloads: 272 / 773
Version history: 24 change(s)
Referenced in: [show references]