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

155
LINES

< > BotCompany Repo | #1033968 // CalculatedFieldIndexedList [dev.] - ArrayList with instant lookup by element after applying a transformation function

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

Libraryless. Click here for Pure Java version (4857L/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 CalculatedFieldIndexedList<A, B> extends RandomAccessAbstractList<A> {
4  
  new Map<B, TreeSet<Elem<A>>> index; // elements by calculated field, sorted by index
5  
  final new ArrayList<Elem<A>> list;
6  
  IF1<A, B> f; // element to "key" (calculated field)
7  
8  
  final sclass Elem<A> extends HasIndex {
9  
    A s; // actual element
10  
    
11  
    toString { ret "Elem " + quote(s) + "@" + idx; }
12  
  }
13  
  
14  
  *(IF1<A, B> *f) {}
15  
  *(IF1<A, B> *f, Map<B, TreeSet<Elem<A>>> *index) {} // use different type of index (e.g. ciMap)
16  
  *(IF1<A, B> *f, Cl<A> l) { addAll(l); }
17  
  
18  
  public A get(int i) { ret list.get(i).s; }
19  
  public int size() { ret list.size(); }
20  
  
21  
  public A set(int i, A s) {
22  
    Elem<A> t = list.get(i);
23  
    A 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(A s) {
32  
    ++modCount;
33  
    new Elem<A> 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, A s) {
42  
    ++modCount;
43  
    new Elem<A> 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 A> l) {
52  
    int n = l.size();
53  
    if (n == 0) false;
54  
    ++modCount;
55  
    L<Elem<A>> l2 = emptyList(n);
56  
    int j = i;
57  
    for (A s : l) {
58  
      new Elem<A> 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 (Elem<A> t : l2)
66  
      addToIdx(t);
67  
    true;
68  
  }
69  
  
70  
  public A remove(int i) {
71  
    ++modCount;
72  
    Elem<A> 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(Elem<A> t) {
86  
    B key = calc(t);
87  
    var idx = index.get(key);
88  
    idx.remove(t);
89  
    if (idx.isEmpty()) index.remove(key);
90  
  }
91  
  
92  
  void addToIdx(Elem<A> t) {
93  
    B key = calc(t);
94  
    var idx = index.get(key);
95  
    if (idx == null)
96  
      index.put(key, idx = new TreeSet);
97  
    idx.add(t);
98  
  }
99  
  
100  
  public A getByKey(B key) {
101  
    var l = index.get(key);
102  
    ret l == null ?: first(l).s;
103  
  }
104  
  
105  
  // doesn't return null
106  
  public L<A> getAllByKey(B key) {
107  
    var l = index.get(key);
108  
    ret l == null ? emptyList() : map(l, x -> x.s);
109  
  }
110  
  
111  
  public int indexOfKey(B key) {
112  
    var l = index.get(key);
113  
    ret l == null ? -1 : first(l).idx;
114  
  }
115  
  
116  
  @Override
117  
  public int lastIndexOf(O s) {
118  
    TreeSet<Elem<A>> l = index.get(s);
119  
    ret l == null ? -1 : last(l).idx;
120  
  }
121  
  
122  
  @Override
123  
  public bool contains(O s) {
124  
    ret index.containsKey(s);
125  
  }
126  
  
127  
  public void clear() {
128  
    ++modCount;
129  
    index.clear();
130  
    list.clear();
131  
  }
132  
  
133  
  protected void removeRange(int fromIndex, int toIndex) {
134  
    if (fromIndex == toIndex) ret;
135  
    ++modCount;
136  
    
137  
    for (int i = fromIndex; i < toIndex; i++)
138  
      removeFromIdx(list.get(i));
139  
      
140  
    list.subList(fromIndex, toIndex).clear();
141  
    reorder(fromIndex);
142  
  }
143  
  
144  
  public int[] indicesOfKey(B o) {
145  
    TreeSet<Elem<A>> idx = index.get(o);
146  
    if (idx == null) ret emptyIntArray();
147  
    int[] a = new int[idx.size()];
148  
    int i = 0;
149  
    for (Elem<A> t : idx) a[i++] = t.idx;
150  
    ret a;
151  
  }
152  
  
153  
  B calc(A a) { ret f.get(a); }
154  
  B calc(Elem<A> a) { ret f.get(a.s); }
155  
}

Author comment

Began life as a copy of #1028238

download  show line numbers  debug dex  old transpilations   

Travelled to 4 computer(s): bhatertpkbcr, ekrmjmnbrukm, mowyntqkapby, mqqgnosmbjvj

No comments. add comment

Snippet ID: #1033968
Snippet name: CalculatedFieldIndexedList [dev.] - ArrayList with instant lookup by element after applying a transformation function
Eternal ID of this version: #1033968/10
Text MD5: af8c796dbd16b0bb152db726716d8f6c
Transpilation MD5: 9e4b08310c7b4cc4b319960766dc2cf5
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2022-01-15 02:08:02
Source code size: 3589 bytes / 155 lines
Pitched / IR pitched: No / No
Views / Downloads: 107 / 201
Version history: 9 change(s)
Referenced in: [show references]