static class MultiMap { Map> data = new HashMap>(); MultiMap() {} MultiMap(bool useTreeMap) { if (useTreeMap) data = new TreeMap; } MultiMap(MultiMap map) { putAll(map); } *(Map> *data) {} void put(A key, B value) { synchronized(data) { List list = data.get(key); if (list == null) data.put(key, list = _makeEmptyList()); list.add(value); }} void add(A key, B value) { put(key, value); } void addAll(A key, Collection values) { synchronized(data) { 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(A key, Collection values) { synchronized(data) { for (B value : values) put(key, value); }} void removeAll(A key, Collection 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; }} // 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()) data.remove(key); }} Set keySet() { synchronized(data) { return data.keySet(); }} Set keys() { synchronized(data) { return data.keySet(); }} void remove(A key) { synchronized(data) { data.remove(key); }} void remove(A key, B value) { synchronized(data) { List list = data.get(key); if (list != null) { list.remove(value); 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) { List 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() { synchronized(data) { ret l(data); }} // full size - note: expensive operation int size() { synchronized(data) { int n = 0; for (L l : data.values()) n += l(l); ret n; }} // 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; } Collection> allLists() { synchronized(data) { ret new L(data.values()); } } L allValues() { ret concatLists(values(data)); } O mutex() { ret data; } toString { ret "mm" + str(data); } }