static class MultiMap<A,B> {
  Map<A, List<B>> data = new HashMap<A, List<B>>();
  
  MultiMap() {}
  MultiMap(bool useTreeMap) { if (useTreeMap) data = new TreeMap; }
  MultiMap(MultiMap<A, B> map) { putAll(map); }

  synchronized void put(A key, B value) {
    List<B> list = data.get(key);
    if (list == null)
      data.put(key, list = new ArrayList<B>());
    list.add(value);
  }

  synchronized void addAll(A key, Collection<B> values) {
    putAll(key, values);
  }
  
  synchronized void addAllIfNotThere(A key, Collection<B> values) {
    for (B value : values)
      setPut(key, value);
  }
  
  synchronized void setPut(A key, B value) {
    if (!containsPair(key, value))
      put(key, value);
  }
  
  synchronized boolean containsPair(A key, B value) {
    ret get(key).contains(value);
  }
  
  synchronized void putAll(A key, Collection<B> values) {
    for (B value : values)
      put(key, value);
  }

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

  // returns actual mutable live list
  // creates the list if not there
  synchronized List<B> getActual(A key) {
    List<B> list = data.get(key);
    if (list == null)
      data.put(key, list = litlist());
    ret list;
  }
 
  synchronized void clean(A key) {
    L<B> list = data.get(key);
    if (list != null && list.isEmpty())
      data.remove(key);
  }

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

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

  synchronized void remove(A key) {
    data.remove(key);
  }

  synchronized void remove(A key, B value) {
    List<B> list = data.get(key);
    if (list != null) {
      list.remove(value);
      if (list.isEmpty())
        data.remove(key);
    }
  }

  synchronized void clear() {
    data.clear();
  }

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

  synchronized B getFirst(A key) {
    List<B> list = get(key);
    return list.isEmpty() ? null : list.get(0);
  }
  
  synchronized void putAll(MultiMap<A, B> map) {
    for (A key : map.keySet())
      putAll(key, map.get(key));
  }
  
  // note: expensive operation
  synchronized int size() {
    int n = 0;
    for (L l : data.values())
      n += l(l);
    ret n;
  }
  
  // expensive operation
  synchronized L<A> reverseGet(B b) {
    new L<A> l;
    for (A key : data.keySet())
      if (data.get(key).contains(b))
        l.add(key);
    ret l;
  }
  
  synchronized Map<A, L<B>> asMap() {
    ret cloneMap(data);
  }
  
  bool isEmpty() { ret data.isEmpty(); }
}