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}