// uses HashMap by default
static class MultiSet<A> implements IMultiSet<A> {
  Map<A, Integer> map = new HashMap;
  int size; // now maintaining a size counter
  
  *(bool useTreeMap) {
    if (useTreeMap) map = new TreeMap;
  }
  *(TreeMap *map) {}
  
  *() {}
  *(Iterable<A> c) { addAll(c); }
  *(MultiSet<A> ms) { synchronized(ms) {
    for (A a : ms.keySet()) add(a, ms.get(a));
  }}
  
  // returns new count
  public synchronized int add(A key) { ret add(key, 1); }
  
  synchronized void addAll(Iterable<A> c) {
    if (c != null) for (A a : c) add(a);
  }

  synchronized void addAll(MultiSet<A> ms) {
    for (A a : ms.keySet()) add(a, ms.get(a));
  }
  
  synchronized int add(A key, int count) {
    if (count <= 0) ret 0; // don't calculate return value in this case
    size += count;
    Int i = map.get(key);
    map.put(key, i != null ? (count += i) : count);
    ret count;
  }

  synchronized void put(A key, int count) {
    int oldCount = get(key);
    if (count == oldCount) ret;
    size += count-oldCount;
    if (count != 0)
      map.put(key, count);
    else
      map.remove(key);
  }

  public synchronized int get(A key) {
    Int i = map.get(key);
    ret i != null ? i : 0;
  }
  
  synchronized bool contains(A key) {
    ret map.containsKey(key);
  }

  synchronized void remove(A key) {
    Integer i = map.get(key);
    if (i != null) {
      --size;
      if (i > 1)
        map.put(key, i - 1);
      else
        map.remove(key);
    }
  }

  synchronized List<A> topTen() { ret getTopTen(); }
  
  synchronized List<A> getTopTen() { ret getTopTen(10); }
  synchronized List<A> getTopTen(int maxSize) {
    List<A> list = getSortedListDescending();
    return list.size() > maxSize ? list.subList(0, maxSize) : list;
  }
  
  synchronized L<A> highestFirst() {
    ret getSortedListDescending();
  }

  synchronized L<A> lowestFirst() {
    ret reversedList(getSortedListDescending());
  }

  synchronized L<A> getSortedListDescending() {
    List<A> list = new ArrayList<A>(map.keySet());
    Collections.sort(list, new Comparator<A>() {
      public int compare(A a, A b) {
        return map.get(b).compareTo(map.get(a));
      }
    });
    ret list;
  }

  synchronized int getNumberOfUniqueElements() {
    return map.size();
  }
  
  synchronized int uniqueSize() {
    ret map.size();
  }

  synchronized Set<A> asSet() {
    return map.keySet();
  }

  synchronized NavigableSet<A> navigableSet() {
    return navigableKeys((NavigableMap) map);
  }

  public synchronized Set<A> keySet() {
    return map.keySet();
  }
  
  synchronized A getMostPopularEntry aka mostPopular() {
    int max = 0;
    A a = null;
    for (Map.Entry<A,Integer> entry : map.entrySet()) {
      if (entry.getValue() > max) {
        max = entry.getValue();
        a = entry.getKey();
      }
    }
    return a;
  }

  synchronized void removeAll(A key) {
    size -= get(key);
    map.remove(key);
  }

  public synchronized int size() {
    ret size;
  }

  synchronized MultiSet<A> mergeWith(MultiSet<A> set) {
    MultiSet<A> result = new MultiSet<A>();
    for (A a : set.asSet()) {
      result.add(a, set.get(a));
    }
    return result;
  }
  
  public synchronized boolean isEmpty() {
    return map.isEmpty();
  }
  
  synchronized public String toString() { // hmm. sync this?
    return str(map);
  }
  
  synchronized void clear() {
    map.clear();
    size = 0;
  }
  
  synchronized Map<A, Int> asMap aka toMap() {
    ret cloneMap(map);
  }
}