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