// uses hash sets as inner sets unless subclassed
// uses a hash map as the outer map by default
static class MultiSetMap<A, B> {
  Map<A, Set<B>> data = new HashMap<A, Set<B>>();
  int size;
  
  *() {}
  *(bool useTreeMap) { if (useTreeMap) data = new TreeMap; }
  *(MultiSetMap<A, B> map) { putAll(map); }
  *(Map<A, Set<B>> *data) {}

  bool put(A key, B value) { synchronized(data) {
    Set<B> set = data.get(key);
    if (set == null)
      data.put(key, set = _makeEmptySet());
    if (!set.add(value)) false;
    ret true with ++size;
  }}

  bool add(A key, B value) { ret put(key, value); }

  void addAll(A key, Collection<B> values) { synchronized(data) {
    putAll(key, values);
  }}
  
  void addAllIfNotThere(A key, Collection<B> 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<B> values) { synchronized(data) {
    for (B value : values)
      put(key, value);
  }}

  void removeAll(A key, Collection<B> values) { synchronized(data) {
    for (B value : values)
      remove(key, value);
  }}
  
  Set<B> get(A key) { synchronized(data) {
    Set<B> set = data.get(key);
    return set == null ? Collections.<B> emptySet() : set;
  }}

  // return null if empty
  Set<B> getOpt(A key) { synchronized(data) {
    ret data.get(key);
  }}

  // returns actual mutable live set
  // creates the set if not there
  Set<B> getActual(A key) { synchronized(data) {
    Set<B> set = data.get(key);
    if (set == null)
      data.put(key, set = _makeEmptySet());
    ret set;
  }}
 
  // TODO: this looks unnecessary
  void clean(A key) { synchronized(data) {
    Set<B> list = data.get(key);
    if (list != null && list.isEmpty())
      data.remove(key);
  }}

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

  Set<A> keys() { synchronized(data) {
    return data.keySet();
  }}

  void remove(A key) { synchronized(data) {
    size -= l(data.get(key));
    data.remove(key);
  }}

  void remove(A key, B value) { synchronized(data) {
    Set<B> set = data.get(key);
    if (set != null) {
      if (set.remove(value)) {
        --size;
        if (set.isEmpty())
          data.remove(key);
      }
    }
  }}

  void clear() { synchronized(data) {
    data.clear();
    size = 0;
  }}

  boolean containsKey(A key) { synchronized(data) {
    return data.containsKey(key);
  }}

  B getFirst(A key) { synchronized(data) {
    return first(get(key));
  }}
  
  void addAll(MultiSetMap<A, B> map) { putAll(map); }
  
  void putAll(MultiSetMap<A, B> map) { synchronized(data) {
    for (A key : map.keySet())
      putAll(key, map.get(key));
  }}
  
  void putAll(Map<A, B> map) { synchronized(data) {
    if (map != null) for (Map.Entry<A, B> e : map.entrySet())
      put(e.getKey(), e.getValue());
  }}
  
  int keysSize() { synchronized(data) { ret l(data); }}
  
  // full size
  int size() { synchronized(data) {
    ret size;
  }}
  
  // count values for key
  int getSize(A key) { ret l(data.get(key)); }
  int count(A key) { ret getSize(key); }
  
  // expensive operation
  Set<A> reverseGet(B b) { synchronized(data) {
    new Set<A> l;
    for (A key : data.keySet())
      if (data.get(key).contains(b))
        l.add(key);
    ret l;
  }}
  
  Map<A, Set<B>> asMap() { synchronized(data) {
    ret cloneMap(data);
  }}
  
  bool isEmpty() { synchronized(data) { ret data.isEmpty(); }}
  
  // override in subclasses
  Set<B> _makeEmptySet() {
    ret new HashSet;
  }
  
  Collection<Set<B>> allLists() {
    synchronized(data) {
      ret new Set(data.values());
    }
  }
  
  L<B> allValues() {
    ret concatLists(values(data));
  }
  
  O mutex() { ret data; }
  
  toString { ret "mm" + str(data); }
  
  Pair<A, B> firstEntry() {
    if (empty(data)) null;
    Map.Entry<A, Set<B>> entry = data.entrySet().iterator().next();
    ret pair(entry.getKey(), first(entry.getValue()));
  }
}

Began life as a copy of #1001296