static class MultiMap { Map> data = new HashMap>(); int fullSize; MultiMap() {} MultiMap(bool useTreeMap) { if (useTreeMap) data = new TreeMap; } MultiMap(MultiMap map) { putAll(map); } *(Map> *data) {} void put(A key, B value) { synchronized(data) { L list = data.get(key); if (list == null) data.put(key, list = _makeEmptyList()); list.add(value); ++fullSize; }} void add(A key, B value) { put(key, value); } void addAll(A key, Collection values) { putAll(key, values); } void addAllIfNotThere(A key, Collection values) { synchronized(data) { for (B value : values) setPut(key, value); }} void setPut(A key, B value) { synchronized(data) { if (!containsPair(key, value)) put(key, value); }} boolean containsPair(A key, B value) { synchronized(data) { ret get(key).contains(value); }} void putAll(Cl keys, B value) { synchronized(data) { fOr (A key : keys) put(key, value); }} void putAll(A key, Collection values) { synchronized(data) { if (nempty(values)) getActual(key).addAll(values); }} void putAll(Iterable> pairs) { synchronized(data) { fOr (Pair p : pairs) put(p.a, p.b); }} void removeAll(A key, Cl values) { synchronized(data) { for (B value : values) remove(key, value); }} List get(A key) { synchronized(data) { List list = data.get(key); return list == null ? Collections. emptyList() : list; }} L getOpt(A key) { synchronized(data) { ret data.get(key); }} L getAndClear(A key) { synchronized(data) { L l = cloneList(data.get(key)); remove(key); ret l; }} // returns actual mutable live list // creates the list if not there List getActual(A key) { synchronized(data) { List list = data.get(key); if (list == null) data.put(key, list = _makeEmptyList()); ret list; }} void clean(A key) { synchronized(data) { L list = data.get(key); if (list != null && list.isEmpty()) { fullSize -= l(list); data.remove(key); } }} Set keySet() { synchronized(data) { return data.keySet(); }} Set keys() { synchronized(data) { return data.keySet(); }} void remove(A key) { synchronized(data) { fullSize -= l(getOpt(key)); data.remove(key); }} void remove(Pair p) { if (p != null) remove(p.a, p.b); } void remove(A key, B value) { synchronized(data) { L list = data.get(key); if (list != null) { if (list.remove(value)) fullSize--; if (list.isEmpty()) data.remove(key); } }} void clear() { synchronized(data) { data.clear(); }} boolean containsKey(A key) { synchronized(data) { return data.containsKey(key); }} B getFirst(A key) { synchronized(data) { L list = get(key); return list.isEmpty() ? null : list.get(0); }} void addAll(MultiMap map) { putAll(map); } void putAll(MultiMap map) { synchronized(data) { for (A key : map.keySet()) putAll(key, map.get(key)); }} void putAll(Map map) { synchronized(data) { if (map != null) for (Map.Entry e : map.entrySet()) put(e.getKey(), e.getValue()); }} int keysSize aka keyCount() { synchronized(data) { ret l(data); }} // full size - note: expensive operation int size aka fullSize() { synchronized(data) { ret fullSize; }} // expensive operation L reverseGet(B b) { synchronized(data) { new L l; for (A key : data.keySet()) if (data.get(key).contains(b)) l.add(key); ret l; }} Map> asMap() { synchronized(data) { ret cloneMap(data); }} bool isEmpty() { synchronized(data) { ret data.isEmpty(); }} // override in subclasses L _makeEmptyList() { ret new ArrayList; } // returns live lists Collection> allLists() { synchronized(data) { ret new L(data.values()); } } Cl> values() { ret allLists(); } L allValues() { ret concatLists(data.values()); } O mutex() { ret data; } toString { ret "mm" + str(data); } }