sclass RandomizerFromHistogram<A> implements IF0<A> {
  new LPair<A, Long> list;
  transient Random randomizer = defaultRandomizer();
  
  *(MultiSet<A> ms) {
    long sum = 0;
    for (A a : keys(ms)) {
      int val = ms.get(a);
      if (val == 0) continue;
      sum += val;
      list.add(pair(a, sum));
    }
  }
  
  public A get() {
    if (empty(list)) null;
    long val = randomLong(randomizer, sum());
    ret get(val);
  }
  
  long sum() { ret empty(list) ? 0 : last(list).b; }
  
  // val must be between 0 and sum()-1
  A get(long val) {
    int idx = generalizedBinarySearch2(list, p -> cmp((long) p.b, val+1));
    if (idx < 0) {
      ifdef RandomizerFromHistogram_debug
        print("idx1: " + idx);
      endifdef
      idx = -idx-1;
    }
    //print("idx: " + idx);
    ret assertNotNull(pairA(_get(list, idx)));
  }
}