Warning: session_start(): open(/var/lib/php/sessions/sess_iaf8hjn1macvvgl57c97hmno0i, 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
// as long as you don't access the by-numeral-index functions,
// you can add and remove elements quickly.
// upon accessing the list, it is updated once to fit the new data
// Note: When adding the same element twice, it will be stored only
// once with the higher probabilities of the two.
//
// class is synchronized
sclass ProbabilisticList extends AbstractRandomAccessList> {
// these are the 2 main data structures we update
Map probabilities = hashMap();
MultiSetMap byProbability
= multiSetMap_outerDescTreeMap_innerCompactLinkedHashSet();
// = multiSetMap_outerDescTreeMap_innerBetterLinkedHashSet();
L> list; // this is only updated when requested
// CUSTOMIZATION
// must be >= 0. probability 0 is never added
double cutoffProbabilityOnAdd = 0;
*() {}
*(Iterable> l) {
main addAll(this, l);
}
public synchronized WithProbability get(int idx) {
if (idx < 0 || idx >= size()) null;
makeListUpToIndex(idx);
ret list.get(idx);
}
public synchronized int size() { ret l(probabilities); }
// assuming the index is within range
void makeListUpToIndex(int idx) {
if (idx < l(list)) ret; // index already there
if (list == null) list = new L;
WithProbability lastEntry = main last(list);
A a = lastEntry?!;
double probability = lastEntry == null ? 0 : lastEntry.probability();
//print("Making list from " + l(list) + " to " + idx);
while (idx >= l(list)) {
//printVars_str(+idx, +a, +probability);
if (a == null) {
probability = byProbability.firstKey();
a = first(byProbability.get(probability));
} else {
CompactLinkedHashSet setForProbability = cast byProbability.get(probability);
a = setForProbability.nextElement(a);
//printVars_str(+probability, +setForProbability, +a);
if (a == null) {
probability = byProbability.higherKey(probability);
a = first(byProbability.get(probability));
}
}
list.add(WithProbability(probability, a));
}
}
synchronized bool containsElement(A a) {
ret probabilities.containsKey(a);
}
public synchronized bool add(WithProbability wp) {
if (wp == null || wp.probability() <= cutoffProbabilityOnAdd) false;
A a = wp!;
double newP = wp.probability();
Double oldP = probabilities.get(a);
if (oldP != null) {
if (oldP.doubleValue() >= newP)
false;
else
remove(WithProbability(oldP, a));
}
clearListFrom(newP);
probabilities.put(a, newP);
byProbability.add(newP, a);
true;
}
// will also delete if given probability doesn't match
@Override
public bool remove(O wp) {
if (wp == null) false;
cast wp to WithProbability;
ret removeElement(wp!);
}
public synchronized bool removeElement(A a) {
if (a == null) false;
Double oldP = probabilities.get(a);
if (oldP == null) false;
clearListFrom(oldP);
probabilities.remove(a);
byProbability.remove(oldP, a);
true;
}
@Override
public synchronized WithProbability remove(int idx) {
var a = get(idx);
remove(a);
ret a;
}
// internal
void clearListFrom(double p) {
int idx = generalizedBinarySearch2(list, a -> a.probability() <= p ? 1 : -1);
idx = -idx-1;
//printVars clearListFrom(p, idx, before := takeFirst(idx, list), after := main subList(idx, list));
truncateList(list, idx);
}
void at(double p, A a) {
add(WithProbability(p, a));
}
// faster version of truncateList
void truncate(int size) {
if (size < 0) fail();
while (size() > size)
removeLast();
}
double getProbability(A a) {
ret orZero(probabilities.get(a));
}
void truncateBelow(double thresholdProbability) {
A a;
while ((a = last()) != null && getProbability(a) < thresholdProbability)
removeElement(a);
}
A last() {
Double last = byProbability.lastKey();
if (last == null) null;
CompactLinkedHashSet set = cast byProbability.getOpt(last);
ret set.last();
}
void removeLast {
removeElement(last());
}
}