001    // License: GPL. See LICENSE file for details.
002    package org.openstreetmap.josm.tools;
003    
004    import java.util.ArrayList;
005    import java.util.Collection;
006    import java.util.HashMap;
007    import java.util.LinkedHashSet;
008    import java.util.List;
009    import java.util.Map;
010    import java.util.Map.Entry;
011    import java.util.Set;
012    
013    /**
014     * MultiMap - maps keys to multiple values
015     *
016     * Corresponds to Google guava LinkedHashMultimap and Apache Collections MultiValueMap
017     * but it is an independent (simple) implementation.
018     *
019     */
020    public class MultiMap<A, B> {
021    
022        private final Map<A, LinkedHashSet<B>> map;
023    
024        public MultiMap() {
025            map = new HashMap<A, LinkedHashSet<B>>();
026        }
027    
028        public MultiMap(int capacity) {
029            map = new HashMap<A, LinkedHashSet<B>>(capacity);
030        }
031    
032        /**
033         * Map a key to a value.
034         *
035         * Can be called multiple times with the same key, but different value.
036         */
037        public void put(A key, B value) {
038            LinkedHashSet<B> vals = map.get(key);
039            if (vals == null) {
040                vals = new LinkedHashSet<B>();
041                map.put(key, vals);
042            }
043            vals.add(value);
044        }
045    
046        /**
047         * Put a key that maps to nothing. (Only if it is not already in the map)
048         *
049         * Afterwards containsKey(key) will return true and get(key) will return
050         * an empty Set instead of null.
051         */
052        public void putVoid(A key) {
053            if (map.containsKey(key))
054                return;
055            map.put(key, new LinkedHashSet<B>());
056        }
057    
058        /**
059         * Map the key to all the given values.
060         *
061         * Adds to the mappings that are already there.
062         */
063        public void putAll(A key, Collection<B> values) {
064            LinkedHashSet<B> vals = map.get(key);
065            if (vals == null) {
066                vals = new LinkedHashSet<B>(values);
067                map.put(key, vals);
068            }
069            vals.addAll(values);
070        }
071    
072        /**
073         * Get the keySet.
074         */
075        public Set<A> keySet() {
076            return map.keySet();
077        }
078    
079        /**
080         * Returns the Set associated with the given key. Result is null if
081         * nothing has been mapped to this key.
082         *
083         * Modifications of the returned list changes the underling map,
084         * but you should better not do that.
085         */
086        public Set<B> get(A key) {
087            return map.get(key);
088        }
089    
090        /**
091         * Like get, but returns an empty Set if nothing has been mapped to the key.
092         */
093        public LinkedHashSet<B> getValues(A key) {
094            if (!map.containsKey(key))
095                return new LinkedHashSet<B>();
096            return map.get(key);
097        }
098    
099        public boolean isEmpty() {
100            return map.isEmpty();
101        }
102    
103        public boolean containsKey(A key) {
104            return map.containsKey(key);
105        }
106    
107        /**
108         * Returns true if the multimap contains a value for a key.
109         *
110         * @param key The key
111         * @param value The value
112         * @return true if the key contains the value
113         */
114        public boolean contains(A key, B value) {
115            Set<B> values = get(key);
116            return (values == null) ? false : values.contains(value);
117        }
118    
119        public void clear() {
120            map.clear();
121        }
122    
123        public Set<Entry<A, LinkedHashSet<B>>> entrySet() {
124            return map.entrySet();
125        }
126    
127        /**
128         * Returns the number of keys.
129         */
130        public int size() {
131            return map.size();
132        }
133    
134        /**
135         * Returns a collection of all value sets.
136         */
137        public Collection<LinkedHashSet<B>> values() {
138            return map.values();
139        }
140    
141        /**
142         * Removes a cerain key=value mapping.
143         *
144         * @return true, if something was removed
145         */
146        public boolean remove(A key, B value) {
147            Set<B> values = get(key);
148            if (values != null) {
149                return values.remove(value);
150            }
151            return false;
152        }
153    
154        /**
155         * Removes all mappings for a certain key.
156         */
157        public LinkedHashSet<B> remove(A key) {
158            return map.remove(key);
159        }
160    
161        public String toString() {
162            List<String> entries = new ArrayList<String>(map.size());
163            for (A key : map.keySet()) {
164                entries.add(key + "->{" + Utils.join(",", map.get(key)) + "}");
165            }
166            return "(" + Utils.join(",", entries) + ")";
167        }
168    }