// 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: doesn't allow the same element to be added twice
//       (will just overwrite the probability in this case)
sclass ProbabilisticList<A> extends AbstractRandomAccessList<WithProbability<A>> {
  // these are the 2 main data structures we update
  Map<A, Double> probabilities = hashMap();
  MultiSetMap<Double, A> byProbability = multiSetMap_outerDescTreeMap_innerBetterLinkedHashSet();
  
  L<WithProbability<A>> list; // this is only updated when requested
  
  public WithProbability<A> get(int idx) {
    if (idx < 0 || idx >= size()) null;
    makeListUpToIndex(idx);
    ret list.get(idx);
  }
  
  public 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;
    
    A a = null;
    double probability = 0;
    
    while (idx >= l(list)) {
      if (a == null) {
        probability = byProbability.firstKey();
        a = first(byProbability.get(probability));
      } else {
        BetterLinkedHashSet<A> setForProbability = cast byProbability.get(probability);
        a = setForProbability.nextElement(a);
        if (a == null) {
          probability = byProbability.higherKey(probability);
          a = first(byProbability.get(probability));
        }
      }
      list.add(WithProbability(probability, a));
    }
  }
  
  public bool add(WithProbability<A> wp) {
    if (wp == null) false;
    A a = wp!;
    double newP = wp.probability();
    Double oldP = probabilities.get(a);
    if (oldP != null) {
      if (oldP.doubleValue() == newP)
        false;
      else
        remove(WithProbability<A>(oldP, a));
    }
      
    clearListFrom(newP);
    probabilities.put(a, newP);
    byProbability.add(newP, a);
    true;
  }
  
  // will also delete if given probability doesn't match
  public bool remove(WithProbability<A> wp) {
    if (wp == null) false;
    A a = wp!;
    Double oldP = probabilities.get(a);
    if (oldP == null) false;
    clearListFrom(oldP);
    probabilities.remove(a);
    byProbability.remove(oldP, a);
    true;
  }
  
  // internal
  void clearListFrom(double p) {
    int idx = generalizedBinarySearch2(list, a ->
      probabilities.get(a) >= p ? 1 : -1);
    idx = -idx-1;
    printVars clearListFrom(p, idx);
    truncateList(list, idx);
  }
}