// not synchronized yet
persistable sclass OptimizedMultiSet<A> is IMultiSet<A> {
  new Map<A, Int> map;
  // outer tree map for sorting
  // inner linked hash set for reproducability (HashSet ordering sucks)
  transient MultiSetMap<Int, A> byCount = multiSetMap_innerLinkedHashSet_outerRevTreeMap();
  int size;
  
  public int add(A a) { ret add(a, 1); }
  
  int add(A a, int count) {
    if (count <= 0) ret 0;
    size += count;
    Int i = map.get(a);
    if (i != null)
      byCount.remove(i += count, a);
    else
      i = count;
    map.put(a, i);
    byCount.add(i, a);
    ret i;
  }
  
  // remove one occurrence of a (decrease its count)
  void remove(A a) {
    Int i = map.get(a);
    if (i != null) {
      --size;
      byCount.remove(i, a);
      if (--i > 0) {
        map.put(a, i);
        byCount.add(i, a);
      } else
        map.remove(a);
    }
  }
  
  // remove all occurrences of a
  void removeAll(A a) {
    Int i = map.get(a);
    if (i == null) ret;
    map.remove(a);
    byCount.remove(i, a);
    size -= i;
  }
  
  public bool isEmpty() {
    ret map.isEmpty();
  }
  
  toString {
    ret str(map);
  }
  
  A getMostPopularEntry() {
    ret firstValue(byCount);
  }
  
  // returns first of least popular entries if there is a tie
  A leastPopularEntry() {
    ret first(lastValue(castMultiSetMapToNavigableMap(byCount));
  }
  
  void _doneLoading {
    rebuildByCount();
  }
  
  // internal
  void rebuildByCount {
    byCount.clear();
    for (A entry, int count : map)
      byCount.put(count, entry);
  }
  
  public int get(A a) {
    ret map.get(a);
  }
  
  public int size() {
    ret size;
  }
  
  int uniqueSize() {
    ret map.size();
  }
  
  L<A> highestFirst aka getSortedListDescending() {
    ret asList(multiSetMapValuesIterator(byCount));
  }
  
  // drop least popular items until at or below maxSize of (distinct) entries
  void truncate(int maxSize) {
    assertTrue(maxSize >= 0);
    while (uniqueSize() > maxSize)
      removeAll(leastPopularEntry());
  }
  
  public synchronized Set<A> keySet() {
    return map.keySet();
  }
}