gt:         Collection<V> value = e.getValue();
context: package edu.stanford.nlp.util;
  
  import java.io.Serializable;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.Iterator;
  import java.util.Map;
  import java.util.Random;
  import java.util.Set;
  
  /**
   * Map from keys to {@link Collection}s. Important methods are the {@link #add}
   * and {@link #remove} methods for adding and removing a value to/from the
   * Collection associated with the key, and the {@link #get} method for getting
   * the Collection associated with a key. The class is quite general, because on
   * construction, it is possible to pass a {@link MapFactory} which will be used
   * to create the underlying map and a {@link CollectionFactory} which will be
   * used to create the Collections. Thus this class can be configured to act like
   * a "HashSetValuedMap" or a "ListValuedMap", or even a
   * "HashSetValuedIdentityHashMap". The possibilities are endless!
   * 
   * @param <K>
   *          Key type of map
   * @param <V>
   *          Type of the Collection that is the Map's value
   * @author Teg Grenager (grenager@cs.stanford.edu)
   * @author Sarah Spikes (sdspikes@cs.stanford.edu) - cleanup and filling in
   *         types
   */
  public class CollectionValuedMap<K, V> implements Map<K, Collection<V>>, Serializable {
  
    private static final long serialVersionUID = -9064664153962599076L;
    private Map<K, Collection<V>> map;
    protected CollectionFactory<V> cf;
    private boolean treatCollectionsAsImmutable;
    protected MapFactory<K, Collection<V>> mf;
  
    /**
     * Replaces current Collection mapped to key with the specified Collection.
     * Use carefully!
     * 
     */
    public Collection<V> put(K key, Collection<V> collection) {
      return map.put(key, collection);
    }
  
    /**
     * Unsupported. Use {@link #addAll(Map)} instead.
     */
    public void putAll(Map<? extends K, ? extends Collection<V>> m) {
      throw new UnsupportedOperationException();
    }
  
    /**
     * The empty collection to be returned when a <code>get</code> doesn't find
     * the key. The collection returned should be empty, such as
     * Collections.emptySet, for example.
     */
    private final Collection<V> emptyValue;
  
    /**
     * @return the Collection mapped to by key, never null, but may be empty.
     */
    public Collection<V> get(Object key) {
      Collection<V> c = map.get(key);
      if (c == null) {
        c = emptyValue;
      }
      return c;
    }
  
    /**
     * Adds the value to the Collection mapped to by the key.
     * 
     */
    public void add(K key, V value) {
      if (treatCollectionsAsImmutable) {
        Collection<V> newC = cf.newCollection();
        Collection<V> c = map.get(key);
        if (c != null) {
          newC.addAll(c);
        }
        newC.add(value);
        map.put(key, newC); // replacing the old collection
      } else {
        Collection<V> c = map.get(key);
        if (c == null) {
          c = cf.newCollection();
          map.put(key, c);
        }
        c.add(value); // modifying the old collection
      }
    }
    
    /**
     * Adds the values to the Collection mapped to by the key.
     */
    
    public void addAll(K key, Collection<V> values) {
      if (treatCollectionsAsImmutable) {
        Collection<V> newC = cf.newCollection();
        Collection<V> c = map.get(key);
        if (c != null) {
          newC.addAll(c);
        }
        newC.addAll(values);
        map.put(key, newC); // replacing the old collection
      } else {
        Collection<V> c = map.get(key);
        if (c == null) {
          c = cf.newCollection();
          map.put(key, c);
        }
        c.addAll(values); // modifying the old collection
      }
    }
  
    // Just add the key (empty collection, but key is in the keySet
    public void addKey(K key) {
      Collection<V> c = map.get(key);
      if (c == null) {
        c = cf.newCollection();
        map.put(key, c);
      }
    }
  
    /**
     * Adds all of the mappings in m to this CollectionValuedMap. If m is a
     * CollectionValuedMap, it will behave strangely. Use the constructor instead.
     * 
     */
    public void addAll(Map<K, V> m) {
      if (m instanceof CollectionValuedMap<?, ?>) {
        throw new UnsupportedOperationException();
      }
      for (Map.Entry<K, V> e : m.entrySet()) {
        add(e.getKey(), e.getValue());
      }
    }
  
    public void addAll(CollectionValuedMap<K, V> cvm) {
      for (Entry<K, Collection<V>> entry : cvm.entrySet()) {
        K key = entry.getKey();
        Collection<V> currentCollection = get(key);
        Collection<V> newValues = entry.getValue();
        if (treatCollectionsAsImmutable) {
          Collection<V> newCollection = cf.newCollection();
          if (currentCollection != null) {
            newCollection.addAll(currentCollection);
          }
          newCollection.addAll(newValues);
          map.put(key, newCollection); // replacing the old collection
        } else {
          boolean needToAdd = false;
          if (currentCollection == emptyValue) {
            currentCollection = cf.newCollection();
            needToAdd = true;
          }
          currentCollection.addAll(newValues); // modifying the old collection
          if (needToAdd) {
            map.put(key, currentCollection);
          }
        }
      }
    }
  
    /**
     * Removes the mapping associated with this key from this Map.
     * 
     * @return the Collection mapped to by this key.
     */
    public Collection<V> remove(Object key) {
      return map.remove(key);
    }
  
    /**
     * removes the mappings associated with the keys from this map
     * @param keys
     */
    public void removeAll(Collection<K> keys) {
      for (K k : keys) {
        remove(k);
      }
    }
  
    /**
     * Removes the value from the Collection mapped to by this key, leaving the
     * rest of the collection intact.
     * 
     * @param key
     *          the key to the Collection to remove the value from
     * @param value
     *          the value to remove
     */
    public void removeMapping(K key, V value) {
      if (treatCollectionsAsImmutable) {
        Collection<V> c = map.get(key);
        if (c != null) {
          Collection<V> newC = cf.newCollection();
          newC.addAll(c);
          newC.remove(value);
          map.put(key, newC);
        }
  
      } else {
        Collection<V> c = get(key);
        c.remove(value);
      }
    }
  
    /**
     * Clears this Map.
     */
    public void clear() {
      map.clear();
    }
  
    /**
     * @return true iff this key is in this map
     */
    public boolean containsKey(Object key) {
      return map.containsKey(key);
    }
  
    /**
     * Unsupported.
     */
    public boolean containsValue(Object value) {
      throw new UnsupportedOperationException();
    }
  
    /**
     * @return true iff this Map has no mappings in it.
     */
    public boolean isEmpty() {
      return map.isEmpty();
    }
  
    /**
     * Each element of the Set is a Map.Entry object, where getKey() returns the
     * key of the mapping, and getValue() returns the Collection mapped to by the
     * key.
     * 
     * @return a Set view of the mappings contained in this map.
     */
    public Set<Entry<K, Collection<V>>> entrySet() {
      return map.entrySet();
    }
  
    /**
     * @return a Set view of the keys in this Map.
     */
    public Set<K> keySet() {
      return map.keySet();
    }
  
    /**
     * The number of keys in this map.
     */
    public int size() {
      return map.size();
    }
  
    /**
     * @return a collection of the values (really, a collection of values) in this
     *         Map
     */
    public Collection<Collection<V>> values() {
      return map.values();
    }
  
    public Collection<V> allValues() {
      Collection<V> c = cf.newCollection();
      for (Collection<V> c1 : map.values()) {
        c.addAll(c1);
      }
      return c;
    }
  
    /**
     * @return true iff o is a CollectionValuedMap, and each key maps to the a
     *         Collection of the same objects in o as it does in this
     *         CollectionValuedMap.
     */
    @Override
    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
      if (!(o instanceof CollectionValuedMap<?, ?>)) {
        return false;
      }
  
      CollectionValuedMap<K, V> other = ErasureUtils.uncheckedCast(o);
  
      if (other.size() != size()) {
        return false;
      }
  
      try {
        for (Map.Entry<K, Collection<V>> e : entrySet()) {
          K key = e.getKey();
  