001 /*
002 * Copyright (C) 2007 The Guava Authors
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.Beta;
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.annotations.GwtIncompatible;
025 import com.google.common.base.Function;
026 import com.google.common.base.Joiner.MapJoiner;
027 import com.google.common.base.Objects;
028 import com.google.common.base.Predicate;
029 import com.google.common.base.Predicates;
030 import com.google.common.base.Supplier;
031 import com.google.common.collect.MapDifference.ValueDifference;
032 import com.google.common.primitives.Ints;
033
034 import java.io.Serializable;
035 import java.util.AbstractCollection;
036 import java.util.AbstractMap;
037 import java.util.AbstractSet;
038 import java.util.Collection;
039 import java.util.Collections;
040 import java.util.Comparator;
041 import java.util.EnumMap;
042 import java.util.Enumeration;
043 import java.util.HashMap;
044 import java.util.IdentityHashMap;
045 import java.util.Iterator;
046 import java.util.LinkedHashMap;
047 import java.util.Map;
048 import java.util.Map.Entry;
049 import java.util.Properties;
050 import java.util.Set;
051 import java.util.SortedMap;
052 import java.util.TreeMap;
053 import java.util.concurrent.ConcurrentMap;
054
055 import javax.annotation.Nullable;
056
057 /**
058 * Static utility methods pertaining to {@link Map} instances. Also see this
059 * class's counterparts {@link Lists} and {@link Sets}.
060 *
061 * @author Kevin Bourrillion
062 * @author Mike Bostock
063 * @author Isaac Shum
064 * @author Louis Wasserman
065 * @since 2 (imported from Google Collections Library)
066 */
067 @GwtCompatible(emulated = true)
068 public final class Maps {
069 private Maps() {}
070
071 /**
072 * Creates a <i>mutable</i>, empty {@code HashMap} instance.
073 *
074 * <p><b>Note:</b> if mutability is not required, use {@link
075 * ImmutableMap#of()} instead.
076 *
077 * <p><b>Note:</b> if {@code K} is an {@code enum} type, use {@link
078 * #newEnumMap} instead.
079 *
080 * @return a new, empty {@code HashMap}
081 */
082 public static <K, V> HashMap<K, V> newHashMap() {
083 return new HashMap<K, V>();
084 }
085
086 /**
087 * Creates a {@code HashMap} instance with enough capacity to hold the
088 * specified number of elements without rehashing.
089 *
090 * @param expectedSize the expected size
091 * @return a new, empty {@code HashMap} with enough capacity to hold {@code
092 * expectedSize} elements without rehashing
093 * @throws IllegalArgumentException if {@code expectedSize} is negative
094 */
095 public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(
096 int expectedSize) {
097 /*
098 * The HashMap is constructed with an initialCapacity that's greater than
099 * expectedSize. The larger value is necessary because HashMap resizes its
100 * internal array if the map size exceeds loadFactor * initialCapacity.
101 */
102 return new HashMap<K, V>(capacity(expectedSize));
103 }
104
105 /**
106 * Returns an appropriate value for the "capacity" (in reality, "minimum table
107 * size") parameter of a {@link HashMap} constructor, such that the resulting
108 * table will be between 25% and 50% full when it contains {@code
109 * expectedSize} entries, unless {@code expectedSize} is greater than
110 * {@link Integer#MAX_VALUE} / 2.
111 *
112 * @throws IllegalArgumentException if {@code expectedSize} is negative
113 */
114 static int capacity(int expectedSize) {
115 checkArgument(expectedSize >= 0);
116 // Avoid the int overflow if expectedSize > (Integer.MAX_VALUE / 2)
117 return Ints.saturatedCast(Math.max(expectedSize * 2L, 16L));
118 }
119
120 /**
121 * Creates a <i>mutable</i> {@code HashMap} instance with the same mappings as
122 * the specified map.
123 *
124 * <p><b>Note:</b> if mutability is not required, use {@link
125 * ImmutableMap#copyOf(Map)} instead.
126 *
127 * <p><b>Note:</b> if {@code K} is an {@link Enum} type, use {@link
128 * #newEnumMap} instead.
129 *
130 * @param map the mappings to be placed in the new map
131 * @return a new {@code HashMap} initialized with the mappings from {@code
132 * map}
133 */
134 public static <K, V> HashMap<K, V> newHashMap(
135 Map<? extends K, ? extends V> map) {
136 return new HashMap<K, V>(map);
137 }
138
139 /**
140 * Creates a <i>mutable</i>, empty, insertion-ordered {@code LinkedHashMap}
141 * instance.
142 *
143 * <p><b>Note:</b> if mutability is not required, use {@link
144 * ImmutableMap#of()} instead.
145 *
146 * @return a new, empty {@code LinkedHashMap}
147 */
148 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap() {
149 return new LinkedHashMap<K, V>();
150 }
151
152 /**
153 * Creates a <i>mutable</i>, insertion-ordered {@code LinkedHashMap} instance
154 * with the same mappings as the specified map.
155 *
156 * <p><b>Note:</b> if mutability is not required, use {@link
157 * ImmutableMap#copyOf(Map)} instead.
158 *
159 * @param map the mappings to be placed in the new map
160 * @return a new, {@code LinkedHashMap} initialized with the mappings from
161 * {@code map}
162 */
163 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(
164 Map<? extends K, ? extends V> map) {
165 return new LinkedHashMap<K, V>(map);
166 }
167
168 /**
169 * Returns a general-purpose instance of {@code ConcurrentMap}, which supports
170 * all optional operations of the ConcurrentMap interface. It does not permit
171 * null keys or values. It is serializable.
172 *
173 * <p>This is currently accomplished by calling {@link MapMaker#makeMap()}.
174 *
175 * <p>It is preferable to use {@code MapMaker} directly (rather than through
176 * this method), as it presents numerous useful configuration options,
177 * such as the concurrency level, load factor, key/value reference types,
178 * and value computation.
179 *
180 * @return a new, empty {@code ConcurrentMap}
181 * @since 3
182 */
183 public static <K, V> ConcurrentMap<K, V> newConcurrentMap() {
184 return new MapMaker().<K, V>makeMap();
185 }
186
187 /**
188 * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the natural
189 * ordering of its elements.
190 *
191 * <p><b>Note:</b> if mutability is not required, use {@link
192 * ImmutableSortedMap#of()} instead.
193 *
194 * @return a new, empty {@code TreeMap}
195 */
196 @SuppressWarnings("unchecked") // eclipse doesn't like the raw Comparable
197 public static <K extends Comparable, V> TreeMap<K, V> newTreeMap() {
198 return new TreeMap<K, V>();
199 }
200
201 /**
202 * Creates a <i>mutable</i> {@code TreeMap} instance with the same mappings as
203 * the specified map and using the same ordering as the specified map.
204 *
205 * <p><b>Note:</b> if mutability is not required, use {@link
206 * ImmutableSortedMap#copyOfSorted(SortedMap)} instead.
207 *
208 * @param map the sorted map whose mappings are to be placed in the new map
209 * and whose comparator is to be used to sort the new map
210 * @return a new {@code TreeMap} initialized with the mappings from {@code
211 * map} and using the comparator of {@code map}
212 */
213 public static <K, V> TreeMap<K, V> newTreeMap(SortedMap<K, ? extends V> map) {
214 return new TreeMap<K, V>(map);
215 }
216
217 /**
218 * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the given
219 * comparator.
220 *
221 * <p><b>Note:</b> if mutability is not required, use {@code
222 * ImmutableSortedMap.orderedBy(comparator).build()} instead.
223 *
224 * @param comparator the comparator to sort the keys with
225 * @return a new, empty {@code TreeMap}
226 */
227 public static <C, K extends C, V> TreeMap<K, V> newTreeMap(
228 @Nullable Comparator<C> comparator) {
229 // Ideally, the extra type parameter "C" shouldn't be necessary. It is a
230 // work-around of a compiler type inference quirk that prevents the
231 // following code from being compiled:
232 // Comparator<Class<?>> comparator = null;
233 // Map<Class<? extends Throwable>, String> map = newTreeMap(comparator);
234 return new TreeMap<K, V>(comparator);
235 }
236
237 /**
238 * Creates an {@code EnumMap} instance.
239 *
240 * @param type the key type for this map
241 * @return a new, empty {@code EnumMap}
242 */
243 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(Class<K> type) {
244 return new EnumMap<K, V>(checkNotNull(type));
245 }
246
247 /**
248 * Creates an {@code EnumMap} with the same mappings as the specified map.
249 *
250 * @param map the map from which to initialize this {@code EnumMap}
251 * @return a new {@code EnumMap} initialized with the mappings from {@code
252 * map}
253 * @throws IllegalArgumentException if {@code m} is not an {@code EnumMap}
254 * instance and contains no mappings
255 */
256 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(
257 Map<K, ? extends V> map) {
258 return new EnumMap<K, V>(map);
259 }
260
261 /**
262 * Creates an {@code IdentityHashMap} instance.
263 *
264 * @return a new, empty {@code IdentityHashMap}
265 */
266 public static <K, V> IdentityHashMap<K, V> newIdentityHashMap() {
267 return new IdentityHashMap<K, V>();
268 }
269
270 /**
271 * Returns a synchronized (thread-safe) bimap backed by the specified bimap.
272 * In order to guarantee serial access, it is critical that <b>all</b> access
273 * to the backing bimap is accomplished through the returned bimap.
274 *
275 * <p>It is imperative that the user manually synchronize on the returned map
276 * when accessing any of its collection views: <pre> {@code
277 *
278 * BiMap<Long, String> map = Maps.synchronizedBiMap(
279 * HashBiMap.<Long, String>create());
280 * ...
281 * Set<Long> set = map.keySet(); // Needn't be in synchronized block
282 * ...
283 * synchronized (map) { // Synchronizing on map, not set!
284 * Iterator<Long> it = set.iterator(); // Must be in synchronized block
285 * while (it.hasNext()) {
286 * foo(it.next());
287 * }
288 * }}</pre>
289 *
290 * Failure to follow this advice may result in non-deterministic behavior.
291 *
292 * <p>The returned bimap will be serializable if the specified bimap is
293 * serializable.
294 *
295 * @param bimap the bimap to be wrapped in a synchronized view
296 * @return a sychronized view of the specified bimap
297 */
298 public static <K, V> BiMap<K, V> synchronizedBiMap(BiMap<K, V> bimap) {
299 return Synchronized.biMap(bimap, null);
300 }
301
302 /**
303 * Computes the difference between two maps. This difference is an immutable
304 * snapshot of the state of the maps at the time this method is called. It
305 * will never change, even if the maps change at a later time.
306 *
307 * <p>Since this method uses {@code HashMap} instances internally, the keys of
308 * the supplied maps must be well-behaved with respect to
309 * {@link Object#equals} and {@link Object#hashCode}.
310 *
311 * <p><b>Note:</b>If you only need to know whether two maps have the same
312 * mappings, call {@code left.equals(right)} instead of this method.
313 *
314 * @param left the map to treat as the "left" map for purposes of comparison
315 * @param right the map to treat as the "right" map for purposes of comparison
316 * @return the difference between the two maps
317 */
318 public static <K, V> MapDifference<K, V> difference(
319 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) {
320 Map<K, V> onlyOnLeft = newHashMap();
321 Map<K, V> onlyOnRight = new HashMap<K, V>(right); // will whittle it down
322 Map<K, V> onBoth = newHashMap();
323 Map<K, MapDifference.ValueDifference<V>> differences = newHashMap();
324 boolean eq = true;
325
326 for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
327 K leftKey = entry.getKey();
328 V leftValue = entry.getValue();
329 if (right.containsKey(leftKey)) {
330 V rightValue = onlyOnRight.remove(leftKey);
331 if (Objects.equal(leftValue, rightValue)) {
332 onBoth.put(leftKey, leftValue);
333 } else {
334 eq = false;
335 differences.put(
336 leftKey, new ValueDifferenceImpl<V>(leftValue, rightValue));
337 }
338 } else {
339 eq = false;
340 onlyOnLeft.put(leftKey, leftValue);
341 }
342 }
343
344 boolean areEqual = eq && onlyOnRight.isEmpty();
345 return mapDifference(
346 areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
347 }
348
349 private static <K, V> MapDifference<K, V> mapDifference(boolean areEqual,
350 Map<K, V> onlyOnLeft, Map<K, V> onlyOnRight, Map<K, V> onBoth,
351 Map<K, ValueDifference<V>> differences) {
352 return new MapDifferenceImpl<K, V>(areEqual,
353 Collections.unmodifiableMap(onlyOnLeft),
354 Collections.unmodifiableMap(onlyOnRight),
355 Collections.unmodifiableMap(onBoth),
356 Collections.unmodifiableMap(differences));
357 }
358
359 static class MapDifferenceImpl<K, V> implements MapDifference<K, V> {
360 final boolean areEqual;
361 final Map<K, V> onlyOnLeft;
362 final Map<K, V> onlyOnRight;
363 final Map<K, V> onBoth;
364 final Map<K, ValueDifference<V>> differences;
365
366 MapDifferenceImpl(boolean areEqual, Map<K, V> onlyOnLeft,
367 Map<K, V> onlyOnRight, Map<K, V> onBoth,
368 Map<K, ValueDifference<V>> differences) {
369 this.areEqual = areEqual;
370 this.onlyOnLeft = onlyOnLeft;
371 this.onlyOnRight = onlyOnRight;
372 this.onBoth = onBoth;
373 this.differences = differences;
374 }
375
376 @Override
377 public boolean areEqual() {
378 return areEqual;
379 }
380
381 @Override
382 public Map<K, V> entriesOnlyOnLeft() {
383 return onlyOnLeft;
384 }
385
386 @Override
387 public Map<K, V> entriesOnlyOnRight() {
388 return onlyOnRight;
389 }
390
391 @Override
392 public Map<K, V> entriesInCommon() {
393 return onBoth;
394 }
395
396 @Override
397 public Map<K, ValueDifference<V>> entriesDiffering() {
398 return differences;
399 }
400
401 @Override public boolean equals(Object object) {
402 if (object == this) {
403 return true;
404 }
405 if (object instanceof MapDifference) {
406 MapDifference<?, ?> other = (MapDifference<?, ?>) object;
407 return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft())
408 && entriesOnlyOnRight().equals(other.entriesOnlyOnRight())
409 && entriesInCommon().equals(other.entriesInCommon())
410 && entriesDiffering().equals(other.entriesDiffering());
411 }
412 return false;
413 }
414
415 @Override public int hashCode() {
416 return Objects.hashCode(entriesOnlyOnLeft(), entriesOnlyOnRight(),
417 entriesInCommon(), entriesDiffering());
418 }
419
420 @Override public String toString() {
421 if (areEqual) {
422 return "equal";
423 }
424
425 StringBuilder result = new StringBuilder("not equal");
426 if (!onlyOnLeft.isEmpty()) {
427 result.append(": only on left=").append(onlyOnLeft);
428 }
429 if (!onlyOnRight.isEmpty()) {
430 result.append(": only on right=").append(onlyOnRight);
431 }
432 if (!differences.isEmpty()) {
433 result.append(": value differences=").append(differences);
434 }
435 return result.toString();
436 }
437 }
438
439 static class ValueDifferenceImpl<V>
440 implements MapDifference.ValueDifference<V> {
441 private final V left;
442 private final V right;
443
444 ValueDifferenceImpl(@Nullable V left, @Nullable V right) {
445 this.left = left;
446 this.right = right;
447 }
448
449 @Override
450 public V leftValue() {
451 return left;
452 }
453
454 @Override
455 public V rightValue() {
456 return right;
457 }
458
459 @Override public boolean equals(@Nullable Object object) {
460 if (object instanceof MapDifference.ValueDifference<?>) {
461 MapDifference.ValueDifference<?> that =
462 (MapDifference.ValueDifference<?>) object;
463 return Objects.equal(this.left, that.leftValue())
464 && Objects.equal(this.right, that.rightValue());
465 }
466 return false;
467 }
468
469 @Override public int hashCode() {
470 return Objects.hashCode(left, right);
471 }
472
473 @Override public String toString() {
474 return "(" + left + ", " + right + ")";
475 }
476 }
477
478 /**
479 * Returns an immutable map for which the {@link Map#values} are the given
480 * elements in the given order, and each key is the product of invoking a
481 * supplied function on its corresponding value.
482 *
483 * @param values the values to use when constructing the {@code Map}
484 * @param keyFunction the function used to produce the key for each value
485 * @return a map mapping the result of evaluating the function {@code
486 * keyFunction} on each value in the input collection to that value
487 * @throws IllegalArgumentException if {@code keyFunction} produces the same
488 * key for more than one value in the input collection
489 * @throws NullPointerException if any elements of {@code values} is null, or
490 * if {@code keyFunction} produces {@code null} for any value
491 */
492 public static <K, V> ImmutableMap<K, V> uniqueIndex(
493 Iterable<V> values, Function<? super V, K> keyFunction) {
494 checkNotNull(keyFunction);
495 ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
496 for (V value : values) {
497 builder.put(keyFunction.apply(value), value);
498 }
499 return builder.build();
500 }
501
502 /**
503 * Creates an {@code ImmutableMap<String, String>} from a {@code Properties}
504 * instance. Properties normally derive from {@code Map<Object, Object>}, but
505 * they typically contain strings, which is awkward. This method lets you get
506 * a plain-old-{@code Map} out of a {@code Properties}.
507 *
508 * @param properties a {@code Properties} object to be converted
509 * @return an immutable map containing all the entries in {@code properties}
510 * @throws ClassCastException if any key in {@code Properties} is not a {@code
511 * String}
512 * @throws NullPointerException if any key or value in {@code Properties} is
513 * null
514 */
515 @GwtIncompatible("java.util.Properties")
516 public static ImmutableMap<String, String> fromProperties(
517 Properties properties) {
518 ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
519
520 for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements();) {
521 String key = (String) e.nextElement();
522 builder.put(key, properties.getProperty(key));
523 }
524
525 return builder.build();
526 }
527
528 /**
529 * Returns an immutable map entry with the specified key and value. The {@link
530 * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
531 *
532 * <p>The returned entry is serializable.
533 *
534 * @param key the key to be associated with the returned entry
535 * @param value the value to be associated with the returned entry
536 */
537 @GwtCompatible(serializable = true)
538 public static <K, V> Entry<K, V> immutableEntry(
539 @Nullable K key, @Nullable V value) {
540 return new ImmutableEntry<K, V>(key, value);
541 }
542
543 /**
544 * Returns an unmodifiable view of the specified set of entries. The {@link
545 * Entry#setValue} operation throws an {@link UnsupportedOperationException},
546 * as do any operations that would modify the returned set.
547 *
548 * @param entrySet the entries for which to return an unmodifiable view
549 * @return an unmodifiable view of the entries
550 */
551 static <K, V> Set<Entry<K, V>> unmodifiableEntrySet(
552 Set<Entry<K, V>> entrySet) {
553 return new UnmodifiableEntrySet<K, V>(
554 Collections.unmodifiableSet(entrySet));
555 }
556
557 /**
558 * Returns an unmodifiable view of the specified map entry. The {@link
559 * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
560 * This also has the side-effect of redefining {@code equals} to comply with
561 * the Entry contract, to avoid a possible nefarious implementation of equals.
562 *
563 * @param entry the entry for which to return an unmodifiable view
564 * @return an unmodifiable view of the entry
565 */
566 static <K, V> Entry<K, V> unmodifiableEntry(final Entry<K, V> entry) {
567 checkNotNull(entry);
568 return new AbstractMapEntry<K, V>() {
569 @Override public K getKey() {
570 return entry.getKey();
571 }
572
573 @Override public V getValue() {
574 return entry.getValue();
575 }
576 };
577 }
578
579 /** @see Multimaps#unmodifiableEntries */
580 static class UnmodifiableEntries<K, V>
581 extends ForwardingCollection<Entry<K, V>> {
582 private final Collection<Entry<K, V>> entries;
583
584 UnmodifiableEntries(Collection<Entry<K, V>> entries) {
585 this.entries = entries;
586 }
587
588 @Override protected Collection<Entry<K, V>> delegate() {
589 return entries;
590 }
591
592 @Override public Iterator<Entry<K, V>> iterator() {
593 final Iterator<Entry<K, V>> delegate = super.iterator();
594 return new ForwardingIterator<Entry<K, V>>() {
595 @Override public Entry<K, V> next() {
596 return unmodifiableEntry(super.next());
597 }
598
599 @Override public void remove() {
600 throw new UnsupportedOperationException();
601 }
602
603 @Override protected Iterator<Entry<K, V>> delegate() {
604 return delegate;
605 }
606 };
607 }
608
609 // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
610
611 @Override public boolean add(Entry<K, V> element) {
612 throw new UnsupportedOperationException();
613 }
614
615 @Override public boolean addAll(
616 Collection<? extends Entry<K, V>> collection) {
617 throw new UnsupportedOperationException();
618 }
619
620 @Override public void clear() {
621 throw new UnsupportedOperationException();
622 }
623
624 @Override public boolean remove(Object object) {
625 throw new UnsupportedOperationException();
626 }
627
628 @Override public boolean removeAll(Collection<?> collection) {
629 throw new UnsupportedOperationException();
630 }
631
632 @Override public boolean retainAll(Collection<?> collection) {
633 throw new UnsupportedOperationException();
634 }
635
636 @Override public Object[] toArray() {
637 return standardToArray();
638 }
639
640 @Override public <T> T[] toArray(T[] array) {
641 return standardToArray(array);
642 }
643 }
644
645 /** @see Maps#unmodifiableEntrySet(Set) */
646 static class UnmodifiableEntrySet<K, V>
647 extends UnmodifiableEntries<K, V> implements Set<Entry<K, V>> {
648 UnmodifiableEntrySet(Set<Entry<K, V>> entries) {
649 super(entries);
650 }
651
652 // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
653
654 @Override public boolean equals(@Nullable Object object) {
655 return Sets.equalsImpl(this, object);
656 }
657
658 @Override public int hashCode() {
659 return Sets.hashCodeImpl(this);
660 }
661 }
662
663 /**
664 * Returns an unmodifiable view of the specified bimap. This method allows
665 * modules to provide users with "read-only" access to internal bimaps. Query
666 * operations on the returned bimap "read through" to the specified bimap, and
667 * attemps to modify the returned map, whether direct or via its collection
668 * views, result in an {@code UnsupportedOperationException}.
669 *
670 * <p>The returned bimap will be serializable if the specified bimap is
671 * serializable.
672 *
673 * @param bimap the bimap for which an unmodifiable view is to be returned
674 * @return an unmodifiable view of the specified bimap
675 */
676 public static <K, V> BiMap<K, V> unmodifiableBiMap(
677 BiMap<? extends K, ? extends V> bimap) {
678 return new UnmodifiableBiMap<K, V>(bimap, null);
679 }
680
681 /** @see Maps#unmodifiableBiMap(BiMap) */
682 private static class UnmodifiableBiMap<K, V>
683 extends ForwardingMap<K, V> implements BiMap<K, V>, Serializable {
684 final Map<K, V> unmodifiableMap;
685 final BiMap<? extends K, ? extends V> delegate;
686 transient BiMap<V, K> inverse;
687 transient Set<V> values;
688
689 UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate,
690 @Nullable BiMap<V, K> inverse) {
691 unmodifiableMap = Collections.unmodifiableMap(delegate);
692 this.delegate = delegate;
693 this.inverse = inverse;
694 }
695
696 @Override protected Map<K, V> delegate() {
697 return unmodifiableMap;
698 }
699
700 @Override
701 public V forcePut(K key, V value) {
702 throw new UnsupportedOperationException();
703 }
704
705 @Override
706 public BiMap<V, K> inverse() {
707 BiMap<V, K> result = inverse;
708 return (result == null)
709 ? inverse = new UnmodifiableBiMap<V, K>(delegate.inverse(), this)
710 : result;
711 }
712
713 @Override public Set<V> values() {
714 Set<V> result = values;
715 return (result == null)
716 ? values = Collections.unmodifiableSet(delegate.values())
717 : result;
718 }
719
720 private static final long serialVersionUID = 0;
721 }
722
723 /**
724 * Returns a view of a map where each value is transformed by a function. All
725 * other properties of the map, such as iteration order, are left intact. For
726 * example, the code: <pre> {@code
727 *
728 * Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
729 * Function<Integer, Double> sqrt =
730 * new Function<Integer, Double>() {
731 * public Double apply(Integer in) {
732 * return Math.sqrt((int) in);
733 * }
734 * };
735 * Map<String, Double> transformed = Maps.transformValues(map, sqrt);
736 * System.out.println(transformed);}</pre>
737 *
738 * ... prints {@code {a=2.0, b=3.0}}.
739 *
740 * <p>Changes in the underlying map are reflected in this view. Conversely,
741 * this view supports removal operations, and these are reflected in the
742 * underlying map.
743 *
744 * <p>It's acceptable for the underlying map to contain null keys, and even
745 * null values provided that the function is capable of accepting null input.
746 * The transformed map might contain null values, if the function sometimes
747 * gives a null result.
748 *
749 * <p>The returned map is not thread-safe or serializable, even if the
750 * underlying map is.
751 *
752 * <p>The function is applied lazily, invoked when needed. This is necessary
753 * for the returned map to be a view, but it means that the function will be
754 * applied many times for bulk operations like {@link Map#containsValue} and
755 * {@code Map.toString()}. For this to perform well, {@code function} should
756 * be fast. To avoid lazy evaluation when the returned map doesn't need to be
757 * a view, copy the returned map into a new map of your choosing.
758 */
759 public static <K, V1, V2> Map<K, V2> transformValues(
760 Map<K, V1> fromMap, final Function<? super V1, V2> function) {
761 checkNotNull(function);
762 EntryTransformer<K, V1, V2> transformer =
763 new EntryTransformer<K, V1, V2>() {
764 @Override
765 public V2 transformEntry(K key, V1 value) {
766 return function.apply(value);
767 }
768 };
769 return transformEntries(fromMap, transformer);
770 }
771
772 /**
773 * Returns a view of a map whose values are derived from the original map's
774 * entries. In contrast to {@link #transformValues}, this method's
775 * entry-transformation logic may depend on the key as well as the value.
776 *
777 * <p>All other properties of the transformed map, such as iteration order,
778 * are left intact. For example, the code: <pre> {@code
779 *
780 * Map<String, Boolean> options =
781 * ImmutableMap.of("verbose", true, "sort", false);
782 * EntryTransformer<String, Boolean, String> flagPrefixer =
783 * new EntryTransformer<String, Boolean, String>() {
784 * public String transformEntry(String key, Boolean value) {
785 * return value ? key : "no" + key;
786 * }
787 * };
788 * Map<String, String> transformed =
789 * Maps.transformEntries(options, flagPrefixer);
790 * System.out.println(transformed);}</pre>
791 *
792 * ... prints {@code {verbose=verbose, sort=nosort}}.
793 *
794 * <p>Changes in the underlying map are reflected in this view. Conversely,
795 * this view supports removal operations, and these are reflected in the
796 * underlying map.
797 *
798 * <p>It's acceptable for the underlying map to contain null keys and null
799 * values provided that the transformer is capable of accepting null inputs.
800 * The transformed map might contain null values if the transformer sometimes
801 * gives a null result.
802 *
803 * <p>The returned map is not thread-safe or serializable, even if the
804 * underlying map is.
805 *
806 * <p>The transformer is applied lazily, invoked when needed. This is
807 * necessary for the returned map to be a view, but it means that the
808 * transformer will be applied many times for bulk operations like {@link
809 * Map#containsValue} and {@link Object#toString}. For this to perform well,
810 * {@code transformer} should be fast. To avoid lazy evaluation when the
811 * returned map doesn't need to be a view, copy the returned map into a new
812 * map of your choosing.
813 *
814 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
815 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
816 * that {@code k2} is also of type {@code K}. Using an {@code
817 * EntryTransformer} key type for which this may not hold, such as {@code
818 * ArrayList}, may risk a {@code ClassCastException} when calling methods on
819 * the transformed map.
820 *
821 * @since 7
822 */
823 @Beta
824 public static <K, V1, V2> Map<K, V2> transformEntries(
825 Map<K, V1> fromMap,
826 EntryTransformer<? super K, ? super V1, V2> transformer) {
827 return new TransformedEntriesMap<K, V1, V2>(fromMap, transformer);
828 }
829
830 /**
831 * A transformation of the value of a key-value pair, using both key and value
832 * as inputs. To apply the transformation to a map, use
833 * {@link Maps#transformEntries(Map, EntryTransformer)}.
834 *
835 * @param <K> the key type of the input and output entries
836 * @param <V1> the value type of the input entry
837 * @param <V2> the value type of the output entry
838 * @since 7
839 */
840 @Beta
841 public interface EntryTransformer<K, V1, V2> {
842 /**
843 * Determines an output value based on a key-value pair. This method is
844 * <i>generally expected</i>, but not absolutely required, to have the
845 * following properties:
846 *
847 * <ul>
848 * <li>Its execution does not cause any observable side effects.
849 * <li>The computation is <i>consistent with equals</i>; that is,
850 * {@link Objects#equal Objects.equal}{@code (k1, k2) &&}
851 * {@link Objects#equal}{@code (v1, v2)} implies that {@code
852 * Objects.equal(transformer.transform(k1, v1),
853 * transformer.transform(k2, v2))}.
854 * </ul>
855 *
856 * @throws NullPointerException if the key or value is null and this
857 * transformer does not accept null arguments
858 */
859 V2 transformEntry(@Nullable K key, @Nullable V1 value);
860 }
861
862 static class TransformedEntriesMap<K, V1, V2>
863 extends AbstractMap<K, V2> {
864 final Map<K, V1> fromMap;
865 final EntryTransformer<? super K, ? super V1, V2> transformer;
866
867 TransformedEntriesMap(
868 Map<K, V1> fromMap,
869 EntryTransformer<? super K, ? super V1, V2> transformer) {
870 this.fromMap = checkNotNull(fromMap);
871 this.transformer = checkNotNull(transformer);
872 }
873
874 @Override public int size() {
875 return fromMap.size();
876 }
877
878 @Override public boolean containsKey(Object key) {
879 return fromMap.containsKey(key);
880 }
881
882 // safe as long as the user followed the <b>Warning</b> in the javadoc
883 @SuppressWarnings("unchecked")
884 @Override public V2 get(Object key) {
885 V1 value = fromMap.get(key);
886 return (value != null || fromMap.containsKey(key))
887 ? transformer.transformEntry((K) key, value)
888 : null;
889 }
890
891 // safe as long as the user followed the <b>Warning</b> in the javadoc
892 @SuppressWarnings("unchecked")
893 @Override public V2 remove(Object key) {
894 return fromMap.containsKey(key)
895 ? transformer.transformEntry((K) key, fromMap.remove(key))
896 : null;
897 }
898
899 @Override public void clear() {
900 fromMap.clear();
901 }
902
903 EntrySet entrySet;
904
905 @Override public Set<Entry<K, V2>> entrySet() {
906 EntrySet result = entrySet;
907 if (result == null) {
908 entrySet = result = new EntrySet();
909 }
910 return result;
911 }
912
913 class EntrySet extends AbstractSet<Entry<K, V2>> {
914 @Override public int size() {
915 return TransformedEntriesMap.this.size();
916 }
917
918 @Override public Iterator<Entry<K, V2>> iterator() {
919 final Iterator<Entry<K, V1>> mapIterator =
920 fromMap.entrySet().iterator();
921
922 return new Iterator<Entry<K, V2>>() {
923 @Override
924 public boolean hasNext() {
925 return mapIterator.hasNext();
926 }
927
928 @Override
929 public Entry<K, V2> next() {
930 final Entry<K, V1> entry = mapIterator.next();
931 return new AbstractMapEntry<K, V2>() {
932 @Override public K getKey() {
933 return entry.getKey();
934 }
935
936 @Override public V2 getValue() {
937 return transformer.transformEntry(
938 entry.getKey(), entry.getValue());
939 }
940 };
941 }
942
943 @Override
944 public void remove() {
945 mapIterator.remove();
946 }
947 };
948 }
949
950 @Override public void clear() {
951 fromMap.clear();
952 }
953
954 @Override public boolean contains(Object o) {
955 if (!(o instanceof Entry)) {
956 return false;
957 }
958 Entry<?, ?> entry = (Entry<?, ?>) o;
959 Object entryKey = entry.getKey();
960 Object entryValue = entry.getValue();
961 V2 mapValue = TransformedEntriesMap.this.get(entryKey);
962 if (mapValue != null) {
963 return mapValue.equals(entryValue);
964 }
965 return entryValue == null && containsKey(entryKey);
966 }
967
968 @Override public boolean remove(Object o) {
969 if (contains(o)) {
970 Entry<?, ?> entry = (Entry<?, ?>) o;
971 Object key = entry.getKey();
972 fromMap.remove(key);
973 return true;
974 }
975 return false;
976 }
977 }
978 }
979
980 /**
981 * Returns a map containing the mappings in {@code unfiltered} whose keys
982 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
983 * changes to one affect the other.
984 *
985 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
986 * values()} views have iterators that don't support {@code remove()}, but all
987 * other methods are supported by the map and its views. When given a key that
988 * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
989 * methods throw an {@link IllegalArgumentException}.
990 *
991 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
992 * on the filtered map or its views, only mappings whose keys satisfy the
993 * filter will be removed from the underlying map.
994 *
995 * <p>The returned map isn't threadsafe or serializable, even if {@code
996 * unfiltered} is.
997 *
998 * <p>Many of the filtered map's methods, such as {@code size()},
999 * iterate across every key/value mapping in the underlying map and determine
1000 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1001 * faster to copy the filtered map and use the copy.
1002 *
1003 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
1004 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1005 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1006 * inconsistent with equals.
1007 */
1008 public static <K, V> Map<K, V> filterKeys(
1009 Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1010 checkNotNull(keyPredicate);
1011 Predicate<Entry<K, V>> entryPredicate =
1012 new Predicate<Entry<K, V>>() {
1013 @Override
1014 public boolean apply(Entry<K, V> input) {
1015 return keyPredicate.apply(input.getKey());
1016 }
1017 };
1018 return (unfiltered instanceof AbstractFilteredMap)
1019 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1020 : new FilteredKeyMap<K, V>(
1021 checkNotNull(unfiltered), keyPredicate, entryPredicate);
1022 }
1023
1024 /**
1025 * Returns a map containing the mappings in {@code unfiltered} whose values
1026 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
1027 * changes to one affect the other.
1028 *
1029 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1030 * values()} views have iterators that don't support {@code remove()}, but all
1031 * other methods are supported by the map and its views. When given a value
1032 * that doesn't satisfy the predicate, the map's {@code put()}, {@code
1033 * putAll()}, and {@link Entry#setValue} methods throw an {@link
1034 * IllegalArgumentException}.
1035 *
1036 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1037 * on the filtered map or its views, only mappings whose values satisfy the
1038 * filter will be removed from the underlying map.
1039 *
1040 * <p>The returned map isn't threadsafe or serializable, even if {@code
1041 * unfiltered} is.
1042 *
1043 * <p>Many of the filtered map's methods, such as {@code size()},
1044 * iterate across every key/value mapping in the underlying map and determine
1045 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1046 * faster to copy the filtered map and use the copy.
1047 *
1048 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
1049 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1050 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1051 * inconsistent with equals.
1052 */
1053 public static <K, V> Map<K, V> filterValues(
1054 Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
1055 checkNotNull(valuePredicate);
1056 Predicate<Entry<K, V>> entryPredicate =
1057 new Predicate<Entry<K, V>>() {
1058 @Override
1059 public boolean apply(Entry<K, V> input) {
1060 return valuePredicate.apply(input.getValue());
1061 }
1062 };
1063 return filterEntries(unfiltered, entryPredicate);
1064 }
1065
1066 /**
1067 * Returns a map containing the mappings in {@code unfiltered} that satisfy a
1068 * predicate. The returned map is a live view of {@code unfiltered}; changes
1069 * to one affect the other.
1070 *
1071 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1072 * values()} views have iterators that don't support {@code remove()}, but all
1073 * other methods are supported by the map and its views. When given a
1074 * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
1075 * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
1076 * Similarly, the map's entries have a {@link Entry#setValue} method that
1077 * throws an {@link IllegalArgumentException} when the existing key and the
1078 * provided value don't satisfy the predicate.
1079 *
1080 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1081 * on the filtered map or its views, only mappings that satisfy the filter
1082 * will be removed from the underlying map.
1083 *
1084 * <p>The returned map isn't threadsafe or serializable, even if {@code
1085 * unfiltered} is.
1086 *
1087 * <p>Many of the filtered map's methods, such as {@code size()},
1088 * iterate across every key/value mapping in the underlying map and determine
1089 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1090 * faster to copy the filtered map and use the copy.
1091 *
1092 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
1093 * equals</i>, as documented at {@link Predicate#apply}.
1094 */
1095 public static <K, V> Map<K, V> filterEntries(
1096 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1097 checkNotNull(entryPredicate);
1098 return (unfiltered instanceof AbstractFilteredMap)
1099 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1100 : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate);
1101 }
1102
1103 /**
1104 * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
1105 * filtering a filtered map.
1106 */
1107 private static <K, V> Map<K, V> filterFiltered(AbstractFilteredMap<K, V> map,
1108 Predicate<? super Entry<K, V>> entryPredicate) {
1109 Predicate<Entry<K, V>> predicate =
1110 Predicates.and(map.predicate, entryPredicate);
1111 return new FilteredEntryMap<K, V>(map.unfiltered, predicate);
1112 }
1113
1114 private abstract static class AbstractFilteredMap<K, V>
1115 extends AbstractMap<K, V> {
1116 final Map<K, V> unfiltered;
1117 final Predicate<? super Entry<K, V>> predicate;
1118
1119 AbstractFilteredMap(
1120 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
1121 this.unfiltered = unfiltered;
1122 this.predicate = predicate;
1123 }
1124
1125 boolean apply(Object key, V value) {
1126 // This method is called only when the key is in the map, implying that
1127 // key is a K.
1128 @SuppressWarnings("unchecked")
1129 K k = (K) key;
1130 return predicate.apply(Maps.immutableEntry(k, value));
1131 }
1132
1133 @Override public V put(K key, V value) {
1134 checkArgument(apply(key, value));
1135 return unfiltered.put(key, value);
1136 }
1137
1138 @Override public void putAll(Map<? extends K, ? extends V> map) {
1139 for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
1140 checkArgument(apply(entry.getKey(), entry.getValue()));
1141 }
1142 unfiltered.putAll(map);
1143 }
1144
1145 @Override public boolean containsKey(Object key) {
1146 return unfiltered.containsKey(key) && apply(key, unfiltered.get(key));
1147 }
1148
1149 @Override public V get(Object key) {
1150 V value = unfiltered.get(key);
1151 return ((value != null) && apply(key, value)) ? value : null;
1152 }
1153
1154 @Override public boolean isEmpty() {
1155 return entrySet().isEmpty();
1156 }
1157
1158 @Override public V remove(Object key) {
1159 return containsKey(key) ? unfiltered.remove(key) : null;
1160 }
1161
1162 Collection<V> values;
1163
1164 @Override public Collection<V> values() {
1165 Collection<V> result = values;
1166 return (result == null) ? values = new Values() : result;
1167 }
1168
1169 class Values extends AbstractCollection<V> {
1170 @Override public Iterator<V> iterator() {
1171 final Iterator<Entry<K, V>> entryIterator = entrySet().iterator();
1172 return new UnmodifiableIterator<V>() {
1173 @Override
1174 public boolean hasNext() {
1175 return entryIterator.hasNext();
1176 }
1177
1178 @Override
1179 public V next() {
1180 return entryIterator.next().getValue();
1181 }
1182 };
1183 }
1184
1185 @Override public int size() {
1186 return entrySet().size();
1187 }
1188
1189 @Override public void clear() {
1190 entrySet().clear();
1191 }
1192
1193 @Override public boolean isEmpty() {
1194 return entrySet().isEmpty();
1195 }
1196
1197 @Override public boolean remove(Object o) {
1198 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1199 while (iterator.hasNext()) {
1200 Entry<K, V> entry = iterator.next();
1201 if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) {
1202 iterator.remove();
1203 return true;
1204 }
1205 }
1206 return false;
1207 }
1208
1209 @Override public boolean removeAll(Collection<?> collection) {
1210 checkNotNull(collection);
1211 boolean changed = false;
1212 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1213 while (iterator.hasNext()) {
1214 Entry<K, V> entry = iterator.next();
1215 if (collection.contains(entry.getValue()) && predicate.apply(entry)) {
1216 iterator.remove();
1217 changed = true;
1218 }
1219 }
1220 return changed;
1221 }
1222
1223 @Override public boolean retainAll(Collection<?> collection) {
1224 checkNotNull(collection);
1225 boolean changed = false;
1226 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1227 while (iterator.hasNext()) {
1228 Entry<K, V> entry = iterator.next();
1229 if (!collection.contains(entry.getValue())
1230 && predicate.apply(entry)) {
1231 iterator.remove();
1232 changed = true;
1233 }
1234 }
1235 return changed;
1236 }
1237
1238 @Override public Object[] toArray() {
1239 // creating an ArrayList so filtering happens once
1240 return Lists.newArrayList(iterator()).toArray();
1241 }
1242
1243 @Override public <T> T[] toArray(T[] array) {
1244 return Lists.newArrayList(iterator()).toArray(array);
1245 }
1246 }
1247 }
1248
1249 private static class FilteredKeyMap<K, V> extends AbstractFilteredMap<K, V> {
1250 Predicate<? super K> keyPredicate;
1251
1252 FilteredKeyMap(Map<K, V> unfiltered, Predicate<? super K> keyPredicate,
1253 Predicate<Entry<K, V>> entryPredicate) {
1254 super(unfiltered, entryPredicate);
1255 this.keyPredicate = keyPredicate;
1256 }
1257
1258 Set<Entry<K, V>> entrySet;
1259
1260 @Override public Set<Entry<K, V>> entrySet() {
1261 Set<Entry<K, V>> result = entrySet;
1262 return (result == null)
1263 ? entrySet = Sets.filter(unfiltered.entrySet(), predicate)
1264 : result;
1265 }
1266
1267 Set<K> keySet;
1268
1269 @Override public Set<K> keySet() {
1270 Set<K> result = keySet;
1271 return (result == null)
1272 ? keySet = Sets.filter(unfiltered.keySet(), keyPredicate)
1273 : result;
1274 }
1275
1276 // The cast is called only when the key is in the unfiltered map, implying
1277 // that key is a K.
1278 @Override
1279 @SuppressWarnings("unchecked")
1280 public boolean containsKey(Object key) {
1281 return unfiltered.containsKey(key) && keyPredicate.apply((K) key);
1282 }
1283 }
1284
1285 static class FilteredEntryMap<K, V> extends AbstractFilteredMap<K, V> {
1286 /**
1287 * Entries in this set satisfy the predicate, but they don't validate the
1288 * input to {@code Entry.setValue()}.
1289 */
1290 final Set<Entry<K, V>> filteredEntrySet;
1291
1292 FilteredEntryMap(
1293 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1294 super(unfiltered, entryPredicate);
1295 filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate);
1296 }
1297
1298 Set<Entry<K, V>> entrySet;
1299
1300 @Override public Set<Entry<K, V>> entrySet() {
1301 Set<Entry<K, V>> result = entrySet;
1302 return (result == null) ? entrySet = new EntrySet() : result;
1303 }
1304
1305 private class EntrySet extends ForwardingSet<Entry<K, V>> {
1306 @Override protected Set<Entry<K, V>> delegate() {
1307 return filteredEntrySet;
1308 }
1309
1310 @Override public Iterator<Entry<K, V>> iterator() {
1311 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1312 return new UnmodifiableIterator<Entry<K, V>>() {
1313 @Override
1314 public boolean hasNext() {
1315 return iterator.hasNext();
1316 }
1317
1318 @Override
1319 public Entry<K, V> next() {
1320 final Entry<K, V> entry = iterator.next();
1321 return new ForwardingMapEntry<K, V>() {
1322 @Override protected Entry<K, V> delegate() {
1323 return entry;
1324 }
1325
1326 @Override public V setValue(V value) {
1327 checkArgument(apply(entry.getKey(), value));
1328 return super.setValue(value);
1329 }
1330 };
1331 }
1332 };
1333 }
1334 }
1335
1336 Set<K> keySet;
1337
1338 @Override public Set<K> keySet() {
1339 Set<K> result = keySet;
1340 return (result == null) ? keySet = new KeySet() : result;
1341 }
1342
1343 private class KeySet extends AbstractSet<K> {
1344 @Override public Iterator<K> iterator() {
1345 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1346 return new UnmodifiableIterator<K>() {
1347 @Override
1348 public boolean hasNext() {
1349 return iterator.hasNext();
1350 }
1351
1352 @Override
1353 public K next() {
1354 return iterator.next().getKey();
1355 }
1356 };
1357 }
1358
1359 @Override public int size() {
1360 return filteredEntrySet.size();
1361 }
1362
1363 @Override public void clear() {
1364 filteredEntrySet.clear();
1365 }
1366
1367 @Override public boolean contains(Object o) {
1368 return containsKey(o);
1369 }
1370
1371 @Override public boolean remove(Object o) {
1372 if (containsKey(o)) {
1373 unfiltered.remove(o);
1374 return true;
1375 }
1376 return false;
1377 }
1378
1379 @Override public boolean removeAll(Collection<?> collection) {
1380 checkNotNull(collection); // for GWT
1381 boolean changed = false;
1382 for (Object obj : collection) {
1383 changed |= remove(obj);
1384 }
1385 return changed;
1386 }
1387
1388 @Override public boolean retainAll(Collection<?> collection) {
1389 checkNotNull(collection); // for GWT
1390 boolean changed = false;
1391 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1392 while (iterator.hasNext()) {
1393 Entry<K, V> entry = iterator.next();
1394 if (!collection.contains(entry.getKey()) && predicate.apply(entry)) {
1395 iterator.remove();
1396 changed = true;
1397 }
1398 }
1399 return changed;
1400 }
1401
1402 @Override public Object[] toArray() {
1403 // creating an ArrayList so filtering happens once
1404 return Lists.newArrayList(iterator()).toArray();
1405 }
1406
1407 @Override public <T> T[] toArray(T[] array) {
1408 return Lists.newArrayList(iterator()).toArray(array);
1409 }
1410 }
1411 }
1412
1413 /**
1414 * {@code AbstractMap} extension that implements {@link #isEmpty()} as {@code
1415 * entrySet().isEmpty()} instead of {@code size() == 0} to speed up
1416 * implementations where {@code size()} is O(n), and it delegates the {@code
1417 * isEmpty()} methods of its key set and value collection to this
1418 * implementation.
1419 */
1420 @GwtCompatible
1421 abstract static class ImprovedAbstractMap<K, V> extends AbstractMap<K, V> {
1422 /**
1423 * Creates the entry set to be returned by {@link #entrySet()}. This method
1424 * is invoked at most once on a given map, at the time when {@code entrySet}
1425 * is first called.
1426 */
1427 protected abstract Set<Entry<K, V>> createEntrySet();
1428
1429 private Set<Entry<K, V>> entrySet;
1430
1431 @Override public Set<Entry<K, V>> entrySet() {
1432 Set<Entry<K, V>> result = entrySet;
1433 if (result == null) {
1434 entrySet = result = createEntrySet();
1435 }
1436 return result;
1437 }
1438
1439 private Set<K> keySet;
1440
1441 @Override public Set<K> keySet() {
1442 Set<K> result = keySet;
1443 if (result == null) {
1444 final Set<K> delegate = super.keySet();
1445 keySet = result = new ForwardingSet<K>() {
1446 @Override protected Set<K> delegate() {
1447 return delegate;
1448 }
1449
1450 @Override public boolean isEmpty() {
1451 return ImprovedAbstractMap.this.isEmpty();
1452 }
1453
1454 @Override public boolean remove(Object object) {
1455 if (contains(object)) {
1456 ImprovedAbstractMap.this.remove(object);
1457 return true;
1458 }
1459 return false;
1460 }
1461 };
1462 }
1463 return result;
1464 }
1465
1466 private Collection<V> values;
1467
1468 @Override public Collection<V> values() {
1469 Collection<V> result = values;
1470 if (result == null) {
1471 final Collection<V> delegate = super.values();
1472 values = result = new ForwardingCollection<V>() {
1473 @Override protected Collection<V> delegate() {
1474 return delegate;
1475 }
1476
1477 @Override public boolean isEmpty() {
1478 return ImprovedAbstractMap.this.isEmpty();
1479 }
1480 };
1481 }
1482 return result;
1483 }
1484
1485 /**
1486 * Returns {@code true} if this map contains no key-value mappings.
1487 *
1488 * <p>The implementation returns {@code entrySet().isEmpty()}.
1489 *
1490 * @return {@code true} if this map contains no key-value mappings
1491 */
1492 @Override public boolean isEmpty() {
1493 return entrySet().isEmpty();
1494 }
1495 }
1496
1497 static final MapJoiner STANDARD_JOINER =
1498 Collections2.STANDARD_JOINER.withKeyValueSeparator("=");
1499
1500 /**
1501 * Delegates to {@link Map#get}. Returns {@code null} on {@code
1502 * ClassCastException}.
1503 */
1504 static <V> V safeGet(Map<?, V> map, Object key) {
1505 try {
1506 return map.get(key);
1507 } catch (ClassCastException e) {
1508 return null;
1509 }
1510 }
1511
1512 /**
1513 * Delegates to {@link Map#containsKey}. Returns {@code false} on {@code
1514 * ClassCastException}
1515 */
1516 static boolean safeContainsKey(Map<?, ?> map, Object key) {
1517 try {
1518 return map.containsKey(key);
1519 } catch (ClassCastException e) {
1520 return false;
1521 }
1522 }
1523
1524 /**
1525 * An implementation of {@link Map#entrySet}.
1526 */
1527 static <K, V> Set<Entry<K, V>> entrySetImpl(
1528 Map<K, V> map, Supplier<Iterator<Entry<K, V>>> entryIteratorSupplier) {
1529 return new EntrySetImpl<K, V>(map, entryIteratorSupplier);
1530 }
1531
1532 private static class EntrySetImpl<K, V> extends AbstractSet<Entry<K, V>> {
1533 private final Map<K, V> map;
1534 private final Supplier<Iterator<Entry<K, V>>> entryIteratorSupplier;
1535
1536 EntrySetImpl(
1537 Map<K, V> map, Supplier<Iterator<Entry<K, V>>> entryIteratorSupplier) {
1538 this.map = checkNotNull(map);
1539 this.entryIteratorSupplier = checkNotNull(entryIteratorSupplier);
1540 }
1541
1542 @Override public Iterator<Entry<K, V>> iterator() {
1543 return entryIteratorSupplier.get();
1544 }
1545
1546 @Override public int size() {
1547 return map.size();
1548 }
1549
1550 @Override public void clear() {
1551 map.clear();
1552 }
1553
1554 @Override public boolean contains(Object o) {
1555 if (o instanceof Entry) {
1556 Entry<?, ?> entry = (Entry<?, ?>) o;
1557 Object key = entry.getKey();
1558 if (map.containsKey(key)) {
1559 V value = map.get(entry.getKey());
1560 return Objects.equal(value, entry.getValue());
1561 }
1562 }
1563 return false;
1564 }
1565
1566 @Override public boolean isEmpty() {
1567 return map.isEmpty();
1568 }
1569
1570 @Override public boolean remove(Object o) {
1571 if (contains(o)) {
1572 Entry<?, ?> entry = (Entry<?, ?>) o;
1573 map.remove(entry.getKey());
1574 return true;
1575 }
1576 return false;
1577 }
1578
1579 @Override public int hashCode() {
1580 return map.hashCode();
1581 }
1582 }
1583
1584 /**
1585 * Implements {@code Collection.contains} safely for forwarding collections of
1586 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
1587 * wrapped using {@link #unmodifiableEntry} to protect against a possible
1588 * nefarious equals method.
1589 *
1590 * <p>Note that {@code c} is the backing (delegate) collection, rather than
1591 * the forwarding collection.
1592 *
1593 * @param c the delegate (unwrapped) collection of map entries
1594 * @param o the object that might be contained in {@code c}
1595 * @return {@code true} if {@code c} contains {@code o}
1596 */
1597 static <K, V> boolean containsEntryImpl(Collection<Entry<K, V>> c, Object o) {
1598 if (!(o instanceof Entry)) {
1599 return false;
1600 }
1601 return c.contains(unmodifiableEntry((Entry<?, ?>) o));
1602 }
1603
1604 /**
1605 * Implements {@code Collection.remove} safely for forwarding collections of
1606 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
1607 * wrapped using {@link #unmodifiableEntry} to protect against a possible
1608 * nefarious equals method.
1609 *
1610 * <p>Note that {@code c} is backing (delegate) collection, rather than the
1611 * forwarding collection.
1612 *
1613 * @param c the delegate (unwrapped) collection of map entries
1614 * @param o the object to remove from {@code c}
1615 * @return {@code true} if {@code c} was changed
1616 */
1617 static <K, V> boolean removeEntryImpl(Collection<Entry<K, V>> c, Object o) {
1618 if (!(o instanceof Entry)) {
1619 return false;
1620 }
1621 return c.remove(unmodifiableEntry((Entry<?, ?>) o));
1622 }
1623
1624 /**
1625 * An implementation of {@link Map#equals}.
1626 */
1627 static boolean equalsImpl(Map<?, ?> map, Object object) {
1628 if (map == object) {
1629 return true;
1630 }
1631 if (object instanceof Map) {
1632 Map<?, ?> o = (Map<?, ?>) object;
1633 return map.entrySet().equals(o.entrySet());
1634 }
1635 return false;
1636 }
1637
1638 /**
1639 * An implementation of {@link Map#hashCode}.
1640 */
1641 static int hashCodeImpl(Map<?, ?> map) {
1642 return Sets.hashCodeImpl(map.entrySet());
1643 }
1644
1645 /**
1646 * An implementation of {@link Map#toString}.
1647 */
1648 static String toStringImpl(Map<?, ?> map) {
1649 StringBuilder sb
1650 = Collections2.newStringBuilderForCollection(map.size()).append('{');
1651 STANDARD_JOINER.appendTo(sb, map);
1652 return sb.append('}').toString();
1653 }
1654
1655 /**
1656 * An implementation of {@link Map#putAll}.
1657 */
1658 static <K, V> void putAllImpl(
1659 Map<K, V> self, Map<? extends K, ? extends V> map) {
1660 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
1661 self.put(entry.getKey(), entry.getValue());
1662 }
1663 }
1664
1665 /**
1666 * An implementation of {@link Map#keySet}.
1667 */
1668 static <K, V> Set<K> keySetImpl(final Map<K, V> map) {
1669 return new AbstractMapWrapper<K, V>(map).keySet();
1670 }
1671
1672 /**
1673 * An admittedly inefficient implementation of {@link Map#containsKey}.
1674 */
1675 static boolean containsKeyImpl(Map<?, ?> map, @Nullable Object key) {
1676 for (Entry<?, ?> entry : map.entrySet()) {
1677 if (Objects.equal(entry.getKey(), key)) {
1678 return true;
1679 }
1680 }
1681 return false;
1682 }
1683
1684 /**
1685 * An implementation of {@link Map#values}.
1686 */
1687 static <K, V> Collection<V> valuesImpl(Map<K, V> map) {
1688 return new AbstractMapWrapper<K, V>(map).values();
1689 }
1690
1691 /**
1692 * An implementation of {@link Map#containsValue}.
1693 */
1694 static boolean containsValueImpl(Map<?, ?> map, @Nullable Object value) {
1695 for (Entry<?, ?> entry : map.entrySet()) {
1696 if (Objects.equal(entry.getValue(), value)) {
1697 return true;
1698 }
1699 }
1700 return false;
1701 }
1702
1703 /**
1704 * A wrapper on a map that supplies the {@code ImprovedAbstractMap}
1705 * implementations of {@code keySet()} and {@code values()}.
1706 */
1707 private static final class AbstractMapWrapper<K, V>
1708 extends ImprovedAbstractMap<K, V>{
1709 private final Map<K, V> map;
1710
1711 AbstractMapWrapper(Map<K, V> map) {
1712 this.map = checkNotNull(map);
1713 }
1714
1715 @Override public void clear() {
1716 map.clear();
1717 }
1718
1719 @Override public boolean containsKey(Object key) {
1720 return map.containsKey(key);
1721 }
1722
1723 @Override public V remove(Object key) {
1724 return map.remove(key);
1725 }
1726
1727 @Override public boolean containsValue(Object value) {
1728 return map.containsValue(value);
1729 }
1730
1731 @Override protected Set<Entry<K, V>> createEntrySet() {
1732 return map.entrySet();
1733 }
1734
1735 @Override public boolean isEmpty() {
1736 return map.isEmpty();
1737 }
1738
1739 @Override public int size() {
1740 return map.size();
1741 }
1742 }
1743 }