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