001// License: GPL. See LICENSE file for details.
002package org.openstreetmap.josm.tools;
003
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.HashMap;
007import java.util.LinkedHashSet;
008import java.util.List;
009import java.util.Map;
010import java.util.Map.Entry;
011import 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 * @param <A> Key type
020 * @param <B> Value type
021 *
022 * @since 2702
023 */
024public class MultiMap<A, B> {
025
026    private final Map<A, Set<B>> map;
027
028    /**
029     * Constructs a new {@code MultiMap}.
030     */
031    public MultiMap() {
032        map = new HashMap<>();
033    }
034
035    /**
036     * Constructs a new {@code MultiMap} with the specified initial capacity.
037     * @param capacity the initial capacity
038     */
039    public MultiMap(int capacity) {
040        map = new HashMap<>(capacity);
041    }
042
043    /**
044     * Map a key to a value.
045     *
046     * Can be called multiple times with the same key, but different value.
047     * @param key key with which the specified value is to be associated
048     * @param value value to be associated with the specified key
049     */
050    public void put(A key, B value) {
051        Set<B> vals = map.get(key);
052        if (vals == null) {
053            vals = new LinkedHashSet<>();
054            map.put(key, vals);
055        }
056        vals.add(value);
057    }
058
059    /**
060     * Put a key that maps to nothing. (Only if it is not already in the map)
061     *
062     * Afterwards containsKey(key) will return true and get(key) will return
063     * an empty Set instead of null.
064     * @param key key with which an empty set is to be associated
065     */
066    public void putVoid(A key) {
067        if (map.containsKey(key))
068            return;
069        map.put(key, new LinkedHashSet<B>());
070    }
071
072    /**
073     * Map the key to all the given values.
074     *
075     * Adds to the mappings that are already there.
076     * @param key key with which the specified values are to be associated
077     * @param values values to be associated with the specified key
078     */
079    public void putAll(A key, Collection<B> values) {
080        Set<B> vals = map.get(key);
081        if (vals == null) {
082            vals = new LinkedHashSet<>(values);
083            map.put(key, vals);
084        }
085        vals.addAll(values);
086    }
087
088    /**
089     * Get the keySet.
090     * @return a set view of the keys contained in this map
091     * @see Map#keySet()
092     */
093    public Set<A> keySet() {
094        return map.keySet();
095    }
096
097    /**
098     * Returns the Set associated with the given key. Result is null if
099     * nothing has been mapped to this key.
100     *
101     * Modifications of the returned list changes the underling map,
102     * but you should better not do that.
103     * @param key the key whose associated value is to be returned
104     * @return the set of values to which the specified key is mapped, or {@code null} if this map contains no mapping for the key
105     * @see Map#get(Object)
106     */
107    public Set<B> get(A key) {
108        return map.get(key);
109    }
110
111    /**
112     * Like get, but returns an empty Set if nothing has been mapped to the key.
113     * @param key the key whose associated value is to be returned
114     * @return the set of values to which the specified key is mapped, or an empty set if this map contains no mapping for the key
115     */
116    public Set<B> getValues(A key) {
117        if (!map.containsKey(key))
118            return new LinkedHashSet<>();
119        return map.get(key);
120    }
121
122    /**
123     * Returns {@code true} if this map contains no key-value mappings.
124     * @return {@code true} if this map contains no key-value mappings
125     * @see Map#isEmpty()
126     */
127    public boolean isEmpty() {
128        return map.isEmpty();
129    }
130
131    /**
132     * Returns {@code true} if this map contains a mapping for the specified key.
133     * @param key key whose presence in this map is to be tested
134     * @return {@code true} if this map contains a mapping for the specified key
135     * @see Map#containsKey(Object)
136     */
137    public boolean containsKey(A key) {
138        return map.containsKey(key);
139    }
140
141    /**
142     * Returns true if the multimap contains a value for a key.
143     *
144     * @param key The key
145     * @param value The value
146     * @return true if the key contains the value
147     */
148    public boolean contains(A key, B value) {
149        Set<B> values = get(key);
150        return (values == null) ? false : values.contains(value);
151    }
152
153    /**
154     * Removes all of the mappings from this map. The map will be empty after this call returns.
155     * @see Map#clear()
156     */
157    public void clear() {
158        map.clear();
159    }
160
161    /**
162     * Returns a Set view of the mappings contained in this map.
163     * The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.
164     * @return a set view of the mappings contained in this map
165     * @see Map#entrySet()
166     */
167    public Set<Entry<A, Set<B>>> entrySet() {
168        return map.entrySet();
169    }
170
171    /**
172     * Returns the number of keys.
173     * @return the number of key-value mappings in this map
174     * @see Map#size()
175     */
176    public int size() {
177        return map.size();
178    }
179
180    /**
181     * Returns a collection of all value sets.
182     * @return a collection view of the values contained in this map
183     * @see Map#values()
184     */
185    public Collection<Set<B>> values() {
186        return map.values();
187    }
188
189    /**
190     * Removes a certain key=value mapping.
191     * @param key key whose mapping is to be removed from the map
192     * @param value value whose mapping is to be removed from the map
193     *
194     * @return {@code true}, if something was removed
195     */
196    public boolean remove(A key, B value) {
197        Set<B> values = get(key);
198        if (values != null) {
199            return values.remove(value);
200        }
201        return false;
202    }
203
204    /**
205     * Removes all mappings for a certain key.
206     * @param key key whose mapping is to be removed from the map
207     * @return the previous value associated with key, or {@code null} if there was no mapping for key.
208     * @see Map#remove(Object)
209     */
210    public Set<B> remove(A key) {
211        return map.remove(key);
212    }
213
214    @Override
215    public int hashCode() {
216        return map.hashCode();
217    }
218
219    @Override
220    public boolean equals(Object obj) {
221        if (this == obj)
222            return true;
223        if (obj == null)
224            return false;
225        if (!(obj instanceof MultiMap))
226            return false;
227        return map.equals(((MultiMap<?,?>) obj).map);
228    }
229
230    @Override
231    public String toString() {
232        List<String> entries = new ArrayList<>(map.size());
233        for (A key : map.keySet()) {
234            entries.add(key + "->{" + Utils.join(",", map.get(key)) + "}");
235        }
236        return "(" + Utils.join(",", entries) + ")";
237    }
238}