import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;


/**
 * * Reverse a Map, such that the keys become
 * * the values and vice versa. The former
 * * need to be held in a List owing to the
 * * possible presence of duplicates
 * *
 * * @author Charles Johnson
 * * @version 1.0
 * *
 * * @param <K> The key type of the original map
 * * @param <V> The value type of the original map
 * */
public class MapReverser<K, V> {
        private Map<K, V> map;

        public MapReverser(Map<K, V> map) {
                this.map = map;
        }

        public Map<V, List<K>> getMap() {
                Map<V, List<K>> reversed = new HashMap<V, List<K>>();
                Iterator<Map.Entry<K, V>> i = map.entrySet().iterator();

                while (i.hasNext()) {
                        Map.Entry<K, V> e = i.next();
                        K key = e.getKey();
                        V value = e.getValue();
                        List<K> reversedKeys = null;

                        if (reversed.containsKey(value)) {
                                reversedKeys = reversed.get(value);
                        } else {
                                reversedKeys = new ArrayList<K>();
                                reversed.put(value, reversedKeys);
                        }

                        reversedKeys.add(key);
                }

                return reversed;
        }
}