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}