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        Set<B> vals = map.get(key);
069        if (vals == null) {
070            vals = new LinkedHashSet<>();
071            map.put(key, vals);
072        }
073        vals.add(value);
074    }
075
076    /**
077     * Put a key that maps to nothing. (Only if it is not already in the map)
078     *
079     * Afterwards containsKey(key) will return true and get(key) will return
080     * an empty Set instead of null.
081     * @param key key with which an empty set is to be associated
082     */
083    public void putVoid(A key) {
084        if (map.containsKey(key))
085            return;
086        map.put(key, new LinkedHashSet<B>());
087    }
088
089    /**
090     * Map the key to all the given values.
091     *
092     * Adds to the mappings that are already there.
093     * @param key key with which the specified values are to be associated
094     * @param values values to be associated with the specified key
095     */
096    public void putAll(A key, Collection<B> values) {
097        Set<B> vals = map.get(key);
098        if (vals == null) {
099            vals = new LinkedHashSet<>(values);
100            map.put(key, vals);
101        }
102        vals.addAll(values);
103    }
104
105    /**
106     * Get the keySet.
107     * @return a set view of the keys contained in this map
108     * @see Map#keySet()
109     */
110    public Set<A> keySet() {
111        return map.keySet();
112    }
113
114    /**
115     * Returns the Set associated with the given key. Result is null if
116     * nothing has been mapped to this key.
117     *
118     * Modifications of the returned list changes the underling map,
119     * but you should better not do that.
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 {@code null} if this map contains no mapping for the key
122     * @see Map#get(Object)
123     */
124    public Set<B> get(A key) {
125        return map.get(key);
126    }
127
128    /**
129     * Like get, but returns an empty Set if nothing has been mapped to the key.
130     * @param key the key whose associated value is to be returned
131     * @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
132     */
133    public Set<B> getValues(A key) {
134        if (!map.containsKey(key))
135            return new LinkedHashSet<>();
136        return map.get(key);
137    }
138
139    /**
140     * Returns {@code true} if this map contains no key-value mappings.
141     * @return {@code true} if this map contains no key-value mappings
142     * @see Map#isEmpty()
143     */
144    public boolean isEmpty() {
145        return map.isEmpty();
146    }
147
148    /**
149     * Returns {@code true} if this map contains a mapping for the specified key.
150     * @param key key whose presence in this map is to be tested
151     * @return {@code true} if this map contains a mapping for the specified key
152     * @see Map#containsKey(Object)
153     */
154    public boolean containsKey(A key) {
155        return map.containsKey(key);
156    }
157
158    /**
159     * Returns true if the multimap contains a value for a key.
160     *
161     * @param key The key
162     * @param value The value
163     * @return true if the key contains the value
164     */
165    public boolean contains(A key, B value) {
166        Set<B> values = get(key);
167        return values != null && values.contains(value);
168    }
169
170    /**
171     * Removes all of the mappings from this map. The map will be empty after this call returns.
172     * @see Map#clear()
173     */
174    public void clear() {
175        map.clear();
176    }
177
178    /**
179     * Returns a Set view of the mappings contained in this map.
180     * The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.
181     * @return a set view of the mappings contained in this map
182     * @see Map#entrySet()
183     */
184    public Set<Entry<A, Set<B>>> entrySet() {
185        return map.entrySet();
186    }
187
188    /**
189     * Returns the number of keys.
190     * @return the number of key-value mappings in this map
191     * @see Map#size()
192     */
193    public int size() {
194        return map.size();
195    }
196
197    /**
198     * Returns a collection of all value sets.
199     * @return a collection view of the values contained in this map
200     * @see Map#values()
201     */
202    public Collection<Set<B>> values() {
203        return map.values();
204    }
205
206    /**
207     * Removes a certain key=value mapping.
208     * @param key key whose mapping is to be removed from the map
209     * @param value value whose mapping is to be removed from the map
210     *
211     * @return {@code true}, if something was removed
212     */
213    public boolean remove(A key, B value) {
214        Set<B> values = get(key);
215        if (values != null) {
216            return values.remove(value);
217        }
218        return false;
219    }
220
221    /**
222     * Removes all mappings for a certain key.
223     * @param key key whose mapping is to be removed from the map
224     * @return the previous value associated with key, or {@code null} if there was no mapping for key.
225     * @see Map#remove(Object)
226     */
227    public Set<B> remove(A key) {
228        return map.remove(key);
229    }
230
231    @Override
232    public int hashCode() {
233        return Objects.hash(map);
234    }
235
236    /**
237     * Converts this {@code MultiMap} to a {@code Map} with {@code Set} values.
238     * @return the converted {@code Map}
239     */
240    public Map<A, Set<B>> toMap() {
241        Map<A, Set<B>> result = new HashMap<>();
242        for (Entry<A, Set<B>> e : map.entrySet()) {
243            result.put(e.getKey(), Collections.unmodifiableSet(e.getValue()));
244        }
245        return result;
246    }
247
248    @Override
249    public boolean equals(Object obj) {
250        if (this == obj) return true;
251        if (obj == null || getClass() != obj.getClass()) return false;
252        MultiMap<?, ?> multiMap = (MultiMap<?, ?>) obj;
253        return Objects.equals(map, multiMap.map);
254    }
255
256    @Override
257    public String toString() {
258        List<String> entries = new ArrayList<>(map.size());
259        for (Entry<A, Set<B>> entry : map.entrySet()) {
260            entries.add(entry.getKey() + "->{" + Utils.join(",", entry.getValue()) + '}');
261        }
262        return '(' + Utils.join(",", entries) + ')';
263    }
264}