// uses hash sets as inner sets unless subclassed

// uses a hash map as the outer map by default

sclass MultiSetMap<A, B>is IMultiMap<A, B> {

  Map<A, Set<B>> data = new HashMap<A, Set<B>>();

  int size; // number of values

  *() {}

  *(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 aka contains(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);

  }}

  public Set<B> get(A key) { synchronized(data) {

    Set<B> set = data.get(key);

    return set == null ? Collections.<B> emptySet() : set;

  }}

  L<B> getAndClear(A key) { synchronized(data) {

    L<B> l = cloneList(data.get(key));

    remove(key);

    ret l;

  }}

  // 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);

  }}

  public Set<A> keySet aka 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());

  }}

  public int keysSize aka keyCount() { synchronized(data) { ret l(data); }}

  // full size

  public 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;

  }}

  // expensive operation

  A keyForValue(B b) { synchronized(data) {

    for (A key : data.keySet())

      if (data.get(key).contains(b))

        ret key;

    null;

  }}

  Map<A, Set<B>> asMap() { synchronized(data) {

    ret cloneMap(data);

  }}

  public 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));

  }

  LPair<A, B> allEntries() { synchronized(data) {

    LPair<A, B> l = emptyList(size);

    for (A a, Set<B> set : data)

      for (B b : set)

        l.add(pair(a, b));

    ret l;

  }}

  O mutex() { ret data; }

  toString { ret "mm" + str(data); }

  Pair<A, B> firstEntry() { synchronized(data) {

    if (empty(data)) null;

    Map.Entry<A, Set<B>> entry = data.entrySet().iterator().next();

    ret pair(entry.getKey(), first(entry.getValue()));

  }}

  A firstKey() { synchronized(data) { ret main firstKey(data); }}

  A lastKey() { synchronized(data) { ret (A) ((NavigableMap) data).lastKey(); }}

  A higherKey(O a) { synchronized(data) { ret (A) ((NavigableMap) data).higherKey(a); }}

}