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