// records its full size (total value count) in a field now

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

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

  int fullSize;

  MultiMap() {}

  MultiMap(bool useTreeMap) { if (useTreeMap) data = new TreeMap; }

  MultiMap(MultiMap<A, B> map) { putAll(map); }

  *(Map<A, L<B>> *data) {}

  void put(A key, B value) { synchronized(data) {

    L<B> 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<B> values) { 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(Cl<A> keys, B value) { synchronized(data) {

    fOr (A key : keys)

      put(key, value);

  }}

  void putAll(A key, Collection<B> values) { synchronized(data) {

    if (nempty(values)) getActual(key).addAll(values);

  }}

  void putAll(Iterable<Pair<A, B>> pairs) { synchronized(data) {

    fOr (Pair<A, B> p : pairs)

      put(p.a, p.b);

  }}

  void removeAll(A key, Cl<B> values) { synchronized(data) {

    for (B value : values)

      remove(key, value);

  }}

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

    List<B> list = data.get(key);

    return list == null ? Collections.<B> emptyList() : list;

  }}

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

    ret data.get(key);

  }}

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

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

    remove(key);

    ret l;

  }}

  // returns actual mutable live list

  // creates the list if not there

  List<B> getActual(A key) { synchronized(data) {

    List<B> list = data.get(key);

    if (list == null)

      data.put(key, list = _makeEmptyList());

    ret list;

  }}

  void clean(A key) { synchronized(data) {

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

    if (list != null && list.isEmpty()) {

      fullSize -= l(list);

      data.remove(key);

    }

  }}

  public Set<A> keySet aka keys() { synchronized(data) {

    return data.keySet();

  }}

  void remove(A key) { synchronized(data) {

    fullSize -= l(this.getOpt(key));

    data.remove(key);

  }}

  void removePair aka remove(Pair<A, B> p) {

    if (p != null) remove(p.a, p.b);

  }

  void remove(A key, B value) { synchronized(data) {

    L<B> 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<B> list = get(key);

    return list.isEmpty() ? null : list.get(0);

  }}

  void addAll(MultiMap<A, B> map) { putAll(map); }

  void putAll(MultiMap<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); }}

  public int size aka fullSize() { synchronized(data) {

    ret fullSize;

  }}

  // expensive operation

  L<A> reverseGet(B b) { synchronized(data) {

    new L<A> l;

    for (A key : data.keySet())

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

        l.add(key);

    ret l;

  }}

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

    ret cloneMap(data);

  }}

  public bool isEmpty() { synchronized(data) { ret data.isEmpty(); }}

  // override in subclasses

  L<B> _makeEmptyList() {

    ret new ArrayList;

  }

  // returns live lists

  Collection<L<B>> allLists() {

    synchronized(data) {

      ret new L(data.values());

    }

  }

  Cl<L<B>> values() { ret allLists(); }

  L<B> allValues() {

    ret concatLists(data.values());

  }

  O mutex() { ret data; }

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

  Map<A, L<B>> innerMap() { ret data; }

}