001 /*
002 * Copyright (C) 2007 Google Inc.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021
022 import com.google.common.annotations.GwtCompatible;
023 import com.google.common.base.Function;
024 import com.google.common.base.Joiner.MapJoiner;
025 import com.google.common.base.Objects;
026 import com.google.common.base.Predicate;
027 import com.google.common.base.Predicates;
028
029 import java.io.Serializable;
030 import java.util.AbstractCollection;
031 import java.util.AbstractMap;
032 import java.util.AbstractSet;
033 import java.util.Collection;
034 import java.util.Collections;
035 import java.util.Comparator;
036 import java.util.EnumMap;
037 import java.util.Enumeration;
038 import java.util.HashMap;
039 import java.util.IdentityHashMap;
040 import java.util.Iterator;
041 import java.util.LinkedHashMap;
042 import java.util.Map;
043 import java.util.Map.Entry;
044 import java.util.Properties;
045 import java.util.Set;
046 import java.util.SortedMap;
047 import java.util.TreeMap;
048 import java.util.concurrent.ConcurrentMap;
049
050 import javax.annotation.Nullable;
051
052 /**
053 * Static utility methods pertaining to {@link Map} instances. Also see this
054 * class's counterparts {@link Lists} and {@link Sets}.
055 *
056 * @author Kevin Bourrillion
057 * @author Mike Bostock
058 * @author Isaac Shum
059 * @since 2 (imported from Google Collections Library)
060 */
061 @GwtCompatible
062 public final class Maps {
063 private Maps() {}
064
065 /**
066 * Creates a <i>mutable</i>, empty {@code HashMap} instance.
067 *
068 * <p><b>Note:</b> if mutability is not required, use {@link
069 * ImmutableMap#of()} instead.
070 *
071 * <p><b>Note:</b> if {@code K} is an {@code enum} type, use {@link
072 * #newEnumMap} instead.
073 *
074 * @return a new, empty {@code HashMap}
075 */
076 public static <K, V> HashMap<K, V> newHashMap() {
077 return new HashMap<K, V>();
078 }
079
080 /**
081 * Creates a {@code HashMap} instance with enough capacity to hold the
082 * specified number of elements without rehashing.
083 *
084 * @param expectedSize the expected size
085 * @return a new, empty {@code HashMap} with enough capacity to hold {@code
086 * expectedSize} elements without rehashing
087 * @throws IllegalArgumentException if {@code expectedSize} is negative
088 */
089 public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(
090 int expectedSize) {
091 /*
092 * The HashMap is constructed with an initialCapacity that's greater than
093 * expectedSize. The larger value is necessary because HashMap resizes its
094 * internal array if the map size exceeds loadFactor * initialCapacity.
095 */
096 return new HashMap<K, V>(capacity(expectedSize));
097 }
098
099 /**
100 * Returns an appropriate value for the "capacity" (in reality, "minimum table
101 * size") parameter of a {@link HashMap} constructor, such that the resulting
102 * table will be between 25% and 50% full when it contains {@code
103 * expectedSize} entries.
104 *
105 * @throws IllegalArgumentException if {@code expectedSize} is negative
106 */
107 static int capacity(int expectedSize) {
108 checkArgument(expectedSize >= 0);
109 return Math.max(expectedSize * 2, 16);
110 }
111
112 /**
113 * Creates a <i>mutable</i> {@code HashMap} instance with the same mappings as
114 * the specified map.
115 *
116 * <p><b>Note:</b> if mutability is not required, use {@link
117 * ImmutableMap#copyOf(Map)} instead.
118 *
119 * <p><b>Note:</b> if {@code K} is an {@link Enum} type, use {@link
120 * #newEnumMap} instead.
121 *
122 * @param map the mappings to be placed in the new map
123 * @return a new {@code HashMap} initialized with the mappings from {@code
124 * map}
125 */
126 public static <K, V> HashMap<K, V> newHashMap(
127 Map<? extends K, ? extends V> map) {
128 return new HashMap<K, V>(map);
129 }
130
131 /**
132 * Creates a <i>mutable</i>, empty, insertion-ordered {@code LinkedHashMap}
133 * instance.
134 *
135 * <p><b>Note:</b> if mutability is not required, use {@link
136 * ImmutableMap#of()} instead.
137 *
138 * @return a new, empty {@code LinkedHashMap}
139 */
140 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap() {
141 return new LinkedHashMap<K, V>();
142 }
143
144 /**
145 * Creates a <i>mutable</i>, insertion-ordered {@code LinkedHashMap} instance
146 * with the same mappings as the specified map.
147 *
148 * <p><b>Note:</b> if mutability is not required, use {@link
149 * ImmutableMap#copyOf(Map)} instead.
150 *
151 * @param map the mappings to be placed in the new map
152 * @return a new, {@code LinkedHashMap} initialized with the mappings from
153 * {@code map}
154 */
155 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(
156 Map<? extends K, ? extends V> map) {
157 return new LinkedHashMap<K, V>(map);
158 }
159
160 /**
161 * Returns a general-purpose instance of {@code ConcurrentMap}, which supports
162 * all optional operations of the ConcurrentMap interface. It does not permit
163 * null keys or values. It is serializable.
164 *
165 * <p>This is currently accomplished by calling {@link MapMaker#makeMap()}.
166 *
167 * <p>It is preferable to use {@code MapMaker} directly (rather than through
168 * this method), as it presents numerous useful configuration options,
169 * such as the concurrency level, load factor, key/value reference types,
170 * and value computation.
171 *
172 * @return a new, empty {@code ConcurrentMap}
173 * @since 3
174 */
175 public static <K, V> ConcurrentMap<K, V> newConcurrentMap() {
176 return new MapMaker().<K, V>makeMap();
177 }
178
179 /**
180 * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the natural
181 * ordering of its elements.
182 *
183 * <p><b>Note:</b> if mutability is not required, use {@link
184 * ImmutableSortedMap#of()} instead.
185 *
186 * @return a new, empty {@code TreeMap}
187 */
188 @SuppressWarnings("unchecked") // eclipse doesn't like the raw Comparable
189 public static <K extends Comparable, V> TreeMap<K, V> newTreeMap() {
190 return new TreeMap<K, V>();
191 }
192
193 /**
194 * Creates a <i>mutable</i> {@code TreeMap} instance with the same mappings as
195 * the specified map and using the same ordering as the specified map.
196 *
197 * <p><b>Note:</b> if mutability is not required, use {@link
198 * ImmutableSortedMap#copyOfSorted(SortedMap)} instead.
199 *
200 * @param map the sorted map whose mappings are to be placed in the new map
201 * and whose comparator is to be used to sort the new map
202 * @return a new {@code TreeMap} initialized with the mappings from {@code
203 * map} and using the comparator of {@code map}
204 */
205 public static <K, V> TreeMap<K, V> newTreeMap(SortedMap<K, ? extends V> map) {
206 return new TreeMap<K, V>(map);
207 }
208
209 /**
210 * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the given
211 * comparator.
212 *
213 * <p><b>Note:</b> if mutability is not required, use {@code
214 * ImmutableSortedMap.orderedBy(comparator).build()} instead.
215 *
216 * @param comparator the comparator to sort the keys with
217 * @return a new, empty {@code TreeMap}
218 */
219 public static <C, K extends C, V> TreeMap<K, V> newTreeMap(
220 @Nullable Comparator<C> comparator) {
221 // Ideally, the extra type parameter "C" shouldn't be necessary. It is a
222 // work-around of a compiler type inference quirk that prevents the
223 // following code from being compiled:
224 // Comparator<Class<?>> comparator = null;
225 // Map<Class<? extends Throwable>, String> map = newTreeMap(comparator);
226 return new TreeMap<K, V>(comparator);
227 }
228
229 /**
230 * Creates an {@code EnumMap} instance.
231 *
232 * @param type the key type for this map
233 * @return a new, empty {@code EnumMap}
234 */
235 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(Class<K> type) {
236 return new EnumMap<K, V>(checkNotNull(type));
237 }
238
239 /**
240 * Creates an {@code EnumMap} with the same mappings as the specified map.
241 *
242 * @param map the map from which to initialize this {@code EnumMap}
243 * @return a new {@code EnumMap} initialized with the mappings from {@code
244 * map}
245 * @throws IllegalArgumentException if {@code m} is not an {@code EnumMap}
246 * instance and contains no mappings
247 */
248 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(
249 Map<K, ? extends V> map) {
250 return new EnumMap<K, V>(map);
251 }
252
253 /**
254 * Creates an {@code IdentityHashMap} instance.
255 *
256 * @return a new, empty {@code IdentityHashMap}
257 */
258 public static <K, V> IdentityHashMap<K, V> newIdentityHashMap() {
259 return new IdentityHashMap<K, V>();
260 }
261
262 /**
263 * Returns a synchronized (thread-safe) bimap backed by the specified bimap.
264 * In order to guarantee serial access, it is critical that <b>all</b> access
265 * to the backing bimap is accomplished through the returned bimap.
266 *
267 * <p>It is imperative that the user manually synchronize on the returned map
268 * when accessing any of its collection views: <pre> {@code
269 *
270 * BiMap<Long, String> map = Maps.synchronizedBiMap(
271 * HashBiMap.<Long, String>create());
272 * ...
273 * Set<Long> set = map.keySet(); // Needn't be in synchronized block
274 * ...
275 * synchronized (map) { // Synchronizing on map, not set!
276 * Iterator<Long> it = set.iterator(); // Must be in synchronized block
277 * while (it.hasNext()) {
278 * foo(it.next());
279 * }
280 * }}</pre>
281 *
282 * Failure to follow this advice may result in non-deterministic behavior.
283 *
284 * <p>The returned bimap will be serializable if the specified bimap is
285 * serializable.
286 *
287 * @param bimap the bimap to be wrapped in a synchronized view
288 * @return a sychronized view of the specified bimap
289 */
290 public static <K, V> BiMap<K, V> synchronizedBiMap(BiMap<K, V> bimap) {
291 return Synchronized.biMap(bimap, null);
292 }
293
294 /**
295 * Computes the difference between two maps. This difference is an immutable
296 * snapshot of the state of the maps at the time this method is called. It
297 * will never change, even if the maps change at a later time.
298 *
299 * <p>Since this method uses {@code HashMap} instances internally, the keys of
300 * the supplied maps must be well-behaved with respect to
301 * {@link Object#equals} and {@link Object#hashCode}.
302 *
303 * <p><b>Note:</b>If you only need to know whether two maps have the same
304 * mappings, call {@code left.equals(right)} instead of this method.
305 *
306 * @param left the map to treat as the "left" map for purposes of comparison
307 * @param right the map to treat as the "right" map for purposes of comparison
308 * @return the difference between the two maps
309 */
310 public static <K, V> MapDifference<K, V> difference(
311 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) {
312 Map<K, V> onlyOnLeft = newHashMap();
313 Map<K, V> onlyOnRight = new HashMap<K, V>(right); // will whittle it down
314 Map<K, V> onBoth = newHashMap();
315 Map<K, MapDifference.ValueDifference<V>> differences = newHashMap();
316 boolean eq = true;
317
318 for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
319 K leftKey = entry.getKey();
320 V leftValue = entry.getValue();
321 if (right.containsKey(leftKey)) {
322 V rightValue = onlyOnRight.remove(leftKey);
323 if (Objects.equal(leftValue, rightValue)) {
324 onBoth.put(leftKey, leftValue);
325 } else {
326 eq = false;
327 differences.put(
328 leftKey, new ValueDifferenceImpl<V>(leftValue, rightValue));
329 }
330 } else {
331 eq = false;
332 onlyOnLeft.put(leftKey, leftValue);
333 }
334 }
335
336 boolean areEqual = eq && onlyOnRight.isEmpty();
337 return new MapDifferenceImpl<K, V>(
338 areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
339 }
340
341 private static class MapDifferenceImpl<K, V> implements MapDifference<K, V> {
342 final boolean areEqual;
343 final Map<K, V> onlyOnLeft;
344 final Map<K, V> onlyOnRight;
345 final Map<K, V> onBoth;
346 final Map<K, ValueDifference<V>> differences;
347
348 MapDifferenceImpl(boolean areEqual, Map<K, V> onlyOnLeft,
349 Map<K, V> onlyOnRight, Map<K, V> onBoth,
350 Map<K, ValueDifference<V>> differences) {
351 this.areEqual = areEqual;
352 this.onlyOnLeft = Collections.unmodifiableMap(onlyOnLeft);
353 this.onlyOnRight = Collections.unmodifiableMap(onlyOnRight);
354 this.onBoth = Collections.unmodifiableMap(onBoth);
355 this.differences = Collections.unmodifiableMap(differences);
356 }
357
358 public boolean areEqual() {
359 return areEqual;
360 }
361
362 public Map<K, V> entriesOnlyOnLeft() {
363 return onlyOnLeft;
364 }
365
366 public Map<K, V> entriesOnlyOnRight() {
367 return onlyOnRight;
368 }
369
370 public Map<K, V> entriesInCommon() {
371 return onBoth;
372 }
373
374 public Map<K, ValueDifference<V>> entriesDiffering() {
375 return differences;
376 }
377
378 @Override public boolean equals(Object object) {
379 if (object == this) {
380 return true;
381 }
382 if (object instanceof MapDifference) {
383 MapDifference<?, ?> other = (MapDifference<?, ?>) object;
384 return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft())
385 && entriesOnlyOnRight().equals(other.entriesOnlyOnRight())
386 && entriesInCommon().equals(other.entriesInCommon())
387 && entriesDiffering().equals(other.entriesDiffering());
388 }
389 return false;
390 }
391
392 @Override public int hashCode() {
393 return Objects.hashCode(entriesOnlyOnLeft(), entriesOnlyOnRight(),
394 entriesInCommon(), entriesDiffering());
395 }
396
397 @Override public String toString() {
398 if (areEqual) {
399 return "equal";
400 }
401
402 StringBuilder result = new StringBuilder("not equal");
403 if (!onlyOnLeft.isEmpty()) {
404 result.append(": only on left=").append(onlyOnLeft);
405 }
406 if (!onlyOnRight.isEmpty()) {
407 result.append(": only on right=").append(onlyOnRight);
408 }
409 if (!differences.isEmpty()) {
410 result.append(": value differences=").append(differences);
411 }
412 return result.toString();
413 }
414 }
415
416 static class ValueDifferenceImpl<V>
417 implements MapDifference.ValueDifference<V> {
418 private final V left;
419 private final V right;
420
421 ValueDifferenceImpl(@Nullable V left, @Nullable V right) {
422 this.left = left;
423 this.right = right;
424 }
425
426 public V leftValue() {
427 return left;
428 }
429
430 public V rightValue() {
431 return right;
432 }
433
434 @Override public boolean equals(@Nullable Object object) {
435 if (object instanceof MapDifference.ValueDifference<?>) {
436 MapDifference.ValueDifference<?> that =
437 (MapDifference.ValueDifference<?>) object;
438 return Objects.equal(this.left, that.leftValue())
439 && Objects.equal(this.right, that.rightValue());
440 }
441 return false;
442 }
443
444 @Override public int hashCode() {
445 return Objects.hashCode(left, right);
446 }
447
448 @Override public String toString() {
449 return "(" + left + ", " + right + ")";
450 }
451 }
452
453 /**
454 * Returns an immutable map for which the {@link Map#values} are the given
455 * elements in the given order, and each key is the product of invoking a
456 * supplied function on its corresponding value.
457 *
458 * @param values the values to use when constructing the {@code Map}
459 * @param keyFunction the function used to produce the key for each value
460 * @return a map mapping the result of evaluating the function {@code
461 * keyFunction} on each value in the input collection to that value
462 * @throws IllegalArgumentException if {@code keyFunction} produces the same
463 * key for more than one value in the input collection
464 * @throws NullPointerException if any elements of {@code values} is null, or
465 * if {@code keyFunction} produces {@code null} for any value
466 */
467 // TODO: consider returning a bimap, whose inverse view does lookups by
468 // invoking the function.
469 public static <K, V> ImmutableMap<K, V> uniqueIndex(
470 Iterable<V> values, Function<? super V, K> keyFunction) {
471 checkNotNull(keyFunction);
472 ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
473 for (V value : values) {
474 builder.put(keyFunction.apply(value), value);
475 }
476 return builder.build();
477 }
478
479 /**
480 * Creates an {@code ImmutableMap<String, String>} from a {@code Properties}
481 * instance. Properties normally derive from {@code Map<Object, Object>}, but
482 * they typically contain strings, which is awkward. This method lets you get
483 * a plain-old-{@code Map} out of a {@code Properties}.
484 *
485 * @param properties a {@code Properties} object to be converted
486 * @return an immutable map containing all the entries in {@code properties}
487 * @throws ClassCastException if any key in {@code Properties} is not a {@code
488 * String}
489 * @throws NullPointerException if any key or value in {@code Properties} is
490 * null
491 */
492 public static ImmutableMap<String, String> fromProperties(
493 Properties properties) {
494 ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
495
496 for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements();) {
497 String key = (String) e.nextElement();
498 builder.put(key, properties.getProperty(key));
499 }
500
501 return builder.build();
502 }
503
504 /**
505 * Returns an immutable map entry with the specified key and value. The {@link
506 * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
507 *
508 * <p>The returned entry is serializable.
509 *
510 * @param key the key to be associated with the returned entry
511 * @param value the value to be associated with the returned entry
512 */
513 public static <K, V> Entry<K, V> immutableEntry(
514 @Nullable K key, @Nullable V value) {
515 return new ImmutableEntry<K, V>(key, value);
516 }
517
518 /**
519 * Returns an unmodifiable view of the specified set of entries. The {@link
520 * Entry#setValue} operation throws an {@link UnsupportedOperationException},
521 * as do any operations that would modify the returned set.
522 *
523 * @param entrySet the entries for which to return an unmodifiable view
524 * @return an unmodifiable view of the entries
525 */
526 static <K, V> Set<Entry<K, V>> unmodifiableEntrySet(
527 Set<Entry<K, V>> entrySet) {
528 return new UnmodifiableEntrySet<K, V>(
529 Collections.unmodifiableSet(entrySet));
530 }
531
532 /**
533 * Returns an unmodifiable view of the specified map entry. The {@link
534 * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
535 * This also has the side-effect of redefining {@code equals} to comply with
536 * the Entry contract, to avoid a possible nefarious implementation of equals.
537 *
538 * @param entry the entry for which to return an unmodifiable view
539 * @return an unmodifiable view of the entry
540 */
541 private static <K, V> Entry<K, V> unmodifiableEntry(final Entry<K, V> entry) {
542 checkNotNull(entry);
543 return new AbstractMapEntry<K, V>() {
544 @Override public K getKey() {
545 return entry.getKey();
546 }
547
548 @Override public V getValue() {
549 return entry.getValue();
550 }
551 };
552 }
553
554 /** @see Multimaps#unmodifiableEntries */
555 static class UnmodifiableEntries<K, V>
556 extends ForwardingCollection<Entry<K, V>> {
557 private final Collection<Entry<K, V>> entries;
558
559 UnmodifiableEntries(Collection<Entry<K, V>> entries) {
560 this.entries = entries;
561 }
562
563 @Override protected Collection<Entry<K, V>> delegate() {
564 return entries;
565 }
566
567 @Override public Iterator<Entry<K, V>> iterator() {
568 final Iterator<Entry<K, V>> delegate = super.iterator();
569 return new ForwardingIterator<Entry<K, V>>() {
570 @Override public Entry<K, V> next() {
571 return unmodifiableEntry(super.next());
572 }
573
574 @Override protected Iterator<Entry<K, V>> delegate() {
575 return delegate;
576 }
577 };
578 }
579
580 // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
581
582 @Override public Object[] toArray() {
583 return ObjectArrays.toArrayImpl(this);
584 }
585
586 @Override public <T> T[] toArray(T[] array) {
587 return ObjectArrays.toArrayImpl(this, array);
588 }
589
590 @Override public boolean contains(Object o) {
591 return containsEntryImpl(delegate(), o);
592 }
593
594 @Override public boolean containsAll(Collection<?> c) {
595 return Collections2.containsAll(this, c);
596 }
597 }
598
599 /** @see Maps#unmodifiableEntrySet(Set) */
600 static class UnmodifiableEntrySet<K, V>
601 extends UnmodifiableEntries<K, V> implements Set<Entry<K, V>> {
602 UnmodifiableEntrySet(Set<Entry<K, V>> entries) {
603 super(entries);
604 }
605
606 // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
607
608 @Override public boolean equals(@Nullable Object object) {
609 return Collections2.setEquals(this, object);
610 }
611
612 @Override public int hashCode() {
613 return Sets.hashCodeImpl(this);
614 }
615 }
616
617 /**
618 * Returns an unmodifiable view of the specified bimap. This method allows
619 * modules to provide users with "read-only" access to internal bimaps. Query
620 * operations on the returned bimap "read through" to the specified bimap, and
621 * attemps to modify the returned map, whether direct or via its collection
622 * views, result in an {@code UnsupportedOperationException}.
623 *
624 * <p>The returned bimap will be serializable if the specified bimap is
625 * serializable.
626 *
627 * @param bimap the bimap for which an unmodifiable view is to be returned
628 * @return an unmodifiable view of the specified bimap
629 */
630 public static <K, V> BiMap<K, V> unmodifiableBiMap(
631 BiMap<? extends K, ? extends V> bimap) {
632 return new UnmodifiableBiMap<K, V>(bimap, null);
633 }
634
635 /** @see Maps#unmodifiableBiMap(BiMap) */
636 private static class UnmodifiableBiMap<K, V>
637 extends ForwardingMap<K, V> implements BiMap<K, V>, Serializable {
638 final Map<K, V> unmodifiableMap;
639 final BiMap<? extends K, ? extends V> delegate;
640 transient BiMap<V, K> inverse;
641 transient Set<V> values;
642
643 UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate,
644 @Nullable BiMap<V, K> inverse) {
645 unmodifiableMap = Collections.unmodifiableMap(delegate);
646 this.delegate = delegate;
647 this.inverse = inverse;
648 }
649
650 @Override protected Map<K, V> delegate() {
651 return unmodifiableMap;
652 }
653
654 public V forcePut(K key, V value) {
655 throw new UnsupportedOperationException();
656 }
657
658 public BiMap<V, K> inverse() {
659 BiMap<V, K> result = inverse;
660 return (result == null)
661 ? inverse = new UnmodifiableBiMap<V, K>(delegate.inverse(), this)
662 : result;
663 }
664
665 @Override public Set<V> values() {
666 Set<V> result = values;
667 return (result == null)
668 ? values = Collections.unmodifiableSet(delegate.values())
669 : result;
670 }
671
672 private static final long serialVersionUID = 0;
673 }
674
675 /**
676 * Implements {@code Collection.contains} safely for forwarding collections of
677 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
678 * wrapped using {@link #unmodifiableEntry} to protect against a possible
679 * nefarious equals method.
680 *
681 * <p>Note that {@code c} is the backing (delegate) collection, rather than
682 * the forwarding collection.
683 *
684 * @param c the delegate (unwrapped) collection of map entries
685 * @param o the object that might be contained in {@code c}
686 * @return {@code true} if {@code c} contains {@code o}
687 */
688 static <K, V> boolean containsEntryImpl(Collection<Entry<K, V>> c, Object o) {
689 if (!(o instanceof Entry)) {
690 return false;
691 }
692 return c.contains(unmodifiableEntry((Entry<?, ?>) o));
693 }
694
695 /**
696 * Implements {@code Collection.remove} safely for forwarding collections of
697 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
698 * wrapped using {@link #unmodifiableEntry} to protect against a possible
699 * nefarious equals method.
700 *
701 * <p>Note that {@code c} is backing (delegate) collection, rather than the
702 * forwarding collection.
703 *
704 * @param c the delegate (unwrapped) collection of map entries
705 * @param o the object to remove from {@code c}
706 * @return {@code true} if {@code c} was changed
707 */
708 static <K, V> boolean removeEntryImpl(Collection<Entry<K, V>> c, Object o) {
709 if (!(o instanceof Entry)) {
710 return false;
711 }
712 return c.remove(unmodifiableEntry((Entry<?, ?>) o));
713 }
714
715 /**
716 * Returns a view of a map where each value is transformed by a function. All
717 * other properties of the map, such as iteration order, are left intact. For
718 * example, the code: <pre> {@code
719 *
720 * Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
721 * Function<Integer, Double> sqrt =
722 * new Function<Integer, Double>() {
723 * public Double apply(Integer in) {
724 * return Math.sqrt((int) in);
725 * }
726 * };
727 * Map<String, Double> transformed = Maps.transformValues(map, sqrt);
728 * System.out.println(transformed);}</pre>
729 *
730 * ... prints {@code {a=2.0, b=3.0}}.
731 *
732 * <p>Changes in the underlying map are reflected in this view. Conversely,
733 * this view supports removal operations, and these are reflected in the
734 * underlying map.
735 *
736 * <p>It's acceptable for the underlying map to contain null keys, and even
737 * null values provided that the function is capable of accepting null input.
738 * The transformed map might contain null values, if the function sometimes
739 * gives a null result.
740 *
741 * <p>The returned map is not thread-safe or serializable, even if the
742 * underlying map is.
743 *
744 * <p>The function is applied lazily, invoked when needed. This is necessary
745 * for the returned map to be a view, but it means that the function will be
746 * applied many times for bulk operations like {@link Map#containsValue} and
747 * {@code Map.toString()}. For this to perform well, {@code function} should
748 * be fast. To avoid lazy evaluation when the returned map doesn't need to be
749 * a view, copy the returned map into a new map of your choosing.
750 */
751 public static <K, V1, V2> Map<K, V2> transformValues(
752 Map<K, V1> fromMap, Function<? super V1, V2> function) {
753 return new TransformedValuesMap<K, V1, V2>(fromMap, function);
754 }
755
756 private static class TransformedValuesMap<K, V1, V2>
757 extends AbstractMap<K, V2> {
758 final Map<K, V1> fromMap;
759 final Function<? super V1, V2> function;
760
761 TransformedValuesMap(
762 Map<K, V1> fromMap, Function<? super V1, V2> function) {
763 this.fromMap = checkNotNull(fromMap);
764 this.function = checkNotNull(function);
765 }
766
767 @Override public int size() {
768 return fromMap.size();
769 }
770
771 @Override public boolean containsKey(Object key) {
772 return fromMap.containsKey(key);
773 }
774
775 @Override public V2 get(Object key) {
776 V1 value = fromMap.get(key);
777 return (value != null || fromMap.containsKey(key))
778 ? function.apply(value)
779 : null;
780 }
781
782 @Override public V2 remove(Object key) {
783 return fromMap.containsKey(key)
784 ? function.apply(fromMap.remove(key))
785 : null;
786 }
787
788 @Override public void clear() {
789 fromMap.clear();
790 }
791
792 EntrySet entrySet;
793
794 @Override public Set<Entry<K, V2>> entrySet() {
795 EntrySet result = entrySet;
796 if (result == null) {
797 entrySet = result = new EntrySet();
798 }
799 return result;
800 }
801
802 class EntrySet extends AbstractSet<Entry<K, V2>> {
803 @Override public int size() {
804 return TransformedValuesMap.this.size();
805 }
806
807 @Override public Iterator<Entry<K, V2>> iterator() {
808 final Iterator<Entry<K, V1>> mapIterator =
809 fromMap.entrySet().iterator();
810
811 return new Iterator<Entry<K, V2>>() {
812 public boolean hasNext() {
813 return mapIterator.hasNext();
814 }
815
816 public Entry<K, V2> next() {
817 final Entry<K, V1> entry = mapIterator.next();
818 return new AbstractMapEntry<K, V2>() {
819 @Override public K getKey() {
820 return entry.getKey();
821 }
822
823 @Override public V2 getValue() {
824 return function.apply(entry.getValue());
825 }
826 };
827 }
828
829 public void remove() {
830 mapIterator.remove();
831 }
832 };
833 }
834
835 @Override public void clear() {
836 fromMap.clear();
837 }
838
839 @Override public boolean contains(Object o) {
840 if (!(o instanceof Entry)) {
841 return false;
842 }
843 Entry<?, ?> entry = (Entry<?, ?>) o;
844 Object entryKey = entry.getKey();
845 Object entryValue = entry.getValue();
846 V2 mapValue = TransformedValuesMap.this.get(entryKey);
847 if (mapValue != null) {
848 return mapValue.equals(entryValue);
849 }
850 return entryValue == null && containsKey(entryKey);
851 }
852
853 @Override public boolean remove(Object o) {
854 if (contains(o)) {
855 Entry<?, ?> entry = (Entry<?, ?>) o;
856 Object key = entry.getKey();
857 fromMap.remove(key);
858 return true;
859 }
860 return false;
861 }
862 }
863 }
864
865 /**
866 * Returns a map containing the mappings in {@code unfiltered} whose keys
867 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
868 * changes to one affect the other.
869 *
870 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
871 * values()} views have iterators that don't support {@code remove()}, but all
872 * other methods are supported by the map and its views. The map's {@code
873 * put()} and {@code putAll()} methods throw an {@link
874 * IllegalArgumentException} if a key that doesn't satisfy the predicate is
875 * provided.
876 *
877 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
878 * on the filtered map or its views, only mappings whose keys satisfy the
879 * filter will be removed from the underlying map.
880 *
881 * <p>The returned map isn't threadsafe or serializable, even if {@code
882 * unfiltered} is.
883 *
884 * <p>Many of the filtered map's methods, such as {@code size()},
885 * iterate across every key/value mapping in the underlying map and determine
886 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
887 * faster to copy the filtered map and use the copy.
888 */
889 public static <K, V> Map<K, V> filterKeys(
890 Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
891 checkNotNull(keyPredicate);
892 Predicate<Entry<K, V>> entryPredicate =
893 new Predicate<Entry<K, V>>() {
894 public boolean apply(Entry<K, V> input) {
895 return keyPredicate.apply(input.getKey());
896 }
897 };
898 return (unfiltered instanceof AbstractFilteredMap)
899 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
900 : new FilteredKeyMap<K, V>(
901 checkNotNull(unfiltered), keyPredicate, entryPredicate);
902 }
903
904 /**
905 * Returns a map containing the mappings in {@code unfiltered} whose values
906 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
907 * changes to one affect the other.
908 *
909 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
910 * values()} views have iterators that don't support {@code remove()}, but all
911 * other methods are supported by the map and its views. The {@link Map#put},
912 * {@link Map#putAll}, and {@link Entry#setValue} methods throw an {@link
913 * IllegalArgumentException} if a value that doesn't satisfy the predicate is
914 * provided.
915 *
916 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
917 * on the filtered map or its views, only mappings whose values satisfy the
918 * filter will be removed from the underlying map.
919 *
920 * <p>The returned map isn't threadsafe or serializable, even if {@code
921 * unfiltered} is.
922 *
923 * <p>Many of the filtered map's methods, such as {@code size()},
924 * iterate across every key/value mapping in the underlying map and determine
925 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
926 * faster to copy the filtered map and use the copy.
927 */
928 public static <K, V> Map<K, V> filterValues(
929 Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
930 checkNotNull(valuePredicate);
931 Predicate<Entry<K, V>> entryPredicate =
932 new Predicate<Entry<K, V>>() {
933 public boolean apply(Entry<K, V> input) {
934 return valuePredicate.apply(input.getValue());
935 }
936 };
937 return filterEntries(unfiltered, entryPredicate);
938 }
939
940 /**
941 * Returns a map containing the mappings in {@code unfiltered} that satisfy a
942 * predicate. The returned map is a live view of {@code unfiltered}; changes
943 * to one affect the other.
944 *
945 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
946 * values()} views have iterators that don't support {@code remove()}, but all
947 * other methods are supported by the map and its views. The map's {@code
948 * put()} and {@code putAll()} methods throw an {@link
949 * IllegalArgumentException} if a key/value pair that doesn't satisfy the
950 * predicate is provided. Similarly, the map's entries have a {@link
951 * Entry#setValue} method that throws an {@link IllegalArgumentException} when
952 * the existing key and the provided value don't satisfy the predicate.
953 *
954 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
955 * on the filtered map or its views, only mappings that satisfy the filter
956 * will be removed from the underlying map.
957 *
958 * <p>The returned map isn't threadsafe or serializable, even if {@code
959 * unfiltered} is.
960 *
961 * <p>Many of the filtered map's methods, such as {@code size()},
962 * iterate across every key/value mapping in the underlying map and determine
963 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
964 * faster to copy the filtered map and use the copy.
965 */
966 public static <K, V> Map<K, V> filterEntries(
967 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
968 checkNotNull(entryPredicate);
969 return (unfiltered instanceof AbstractFilteredMap)
970 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
971 : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate);
972 }
973
974 /**
975 * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
976 * filtering a filtered map.
977 */
978 private static <K, V> Map<K, V> filterFiltered(AbstractFilteredMap<K, V> map,
979 Predicate<? super Entry<K, V>> entryPredicate) {
980 Predicate<Entry<K, V>> predicate =
981 Predicates.and(map.predicate, entryPredicate);
982 return new FilteredEntryMap<K, V>(map.unfiltered, predicate);
983 }
984
985 private abstract static class AbstractFilteredMap<K, V>
986 extends AbstractMap<K, V> {
987 final Map<K, V> unfiltered;
988 final Predicate<? super Entry<K, V>> predicate;
989
990 AbstractFilteredMap(
991 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
992 this.unfiltered = unfiltered;
993 this.predicate = predicate;
994 }
995
996 boolean apply(Object key, V value) {
997 // This method is called only when the key is in the map, implying that
998 // key is a K.
999 @SuppressWarnings("unchecked")
1000 K k = (K) key;
1001 return predicate.apply(Maps.immutableEntry(k, value));
1002 }
1003
1004 @Override public V put(K key, V value) {
1005 checkArgument(apply(key, value));
1006 return unfiltered.put(key, value);
1007 }
1008
1009 @Override public void putAll(Map<? extends K, ? extends V> map) {
1010 for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
1011 checkArgument(apply(entry.getKey(), entry.getValue()));
1012 }
1013 unfiltered.putAll(map);
1014 }
1015
1016 @Override public boolean containsKey(Object key) {
1017 return unfiltered.containsKey(key) && apply(key, unfiltered.get(key));
1018 }
1019
1020 @Override public V get(Object key) {
1021 V value = unfiltered.get(key);
1022 return ((value != null) && apply(key, value)) ? value : null;
1023 }
1024
1025 @Override public boolean isEmpty() {
1026 return entrySet().isEmpty();
1027 }
1028
1029 @Override public V remove(Object key) {
1030 return containsKey(key) ? unfiltered.remove(key) : null;
1031 }
1032
1033 Collection<V> values;
1034
1035 @Override public Collection<V> values() {
1036 Collection<V> result = values;
1037 return (result == null) ? values = new Values() : result;
1038 }
1039
1040 class Values extends AbstractCollection<V> {
1041 @Override public Iterator<V> iterator() {
1042 final Iterator<Entry<K, V>> entryIterator = entrySet().iterator();
1043 return new UnmodifiableIterator<V>() {
1044 public boolean hasNext() {
1045 return entryIterator.hasNext();
1046 }
1047
1048 public V next() {
1049 return entryIterator.next().getValue();
1050 }
1051 };
1052 }
1053
1054 @Override public int size() {
1055 return entrySet().size();
1056 }
1057
1058 @Override public void clear() {
1059 entrySet().clear();
1060 }
1061
1062 @Override public boolean isEmpty() {
1063 return entrySet().isEmpty();
1064 }
1065
1066 @Override public boolean remove(Object o) {
1067 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1068 while (iterator.hasNext()) {
1069 Entry<K, V> entry = iterator.next();
1070 if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) {
1071 iterator.remove();
1072 return true;
1073 }
1074 }
1075 return false;
1076 }
1077
1078 @Override public boolean removeAll(Collection<?> collection) {
1079 checkNotNull(collection);
1080 boolean changed = false;
1081 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1082 while (iterator.hasNext()) {
1083 Entry<K, V> entry = iterator.next();
1084 if (collection.contains(entry.getValue()) && predicate.apply(entry)) {
1085 iterator.remove();
1086 changed = true;
1087 }
1088 }
1089 return changed;
1090 }
1091
1092 @Override public boolean retainAll(Collection<?> collection) {
1093 checkNotNull(collection);
1094 boolean changed = false;
1095 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1096 while (iterator.hasNext()) {
1097 Entry<K, V> entry = iterator.next();
1098 if (!collection.contains(entry.getValue())
1099 && predicate.apply(entry)) {
1100 iterator.remove();
1101 changed = true;
1102 }
1103 }
1104 return changed;
1105 }
1106
1107 @Override public Object[] toArray() {
1108 // creating an ArrayList so filtering happens once
1109 return Lists.newArrayList(iterator()).toArray();
1110 }
1111
1112 @Override public <T> T[] toArray(T[] array) {
1113 return Lists.newArrayList(iterator()).toArray(array);
1114 }
1115 }
1116 }
1117
1118 private static class FilteredKeyMap<K, V> extends AbstractFilteredMap<K, V> {
1119 Predicate<? super K> keyPredicate;
1120
1121 FilteredKeyMap(Map<K, V> unfiltered, Predicate<? super K> keyPredicate,
1122 Predicate<Entry<K, V>> entryPredicate) {
1123 super(unfiltered, entryPredicate);
1124 this.keyPredicate = keyPredicate;
1125 }
1126
1127 Set<Entry<K, V>> entrySet;
1128
1129 @Override public Set<Entry<K, V>> entrySet() {
1130 Set<Entry<K, V>> result = entrySet;
1131 return (result == null)
1132 ? entrySet = Sets.filter(unfiltered.entrySet(), predicate)
1133 : result;
1134 }
1135
1136 Set<K> keySet;
1137
1138 @Override public Set<K> keySet() {
1139 Set<K> result = keySet;
1140 return (result == null)
1141 ? keySet = Sets.filter(unfiltered.keySet(), keyPredicate)
1142 : result;
1143 }
1144
1145 // The cast is called only when the key is in the unfiltered map, implying
1146 // that key is a K.
1147 @Override
1148 @SuppressWarnings("unchecked")
1149 public boolean containsKey(Object key) {
1150 return unfiltered.containsKey(key) && keyPredicate.apply((K) key);
1151 }
1152 }
1153
1154 private static class FilteredEntryMap<K, V>
1155 extends AbstractFilteredMap<K, V> {
1156 /**
1157 * Entries in this set satisfy the predicate, but they don't validate the
1158 * input to {@code Entry.setValue()}.
1159 */
1160 final Set<Entry<K, V>> filteredEntrySet;
1161
1162 FilteredEntryMap(
1163 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1164 super(unfiltered, entryPredicate);
1165 filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate);
1166 }
1167
1168 Set<Entry<K, V>> entrySet;
1169
1170 @Override public Set<Entry<K, V>> entrySet() {
1171 Set<Entry<K, V>> result = entrySet;
1172 return (result == null) ? entrySet = new EntrySet() : result;
1173 }
1174
1175 private class EntrySet extends ForwardingSet<Entry<K, V>> {
1176 @Override protected Set<Entry<K, V>> delegate() {
1177 return filteredEntrySet;
1178 }
1179
1180 @Override public Iterator<Entry<K, V>> iterator() {
1181 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1182 return new UnmodifiableIterator<Entry<K, V>>() {
1183 public boolean hasNext() {
1184 return iterator.hasNext();
1185 }
1186
1187 public Entry<K, V> next() {
1188 final Entry<K, V> entry = iterator.next();
1189 return new ForwardingMapEntry<K, V>() {
1190 @Override protected Entry<K, V> delegate() {
1191 return entry;
1192 }
1193
1194 @Override public V setValue(V value) {
1195 checkArgument(apply(entry.getKey(), value));
1196 return super.setValue(value);
1197 }
1198 };
1199 }
1200 };
1201 }
1202 }
1203
1204 Set<K> keySet;
1205
1206 @Override public Set<K> keySet() {
1207 Set<K> result = keySet;
1208 return (result == null) ? keySet = new KeySet() : result;
1209 }
1210
1211 private class KeySet extends AbstractSet<K> {
1212 @Override public Iterator<K> iterator() {
1213 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1214 return new UnmodifiableIterator<K>() {
1215 public boolean hasNext() {
1216 return iterator.hasNext();
1217 }
1218
1219 public K next() {
1220 return iterator.next().getKey();
1221 }
1222 };
1223 }
1224
1225 @Override public int size() {
1226 return filteredEntrySet.size();
1227 }
1228
1229 @Override public void clear() {
1230 filteredEntrySet.clear();
1231 }
1232
1233 @Override public boolean contains(Object o) {
1234 return containsKey(o);
1235 }
1236
1237 @Override public boolean remove(Object o) {
1238 if (containsKey(o)) {
1239 unfiltered.remove(o);
1240 return true;
1241 }
1242 return false;
1243 }
1244
1245 @Override public boolean removeAll(Collection<?> collection) {
1246 checkNotNull(collection); // for GWT
1247 boolean changed = false;
1248 for (Object obj : collection) {
1249 changed |= remove(obj);
1250 }
1251 return changed;
1252 }
1253
1254 @Override public boolean retainAll(Collection<?> collection) {
1255 checkNotNull(collection); // for GWT
1256 boolean changed = false;
1257 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1258 while (iterator.hasNext()) {
1259 Entry<K, V> entry = iterator.next();
1260 if (!collection.contains(entry.getKey()) && predicate.apply(entry)) {
1261 iterator.remove();
1262 changed = true;
1263 }
1264 }
1265 return changed;
1266 }
1267
1268 @Override public Object[] toArray() {
1269 // creating an ArrayList so filtering happens once
1270 return Lists.newArrayList(iterator()).toArray();
1271 }
1272
1273 @Override public <T> T[] toArray(T[] array) {
1274 return Lists.newArrayList(iterator()).toArray(array);
1275 }
1276 }
1277 }
1278
1279 /**
1280 * {@code AbstractMap} extension that implements {@link #isEmpty()} as {@code
1281 * entrySet().isEmpty()} instead of {@code size() == 0} to speed up
1282 * implementations where {@code size()} is O(n), and it delegates the {@code
1283 * isEmpty()} methods of its key set and value collection to this
1284 * implementation.
1285 */
1286 @GwtCompatible
1287 abstract static class ImprovedAbstractMap<K, V> extends AbstractMap<K, V> {
1288 /**
1289 * Creates the entry set to be returned by {@link #entrySet()}. This method
1290 * is invoked at most once on a given map, at the time when {@code entrySet}
1291 * is first called.
1292 */
1293 protected abstract Set<Entry<K, V>> createEntrySet();
1294
1295 private Set<Entry<K, V>> entrySet;
1296
1297 @Override public Set<Entry<K, V>> entrySet() {
1298 Set<Entry<K, V>> result = entrySet;
1299 if (result == null) {
1300 entrySet = result = createEntrySet();
1301 }
1302 return result;
1303 }
1304
1305 private Set<K> keySet;
1306
1307 @Override public Set<K> keySet() {
1308 Set<K> result = keySet;
1309 if (result == null) {
1310 final Set<K> delegate = super.keySet();
1311 keySet = result =
1312 new ForwardingSet<K>() {
1313 @Override protected Set<K> delegate() {
1314 return delegate;
1315 }
1316
1317 @Override public boolean isEmpty() {
1318 return ImprovedAbstractMap.this.isEmpty();
1319 }
1320 };
1321 }
1322 return result;
1323 }
1324
1325 private Collection<V> values;
1326
1327 @Override public Collection<V> values() {
1328 Collection<V> result = values;
1329 if (result == null) {
1330 final Collection<V> delegate = super.values();
1331 values = result =
1332 new ForwardingCollection<V>() {
1333 @Override protected Collection<V> delegate() {
1334 return delegate;
1335 }
1336
1337 @Override public boolean isEmpty() {
1338 return ImprovedAbstractMap.this.isEmpty();
1339 }
1340 };
1341 }
1342 return result;
1343 }
1344
1345 /**
1346 * Returns {@code true} if this map contains no key-value mappings.
1347 *
1348 * <p>The implementation returns {@code entrySet().isEmpty()}.
1349 *
1350 * @return {@code true} if this map contains no key-value mappings
1351 */
1352 @Override public boolean isEmpty() {
1353 return entrySet().isEmpty();
1354 }
1355 }
1356
1357 static final MapJoiner standardJoiner =
1358 Collections2.standardJoiner.withKeyValueSeparator("=");
1359
1360 /**
1361 * Delegates to {@link Map#get}. Returns {@code null} on {@code
1362 * ClassCastException}.
1363 */
1364 static <V> V safeGet(Map<?, V> map, Object key) {
1365 try {
1366 return map.get(key);
1367 } catch (ClassCastException e) {
1368 return null;
1369 }
1370 }
1371
1372 /**
1373 * Delegates to {@link Map#containsKey}. Returns {@code false} on {@code
1374 * ClassCastException}
1375 */
1376 static boolean safeContainsKey(Map<?, ?> map, Object key) {
1377 try {
1378 return map.containsKey(key);
1379 } catch (ClassCastException e) {
1380 return false;
1381 }
1382 }
1383 }