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).

// optimized for search - O(1) for searching for a certain element
// set is O(log m) with m = number of occurrences of element
final sclass CalculatedFieldIndexedList<A, B> extends RandomAccessAbstractList<A> {
  new Map<B, TreeSet<Elem<A>>> index; // elements by calculated field, sorted by index
  final new ArrayList<Elem<A>> list;
  IF1<A, B> f; // element to "key" (calculated field)

  final sclass Elem<A> extends HasIndex {
    A s; // actual element
    
    toString { ret "Elem " + quote(s) + "@" + idx; }
  }
  
  *(IF1<A, B> *f) {}
  *(IF1<A, B> *f, Map<B, TreeSet<Elem<A>>> *index) {} // use different type of index (e.g. ciMap)
  *(IF1<A, B> *f, Cl<A> l) { addAll(l); }
  
  public A get(int i) { ret list.get(i).s; }
  public int size() { ret list.size(); }
  
  public A set(int i, A s) {
    Elem<A> t = list.get(i);
    A old = t.s;
    if (eq(old, s)) ret old;
    removeFromIdx(t);
    t.s = s;
    addToIdx(t);
    ret old;
  }
  
  public bool add(A s) {
    ++modCount;
    new Elem<A> t;
    t.s = s;
    t.idx = size();
    list.add(t);
    addToIdx(t);
    true;
  }
  
  public void add(int i, A s) {
    ++modCount;
    new Elem<A> t;
    t.s = s;
    t.idx = i;
    list.add(i, t);
    reorder(i+1);
    addToIdx(t);
  }
  
  public bool addAll(int i, Collection<? extends A> l) {
    int n = l.size();
    if (n == 0) false;
    ++modCount;
    L<Elem<A>> l2 = emptyList(n);
    int j = i;
    for (A s : l) {
      new Elem<A> t;
      t.s = s;
      t.idx = j++;
      l2.add(t);
    }
    list.addAll(i, l2);
    reorder(i+n);
    for (Elem<A> t : l2)
      addToIdx(t);
    true;
  }
  
  public A remove(int i) {
    ++modCount;
    Elem<A> 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).idx = i;
  }
  
  void removeFromIdx(Elem<A> t) {
    B key = calc(t);
    var idx = index.get(key);
    idx.remove(t);
    if (idx.isEmpty()) index.remove(key);
  }
  
  void addToIdx(Elem<A> t) {
    B key = calc(t);
    var idx = index.get(key);
    if (idx == null)
      index.put(key, idx = new TreeSet);
    idx.add(t);
  }
  
  public A getByKey(B key) {
    var l = index.get(key);
    ret l == null ?: first(l).s;
  }
  
  // doesn't return null
  public L<A> getAllByKey(B key) {
    var l = index.get(key);
    ret l == null ? emptyList() : map(l, x -> x.s);
  }
  
  public int indexOfKey(B key) {
    var l = index.get(key);
    ret l == null ? -1 : first(l).idx;
  }
  
  @Override
  public int lastIndexOf(O s) {
    TreeSet<Elem<A>> 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[] indicesOfKey(B o) {
    TreeSet<Elem<A>> idx = index.get(o);
    if (idx == null) ret emptyIntArray();
    int[] a = new int[idx.size()];
    int i = 0;
    for (Elem<A> t : idx) a[i++] = t.idx;
    ret a;
  }
  
  B calc(A a) { ret f.get(a); }
  B calc(Elem<A> a) { ret f.get(a.s); }
}

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: 34 / 101
Version history: 9 change(s)
Referenced in: [show references]