// uses HashMap by default static class MultiSet implements IMultiSet { Map map = new HashMap; int size; // now maintaining a size counter *(bool useTreeMap) { if (useTreeMap) map = new TreeMap; } *(TreeMap *map) {} *() {} *(Iterable c) { addAll(c); } *(MultiSet 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 c) { if (c != null) for (A a : c) add(a); } synchronized void addAll(MultiSet 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 topTen() { ret getTopTen(); } synchronized List getTopTen() { ret getTopTen(10); } synchronized List getTopTen(int maxSize) { List list = getSortedListDescending(); return list.size() > maxSize ? list.subList(0, maxSize) : list; } synchronized L highestFirst() { ret getSortedListDescending(); } synchronized L lowestFirst() { ret reversedList(getSortedListDescending()); } synchronized L getSortedListDescending() { List list = new ArrayList(map.keySet()); Collections.sort(list, new Comparator() { 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 asSet() { return map.keySet(); } synchronized NavigableSet navigableSet() { return navigableKeys((NavigableMap) map); } public synchronized Set keySet() { return map.keySet(); } synchronized A getMostPopularEntry aka mostPopular() { int max = 0; A a = null; for (Map.Entry 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 mergeWith(MultiSet set) { MultiSet result = new MultiSet(); 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 asMap aka toMap() { ret cloneMap(map); } }