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

109
LINES

< > BotCompany Repo | #1025481 // TokenIndexedList2 [OK but usually not fast. use TokenIndexedList3 instead]

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

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);
  }
}

Author comment

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)