Warning: session_start(): open(/var/lib/php/sessions/sess_o8gojdcub577s8n6nsfhdh9780, O_RDWR) failed: No space left on device (28) in /var/www/tb-usercake/models/config.php on line 51
Warning: session_start(): Failed to read session data: files (path: /var/lib/php/sessions) in /var/www/tb-usercake/models/config.php on line 51
// 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 {
new Map> index; // tokens are in order
new L list;
sclass Token {
int i; // index in list
S s; // actual token
}
*() {}
*(Collection 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;
++modCount;
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 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 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 comparator() {
ret (Comparator) (a, b) -> b.i-a.i;
}
public int indexOf(S s) {
L 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);
}
}