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}