static final class SmallestListMultiMap<A,B> {

  Map<A, O> data = new HashMap<A, O>(); // values are smallestLists

  *() {}

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

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

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

    O list = data.get(key);

    data.put(key, smallestList_add(list, 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 smallestList_contains(get(key), 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);

  }}

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

    ret smallestList_toList(data.get(key));

  }}

  Set<A> keySet() { synchronized(data) {

    return data.keySet();

  }}

  Set<A> keys() { synchronized(data) {

    return data.keySet();

  }}

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

    data.remove(key);

  }}

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

    O list = data.get(key);

    if (list != null) {

      O list2 = smallestList_remove(list, value);

      if (list2 != list)

        if (list2 == null)

          data.remove(key);

        else

          data.put(key, list2);

    }

  }}

  void clear() { synchronized(data) {

    data.clear();

  }}

  boolean containsKey(A key) { synchronized(data) {

    return data.containsKey(key);

  }}

  B getFirst(A key) { synchronized(data) {

    ret (B) smallestList_get(data.get(key), 0);

  }}

  void putAll(MultiMap<A, B> map) { synchronized(data) {

    for (A key : map.keySet())

      putAll(key, map.get(key));

  }}

  int keysSize() { synchronized(data) { ret l(data); }}

  // full size - note: expensive operation

  int size() { synchronized(data) {

    int n = 0;

    for (O l : data.values())

      n += smallestList_l(l);

    ret n;

  }}

  // expensive operation

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

    new L<A> l;

    for (A key : data.keySet())

      if (smallestList_contains(data.get(key), b))

        l.add(key);

    ret l;

  }}

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

    new HashMap<A, L<B>> map;

    for (A key : data.keySet())

      map.put(key, smallestList_toList(data.get(key)));

    ret map;

  }}

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

}