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

143
LINES

< > BotCompany Repo | #1028238 // ContentsIndexedList - ArrayList with instant lookup by element

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

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

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

Author comment

Began life as a copy of #1025510

download  show line numbers  debug dex  old transpilations   

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

No comments. add comment

Snippet ID: #1028238
Snippet name: ContentsIndexedList - ArrayList with instant lookup by element
Eternal ID of this version: #1028238/11
Text MD5: fe4abc675232f300c5068205e659b874
Transpilation MD5: 1def625adb721684722873a0d25c4f07
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2022-01-15 01:46:29
Source code size: 3303 bytes / 143 lines
Pitched / IR pitched: No / No
Views / Downloads: 221 / 545
Version history: 10 change(s)
Referenced in: [show references]