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}