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        return map.getOrDefault(key, Collections.emptySet());
124    }
125
126    /**
127     * Returns {@code true} if this map contains no key-value mappings.
128     * @return {@code true} if this map contains no key-value mappings
129     * @see Map#isEmpty()
130     */
131    public boolean isEmpty() {
132        return map.isEmpty();
133    }
134
135    /**
136     * Returns {@code true} if this map contains a mapping for the specified key.
137     * @param key key whose presence in this map is to be tested
138     * @return {@code true} if this map contains a mapping for the specified key
139     * @see Map#containsKey(Object)
140     */
141    public boolean containsKey(A key) {
142        return map.containsKey(key);
143    }
144
145    /**
146     * Returns true if the multimap contains a value for a key.
147     *
148     * @param key The key
149     * @param value The value
150     * @return true if the key contains the value
151     */
152    public boolean contains(A key, B value) {
153        Set<B> values = get(key);
154        return values != null && values.contains(value);
155    }
156
157    /**
158     * Removes all of the mappings from this map. The map will be empty after this call returns.
159     * @see Map#clear()
160     */
161    public void clear() {
162        map.clear();
163    }
164
165    /**
166     * Returns a Set view of the mappings contained in this map.
167     * The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.
168     * @return a set view of the mappings contained in this map
169     * @see Map#entrySet()
170     */
171    public Set<Entry<A, Set<B>>> entrySet() {
172        return map.entrySet();
173    }
174
175    /**
176     * Returns the number of keys.
177     * @return the number of key-value mappings in this map
178     * @see Map#size()
179     */
180    public int size() {
181        return map.size();
182    }
183
184    /**
185     * Returns a collection of all value sets.
186     * @return a collection view of the values contained in this map
187     * @see Map#values()
188     */
189    public Collection<Set<B>> values() {
190        return map.values();
191    }
192
193    /**
194     * Removes a certain key=value mapping.
195     * @param key key whose mapping is to be removed from the map
196     * @param value value whose mapping is to be removed from the map
197     *
198     * @return {@code true}, if something was removed
199     */
200    public boolean remove(A key, B value) {
201        Set<B> values = get(key);
202        if (values != null) {
203            return values.remove(value);
204        }
205        return false;
206    }
207
208    /**
209     * Removes all mappings for a certain key.
210     * @param key key whose mapping is to be removed from the map
211     * @return the previous value associated with key, or {@code null} if there was no mapping for key.
212     * @see Map#remove(Object)
213     */
214    public Set<B> remove(A key) {
215        return map.remove(key);
216    }
217
218    @Override
219    public int hashCode() {
220        return Objects.hash(map);
221    }
222
223    /**
224     * Converts this {@code MultiMap} to a {@code Map} with {@code Set} values.
225     * @return the converted {@code Map}
226     */
227    public Map<A, Set<B>> toMap() {
228        Map<A, Set<B>> result = new HashMap<>();
229        for (Entry<A, Set<B>> e : map.entrySet()) {
230            result.put(e.getKey(), Collections.unmodifiableSet(e.getValue()));
231        }
232        return result;
233    }
234
235    @Override
236    public boolean equals(Object obj) {
237        if (this == obj) return true;
238        if (obj == null || getClass() != obj.getClass()) return false;
239        MultiMap<?, ?> multiMap = (MultiMap<?, ?>) obj;
240        return Objects.equals(map, multiMap.map);
241    }
242
243    @Override
244    public String toString() {
245        return map.entrySet().stream()
246                .map(entry -> entry.getKey() + "->" + entry.getValue())
247                .collect(Collectors.joining(",", "(", ")"));
248    }
249}