View Javadoc
1   /*
2    * Copyright (C) 2007 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkArgument;
20  import static com.google.common.base.Preconditions.checkNotNull;
21  import static com.google.common.base.Predicates.compose;
22  import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
23  import static com.google.common.collect.CollectPreconditions.checkNonnegative;
24  
25  import com.google.common.annotations.Beta;
26  import com.google.common.annotations.GwtCompatible;
27  import com.google.common.annotations.GwtIncompatible;
28  import com.google.common.base.Converter;
29  import com.google.common.base.Equivalence;
30  import com.google.common.base.Function;
31  import com.google.common.base.Objects;
32  import com.google.common.base.Preconditions;
33  import com.google.common.base.Predicate;
34  import com.google.common.base.Predicates;
35  import com.google.common.collect.MapDifference.ValueDifference;
36  import com.google.common.primitives.Ints;
37  import com.google.errorprone.annotations.CanIgnoreReturnValue;
38  import com.google.j2objc.annotations.RetainedWith;
39  import com.google.j2objc.annotations.Weak;
40  import com.google.j2objc.annotations.WeakOuter;
41  import java.io.Serializable;
42  import java.util.AbstractCollection;
43  import java.util.AbstractMap;
44  import java.util.Collection;
45  import java.util.Collections;
46  import java.util.Comparator;
47  import java.util.EnumMap;
48  import java.util.Enumeration;
49  import java.util.HashMap;
50  import java.util.IdentityHashMap;
51  import java.util.Iterator;
52  import java.util.LinkedHashMap;
53  import java.util.Map;
54  import java.util.Map.Entry;
55  import java.util.NavigableMap;
56  import java.util.NavigableSet;
57  import java.util.Properties;
58  import java.util.Set;
59  import java.util.SortedMap;
60  import java.util.SortedSet;
61  import java.util.Spliterator;
62  import java.util.Spliterators;
63  import java.util.TreeMap;
64  import java.util.concurrent.ConcurrentHashMap;
65  import java.util.concurrent.ConcurrentMap;
66  import java.util.function.BiConsumer;
67  import java.util.function.BiFunction;
68  import java.util.function.BinaryOperator;
69  import java.util.function.Consumer;
70  import java.util.stream.Collector;
71  import javax.annotation.Nullable;
72  
73  /**
74   * Static utility methods pertaining to {@link Map} instances (including instances of
75   * {@link SortedMap}, {@link BiMap}, etc.). Also see this class's counterparts
76   * {@link Lists}, {@link Sets} and {@link Queues}.
77   *
78   * <p>See the Guava User Guide article on <a href=
79   * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#maps">
80   * {@code Maps}</a>.
81   *
82   * @author Kevin Bourrillion
83   * @author Mike Bostock
84   * @author Isaac Shum
85   * @author Louis Wasserman
86   * @since 2.0
87   */
88  @GwtCompatible(emulated = true)
89  public final class Maps {
90    private Maps() {}
91  
92    private enum EntryFunction implements Function<Entry<?, ?>, Object> {
93      KEY {
94        @Override
95        @Nullable
96        public Object apply(Entry<?, ?> entry) {
97          return entry.getKey();
98        }
99      },
100     VALUE {
101       @Override
102       @Nullable
103       public Object apply(Entry<?, ?> entry) {
104         return entry.getValue();
105       }
106     };
107   }
108 
109   @SuppressWarnings("unchecked")
110   static <K> Function<Entry<K, ?>, K> keyFunction() {
111     return (Function) EntryFunction.KEY;
112   }
113 
114   @SuppressWarnings("unchecked")
115   static <V> Function<Entry<?, V>, V> valueFunction() {
116     return (Function) EntryFunction.VALUE;
117   }
118 
119   static <K, V> Iterator<K> keyIterator(Iterator<Entry<K, V>> entryIterator) {
120     return Iterators.transform(entryIterator, Maps.<K>keyFunction());
121   }
122 
123   static <K, V> Iterator<V> valueIterator(Iterator<Entry<K, V>> entryIterator) {
124     return Iterators.transform(entryIterator, Maps.<V>valueFunction());
125   }
126 
127   /**
128    * Returns an immutable map instance containing the given entries.
129    * Internally, the returned map will be backed by an {@link EnumMap}.
130    *
131    * <p>The iteration order of the returned map follows the enum's iteration
132    * order, not the order in which the elements appear in the given map.
133    *
134    * @param map the map to make an immutable copy of
135    * @return an immutable map containing those entries
136    * @since 14.0
137    */
138   @GwtCompatible(serializable = true)
139   @Beta
140   public static <K extends Enum<K>, V> ImmutableMap<K, V> immutableEnumMap(
141       Map<K, ? extends V> map) {
142     if (map instanceof ImmutableEnumMap) {
143       @SuppressWarnings("unchecked") // safe covariant cast
144       ImmutableEnumMap<K, V> result = (ImmutableEnumMap<K, V>) map;
145       return result;
146     }
147     Iterator<? extends Map.Entry<K, ? extends V>> entryItr = map.entrySet().iterator();
148     if (!entryItr.hasNext()) {
149       return ImmutableMap.of();
150     }
151     Map.Entry<K, ? extends V> entry1 = entryItr.next();
152     K key1 = entry1.getKey();
153     V value1 = entry1.getValue();
154     checkEntryNotNull(key1, value1);
155     Class<K> clazz = key1.getDeclaringClass();
156     EnumMap<K, V> enumMap = new EnumMap<>(clazz);
157     enumMap.put(key1, value1);
158     while (entryItr.hasNext()) {
159       Entry<K, ? extends V> entry = entryItr.next();
160       K key = entry.getKey();
161       V value = entry.getValue();
162       checkEntryNotNull(key, value);
163       enumMap.put(key, value);
164     }
165     return ImmutableEnumMap.asImmutable(enumMap);
166   }
167 
168   private static class Accumulator<K extends Enum<K>, V> {
169     private final BinaryOperator<V> mergeFunction;
170     private EnumMap<K, V> map = null;
171 
172     Accumulator(BinaryOperator<V> mergeFunction) {
173       this.mergeFunction = mergeFunction;
174     }
175 
176     void put(K key, V value) {
177       if (map == null) {
178         map = new EnumMap<>(key.getDeclaringClass());
179       }
180       map.merge(key, value, mergeFunction);
181     }
182 
183     Accumulator<K, V> combine(Accumulator<K, V> other) {
184       if (this.map == null) {
185         return other;
186       } else if (other.map == null) {
187         return this;
188       } else {
189         other.map.forEach(this::put);
190         return this;
191       }
192     }
193 
194     ImmutableMap<K, V> toImmutableMap() {
195       return (map == null) ? ImmutableMap.<K, V>of() : ImmutableEnumMap.asImmutable(map);
196     }
197   }
198 
199   /**
200    * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys
201    * and values are the result of applying the provided mapping functions to the input elements. The
202    * resulting implementation is specialized for enum key types. The returned map and its views will
203    * iterate over keys in their enum definition order, not encounter order.
204    *
205    * <p>If the mapped keys contain duplicates, an {@code IllegalArgumentException} is thrown when
206    * the collection operation is performed. (This differs from the {@code Collector} returned by
207    * {@link java.util.stream.Collectors#toMap(java.util.function.Function,
208    * java.util.function.Function) Collectors.toMap(Function, Function)}, which throws an
209    * {@code IllegalStateException}.)
210    *
211    * @since 21.0
212    */
213   @Beta
214   public static <T, K extends Enum<K>, V> Collector<T, ?, ImmutableMap<K, V>> toImmutableEnumMap(
215       java.util.function.Function<? super T, ? extends K> keyFunction,
216       java.util.function.Function<? super T, ? extends V> valueFunction) {
217     checkNotNull(keyFunction);
218     checkNotNull(valueFunction);
219     return Collector.of(
220         () ->
221             new Accumulator<K, V>(
222                 (v1, v2) -> {
223                   throw new IllegalArgumentException("Multiple values for key: " + v1 + ", " + v2);
224                 }),
225         (accum, t) -> {
226           K key = checkNotNull(keyFunction.apply(t), "Null key for input %s", t);
227           V newValue = checkNotNull(valueFunction.apply(t), "Null value for input %s", t);
228           accum.put(key, newValue);
229         },
230         Accumulator::combine,
231         Accumulator::toImmutableMap,
232         Collector.Characteristics.UNORDERED);
233   }
234 
235   /**
236    * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys
237    * and values are the result of applying the provided mapping functions to the input elements. The
238    * resulting implementation is specialized for enum key types. The returned map and its views will
239    * iterate over keys in their enum definition order, not encounter order.
240    *
241    * <p>If the mapped keys contain duplicates, the values are merged using the specified merging
242    * function.
243    *
244    * @since 21.0
245    */
246   @Beta
247   public static <T, K extends Enum<K>, V> Collector<T, ?, ImmutableMap<K, V>> toImmutableEnumMap(
248       java.util.function.Function<? super T, ? extends K> keyFunction,
249       java.util.function.Function<? super T, ? extends V> valueFunction,
250       BinaryOperator<V> mergeFunction) {
251     checkNotNull(keyFunction);
252     checkNotNull(valueFunction);
253     checkNotNull(mergeFunction);
254     // not UNORDERED because we don't know if mergeFunction is commutative
255     return Collector.of(
256         () -> new Accumulator<K, V>(mergeFunction),
257         (accum, t) -> {
258           K key = checkNotNull(keyFunction.apply(t), "Null key for input %s", t);
259           V newValue = checkNotNull(valueFunction.apply(t), "Null value for input %s", t);
260           accum.put(key, newValue);
261         },
262         Accumulator::combine,
263         Accumulator::toImmutableMap);
264   }
265 
266   /**
267    * Creates a <i>mutable</i>, empty {@code HashMap} instance.
268    *
269    * <p><b>Note:</b> if mutability is not required, use {@link
270    * ImmutableMap#of()} instead.
271    *
272    * <p><b>Note:</b> if {@code K} is an {@code enum} type, use {@link
273    * #newEnumMap} instead.
274    *
275    * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and
276    * should be treated as deprecated. Instead, use the {@code HashMap}
277    * constructor directly, taking advantage of the new
278    * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
279    *
280    * @return a new, empty {@code HashMap}
281    */
282   public static <K, V> HashMap<K, V> newHashMap() {
283     return new HashMap<>();
284   }
285 
286   /**
287    * Creates a {@code HashMap} instance, with a high enough "initial capacity"
288    * that it <i>should</i> hold {@code expectedSize} elements without growth.
289    * This behavior cannot be broadly guaranteed, but it is observed to be true
290    * for OpenJDK 1.7. It also can't be guaranteed that the method isn't
291    * inadvertently <i>oversizing</i> the returned map.
292    *
293    * @param expectedSize the number of entries you expect to add to the
294    *        returned map
295    * @return a new, empty {@code HashMap} with enough capacity to hold {@code
296    *         expectedSize} entries without resizing
297    * @throws IllegalArgumentException if {@code expectedSize} is negative
298    */
299   public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(int expectedSize) {
300     return new HashMap<>(capacity(expectedSize));
301   }
302 
303   /**
304    * Returns a capacity that is sufficient to keep the map from being resized as long as it grows no
305    * larger than expectedSize and the load factor is ≥ its default (0.75).
306    */
307   static int capacity(int expectedSize) {
308     if (expectedSize < 3) {
309       checkNonnegative(expectedSize, "expectedSize");
310       return expectedSize + 1;
311     }
312     if (expectedSize < Ints.MAX_POWER_OF_TWO) {
313       // This is the calculation used in JDK8 to resize when a putAll
314       // happens; it seems to be the most conservative calculation we
315       // can make.  0.75 is the default load factor.
316       return (int) ((float) expectedSize / 0.75F + 1.0F);
317     }
318     return Integer.MAX_VALUE; // any large value
319   }
320 
321   /**
322    * Creates a <i>mutable</i> {@code HashMap} instance with the same mappings as
323    * the specified map.
324    *
325    * <p><b>Note:</b> if mutability is not required, use {@link
326    * ImmutableMap#copyOf(Map)} instead.
327    *
328    * <p><b>Note:</b> if {@code K} is an {@link Enum} type, use {@link
329    * #newEnumMap} instead.
330    *
331    * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and
332    * should be treated as deprecated. Instead, use the {@code HashMap}
333    * constructor directly, taking advantage of the new
334    * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
335    *
336    * @param map the mappings to be placed in the new map
337    * @return a new {@code HashMap} initialized with the mappings from {@code
338    *         map}
339    */
340   public static <K, V> HashMap<K, V> newHashMap(Map<? extends K, ? extends V> map) {
341     return new HashMap<>(map);
342   }
343 
344   /**
345    * Creates a <i>mutable</i>, empty, insertion-ordered {@code LinkedHashMap}
346    * instance.
347    *
348    * <p><b>Note:</b> if mutability is not required, use {@link
349    * ImmutableMap#of()} instead.
350    *
351    * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and
352    * should be treated as deprecated. Instead, use the {@code LinkedHashMap}
353    * constructor directly, taking advantage of the new
354    * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
355    *
356    * @return a new, empty {@code LinkedHashMap}
357    */
358   public static <K, V> LinkedHashMap<K, V> newLinkedHashMap() {
359     return new LinkedHashMap<>();
360   }
361 
362   /**
363    * Creates a {@code LinkedHashMap} instance, with a high enough
364    * "initial capacity" that it <i>should</i> hold {@code expectedSize}
365    * elements without growth. This behavior cannot be broadly guaranteed, but
366    * it is observed to be true for OpenJDK 1.7. It also can't be guaranteed
367    * that the method isn't inadvertently <i>oversizing</i> the returned map.
368    *
369    * @param expectedSize the number of entries you expect to add to the
370    *        returned map
371    * @return a new, empty {@code LinkedHashMap} with enough capacity to hold
372    *         {@code expectedSize} entries without resizing
373    * @throws IllegalArgumentException if {@code expectedSize} is negative
374    * @since 19.0
375    */
376   public static <K, V> LinkedHashMap<K, V> newLinkedHashMapWithExpectedSize(int expectedSize) {
377     return new LinkedHashMap<>(capacity(expectedSize));
378   }
379 
380   /**
381    * Creates a <i>mutable</i>, insertion-ordered {@code LinkedHashMap} instance
382    * with the same mappings as the specified map.
383    *
384    * <p><b>Note:</b> if mutability is not required, use {@link
385    * ImmutableMap#copyOf(Map)} instead.
386    *
387    * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and
388    * should be treated as deprecated. Instead, use the {@code LinkedHashMap}
389    * constructor directly, taking advantage of the new
390    * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
391    *
392    * @param map the mappings to be placed in the new map
393    * @return a new, {@code LinkedHashMap} initialized with the mappings from
394    *         {@code map}
395    */
396   public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(Map<? extends K, ? extends V> map) {
397     return new LinkedHashMap<>(map);
398   }
399 
400   /**
401    * Creates a new empty {@link ConcurrentHashMap} instance.
402    *
403    * @since 3.0
404    */
405   public static <K, V> ConcurrentMap<K, V> newConcurrentMap() {
406     return new ConcurrentHashMap<>();
407   }
408 
409   /**
410    * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the natural
411    * ordering of its elements.
412    *
413    * <p><b>Note:</b> if mutability is not required, use {@link
414    * ImmutableSortedMap#of()} instead.
415    *
416    * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and
417    * should be treated as deprecated. Instead, use the {@code TreeMap}
418    * constructor directly, taking advantage of the new
419    * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
420    *
421    * @return a new, empty {@code TreeMap}
422    */
423   public static <K extends Comparable, V> TreeMap<K, V> newTreeMap() {
424     return new TreeMap<>();
425   }
426 
427   /**
428    * Creates a <i>mutable</i> {@code TreeMap} instance with the same mappings as
429    * the specified map and using the same ordering as the specified map.
430    *
431    * <p><b>Note:</b> if mutability is not required, use {@link
432    * ImmutableSortedMap#copyOfSorted(SortedMap)} instead.
433    *
434    * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and
435    * should be treated as deprecated. Instead, use the {@code TreeMap}
436    * constructor directly, taking advantage of the new
437    * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
438    *
439    * @param map the sorted map whose mappings are to be placed in the new map
440    *        and whose comparator is to be used to sort the new map
441    * @return a new {@code TreeMap} initialized with the mappings from {@code
442    *         map} and using the comparator of {@code map}
443    */
444   public static <K, V> TreeMap<K, V> newTreeMap(SortedMap<K, ? extends V> map) {
445     return new TreeMap<>(map);
446   }
447 
448   /**
449    * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the given
450    * comparator.
451    *
452    * <p><b>Note:</b> if mutability is not required, use {@code
453    * ImmutableSortedMap.orderedBy(comparator).build()} instead.
454    *
455    * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and
456    * should be treated as deprecated. Instead, use the {@code TreeMap}
457    * constructor directly, taking advantage of the new
458    * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
459    *
460    * @param comparator the comparator to sort the keys with
461    * @return a new, empty {@code TreeMap}
462    */
463   public static <C, K extends C, V> TreeMap<K, V> newTreeMap(@Nullable Comparator<C> comparator) {
464     // Ideally, the extra type parameter "C" shouldn't be necessary. It is a
465     // work-around of a compiler type inference quirk that prevents the
466     // following code from being compiled:
467     // Comparator<Class<?>> comparator = null;
468     // Map<Class<? extends Throwable>, String> map = newTreeMap(comparator);
469     return new TreeMap<>(comparator);
470   }
471 
472   /**
473    * Creates an {@code EnumMap} instance.
474    *
475    * @param type the key type for this map
476    * @return a new, empty {@code EnumMap}
477    */
478   public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(Class<K> type) {
479     return new EnumMap<>(checkNotNull(type));
480   }
481 
482   /**
483    * Creates an {@code EnumMap} with the same mappings as the specified map.
484    *
485    * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and
486    * should be treated as deprecated. Instead, use the {@code EnumMap}
487    * constructor directly, taking advantage of the new
488    * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
489    *
490    * @param map the map from which to initialize this {@code EnumMap}
491    * @return a new {@code EnumMap} initialized with the mappings from {@code
492    *         map}
493    * @throws IllegalArgumentException if {@code m} is not an {@code EnumMap}
494    *         instance and contains no mappings
495    */
496   public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(Map<K, ? extends V> map) {
497     return new EnumMap<>(map);
498   }
499 
500   /**
501    * Creates an {@code IdentityHashMap} instance.
502    *
503    * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and
504    * should be treated as deprecated. Instead, use the {@code IdentityHashMap}
505    * constructor directly, taking advantage of the new
506    * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
507    *
508    * @return a new, empty {@code IdentityHashMap}
509    */
510   public static <K, V> IdentityHashMap<K, V> newIdentityHashMap() {
511     return new IdentityHashMap<>();
512   }
513 
514   /**
515    * Computes the difference between two maps. This difference is an immutable
516    * snapshot of the state of the maps at the time this method is called. It
517    * will never change, even if the maps change at a later time.
518    *
519    * <p>Since this method uses {@code HashMap} instances internally, the keys of
520    * the supplied maps must be well-behaved with respect to
521    * {@link Object#equals} and {@link Object#hashCode}.
522    *
523    * <p><b>Note:</b>If you only need to know whether two maps have the same
524    * mappings, call {@code left.equals(right)} instead of this method.
525    *
526    * @param left the map to treat as the "left" map for purposes of comparison
527    * @param right the map to treat as the "right" map for purposes of comparison
528    * @return the difference between the two maps
529    */
530   @SuppressWarnings("unchecked")
531   public static <K, V> MapDifference<K, V> difference(
532       Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) {
533     if (left instanceof SortedMap) {
534       SortedMap<K, ? extends V> sortedLeft = (SortedMap<K, ? extends V>) left;
535       return difference(sortedLeft, right);
536     }
537     return difference(left, right, Equivalence.equals());
538   }
539 
540   /**
541    * Computes the difference between two maps. This difference is an immutable
542    * snapshot of the state of the maps at the time this method is called. It
543    * will never change, even if the maps change at a later time.
544    *
545    * <p>Since this method uses {@code HashMap} instances internally, the keys of
546    * the supplied maps must be well-behaved with respect to
547    * {@link Object#equals} and {@link Object#hashCode}.
548    *
549    * @param left the map to treat as the "left" map for purposes of comparison
550    * @param right the map to treat as the "right" map for purposes of comparison
551    * @param valueEquivalence the equivalence relationship to use to compare
552    *    values
553    * @return the difference between the two maps
554    * @since 10.0
555    */
556   public static <K, V> MapDifference<K, V> difference(
557       Map<? extends K, ? extends V> left,
558       Map<? extends K, ? extends V> right,
559       Equivalence<? super V> valueEquivalence) {
560     Preconditions.checkNotNull(valueEquivalence);
561 
562     Map<K, V> onlyOnLeft = newLinkedHashMap();
563     Map<K, V> onlyOnRight = new LinkedHashMap<>(right); // will whittle it down
564     Map<K, V> onBoth = newLinkedHashMap();
565     Map<K, MapDifference.ValueDifference<V>> differences = newLinkedHashMap();
566     doDifference(left, right, valueEquivalence, onlyOnLeft, onlyOnRight, onBoth, differences);
567     return new MapDifferenceImpl<>(onlyOnLeft, onlyOnRight, onBoth, differences);
568   }
569 
570   private static <K, V> void doDifference(
571       Map<? extends K, ? extends V> left,
572       Map<? extends K, ? extends V> right,
573       Equivalence<? super V> valueEquivalence,
574       Map<K, V> onlyOnLeft,
575       Map<K, V> onlyOnRight,
576       Map<K, V> onBoth,
577       Map<K, MapDifference.ValueDifference<V>> differences) {
578     for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
579       K leftKey = entry.getKey();
580       V leftValue = entry.getValue();
581       if (right.containsKey(leftKey)) {
582         V rightValue = onlyOnRight.remove(leftKey);
583         if (valueEquivalence.equivalent(leftValue, rightValue)) {
584           onBoth.put(leftKey, leftValue);
585         } else {
586           differences.put(leftKey, ValueDifferenceImpl.create(leftValue, rightValue));
587         }
588       } else {
589         onlyOnLeft.put(leftKey, leftValue);
590       }
591     }
592   }
593 
594   private static <K, V> Map<K, V> unmodifiableMap(Map<K, ? extends V> map) {
595     if (map instanceof SortedMap) {
596       return Collections.unmodifiableSortedMap((SortedMap<K, ? extends V>) map);
597     } else {
598       return Collections.unmodifiableMap(map);
599     }
600   }
601 
602   static class MapDifferenceImpl<K, V> implements MapDifference<K, V> {
603     final Map<K, V> onlyOnLeft;
604     final Map<K, V> onlyOnRight;
605     final Map<K, V> onBoth;
606     final Map<K, ValueDifference<V>> differences;
607 
608     MapDifferenceImpl(
609         Map<K, V> onlyOnLeft,
610         Map<K, V> onlyOnRight,
611         Map<K, V> onBoth,
612         Map<K, ValueDifference<V>> differences) {
613       this.onlyOnLeft = unmodifiableMap(onlyOnLeft);
614       this.onlyOnRight = unmodifiableMap(onlyOnRight);
615       this.onBoth = unmodifiableMap(onBoth);
616       this.differences = unmodifiableMap(differences);
617     }
618 
619     @Override
620     public boolean areEqual() {
621       return onlyOnLeft.isEmpty() && onlyOnRight.isEmpty() && differences.isEmpty();
622     }
623 
624     @Override
625     public Map<K, V> entriesOnlyOnLeft() {
626       return onlyOnLeft;
627     }
628 
629     @Override
630     public Map<K, V> entriesOnlyOnRight() {
631       return onlyOnRight;
632     }
633 
634     @Override
635     public Map<K, V> entriesInCommon() {
636       return onBoth;
637     }
638 
639     @Override
640     public Map<K, ValueDifference<V>> entriesDiffering() {
641       return differences;
642     }
643 
644     @Override
645     public boolean equals(Object object) {
646       if (object == this) {
647         return true;
648       }
649       if (object instanceof MapDifference) {
650         MapDifference<?, ?> other = (MapDifference<?, ?>) object;
651         return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft())
652             && entriesOnlyOnRight().equals(other.entriesOnlyOnRight())
653             && entriesInCommon().equals(other.entriesInCommon())
654             && entriesDiffering().equals(other.entriesDiffering());
655       }
656       return false;
657     }
658 
659     @Override
660     public int hashCode() {
661       return Objects.hashCode(
662           entriesOnlyOnLeft(), entriesOnlyOnRight(), entriesInCommon(), entriesDiffering());
663     }
664 
665     @Override
666     public String toString() {
667       if (areEqual()) {
668         return "equal";
669       }
670 
671       StringBuilder result = new StringBuilder("not equal");
672       if (!onlyOnLeft.isEmpty()) {
673         result.append(": only on left=").append(onlyOnLeft);
674       }
675       if (!onlyOnRight.isEmpty()) {
676         result.append(": only on right=").append(onlyOnRight);
677       }
678       if (!differences.isEmpty()) {
679         result.append(": value differences=").append(differences);
680       }
681       return result.toString();
682     }
683   }
684 
685   static class ValueDifferenceImpl<V> implements MapDifference.ValueDifference<V> {
686     private final V left;
687     private final V right;
688 
689     static <V> ValueDifference<V> create(@Nullable V left, @Nullable V right) {
690       return new ValueDifferenceImpl<V>(left, right);
691     }
692 
693     private ValueDifferenceImpl(@Nullable V left, @Nullable V right) {
694       this.left = left;
695       this.right = right;
696     }
697 
698     @Override
699     public V leftValue() {
700       return left;
701     }
702 
703     @Override
704     public V rightValue() {
705       return right;
706     }
707 
708     @Override
709     public boolean equals(@Nullable Object object) {
710       if (object instanceof MapDifference.ValueDifference) {
711         MapDifference.ValueDifference<?> that = (MapDifference.ValueDifference<?>) object;
712         return Objects.equal(this.left, that.leftValue())
713             && Objects.equal(this.right, that.rightValue());
714       }
715       return false;
716     }
717 
718     @Override
719     public int hashCode() {
720       return Objects.hashCode(left, right);
721     }
722 
723     @Override
724     public String toString() {
725       return "(" + left + ", " + right + ")";
726     }
727   }
728 
729   /**
730    * Computes the difference between two sorted maps, using the comparator of
731    * the left map, or {@code Ordering.natural()} if the left map uses the
732    * natural ordering of its elements. This difference is an immutable snapshot
733    * of the state of the maps at the time this method is called. It will never
734    * change, even if the maps change at a later time.
735    *
736    * <p>Since this method uses {@code TreeMap} instances internally, the keys of
737    * the right map must all compare as distinct according to the comparator
738    * of the left map.
739    *
740    * <p><b>Note:</b>If you only need to know whether two sorted maps have the
741    * same mappings, call {@code left.equals(right)} instead of this method.
742    *
743    * @param left the map to treat as the "left" map for purposes of comparison
744    * @param right the map to treat as the "right" map for purposes of comparison
745    * @return the difference between the two maps
746    * @since 11.0
747    */
748   public static <K, V> SortedMapDifference<K, V> difference(
749       SortedMap<K, ? extends V> left, Map<? extends K, ? extends V> right) {
750     checkNotNull(left);
751     checkNotNull(right);
752     Comparator<? super K> comparator = orNaturalOrder(left.comparator());
753     SortedMap<K, V> onlyOnLeft = Maps.newTreeMap(comparator);
754     SortedMap<K, V> onlyOnRight = Maps.newTreeMap(comparator);
755     onlyOnRight.putAll(right); // will whittle it down
756     SortedMap<K, V> onBoth = Maps.newTreeMap(comparator);
757     SortedMap<K, MapDifference.ValueDifference<V>> differences = Maps.newTreeMap(comparator);
758     doDifference(left, right, Equivalence.equals(), onlyOnLeft, onlyOnRight, onBoth, differences);
759     return new SortedMapDifferenceImpl<>(onlyOnLeft, onlyOnRight, onBoth, differences);
760   }
761 
762   static class SortedMapDifferenceImpl<K, V> extends MapDifferenceImpl<K, V>
763       implements SortedMapDifference<K, V> {
764     SortedMapDifferenceImpl(
765         SortedMap<K, V> onlyOnLeft,
766         SortedMap<K, V> onlyOnRight,
767         SortedMap<K, V> onBoth,
768         SortedMap<K, ValueDifference<V>> differences) {
769       super(onlyOnLeft, onlyOnRight, onBoth, differences);
770     }
771 
772     @Override
773     public SortedMap<K, ValueDifference<V>> entriesDiffering() {
774       return (SortedMap<K, ValueDifference<V>>) super.entriesDiffering();
775     }
776 
777     @Override
778     public SortedMap<K, V> entriesInCommon() {
779       return (SortedMap<K, V>) super.entriesInCommon();
780     }
781 
782     @Override
783     public SortedMap<K, V> entriesOnlyOnLeft() {
784       return (SortedMap<K, V>) super.entriesOnlyOnLeft();
785     }
786 
787     @Override
788     public SortedMap<K, V> entriesOnlyOnRight() {
789       return (SortedMap<K, V>) super.entriesOnlyOnRight();
790     }
791   }
792 
793   /**
794    * Returns the specified comparator if not null; otherwise returns {@code
795    * Ordering.natural()}. This method is an abomination of generics; the only
796    * purpose of this method is to contain the ugly type-casting in one place.
797    */
798   @SuppressWarnings("unchecked")
799   static <E> Comparator<? super E> orNaturalOrder(@Nullable Comparator<? super E> comparator) {
800     if (comparator != null) { // can't use ? : because of javac bug 5080917
801       return comparator;
802     }
803     return (Comparator<E>) Ordering.natural();
804   }
805 
806   /**
807    * Returns a live {@link Map} view whose keys are the contents of {@code set}
808    * and whose values are computed on demand using {@code function}. To get an
809    * immutable <i>copy</i> instead, use {@link #toMap(Iterable, Function)}.
810    *
811    * <p>Specifically, for each {@code k} in the backing set, the returned map
812    * has an entry mapping {@code k} to {@code function.apply(k)}. The {@code
813    * keySet}, {@code values}, and {@code entrySet} views of the returned map
814    * iterate in the same order as the backing set.
815    *
816    * <p>Modifications to the backing set are read through to the returned map.
817    * The returned map supports removal operations if the backing set does.
818    * Removal operations write through to the backing set.  The returned map
819    * does not support put operations.
820    *
821    * <p><b>Warning:</b> If the function rejects {@code null}, caution is
822    * required to make sure the set does not contain {@code null}, because the
823    * view cannot stop {@code null} from being added to the set.
824    *
825    * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
826    * key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also
827    * of type {@code K}. Using a key type for which this may not hold, such as
828    * {@code ArrayList}, may risk a {@code ClassCastException} when calling
829    * methods on the resulting map view.
830    *
831    * @since 14.0
832    */
833   public static <K, V> Map<K, V> asMap(Set<K> set, Function<? super K, V> function) {
834     return new AsMapView<>(set, function);
835   }
836 
837   /**
838    * Returns a view of the sorted set as a map, mapping keys from the set
839    * according to the specified function.
840    *
841    * <p>Specifically, for each {@code k} in the backing set, the returned map
842    * has an entry mapping {@code k} to {@code function.apply(k)}. The {@code
843    * keySet}, {@code values}, and {@code entrySet} views of the returned map
844    * iterate in the same order as the backing set.
845    *
846    * <p>Modifications to the backing set are read through to the returned map.
847    * The returned map supports removal operations if the backing set does.
848    * Removal operations write through to the backing set.  The returned map does
849    * not support put operations.
850    *
851    * <p><b>Warning:</b> If the function rejects {@code null}, caution is
852    * required to make sure the set does not contain {@code null}, because the
853    * view cannot stop {@code null} from being added to the set.
854    *
855    * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
856    * key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of
857    * type {@code K}. Using a key type for which this may not hold, such as
858    * {@code ArrayList}, may risk a {@code ClassCastException} when calling
859    * methods on the resulting map view.
860    *
861    * @since 14.0
862    */
863   public static <K, V> SortedMap<K, V> asMap(SortedSet<K> set, Function<? super K, V> function) {
864     return new SortedAsMapView<>(set, function);
865   }
866 
867   /**
868    * Returns a view of the navigable set as a map, mapping keys from the set
869    * according to the specified function.
870    *
871    * <p>Specifically, for each {@code k} in the backing set, the returned map
872    * has an entry mapping {@code k} to {@code function.apply(k)}. The {@code
873    * keySet}, {@code values}, and {@code entrySet} views of the returned map
874    * iterate in the same order as the backing set.
875    *
876    * <p>Modifications to the backing set are read through to the returned map.
877    * The returned map supports removal operations if the backing set does.
878    * Removal operations write through to the backing set.  The returned map
879    * does not support put operations.
880    *
881    * <p><b>Warning:</b> If the function rejects {@code null}, caution is
882    * required to make sure the set does not contain {@code null}, because the
883    * view cannot stop {@code null} from being added to the set.
884    *
885    * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
886    * key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also
887    * of type {@code K}. Using a key type for which this may not hold, such as
888    * {@code ArrayList}, may risk a {@code ClassCastException} when calling
889    * methods on the resulting map view.
890    *
891    * @since 14.0
892    */
893   @GwtIncompatible // NavigableMap
894   public static <K, V> NavigableMap<K, V> asMap(
895       NavigableSet<K> set, Function<? super K, V> function) {
896     return new NavigableAsMapView<>(set, function);
897   }
898 
899   private static class AsMapView<K, V> extends ViewCachingAbstractMap<K, V> {
900 
901     private final Set<K> set;
902     final Function<? super K, V> function;
903 
904     Set<K> backingSet() {
905       return set;
906     }
907 
908     AsMapView(Set<K> set, Function<? super K, V> function) {
909       this.set = checkNotNull(set);
910       this.function = checkNotNull(function);
911     }
912 
913     @Override
914     public Set<K> createKeySet() {
915       return removeOnlySet(backingSet());
916     }
917 
918     @Override
919     Collection<V> createValues() {
920       return Collections2.transform(set, function);
921     }
922 
923     @Override
924     public int size() {
925       return backingSet().size();
926     }
927 
928     @Override
929     public boolean containsKey(@Nullable Object key) {
930       return backingSet().contains(key);
931     }
932 
933     @Override
934     public V get(@Nullable Object key) {
935       return getOrDefault(key, null);
936     }
937 
938     @Override
939     public V getOrDefault(@Nullable Object key, @Nullable V defaultValue) {
940       if (Collections2.safeContains(backingSet(), key)) {
941         @SuppressWarnings("unchecked") // unsafe, but Javadoc warns about it
942         K k = (K) key;
943         return function.apply(k);
944       } else {
945         return defaultValue;
946       }
947     }
948 
949     @Override
950     public V remove(@Nullable Object key) {
951       if (backingSet().remove(key)) {
952         @SuppressWarnings("unchecked") // unsafe, but Javadoc warns about it
953         K k = (K) key;
954         return function.apply(k);
955       } else {
956         return null;
957       }
958     }
959 
960     @Override
961     public void clear() {
962       backingSet().clear();
963     }
964 
965     @Override
966     protected Set<Entry<K, V>> createEntrySet() {
967       @WeakOuter
968       class EntrySetImpl extends EntrySet<K, V> {
969         @Override
970         Map<K, V> map() {
971           return AsMapView.this;
972         }
973 
974         @Override
975         public Iterator<Entry<K, V>> iterator() {
976           return asMapEntryIterator(backingSet(), function);
977         }
978       }
979       return new EntrySetImpl();
980     }
981 
982     @Override
983     public void forEach(BiConsumer<? super K, ? super V> action) {
984       checkNotNull(action);
985       // avoids allocation of entries
986       backingSet().forEach(k -> action.accept(k, function.apply(k)));
987     }
988   }
989 
990   static <K, V> Iterator<Entry<K, V>> asMapEntryIterator(
991       Set<K> set, final Function<? super K, V> function) {
992     return new TransformedIterator<K, Entry<K, V>>(set.iterator()) {
993       @Override
994       Entry<K, V> transform(final K key) {
995         return immutableEntry(key, function.apply(key));
996       }
997     };
998   }
999 
1000   private static class SortedAsMapView<K, V> extends AsMapView<K, V> implements SortedMap<K, V> {
1001 
1002     SortedAsMapView(SortedSet<K> set, Function<? super K, V> function) {
1003       super(set, function);
1004     }
1005 
1006     @Override
1007     SortedSet<K> backingSet() {
1008       return (SortedSet<K>) super.backingSet();
1009     }
1010 
1011     @Override
1012     public Comparator<? super K> comparator() {
1013       return backingSet().comparator();
1014     }
1015 
1016     @Override
1017     public Set<K> keySet() {
1018       return removeOnlySortedSet(backingSet());
1019     }
1020 
1021     @Override
1022     public SortedMap<K, V> subMap(K fromKey, K toKey) {
1023       return asMap(backingSet().subSet(fromKey, toKey), function);
1024     }
1025 
1026     @Override
1027     public SortedMap<K, V> headMap(K toKey) {
1028       return asMap(backingSet().headSet(toKey), function);
1029     }
1030 
1031     @Override
1032     public SortedMap<K, V> tailMap(K fromKey) {
1033       return asMap(backingSet().tailSet(fromKey), function);
1034     }
1035 
1036     @Override
1037     public K firstKey() {
1038       return backingSet().first();
1039     }
1040 
1041     @Override
1042     public K lastKey() {
1043       return backingSet().last();
1044     }
1045   }
1046 
1047   @GwtIncompatible // NavigableMap
1048   private static final class NavigableAsMapView<K, V> extends AbstractNavigableMap<K, V> {
1049     /*
1050      * Using AbstractNavigableMap is simpler than extending SortedAsMapView and rewriting all the
1051      * NavigableMap methods.
1052      */
1053 
1054     private final NavigableSet<K> set;
1055     private final Function<? super K, V> function;
1056 
1057     NavigableAsMapView(NavigableSet<K> ks, Function<? super K, V> vFunction) {
1058       this.set = checkNotNull(ks);
1059       this.function = checkNotNull(vFunction);
1060     }
1061 
1062     @Override
1063     public NavigableMap<K, V> subMap(
1064         K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1065       return asMap(set.subSet(fromKey, fromInclusive, toKey, toInclusive), function);
1066     }
1067 
1068     @Override
1069     public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
1070       return asMap(set.headSet(toKey, inclusive), function);
1071     }
1072 
1073     @Override
1074     public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
1075       return asMap(set.tailSet(fromKey, inclusive), function);
1076     }
1077 
1078     @Override
1079     public Comparator<? super K> comparator() {
1080       return set.comparator();
1081     }
1082 
1083     @Override
1084     @Nullable
1085     public V get(@Nullable Object key) {
1086       return getOrDefault(key, null);
1087     }
1088 
1089     @Override
1090     @Nullable
1091     public V getOrDefault(@Nullable Object key, @Nullable V defaultValue) {
1092       if (Collections2.safeContains(set, key)) {
1093         @SuppressWarnings("unchecked") // unsafe, but Javadoc warns about it
1094         K k = (K) key;
1095         return function.apply(k);
1096       } else {
1097         return defaultValue;
1098       }
1099     }
1100 
1101     @Override
1102     public void clear() {
1103       set.clear();
1104     }
1105 
1106     @Override
1107     Iterator<Entry<K, V>> entryIterator() {
1108       return asMapEntryIterator(set, function);
1109     }
1110 
1111     @Override
1112     Spliterator<Entry<K, V>> entrySpliterator() {
1113       return CollectSpliterators.map(set.spliterator(), e -> immutableEntry(e, function.apply(e)));
1114     }
1115 
1116     @Override
1117     public void forEach(BiConsumer<? super K, ? super V> action) {
1118       set.forEach(k -> action.accept(k, function.apply(k)));
1119     }
1120 
1121     @Override
1122     Iterator<Entry<K, V>> descendingEntryIterator() {
1123       return descendingMap().entrySet().iterator();
1124     }
1125 
1126     @Override
1127     public NavigableSet<K> navigableKeySet() {
1128       return removeOnlyNavigableSet(set);
1129     }
1130 
1131     @Override
1132     public int size() {
1133       return set.size();
1134     }
1135 
1136     @Override
1137     public NavigableMap<K, V> descendingMap() {
1138       return asMap(set.descendingSet(), function);
1139     }
1140   }
1141 
1142   private static <E> Set<E> removeOnlySet(final Set<E> set) {
1143     return new ForwardingSet<E>() {
1144       @Override
1145       protected Set<E> delegate() {
1146         return set;
1147       }
1148 
1149       @Override
1150       public boolean add(E element) {
1151         throw new UnsupportedOperationException();
1152       }
1153 
1154       @Override
1155       public boolean addAll(Collection<? extends E> es) {
1156         throw new UnsupportedOperationException();
1157       }
1158     };
1159   }
1160 
1161   private static <E> SortedSet<E> removeOnlySortedSet(final SortedSet<E> set) {
1162     return new ForwardingSortedSet<E>() {
1163       @Override
1164       protected SortedSet<E> delegate() {
1165         return set;
1166       }
1167 
1168       @Override
1169       public boolean add(E element) {
1170         throw new UnsupportedOperationException();
1171       }
1172 
1173       @Override
1174       public boolean addAll(Collection<? extends E> es) {
1175         throw new UnsupportedOperationException();
1176       }
1177 
1178       @Override
1179       public SortedSet<E> headSet(E toElement) {
1180         return removeOnlySortedSet(super.headSet(toElement));
1181       }
1182 
1183       @Override
1184       public SortedSet<E> subSet(E fromElement, E toElement) {
1185         return removeOnlySortedSet(super.subSet(fromElement, toElement));
1186       }
1187 
1188       @Override
1189       public SortedSet<E> tailSet(E fromElement) {
1190         return removeOnlySortedSet(super.tailSet(fromElement));
1191       }
1192     };
1193   }
1194 
1195   @GwtIncompatible // NavigableSet
1196   private static <E> NavigableSet<E> removeOnlyNavigableSet(final NavigableSet<E> set) {
1197     return new ForwardingNavigableSet<E>() {
1198       @Override
1199       protected NavigableSet<E> delegate() {
1200         return set;
1201       }
1202 
1203       @Override
1204       public boolean add(E element) {
1205         throw new UnsupportedOperationException();
1206       }
1207 
1208       @Override
1209       public boolean addAll(Collection<? extends E> es) {
1210         throw new UnsupportedOperationException();
1211       }
1212 
1213       @Override
1214       public SortedSet<E> headSet(E toElement) {
1215         return removeOnlySortedSet(super.headSet(toElement));
1216       }
1217 
1218       @Override
1219       public SortedSet<E> subSet(E fromElement, E toElement) {
1220         return removeOnlySortedSet(super.subSet(fromElement, toElement));
1221       }
1222 
1223       @Override
1224       public SortedSet<E> tailSet(E fromElement) {
1225         return removeOnlySortedSet(super.tailSet(fromElement));
1226       }
1227 
1228       @Override
1229       public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1230         return removeOnlyNavigableSet(super.headSet(toElement, inclusive));
1231       }
1232 
1233       @Override
1234       public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1235         return removeOnlyNavigableSet(super.tailSet(fromElement, inclusive));
1236       }
1237 
1238       @Override
1239       public NavigableSet<E> subSet(
1240           E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
1241         return removeOnlyNavigableSet(
1242             super.subSet(fromElement, fromInclusive, toElement, toInclusive));
1243       }
1244 
1245       @Override
1246       public NavigableSet<E> descendingSet() {
1247         return removeOnlyNavigableSet(super.descendingSet());
1248       }
1249     };
1250   }
1251 
1252   /**
1253    * Returns an immutable map whose keys are the distinct elements of {@code
1254    * keys} and whose value for each key was computed by {@code valueFunction}.
1255    * The map's iteration order is the order of the first appearance of each key
1256    * in {@code keys}.
1257    *
1258    * <p>When there are multiple instances of a key in {@code keys}, it is
1259    * unspecified whether {@code valueFunction} will be applied to more than one
1260    * instance of that key and, if it is, which result will be mapped to that
1261    * key in the returned map.
1262    *
1263    * <p>If {@code keys} is a {@link Set}, a live view can be obtained instead of
1264    * a copy using {@link Maps#asMap(Set, Function)}.
1265    *
1266    * @throws NullPointerException if any element of {@code keys} is
1267    *     {@code null}, or if {@code valueFunction} produces {@code null}
1268    *     for any key
1269    * @since 14.0
1270    */
1271   public static <K, V> ImmutableMap<K, V> toMap(
1272       Iterable<K> keys, Function<? super K, V> valueFunction) {
1273     return toMap(keys.iterator(), valueFunction);
1274   }
1275 
1276   /**
1277    * Returns an immutable map whose keys are the distinct elements of {@code
1278    * keys} and whose value for each key was computed by {@code valueFunction}.
1279    * The map's iteration order is the order of the first appearance of each key
1280    * in {@code keys}.
1281    *
1282    * <p>When there are multiple instances of a key in {@code keys}, it is
1283    * unspecified whether {@code valueFunction} will be applied to more than one
1284    * instance of that key and, if it is, which result will be mapped to that
1285    * key in the returned map.
1286    *
1287    * @throws NullPointerException if any element of {@code keys} is
1288    *     {@code null}, or if {@code valueFunction} produces {@code null}
1289    *     for any key
1290    * @since 14.0
1291    */
1292   public static <K, V> ImmutableMap<K, V> toMap(
1293       Iterator<K> keys, Function<? super K, V> valueFunction) {
1294     checkNotNull(valueFunction);
1295     // Using LHM instead of a builder so as not to fail on duplicate keys
1296     Map<K, V> builder = newLinkedHashMap();
1297     while (keys.hasNext()) {
1298       K key = keys.next();
1299       builder.put(key, valueFunction.apply(key));
1300     }
1301     return ImmutableMap.copyOf(builder);
1302   }
1303 
1304   /**
1305    * Returns a map with the given {@code values}, indexed by keys derived from
1306    * those values. In other words, each input value produces an entry in the map
1307    * whose key is the result of applying {@code keyFunction} to that value.
1308    * These entries appear in the same order as the input values. Example usage:
1309    * <pre>   {@code
1310    *
1311    *   Color red = new Color("red", 255, 0, 0);
1312    *   ...
1313    *   ImmutableSet<Color> allColors = ImmutableSet.of(red, green, blue);
1314    *
1315    *   Map<String, Color> colorForName =
1316    *       uniqueIndex(allColors, toStringFunction());
1317    *   assertThat(colorForName).containsEntry("red", red);}</pre>
1318    *
1319    * <p>If your index may associate multiple values with each key, use {@link
1320    * Multimaps#index(Iterable, Function) Multimaps.index}.
1321    *
1322    * @param values the values to use when constructing the {@code Map}
1323    * @param keyFunction the function used to produce the key for each value
1324    * @return a map mapping the result of evaluating the function {@code
1325    *         keyFunction} on each value in the input collection to that value
1326    * @throws IllegalArgumentException if {@code keyFunction} produces the same
1327    *         key for more than one value in the input collection
1328    * @throws NullPointerException if any element of {@code values} is {@code
1329    *         null}, or if {@code keyFunction} produces {@code null} for any value
1330    */
1331   @CanIgnoreReturnValue
1332   public static <K, V> ImmutableMap<K, V> uniqueIndex(
1333       Iterable<V> values, Function<? super V, K> keyFunction) {
1334     // TODO(lowasser): consider presizing the builder if values is a Collection
1335     return uniqueIndex(values.iterator(), keyFunction);
1336   }
1337 
1338   /**
1339    * Returns a map with the given {@code values}, indexed by keys derived from
1340    * those values. In other words, each input value produces an entry in the map
1341    * whose key is the result of applying {@code keyFunction} to that value.
1342    * These entries appear in the same order as the input values. Example usage:
1343    * <pre>   {@code
1344    *
1345    *   Color red = new Color("red", 255, 0, 0);
1346    *   ...
1347    *   Iterator<Color> allColors = ImmutableSet.of(red, green, blue).iterator();
1348    *
1349    *   Map<String, Color> colorForName =
1350    *       uniqueIndex(allColors, toStringFunction());
1351    *   assertThat(colorForName).containsEntry("red", red);}</pre>
1352    *
1353    * <p>If your index may associate multiple values with each key, use {@link
1354    * Multimaps#index(Iterator, Function) Multimaps.index}.
1355    *
1356    * @param values the values to use when constructing the {@code Map}
1357    * @param keyFunction the function used to produce the key for each value
1358    * @return a map mapping the result of evaluating the function {@code
1359    *         keyFunction} on each value in the input collection to that value
1360    * @throws IllegalArgumentException if {@code keyFunction} produces the same
1361    *         key for more than one value in the input collection
1362    * @throws NullPointerException if any element of {@code values} is {@code
1363    *         null}, or if {@code keyFunction} produces {@code null} for any value
1364    * @since 10.0
1365    */
1366   @CanIgnoreReturnValue
1367   public static <K, V> ImmutableMap<K, V> uniqueIndex(
1368       Iterator<V> values, Function<? super V, K> keyFunction) {
1369     checkNotNull(keyFunction);
1370     ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
1371     while (values.hasNext()) {
1372       V value = values.next();
1373       builder.put(keyFunction.apply(value), value);
1374     }
1375     try {
1376       return builder.build();
1377     } catch (IllegalArgumentException duplicateKeys) {
1378       throw new IllegalArgumentException(
1379           duplicateKeys.getMessage()
1380               + ". To index multiple values under a key, use Multimaps.index.");
1381     }
1382   }
1383 
1384   /**
1385    * Creates an {@code ImmutableMap<String, String>} from a {@code Properties}
1386    * instance. Properties normally derive from {@code Map<Object, Object>}, but
1387    * they typically contain strings, which is awkward. This method lets you get
1388    * a plain-old-{@code Map} out of a {@code Properties}.
1389    *
1390    * @param properties a {@code Properties} object to be converted
1391    * @return an immutable map containing all the entries in {@code properties}
1392    * @throws ClassCastException if any key in {@code Properties} is not a {@code
1393    *         String}
1394    * @throws NullPointerException if any key or value in {@code Properties} is
1395    *         null
1396    */
1397   @GwtIncompatible // java.util.Properties
1398   public static ImmutableMap<String, String> fromProperties(Properties properties) {
1399     ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
1400 
1401     for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements(); ) {
1402       String key = (String) e.nextElement();
1403       builder.put(key, properties.getProperty(key));
1404     }
1405 
1406     return builder.build();
1407   }
1408 
1409   /**
1410    * Returns an immutable map entry with the specified key and value. The {@link
1411    * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
1412    *
1413    * <p>The returned entry is serializable.
1414    *
1415    * @param key the key to be associated with the returned entry
1416    * @param value the value to be associated with the returned entry
1417    */
1418   @GwtCompatible(serializable = true)
1419   public static <K, V> Entry<K, V> immutableEntry(@Nullable K key, @Nullable V value) {
1420     return new ImmutableEntry<>(key, value);
1421   }
1422 
1423   /**
1424    * Returns an unmodifiable view of the specified set of entries. The {@link
1425    * Entry#setValue} operation throws an {@link UnsupportedOperationException},
1426    * as do any operations that would modify the returned set.
1427    *
1428    * @param entrySet the entries for which to return an unmodifiable view
1429    * @return an unmodifiable view of the entries
1430    */
1431   static <K, V> Set<Entry<K, V>> unmodifiableEntrySet(Set<Entry<K, V>> entrySet) {
1432     return new UnmodifiableEntrySet<>(Collections.unmodifiableSet(entrySet));
1433   }
1434 
1435   /**
1436    * Returns an unmodifiable view of the specified map entry. The {@link
1437    * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
1438    * This also has the side-effect of redefining {@code equals} to comply with
1439    * the Entry contract, to avoid a possible nefarious implementation of equals.
1440    *
1441    * @param entry the entry for which to return an unmodifiable view
1442    * @return an unmodifiable view of the entry
1443    */
1444   static <K, V> Entry<K, V> unmodifiableEntry(final Entry<? extends K, ? extends V> entry) {
1445     checkNotNull(entry);
1446     return new AbstractMapEntry<K, V>() {
1447       @Override
1448       public K getKey() {
1449         return entry.getKey();
1450       }
1451 
1452       @Override
1453       public V getValue() {
1454         return entry.getValue();
1455       }
1456     };
1457   }
1458 
1459   static <K, V> UnmodifiableIterator<Entry<K, V>> unmodifiableEntryIterator(
1460       final Iterator<Entry<K, V>> entryIterator) {
1461     return new UnmodifiableIterator<Entry<K, V>>() {
1462       @Override
1463       public boolean hasNext() {
1464         return entryIterator.hasNext();
1465       }
1466 
1467       @Override
1468       public Entry<K, V> next() {
1469         return unmodifiableEntry(entryIterator.next());
1470       }
1471     };
1472   }
1473 
1474   /** @see Multimaps#unmodifiableEntries */
1475   static class UnmodifiableEntries<K, V> extends ForwardingCollection<Entry<K, V>> {
1476     private final Collection<Entry<K, V>> entries;
1477 
1478     UnmodifiableEntries(Collection<Entry<K, V>> entries) {
1479       this.entries = entries;
1480     }
1481 
1482     @Override
1483     protected Collection<Entry<K, V>> delegate() {
1484       return entries;
1485     }
1486 
1487     @Override
1488     public Iterator<Entry<K, V>> iterator() {
1489       return unmodifiableEntryIterator(entries.iterator());
1490     }
1491 
1492     // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
1493 
1494     @Override
1495     public Object[] toArray() {
1496       return standardToArray();
1497     }
1498 
1499     @Override
1500     public <T> T[] toArray(T[] array) {
1501       return standardToArray(array);
1502     }
1503   }
1504 
1505   /** @see Maps#unmodifiableEntrySet(Set) */
1506   static class UnmodifiableEntrySet<K, V> extends UnmodifiableEntries<K, V>
1507       implements Set<Entry<K, V>> {
1508     UnmodifiableEntrySet(Set<Entry<K, V>> entries) {
1509       super(entries);
1510     }
1511 
1512     // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
1513 
1514     @Override
1515     public boolean equals(@Nullable Object object) {
1516       return Sets.equalsImpl(this, object);
1517     }
1518 
1519     @Override
1520     public int hashCode() {
1521       return Sets.hashCodeImpl(this);
1522     }
1523   }
1524 
1525   /**
1526    * Returns a {@link Converter} that converts values using {@link BiMap#get bimap.get()},
1527    * and whose inverse view converts values using
1528    * {@link BiMap#inverse bimap.inverse()}{@code .get()}.
1529    *
1530    * <p>To use a plain {@link Map} as a {@link Function}, see
1531    * {@link com.google.common.base.Functions#forMap(Map)} or
1532    * {@link com.google.common.base.Functions#forMap(Map, Object)}.
1533    *
1534    * @since 16.0
1535    */
1536   @Beta
1537   public static <A, B> Converter<A, B> asConverter(final BiMap<A, B> bimap) {
1538     return new BiMapConverter<>(bimap);
1539   }
1540 
1541   private static final class BiMapConverter<A, B> extends Converter<A, B> implements Serializable {
1542     private final BiMap<A, B> bimap;
1543 
1544     BiMapConverter(BiMap<A, B> bimap) {
1545       this.bimap = checkNotNull(bimap);
1546     }
1547 
1548     @Override
1549     protected B doForward(A a) {
1550       return convert(bimap, a);
1551     }
1552 
1553     @Override
1554     protected A doBackward(B b) {
1555       return convert(bimap.inverse(), b);
1556     }
1557 
1558     private static <X, Y> Y convert(BiMap<X, Y> bimap, X input) {
1559       Y output = bimap.get(input);
1560       checkArgument(output != null, "No non-null mapping present for input: %s", input);
1561       return output;
1562     }
1563 
1564     @Override
1565     public boolean equals(@Nullable Object object) {
1566       if (object instanceof BiMapConverter) {
1567         BiMapConverter<?, ?> that = (BiMapConverter<?, ?>) object;
1568         return this.bimap.equals(that.bimap);
1569       }
1570       return false;
1571     }
1572 
1573     @Override
1574     public int hashCode() {
1575       return bimap.hashCode();
1576     }
1577 
1578     // There's really no good way to implement toString() without printing the entire BiMap, right?
1579     @Override
1580     public String toString() {
1581       return "Maps.asConverter(" + bimap + ")";
1582     }
1583 
1584     private static final long serialVersionUID = 0L;
1585   }
1586 
1587   /**
1588    * Returns a synchronized (thread-safe) bimap backed by the specified bimap.
1589    * In order to guarantee serial access, it is critical that <b>all</b> access
1590    * to the backing bimap is accomplished through the returned bimap.
1591    *
1592    * <p>It is imperative that the user manually synchronize on the returned map
1593    * when accessing any of its collection views: <pre>   {@code
1594    *
1595    *   BiMap<Long, String> map = Maps.synchronizedBiMap(
1596    *       HashBiMap.<Long, String>create());
1597    *   ...
1598    *   Set<Long> set = map.keySet();  // Needn't be in synchronized block
1599    *   ...
1600    *   synchronized (map) {  // Synchronizing on map, not set!
1601    *     Iterator<Long> it = set.iterator(); // Must be in synchronized block
1602    *     while (it.hasNext()) {
1603    *       foo(it.next());
1604    *     }
1605    *   }}</pre>
1606    *
1607    * <p>Failure to follow this advice may result in non-deterministic behavior.
1608    *
1609    * <p>The returned bimap will be serializable if the specified bimap is
1610    * serializable.
1611    *
1612    * @param bimap the bimap to be wrapped in a synchronized view
1613    * @return a synchronized view of the specified bimap
1614    */
1615   public static <K, V> BiMap<K, V> synchronizedBiMap(BiMap<K, V> bimap) {
1616     return Synchronized.biMap(bimap, null);
1617   }
1618 
1619   /**
1620    * Returns an unmodifiable view of the specified bimap. This method allows
1621    * modules to provide users with "read-only" access to internal bimaps. Query
1622    * operations on the returned bimap "read through" to the specified bimap, and
1623    * attempts to modify the returned map, whether direct or via its collection
1624    * views, result in an {@code UnsupportedOperationException}.
1625    *
1626    * <p>The returned bimap will be serializable if the specified bimap is
1627    * serializable.
1628    *
1629    * @param bimap the bimap for which an unmodifiable view is to be returned
1630    * @return an unmodifiable view of the specified bimap
1631    */
1632   public static <K, V> BiMap<K, V> unmodifiableBiMap(BiMap<? extends K, ? extends V> bimap) {
1633     return new UnmodifiableBiMap<>(bimap, null);
1634   }
1635 
1636   /** @see Maps#unmodifiableBiMap(BiMap) */
1637   private static class UnmodifiableBiMap<K, V> extends ForwardingMap<K, V>
1638       implements BiMap<K, V>, Serializable {
1639     final Map<K, V> unmodifiableMap;
1640     final BiMap<? extends K, ? extends V> delegate;
1641     @RetainedWith
1642     BiMap<V, K> inverse;
1643     transient Set<V> values;
1644 
1645     UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate, @Nullable BiMap<V, K> inverse) {
1646       unmodifiableMap = Collections.unmodifiableMap(delegate);
1647       this.delegate = delegate;
1648       this.inverse = inverse;
1649     }
1650 
1651     @Override
1652     protected Map<K, V> delegate() {
1653       return unmodifiableMap;
1654     }
1655 
1656     @Override
1657     public V forcePut(K key, V value) {
1658       throw new UnsupportedOperationException();
1659     }
1660 
1661     @Override
1662     public BiMap<V, K> inverse() {
1663       BiMap<V, K> result = inverse;
1664       return (result == null)
1665           ? inverse = new UnmodifiableBiMap<>(delegate.inverse(), this)
1666           : result;
1667     }
1668 
1669     @Override
1670     public Set<V> values() {
1671       Set<V> result = values;
1672       return (result == null) ? values = Collections.unmodifiableSet(delegate.values()) : result;
1673     }
1674 
1675     private static final long serialVersionUID = 0;
1676   }
1677 
1678   /**
1679    * Returns a view of a map where each value is transformed by a function. All
1680    * other properties of the map, such as iteration order, are left intact. For
1681    * example, the code: <pre>   {@code
1682    *
1683    *   Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
1684    *   Function<Integer, Double> sqrt =
1685    *       new Function<Integer, Double>() {
1686    *         public Double apply(Integer in) {
1687    *           return Math.sqrt((int) in);
1688    *         }
1689    *       };
1690    *   Map<String, Double> transformed = Maps.transformValues(map, sqrt);
1691    *   System.out.println(transformed);}</pre>
1692    *
1693    * ... prints {@code {a=2.0, b=3.0}}.
1694    *
1695    * <p>Changes in the underlying map are reflected in this view. Conversely,
1696    * this view supports removal operations, and these are reflected in the
1697    * underlying map.
1698    *
1699    * <p>It's acceptable for the underlying map to contain null keys, and even
1700    * null values provided that the function is capable of accepting null input.
1701    * The transformed map might contain null values, if the function sometimes
1702    * gives a null result.
1703    *
1704    * <p>The returned map is not thread-safe or serializable, even if the
1705    * underlying map is.
1706    *
1707    * <p>The function is applied lazily, invoked when needed. This is necessary
1708    * for the returned map to be a view, but it means that the function will be
1709    * applied many times for bulk operations like {@link Map#containsValue} and
1710    * {@code Map.toString()}. For this to perform well, {@code function} should
1711    * be fast. To avoid lazy evaluation when the returned map doesn't need to be
1712    * a view, copy the returned map into a new map of your choosing.
1713    */
1714   public static <K, V1, V2> Map<K, V2> transformValues(
1715       Map<K, V1> fromMap, Function<? super V1, V2> function) {
1716     return transformEntries(fromMap, asEntryTransformer(function));
1717   }
1718 
1719   /**
1720    * Returns a view of a sorted map where each value is transformed by a
1721    * function. All other properties of the map, such as iteration order, are
1722    * left intact. For example, the code: <pre>   {@code
1723    *
1724    *   SortedMap<String, Integer> map = ImmutableSortedMap.of("a", 4, "b", 9);
1725    *   Function<Integer, Double> sqrt =
1726    *       new Function<Integer, Double>() {
1727    *         public Double apply(Integer in) {
1728    *           return Math.sqrt((int) in);
1729    *         }
1730    *       };
1731    *   SortedMap<String, Double> transformed =
1732    *        Maps.transformValues(map, sqrt);
1733    *   System.out.println(transformed);}</pre>
1734    *
1735    * ... prints {@code {a=2.0, b=3.0}}.
1736    *
1737    * <p>Changes in the underlying map are reflected in this view. Conversely,
1738    * this view supports removal operations, and these are reflected in the
1739    * underlying map.
1740    *
1741    * <p>It's acceptable for the underlying map to contain null keys, and even
1742    * null values provided that the function is capable of accepting null input.
1743    * The transformed map might contain null values, if the function sometimes
1744    * gives a null result.
1745    *
1746    * <p>The returned map is not thread-safe or serializable, even if the
1747    * underlying map is.
1748    *
1749    * <p>The function is applied lazily, invoked when needed. This is necessary
1750    * for the returned map to be a view, but it means that the function will be
1751    * applied many times for bulk operations like {@link Map#containsValue} and
1752    * {@code Map.toString()}. For this to perform well, {@code function} should
1753    * be fast. To avoid lazy evaluation when the returned map doesn't need to be
1754    * a view, copy the returned map into a new map of your choosing.
1755    *
1756    * @since 11.0
1757    */
1758   public static <K, V1, V2> SortedMap<K, V2> transformValues(
1759       SortedMap<K, V1> fromMap, Function<? super V1, V2> function) {
1760     return transformEntries(fromMap, asEntryTransformer(function));
1761   }
1762 
1763   /**
1764    * Returns a view of a navigable map where each value is transformed by a
1765    * function. All other properties of the map, such as iteration order, are
1766    * left intact.  For example, the code: <pre>   {@code
1767    *
1768    *   NavigableMap<String, Integer> map = Maps.newTreeMap();
1769    *   map.put("a", 4);
1770    *   map.put("b", 9);
1771    *   Function<Integer, Double> sqrt =
1772    *       new Function<Integer, Double>() {
1773    *         public Double apply(Integer in) {
1774    *           return Math.sqrt((int) in);
1775    *         }
1776    *       };
1777    *   NavigableMap<String, Double> transformed =
1778    *        Maps.transformNavigableValues(map, sqrt);
1779    *   System.out.println(transformed);}</pre>
1780    *
1781    * ... prints {@code {a=2.0, b=3.0}}.
1782    *
1783    * Changes in the underlying map are reflected in this view.
1784    * Conversely, this view supports removal operations, and these are reflected
1785    * in the underlying map.
1786    *
1787    * <p>It's acceptable for the underlying map to contain null keys, and even
1788    * null values provided that the function is capable of accepting null input.
1789    * The transformed map might contain null values, if the function sometimes
1790    * gives a null result.
1791    *
1792    * <p>The returned map is not thread-safe or serializable, even if the
1793    * underlying map is.
1794    *
1795    * <p>The function is applied lazily, invoked when needed. This is necessary
1796    * for the returned map to be a view, but it means that the function will be
1797    * applied many times for bulk operations like {@link Map#containsValue} and
1798    * {@code Map.toString()}. For this to perform well, {@code function} should
1799    * be fast. To avoid lazy evaluation when the returned map doesn't need to be
1800    * a view, copy the returned map into a new map of your choosing.
1801    *
1802    * @since 13.0
1803    */
1804   @GwtIncompatible // NavigableMap
1805   public static <K, V1, V2> NavigableMap<K, V2> transformValues(
1806       NavigableMap<K, V1> fromMap, Function<? super V1, V2> function) {
1807     return transformEntries(fromMap, asEntryTransformer(function));
1808   }
1809 
1810   /**
1811    * Returns a view of a map whose values are derived from the original map's
1812    * entries. In contrast to {@link #transformValues}, this method's
1813    * entry-transformation logic may depend on the key as well as the value.
1814    *
1815    * <p>All other properties of the transformed map, such as iteration order,
1816    * are left intact. For example, the code: <pre>   {@code
1817    *
1818    *   Map<String, Boolean> options =
1819    *       ImmutableMap.of("verbose", true, "sort", false);
1820    *   EntryTransformer<String, Boolean, String> flagPrefixer =
1821    *       new EntryTransformer<String, Boolean, String>() {
1822    *         public String transformEntry(String key, Boolean value) {
1823    *           return value ? key : "no" + key;
1824    *         }
1825    *       };
1826    *   Map<String, String> transformed =
1827    *       Maps.transformEntries(options, flagPrefixer);
1828    *   System.out.println(transformed);}</pre>
1829    *
1830    * ... prints {@code {verbose=verbose, sort=nosort}}.
1831    *
1832    * <p>Changes in the underlying map are reflected in this view. Conversely,
1833    * this view supports removal operations, and these are reflected in the
1834    * underlying map.
1835    *
1836    * <p>It's acceptable for the underlying map to contain null keys and null
1837    * values provided that the transformer is capable of accepting null inputs.
1838    * The transformed map might contain null values if the transformer sometimes
1839    * gives a null result.
1840    *
1841    * <p>The returned map is not thread-safe or serializable, even if the
1842    * underlying map is.
1843    *
1844    * <p>The transformer is applied lazily, invoked when needed. This is
1845    * necessary for the returned map to be a view, but it means that the
1846    * transformer will be applied many times for bulk operations like {@link
1847    * Map#containsValue} and {@link Object#toString}. For this to perform well,
1848    * {@code transformer} should be fast. To avoid lazy evaluation when the
1849    * returned map doesn't need to be a view, copy the returned map into a new
1850    * map of your choosing.
1851    *
1852    * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1853    * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1854    * that {@code k2} is also of type {@code K}. Using an {@code
1855    * EntryTransformer} key type for which this may not hold, such as {@code
1856    * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1857    * the transformed map.
1858    *
1859    * @since 7.0
1860    */
1861   public static <K, V1, V2> Map<K, V2> transformEntries(
1862       Map<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1863     return new TransformedEntriesMap<>(fromMap, transformer);
1864   }
1865 
1866   /**
1867    * Returns a view of a sorted map whose values are derived from the original
1868    * sorted map's entries. In contrast to {@link #transformValues}, this
1869    * method's entry-transformation logic may depend on the key as well as the
1870    * value.
1871    *
1872    * <p>All other properties of the transformed map, such as iteration order,
1873    * are left intact. For example, the code: <pre>   {@code
1874    *
1875    *   Map<String, Boolean> options =
1876    *       ImmutableSortedMap.of("verbose", true, "sort", false);
1877    *   EntryTransformer<String, Boolean, String> flagPrefixer =
1878    *       new EntryTransformer<String, Boolean, String>() {
1879    *         public String transformEntry(String key, Boolean value) {
1880    *           return value ? key : "yes" + key;
1881    *         }
1882    *       };
1883    *   SortedMap<String, String> transformed =
1884    *       Maps.transformEntries(options, flagPrefixer);
1885    *   System.out.println(transformed);}</pre>
1886    *
1887    * ... prints {@code {sort=yessort, verbose=verbose}}.
1888    *
1889    * <p>Changes in the underlying map are reflected in this view. Conversely,
1890    * this view supports removal operations, and these are reflected in the
1891    * underlying map.
1892    *
1893    * <p>It's acceptable for the underlying map to contain null keys and null
1894    * values provided that the transformer is capable of accepting null inputs.
1895    * The transformed map might contain null values if the transformer sometimes
1896    * gives a null result.
1897    *
1898    * <p>The returned map is not thread-safe or serializable, even if the
1899    * underlying map is.
1900    *
1901    * <p>The transformer is applied lazily, invoked when needed. This is
1902    * necessary for the returned map to be a view, but it means that the
1903    * transformer will be applied many times for bulk operations like {@link
1904    * Map#containsValue} and {@link Object#toString}. For this to perform well,
1905    * {@code transformer} should be fast. To avoid lazy evaluation when the
1906    * returned map doesn't need to be a view, copy the returned map into a new
1907    * map of your choosing.
1908    *
1909    * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1910    * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1911    * that {@code k2} is also of type {@code K}. Using an {@code
1912    * EntryTransformer} key type for which this may not hold, such as {@code
1913    * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1914    * the transformed map.
1915    *
1916    * @since 11.0
1917    */
1918   public static <K, V1, V2> SortedMap<K, V2> transformEntries(
1919       SortedMap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1920     return new TransformedEntriesSortedMap<>(fromMap, transformer);
1921   }
1922 
1923   /**
1924    * Returns a view of a navigable map whose values are derived from the
1925    * original navigable map's entries. In contrast to {@link
1926    * #transformValues}, this method's entry-transformation logic may
1927    * depend on the key as well as the value.
1928    *
1929    * <p>All other properties of the transformed map, such as iteration order,
1930    * are left intact. For example, the code: <pre>   {@code
1931    *
1932    *   NavigableMap<String, Boolean> options = Maps.newTreeMap();
1933    *   options.put("verbose", false);
1934    *   options.put("sort", true);
1935    *   EntryTransformer<String, Boolean, String> flagPrefixer =
1936    *       new EntryTransformer<String, Boolean, String>() {
1937    *         public String transformEntry(String key, Boolean value) {
1938    *           return value ? key : ("yes" + key);
1939    *         }
1940    *       };
1941    *   NavigableMap<String, String> transformed =
1942    *       LabsMaps.transformNavigableEntries(options, flagPrefixer);
1943    *   System.out.println(transformed);}</pre>
1944    *
1945    * ... prints {@code {sort=yessort, verbose=verbose}}.
1946    *
1947    * <p>Changes in the underlying map are reflected in this view.
1948    * Conversely, this view supports removal operations, and these are reflected
1949    * in the underlying map.
1950    *
1951    * <p>It's acceptable for the underlying map to contain null keys and null
1952    * values provided that the transformer is capable of accepting null inputs.
1953    * The transformed map might contain null values if the transformer sometimes
1954    * gives a null result.
1955    *
1956    * <p>The returned map is not thread-safe or serializable, even if the
1957    * underlying map is.
1958    *
1959    * <p>The transformer is applied lazily, invoked when needed. This is
1960    * necessary for the returned map to be a view, but it means that the
1961    * transformer will be applied many times for bulk operations like {@link
1962    * Map#containsValue} and {@link Object#toString}. For this to perform well,
1963    * {@code transformer} should be fast. To avoid lazy evaluation when the
1964    * returned map doesn't need to be a view, copy the returned map into a new
1965    * map of your choosing.
1966    *
1967    * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1968    * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1969    * that {@code k2} is also of type {@code K}. Using an {@code
1970    * EntryTransformer} key type for which this may not hold, such as {@code
1971    * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1972    * the transformed map.
1973    *
1974    * @since 13.0
1975    */
1976   @GwtIncompatible // NavigableMap
1977   public static <K, V1, V2> NavigableMap<K, V2> transformEntries(
1978       final NavigableMap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1979     return new TransformedEntriesNavigableMap<>(fromMap, transformer);
1980   }
1981 
1982   /**
1983    * A transformation of the value of a key-value pair, using both key and value
1984    * as inputs. To apply the transformation to a map, use
1985    * {@link Maps#transformEntries(Map, EntryTransformer)}.
1986    *
1987    * @param <K> the key type of the input and output entries
1988    * @param <V1> the value type of the input entry
1989    * @param <V2> the value type of the output entry
1990    * @since 7.0
1991    */
1992   @FunctionalInterface
1993   public interface EntryTransformer<K, V1, V2> {
1994     /**
1995      * Determines an output value based on a key-value pair. This method is
1996      * <i>generally expected</i>, but not absolutely required, to have the
1997      * following properties:
1998      *
1999      * <ul>
2000      * <li>Its execution does not cause any observable side effects.
2001      * <li>The computation is <i>consistent with equals</i>; that is,
2002      *     {@link Objects#equal Objects.equal}{@code (k1, k2) &&}
2003      *     {@link Objects#equal}{@code (v1, v2)} implies that {@code
2004      *     Objects.equal(transformer.transform(k1, v1),
2005      *     transformer.transform(k2, v2))}.
2006      * </ul>
2007      *
2008      * @throws NullPointerException if the key or value is null and this
2009      *     transformer does not accept null arguments
2010      */
2011     V2 transformEntry(@Nullable K key, @Nullable V1 value);
2012   }
2013 
2014   /**
2015    * Views a function as an entry transformer that ignores the entry key.
2016    */
2017   static <K, V1, V2> EntryTransformer<K, V1, V2> asEntryTransformer(
2018       final Function<? super V1, V2> function) {
2019     checkNotNull(function);
2020     return new EntryTransformer<K, V1, V2>() {
2021       @Override
2022       public V2 transformEntry(K key, V1 value) {
2023         return function.apply(value);
2024       }
2025     };
2026   }
2027 
2028   static <K, V1, V2> Function<V1, V2> asValueToValueFunction(
2029       final EntryTransformer<? super K, V1, V2> transformer, final K key) {
2030     checkNotNull(transformer);
2031     return new Function<V1, V2>() {
2032       @Override
2033       public V2 apply(@Nullable V1 v1) {
2034         return transformer.transformEntry(key, v1);
2035       }
2036     };
2037   }
2038 
2039   /**
2040    * Views an entry transformer as a function from {@code Entry} to values.
2041    */
2042   static <K, V1, V2> Function<Entry<K, V1>, V2> asEntryToValueFunction(
2043       final EntryTransformer<? super K, ? super V1, V2> transformer) {
2044     checkNotNull(transformer);
2045     return new Function<Entry<K, V1>, V2>() {
2046       @Override
2047       public V2 apply(Entry<K, V1> entry) {
2048         return transformer.transformEntry(entry.getKey(), entry.getValue());
2049       }
2050     };
2051   }
2052 
2053   /**
2054    * Returns a view of an entry transformed by the specified transformer.
2055    */
2056   static <V2, K, V1> Entry<K, V2> transformEntry(
2057       final EntryTransformer<? super K, ? super V1, V2> transformer, final Entry<K, V1> entry) {
2058     checkNotNull(transformer);
2059     checkNotNull(entry);
2060     return new AbstractMapEntry<K, V2>() {
2061       @Override
2062       public K getKey() {
2063         return entry.getKey();
2064       }
2065 
2066       @Override
2067       public V2 getValue() {
2068         return transformer.transformEntry(entry.getKey(), entry.getValue());
2069       }
2070     };
2071   }
2072 
2073   /**
2074    * Views an entry transformer as a function from entries to entries.
2075    */
2076   static <K, V1, V2> Function<Entry<K, V1>, Entry<K, V2>> asEntryToEntryFunction(
2077       final EntryTransformer<? super K, ? super V1, V2> transformer) {
2078     checkNotNull(transformer);
2079     return new Function<Entry<K, V1>, Entry<K, V2>>() {
2080       @Override
2081       public Entry<K, V2> apply(final Entry<K, V1> entry) {
2082         return transformEntry(transformer, entry);
2083       }
2084     };
2085   }
2086 
2087   static class TransformedEntriesMap<K, V1, V2> extends IteratorBasedAbstractMap<K, V2> {
2088     final Map<K, V1> fromMap;
2089     final EntryTransformer<? super K, ? super V1, V2> transformer;
2090 
2091     TransformedEntriesMap(
2092         Map<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
2093       this.fromMap = checkNotNull(fromMap);
2094       this.transformer = checkNotNull(transformer);
2095     }
2096 
2097     @Override
2098     public int size() {
2099       return fromMap.size();
2100     }
2101 
2102     @Override
2103     public boolean containsKey(Object key) {
2104       return fromMap.containsKey(key);
2105     }
2106 
2107     @Override
2108     @Nullable
2109     public V2 get(@Nullable Object key) {
2110       return getOrDefault(key, null);
2111     }
2112 
2113     // safe as long as the user followed the <b>Warning</b> in the javadoc
2114     @SuppressWarnings("unchecked")
2115     @Override
2116     @Nullable
2117     public V2 getOrDefault(@Nullable Object key, @Nullable V2 defaultValue) {
2118       V1 value = fromMap.get(key);
2119       return (value != null || fromMap.containsKey(key))
2120           ? transformer.transformEntry((K) key, value)
2121           : defaultValue;
2122     }
2123 
2124     // safe as long as the user followed the <b>Warning</b> in the javadoc
2125     @SuppressWarnings("unchecked")
2126     @Override
2127     public V2 remove(Object key) {
2128       return fromMap.containsKey(key)
2129           ? transformer.transformEntry((K) key, fromMap.remove(key))
2130           : null;
2131     }
2132 
2133     @Override
2134     public void clear() {
2135       fromMap.clear();
2136     }
2137 
2138     @Override
2139     public Set<K> keySet() {
2140       return fromMap.keySet();
2141     }
2142 
2143     @Override
2144     Iterator<Entry<K, V2>> entryIterator() {
2145       return Iterators.transform(
2146           fromMap.entrySet().iterator(), Maps.<K, V1, V2>asEntryToEntryFunction(transformer));
2147     }
2148 
2149     @Override
2150     Spliterator<Entry<K, V2>> entrySpliterator() {
2151       return CollectSpliterators.map(
2152           fromMap.entrySet().spliterator(), Maps.<K, V1, V2>asEntryToEntryFunction(transformer));
2153     }
2154 
2155     @Override
2156     public void forEach(BiConsumer<? super K, ? super V2> action) {
2157       checkNotNull(action);
2158       // avoids creating new Entry<K, V2> objects
2159       fromMap.forEach((k, v1) -> action.accept(k, transformer.transformEntry(k, v1)));
2160     }
2161 
2162     @Override
2163     public Collection<V2> values() {
2164       return new Values<>(this);
2165     }
2166   }
2167 
2168   static class TransformedEntriesSortedMap<K, V1, V2> extends TransformedEntriesMap<K, V1, V2>
2169       implements SortedMap<K, V2> {
2170 
2171     protected SortedMap<K, V1> fromMap() {
2172       return (SortedMap<K, V1>) fromMap;
2173     }
2174 
2175     TransformedEntriesSortedMap(
2176         SortedMap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
2177       super(fromMap, transformer);
2178     }
2179 
2180     @Override
2181     public Comparator<? super K> comparator() {
2182       return fromMap().comparator();
2183     }
2184 
2185     @Override
2186     public K firstKey() {
2187       return fromMap().firstKey();
2188     }
2189 
2190     @Override
2191     public SortedMap<K, V2> headMap(K toKey) {
2192       return transformEntries(fromMap().headMap(toKey), transformer);
2193     }
2194 
2195     @Override
2196     public K lastKey() {
2197       return fromMap().lastKey();
2198     }
2199 
2200     @Override
2201     public SortedMap<K, V2> subMap(K fromKey, K toKey) {
2202       return transformEntries(fromMap().subMap(fromKey, toKey), transformer);
2203     }
2204 
2205     @Override
2206     public SortedMap<K, V2> tailMap(K fromKey) {
2207       return transformEntries(fromMap().tailMap(fromKey), transformer);
2208     }
2209   }
2210 
2211   @GwtIncompatible // NavigableMap
2212   private static class TransformedEntriesNavigableMap<K, V1, V2>
2213       extends TransformedEntriesSortedMap<K, V1, V2> implements NavigableMap<K, V2> {
2214 
2215     TransformedEntriesNavigableMap(
2216         NavigableMap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
2217       super(fromMap, transformer);
2218     }
2219 
2220     @Override
2221     public Entry<K, V2> ceilingEntry(K key) {
2222       return transformEntry(fromMap().ceilingEntry(key));
2223     }
2224 
2225     @Override
2226     public K ceilingKey(K key) {
2227       return fromMap().ceilingKey(key);
2228     }
2229 
2230     @Override
2231     public NavigableSet<K> descendingKeySet() {
2232       return fromMap().descendingKeySet();
2233     }
2234 
2235     @Override
2236     public NavigableMap<K, V2> descendingMap() {
2237       return transformEntries(fromMap().descendingMap(), transformer);
2238     }
2239 
2240     @Override
2241     public Entry<K, V2> firstEntry() {
2242       return transformEntry(fromMap().firstEntry());
2243     }
2244 
2245     @Override
2246     public Entry<K, V2> floorEntry(K key) {
2247       return transformEntry(fromMap().floorEntry(key));
2248     }
2249 
2250     @Override
2251     public K floorKey(K key) {
2252       return fromMap().floorKey(key);
2253     }
2254 
2255     @Override
2256     public NavigableMap<K, V2> headMap(K toKey) {
2257       return headMap(toKey, false);
2258     }
2259 
2260     @Override
2261     public NavigableMap<K, V2> headMap(K toKey, boolean inclusive) {
2262       return transformEntries(fromMap().headMap(toKey, inclusive), transformer);
2263     }
2264 
2265     @Override
2266     public Entry<K, V2> higherEntry(K key) {
2267       return transformEntry(fromMap().higherEntry(key));
2268     }
2269 
2270     @Override
2271     public K higherKey(K key) {
2272       return fromMap().higherKey(key);
2273     }
2274 
2275     @Override
2276     public Entry<K, V2> lastEntry() {
2277       return transformEntry(fromMap().lastEntry());
2278     }
2279 
2280     @Override
2281     public Entry<K, V2> lowerEntry(K key) {
2282       return transformEntry(fromMap().lowerEntry(key));
2283     }
2284 
2285     @Override
2286     public K lowerKey(K key) {
2287       return fromMap().lowerKey(key);
2288     }
2289 
2290     @Override
2291     public NavigableSet<K> navigableKeySet() {
2292       return fromMap().navigableKeySet();
2293     }
2294 
2295     @Override
2296     public Entry<K, V2> pollFirstEntry() {
2297       return transformEntry(fromMap().pollFirstEntry());
2298     }
2299 
2300     @Override
2301     public Entry<K, V2> pollLastEntry() {
2302       return transformEntry(fromMap().pollLastEntry());
2303     }
2304 
2305     @Override
2306     public NavigableMap<K, V2> subMap(
2307         K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
2308       return transformEntries(
2309           fromMap().subMap(fromKey, fromInclusive, toKey, toInclusive), transformer);
2310     }
2311 
2312     @Override
2313     public NavigableMap<K, V2> subMap(K fromKey, K toKey) {
2314       return subMap(fromKey, true, toKey, false);
2315     }
2316 
2317     @Override
2318     public NavigableMap<K, V2> tailMap(K fromKey) {
2319       return tailMap(fromKey, true);
2320     }
2321 
2322     @Override
2323     public NavigableMap<K, V2> tailMap(K fromKey, boolean inclusive) {
2324       return transformEntries(fromMap().tailMap(fromKey, inclusive), transformer);
2325     }
2326 
2327     @Nullable
2328     private Entry<K, V2> transformEntry(@Nullable Entry<K, V1> entry) {
2329       return (entry == null) ? null : Maps.transformEntry(transformer, entry);
2330     }
2331 
2332     @Override
2333     protected NavigableMap<K, V1> fromMap() {
2334       return (NavigableMap<K, V1>) super.fromMap();
2335     }
2336   }
2337 
2338   static <K> Predicate<Entry<K, ?>> keyPredicateOnEntries(Predicate<? super K> keyPredicate) {
2339     return compose(keyPredicate, Maps.<K>keyFunction());
2340   }
2341 
2342   static <V> Predicate<Entry<?, V>> valuePredicateOnEntries(Predicate<? super V> valuePredicate) {
2343     return compose(valuePredicate, Maps.<V>valueFunction());
2344   }
2345 
2346   /**
2347    * Returns a map containing the mappings in {@code unfiltered} whose keys
2348    * satisfy a predicate. The returned map is a live view of {@code unfiltered};
2349    * changes to one affect the other.
2350    *
2351    * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
2352    * values()} views have iterators that don't support {@code remove()}, but all
2353    * other methods are supported by the map and its views. When given a key that
2354    * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
2355    * methods throw an {@link IllegalArgumentException}.
2356    *
2357    * <p>When methods such as {@code removeAll()} and {@code clear()} are called
2358    * on the filtered map or its views, only mappings whose keys satisfy the
2359    * filter will be removed from the underlying map.
2360    *
2361    * <p>The returned map isn't threadsafe or serializable, even if {@code
2362    * unfiltered} is.
2363    *
2364    * <p>Many of the filtered map's methods, such as {@code size()},
2365    * iterate across every key/value mapping in the underlying map and determine
2366    * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2367    * faster to copy the filtered map and use the copy.
2368    *
2369    * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
2370    * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
2371    * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
2372    * inconsistent with equals.
2373    */
2374   public static <K, V> Map<K, V> filterKeys(
2375       Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2376     checkNotNull(keyPredicate);
2377     Predicate<Entry<K, ?>> entryPredicate = keyPredicateOnEntries(keyPredicate);
2378     return (unfiltered instanceof AbstractFilteredMap)
2379         ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
2380         : new FilteredKeyMap<K, V>(checkNotNull(unfiltered), keyPredicate, entryPredicate);
2381   }
2382 
2383   /**
2384    * Returns a sorted map containing the mappings in {@code unfiltered} whose
2385    * keys satisfy a predicate. The returned map is a live view of {@code
2386    * unfiltered}; changes to one affect the other.
2387    *
2388    * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
2389    * values()} views have iterators that don't support {@code remove()}, but all
2390    * other methods are supported by the map and its views. When given a key that
2391    * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
2392    * methods throw an {@link IllegalArgumentException}.
2393    *
2394    * <p>When methods such as {@code removeAll()} and {@code clear()} are called
2395    * on the filtered map or its views, only mappings whose keys satisfy the
2396    * filter will be removed from the underlying map.
2397    *
2398    * <p>The returned map isn't threadsafe or serializable, even if {@code
2399    * unfiltered} is.
2400    *
2401    * <p>Many of the filtered map's methods, such as {@code size()},
2402    * iterate across every key/value mapping in the underlying map and determine
2403    * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2404    * faster to copy the filtered map and use the copy.
2405    *
2406    * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
2407    * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
2408    * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
2409    * inconsistent with equals.
2410    *
2411    * @since 11.0
2412    */
2413   public static <K, V> SortedMap<K, V> filterKeys(
2414       SortedMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2415     // TODO(lowasser): Return a subclass of Maps.FilteredKeyMap for slightly better
2416     // performance.
2417     return filterEntries(unfiltered, Maps.<K>keyPredicateOnEntries(keyPredicate));
2418   }
2419 
2420   /**
2421    * Returns a navigable map containing the mappings in {@code unfiltered} whose
2422    * keys satisfy a predicate. The returned map is a live view of {@code
2423    * unfiltered}; changes to one affect the other.
2424    *
2425    * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
2426    * values()} views have iterators that don't support {@code remove()}, but all
2427    * other methods are supported by the map and its views. When given a key that
2428    * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
2429    * methods throw an {@link IllegalArgumentException}.
2430    *
2431    * <p>When methods such as {@code removeAll()} and {@code clear()} are called
2432    * on the filtered map or its views, only mappings whose keys satisfy the
2433    * filter will be removed from the underlying map.
2434    *
2435    * <p>The returned map isn't threadsafe or serializable, even if {@code
2436    * unfiltered} is.
2437    *
2438    * <p>Many of the filtered map's methods, such as {@code size()},
2439    * iterate across every key/value mapping in the underlying map and determine
2440    * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2441    * faster to copy the filtered map and use the copy.
2442    *
2443    * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
2444    * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
2445    * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
2446    * inconsistent with equals.
2447    *
2448    * @since 14.0
2449    */
2450   @GwtIncompatible // NavigableMap
2451   public static <K, V> NavigableMap<K, V> filterKeys(
2452       NavigableMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2453     // TODO(lowasser): Return a subclass of Maps.FilteredKeyMap for slightly better
2454     // performance.
2455     return filterEntries(unfiltered, Maps.<K>keyPredicateOnEntries(keyPredicate));
2456   }
2457 
2458   /**
2459    * Returns a bimap containing the mappings in {@code unfiltered} whose keys satisfy a predicate.
2460    * The returned bimap is a live view of {@code unfiltered}; changes to one affect the other.
2461    *
2462    * <p>The resulting bimap's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2463    * iterators that don't support {@code remove()}, but all other methods are supported by the
2464    * bimap and its views. When given a key that doesn't satisfy the predicate, the bimap's {@code
2465    * put()}, {@code forcePut()} and {@code putAll()} methods throw an {@link
2466    * IllegalArgumentException}.
2467    *
2468    * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2469    * bimap or its views, only mappings that satisfy the filter will be removed from the underlying
2470    * bimap.
2471    *
2472    * <p>The returned bimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2473    *
2474    * <p>Many of the filtered bimap's methods, such as {@code size()}, iterate across every key in
2475    * the underlying bimap and determine which satisfy the filter. When a live view is <i>not</i>
2476    * needed, it may be faster to copy the filtered bimap and use the copy.
2477    *
2478    * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals </i>, as
2479    * documented at {@link Predicate#apply}.
2480    *
2481    * @since 14.0
2482    */
2483   public static <K, V> BiMap<K, V> filterKeys(
2484       BiMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2485     checkNotNull(keyPredicate);
2486     return filterEntries(unfiltered, Maps.<K>keyPredicateOnEntries(keyPredicate));
2487   }
2488 
2489   /**
2490    * Returns a map containing the mappings in {@code unfiltered} whose values
2491    * satisfy a predicate. The returned map is a live view of {@code unfiltered};
2492    * changes to one affect the other.
2493    *
2494    * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
2495    * values()} views have iterators that don't support {@code remove()}, but all
2496    * other methods are supported by the map and its views. When given a value
2497    * that doesn't satisfy the predicate, the map's {@code put()}, {@code
2498    * putAll()}, and {@link Entry#setValue} methods throw an {@link
2499    * IllegalArgumentException}.
2500    *
2501    * <p>When methods such as {@code removeAll()} and {@code clear()} are called
2502    * on the filtered map or its views, only mappings whose values satisfy the
2503    * filter will be removed from the underlying map.
2504    *
2505    * <p>The returned map isn't threadsafe or serializable, even if {@code
2506    * unfiltered} is.
2507    *
2508    * <p>Many of the filtered map's methods, such as {@code size()},
2509    * iterate across every key/value mapping in the underlying map and determine
2510    * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2511    * faster to copy the filtered map and use the copy.
2512    *
2513    * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
2514    * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
2515    * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
2516    * inconsistent with equals.
2517    */
2518   public static <K, V> Map<K, V> filterValues(
2519       Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2520     return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2521   }
2522 
2523   /**
2524    * Returns a sorted map containing the mappings in {@code unfiltered} whose
2525    * values satisfy a predicate. The returned map is a live view of {@code
2526    * unfiltered}; changes to one affect the other.
2527    *
2528    * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
2529    * values()} views have iterators that don't support {@code remove()}, but all
2530    * other methods are supported by the map and its views. When given a value
2531    * that doesn't satisfy the predicate, the map's {@code put()}, {@code
2532    * putAll()}, and {@link Entry#setValue} methods throw an {@link
2533    * IllegalArgumentException}.
2534    *
2535    * <p>When methods such as {@code removeAll()} and {@code clear()} are called
2536    * on the filtered map or its views, only mappings whose values satisfy the
2537    * filter will be removed from the underlying map.
2538    *
2539    * <p>The returned map isn't threadsafe or serializable, even if {@code
2540    * unfiltered} is.
2541    *
2542    * <p>Many of the filtered map's methods, such as {@code size()},
2543    * iterate across every key/value mapping in the underlying map and determine
2544    * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2545    * faster to copy the filtered map and use the copy.
2546    *
2547    * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
2548    * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
2549    * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
2550    * inconsistent with equals.
2551    *
2552    * @since 11.0
2553    */
2554   public static <K, V> SortedMap<K, V> filterValues(
2555       SortedMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2556     return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2557   }
2558 
2559   /**
2560    * Returns a navigable map containing the mappings in {@code unfiltered} whose
2561    * values satisfy a predicate. The returned map is a live view of {@code
2562    * unfiltered}; changes to one affect the other.
2563    *
2564    * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
2565    * values()} views have iterators that don't support {@code remove()}, but all
2566    * other methods are supported by the map and its views. When given a value
2567    * that doesn't satisfy the predicate, the map's {@code put()}, {@code
2568    * putAll()}, and {@link Entry#setValue} methods throw an {@link
2569    * IllegalArgumentException}.
2570    *
2571    * <p>When methods such as {@code removeAll()} and {@code clear()} are called
2572    * on the filtered map or its views, only mappings whose values satisfy the
2573    * filter will be removed from the underlying map.
2574    *
2575    * <p>The returned map isn't threadsafe or serializable, even if {@code
2576    * unfiltered} is.
2577    *
2578    * <p>Many of the filtered map's methods, such as {@code size()},
2579    * iterate across every key/value mapping in the underlying map and determine
2580    * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2581    * faster to copy the filtered map and use the copy.
2582    *
2583    * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
2584    * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
2585    * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
2586    * inconsistent with equals.
2587    *
2588    * @since 14.0
2589    */
2590   @GwtIncompatible // NavigableMap
2591   public static <K, V> NavigableMap<K, V> filterValues(
2592       NavigableMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2593     return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2594   }
2595 
2596   /**
2597    * Returns a bimap containing the mappings in {@code unfiltered} whose values satisfy a
2598    * predicate. The returned bimap is a live view of {@code unfiltered}; changes to one affect the
2599    * other.
2600    *
2601    * <p>The resulting bimap's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2602    * iterators that don't support {@code remove()}, but all other methods are supported by the
2603    * bimap and its views. When given a value that doesn't satisfy the predicate, the bimap's
2604    * {@code put()}, {@code forcePut()} and {@code putAll()} methods throw an {@link
2605    * IllegalArgumentException}. Similarly, the map's entries have a {@link Entry#setValue} method
2606    * that throws an {@link IllegalArgumentException} when the provided value doesn't satisfy the
2607    * predicate.
2608    *
2609    * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2610    * bimap or its views, only mappings that satisfy the filter will be removed from the underlying
2611    * bimap.
2612    *
2613    * <p>The returned bimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2614    *
2615    * <p>Many of the filtered bimap's methods, such as {@code size()}, iterate across every value in
2616    * the underlying bimap and determine which satisfy the filter. When a live view is <i>not</i>
2617    * needed, it may be faster to copy the filtered bimap and use the copy.
2618    *
2619    * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals </i>, as
2620    * documented at {@link Predicate#apply}.
2621    *
2622    * @since 14.0
2623    */
2624   public static <K, V> BiMap<K, V> filterValues(
2625       BiMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2626     return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2627   }
2628 
2629   /**
2630    * Returns a map containing the mappings in {@code unfiltered} that satisfy a
2631    * predicate. The returned map is a live view of {@code unfiltered}; changes
2632    * to one affect the other.
2633    *
2634    * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
2635    * values()} views have iterators that don't support {@code remove()}, but all
2636    * other methods are supported by the map and its views. When given a
2637    * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
2638    * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
2639    * Similarly, the map's entries have a {@link Entry#setValue} method that
2640    * throws an {@link IllegalArgumentException} when the existing key and the
2641    * provided value don't satisfy the predicate.
2642    *
2643    * <p>When methods such as {@code removeAll()} and {@code clear()} are called
2644    * on the filtered map or its views, only mappings that satisfy the filter
2645    * will be removed from the underlying map.
2646    *
2647    * <p>The returned map isn't threadsafe or serializable, even if {@code
2648    * unfiltered} is.
2649    *
2650    * <p>Many of the filtered map's methods, such as {@code size()},
2651    * iterate across every key/value mapping in the underlying map and determine
2652    * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2653    * faster to copy the filtered map and use the copy.
2654    *
2655    * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
2656    * equals</i>, as documented at {@link Predicate#apply}.
2657    */
2658   public static <K, V> Map<K, V> filterEntries(
2659       Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2660     checkNotNull(entryPredicate);
2661     return (unfiltered instanceof AbstractFilteredMap)
2662         ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
2663         : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate);
2664   }
2665 
2666   /**
2667    * Returns a sorted map containing the mappings in {@code unfiltered} that
2668    * satisfy a predicate. The returned map is a live view of {@code unfiltered};
2669    * changes to one affect the other.
2670    *
2671    * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
2672    * values()} views have iterators that don't support {@code remove()}, but all
2673    * other methods are supported by the map and its views. When given a
2674    * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
2675    * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
2676    * Similarly, the map's entries have a {@link Entry#setValue} method that
2677    * throws an {@link IllegalArgumentException} when the existing key and the
2678    * provided value don't satisfy the predicate.
2679    *
2680    * <p>When methods such as {@code removeAll()} and {@code clear()} are called
2681    * on the filtered map or its views, only mappings that satisfy the filter
2682    * will be removed from the underlying map.
2683    *
2684    * <p>The returned map isn't threadsafe or serializable, even if {@code
2685    * unfiltered} is.
2686    *
2687    * <p>Many of the filtered map's methods, such as {@code size()},
2688    * iterate across every key/value mapping in the underlying map and determine
2689    * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2690    * faster to copy the filtered map and use the copy.
2691    *
2692    * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
2693    * equals</i>, as documented at {@link Predicate#apply}.
2694    *
2695    * @since 11.0
2696    */
2697   public static <K, V> SortedMap<K, V> filterEntries(
2698       SortedMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2699     checkNotNull(entryPredicate);
2700     return (unfiltered instanceof FilteredEntrySortedMap)
2701         ? filterFiltered((FilteredEntrySortedMap<K, V>) unfiltered, entryPredicate)
2702         : new FilteredEntrySortedMap<K, V>(checkNotNull(unfiltered), entryPredicate);
2703   }
2704 
2705   /**
2706    * Returns a sorted map containing the mappings in {@code unfiltered} that
2707    * satisfy a predicate. The returned map is a live view of {@code unfiltered};
2708    * changes to one affect the other.
2709    *
2710    * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
2711    * values()} views have iterators that don't support {@code remove()}, but all
2712    * other methods are supported by the map and its views. When given a
2713    * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
2714    * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
2715    * Similarly, the map's entries have a {@link Entry#setValue} method that
2716    * throws an {@link IllegalArgumentException} when the existing key and the
2717    * provided value don't satisfy the predicate.
2718    *
2719    * <p>When methods such as {@code removeAll()} and {@code clear()} are called
2720    * on the filtered map or its views, only mappings that satisfy the filter
2721    * will be removed from the underlying map.
2722    *
2723    * <p>The returned map isn't threadsafe or serializable, even if {@code
2724    * unfiltered} is.
2725    *
2726    * <p>Many of the filtered map's methods, such as {@code size()},
2727    * iterate across every key/value mapping in the underlying map and determine
2728    * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2729    * faster to copy the filtered map and use the copy.
2730    *
2731    * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
2732    * equals</i>, as documented at {@link Predicate#apply}.
2733    *
2734    * @since 14.0
2735    */
2736   @GwtIncompatible // NavigableMap
2737   public static <K, V> NavigableMap<K, V> filterEntries(
2738       NavigableMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2739     checkNotNull(entryPredicate);
2740     return (unfiltered instanceof FilteredEntryNavigableMap)
2741         ? filterFiltered((FilteredEntryNavigableMap<K, V>) unfiltered, entryPredicate)
2742         : new FilteredEntryNavigableMap<K, V>(checkNotNull(unfiltered), entryPredicate);
2743   }
2744 
2745   /**
2746    * Returns a bimap containing the mappings in {@code unfiltered} that satisfy a predicate. The
2747    * returned bimap is a live view of {@code unfiltered}; changes to one affect the other.
2748    *
2749    * <p>The resulting bimap's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2750    * iterators that don't support {@code remove()}, but all other methods are supported by the bimap
2751    * and its views. When given a key/value pair that doesn't satisfy the predicate, the bimap's
2752    * {@code put()}, {@code forcePut()} and {@code putAll()} methods throw an
2753    * {@link IllegalArgumentException}. Similarly, the map's entries have an {@link Entry#setValue}
2754    * method that throws an {@link IllegalArgumentException} when the existing key and the provided
2755    * value don't satisfy the predicate.
2756    *
2757    * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2758    * bimap or its views, only mappings that satisfy the filter will be removed from the underlying
2759    * bimap.
2760    *
2761    * <p>The returned bimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2762    *
2763    * <p>Many of the filtered bimap's methods, such as {@code size()}, iterate across every
2764    * key/value mapping in the underlying bimap and determine which satisfy the filter. When a live
2765    * view is <i>not</i> needed, it may be faster to copy the filtered bimap and use the copy.
2766    *
2767    * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals </i>, as
2768    * documented at {@link Predicate#apply}.
2769    *
2770    * @since 14.0
2771    */
2772   public static <K, V> BiMap<K, V> filterEntries(
2773       BiMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2774     checkNotNull(unfiltered);
2775     checkNotNull(entryPredicate);
2776     return (unfiltered instanceof FilteredEntryBiMap)
2777         ? filterFiltered((FilteredEntryBiMap<K, V>) unfiltered, entryPredicate)
2778         : new FilteredEntryBiMap<K, V>(unfiltered, entryPredicate);
2779   }
2780 
2781   /**
2782    * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
2783    * filtering a filtered map.
2784    */
2785   private static <K, V> Map<K, V> filterFiltered(
2786       AbstractFilteredMap<K, V> map, Predicate<? super Entry<K, V>> entryPredicate) {
2787     return new FilteredEntryMap<>(
2788         map.unfiltered, Predicates.<Entry<K, V>>and(map.predicate, entryPredicate));
2789   }
2790 
2791   private abstract static class AbstractFilteredMap<K, V> extends ViewCachingAbstractMap<K, V> {
2792     final Map<K, V> unfiltered;
2793     final Predicate<? super Entry<K, V>> predicate;
2794 
2795     AbstractFilteredMap(Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
2796       this.unfiltered = unfiltered;
2797       this.predicate = predicate;
2798     }
2799 
2800     boolean apply(@Nullable Object key, @Nullable V value) {
2801       // This method is called only when the key is in the map, implying that
2802       // key is a K.
2803       @SuppressWarnings("unchecked")
2804       K k = (K) key;
2805       return predicate.apply(Maps.immutableEntry(k, value));
2806     }
2807 
2808     @Override
2809     public V put(K key, V value) {
2810       checkArgument(apply(key, value));
2811       return unfiltered.put(key, value);
2812     }
2813 
2814     @Override
2815     public void putAll(Map<? extends K, ? extends V> map) {
2816       for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
2817         checkArgument(apply(entry.getKey(), entry.getValue()));
2818       }
2819       unfiltered.putAll(map);
2820     }
2821 
2822     @Override
2823     public boolean containsKey(Object key) {
2824       return unfiltered.containsKey(key) && apply(key, unfiltered.get(key));
2825     }
2826 
2827     @Override
2828     public V get(Object key) {
2829       V value = unfiltered.get(key);
2830       return ((value != null) && apply(key, value)) ? value : null;
2831     }
2832 
2833     @Override
2834     public boolean isEmpty() {
2835       return entrySet().isEmpty();
2836     }
2837 
2838     @Override
2839     public V remove(Object key) {
2840       return containsKey(key) ? unfiltered.remove(key) : null;
2841     }
2842 
2843     @Override
2844     Collection<V> createValues() {
2845       return new FilteredMapValues<>(this, unfiltered, predicate);
2846     }
2847   }
2848 
2849   private static final class FilteredMapValues<K, V> extends Maps.Values<K, V> {
2850     final Map<K, V> unfiltered;
2851     final Predicate<? super Entry<K, V>> predicate;
2852 
2853     FilteredMapValues(
2854         Map<K, V> filteredMap, Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
2855       super(filteredMap);
2856       this.unfiltered = unfiltered;
2857       this.predicate = predicate;
2858     }
2859 
2860     @Override
2861     public boolean remove(Object o) {
2862       Iterator<Entry<K, V>> entryItr = unfiltered.entrySet().iterator();
2863       while (entryItr.hasNext()) {
2864         Entry<K, V> entry = entryItr.next();
2865         if (predicate.apply(entry) && Objects.equal(entry.getValue(), o)) {
2866           entryItr.remove();
2867           return true;
2868         }
2869       }
2870       return false;
2871     }
2872 
2873     @Override
2874     public boolean removeAll(Collection<?> collection) {
2875       Iterator<Entry<K, V>> entryItr = unfiltered.entrySet().iterator();
2876       boolean result = false;
2877       while (entryItr.hasNext()) {
2878         Entry<K, V> entry = entryItr.next();
2879         if (predicate.apply(entry) && collection.contains(entry.getValue())) {
2880           entryItr.remove();
2881           result = true;
2882         }
2883       }
2884       return result;
2885     }
2886 
2887     @Override
2888     public boolean retainAll(Collection<?> collection) {
2889       Iterator<Entry<K, V>> entryItr = unfiltered.entrySet().iterator();
2890       boolean result = false;
2891       while (entryItr.hasNext()) {
2892         Entry<K, V> entry = entryItr.next();
2893         if (predicate.apply(entry) && !collection.contains(entry.getValue())) {
2894           entryItr.remove();
2895           result = true;
2896         }
2897       }
2898       return result;
2899     }
2900 
2901     @Override
2902     public Object[] toArray() {
2903       // creating an ArrayList so filtering happens once
2904       return Lists.newArrayList(iterator()).toArray();
2905     }
2906 
2907     @Override
2908     public <T> T[] toArray(T[] array) {
2909       return Lists.newArrayList(iterator()).toArray(array);
2910     }
2911   }
2912 
2913   private static class FilteredKeyMap<K, V> extends AbstractFilteredMap<K, V> {
2914     final Predicate<? super K> keyPredicate;
2915 
2916     FilteredKeyMap(
2917         Map<K, V> unfiltered,
2918         Predicate<? super K> keyPredicate,
2919         Predicate<? super Entry<K, V>> entryPredicate) {
2920       super(unfiltered, entryPredicate);
2921       this.keyPredicate = keyPredicate;
2922     }
2923 
2924     @Override
2925     protected Set<Entry<K, V>> createEntrySet() {
2926       return Sets.filter(unfiltered.entrySet(), predicate);
2927     }
2928 
2929     @Override
2930     Set<K> createKeySet() {
2931       return Sets.filter(unfiltered.keySet(), keyPredicate);
2932     }
2933 
2934     // The cast is called only when the key is in the unfiltered map, implying
2935     // that key is a K.
2936     @Override
2937     @SuppressWarnings("unchecked")
2938     public boolean containsKey(Object key) {
2939       return unfiltered.containsKey(key) && keyPredicate.apply((K) key);
2940     }
2941   }
2942 
2943   static class FilteredEntryMap<K, V> extends AbstractFilteredMap<K, V> {
2944     /**
2945      * Entries in this set satisfy the predicate, but they don't validate the
2946      * input to {@code Entry.setValue()}.
2947      */
2948     final Set<Entry<K, V>> filteredEntrySet;
2949 
2950     FilteredEntryMap(Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2951       super(unfiltered, entryPredicate);
2952       filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate);
2953     }
2954 
2955     @Override
2956     protected Set<Entry<K, V>> createEntrySet() {
2957       return new EntrySet();
2958     }
2959 
2960     @WeakOuter
2961     private class EntrySet extends ForwardingSet<Entry<K, V>> {
2962       @Override
2963       protected Set<Entry<K, V>> delegate() {
2964         return filteredEntrySet;
2965       }
2966 
2967       @Override
2968       public Iterator<Entry<K, V>> iterator() {
2969         return new TransformedIterator<Entry<K, V>, Entry<K, V>>(filteredEntrySet.iterator()) {
2970           @Override
2971           Entry<K, V> transform(final Entry<K, V> entry) {
2972             return new ForwardingMapEntry<K, V>() {
2973               @Override
2974               protected Entry<K, V> delegate() {
2975                 return entry;
2976               }
2977 
2978               @Override
2979               public V setValue(V newValue) {
2980                 checkArgument(apply(getKey(), newValue));
2981                 return super.setValue(newValue);
2982               }
2983             };
2984           }
2985         };
2986       }
2987     }
2988 
2989     @Override
2990     Set<K> createKeySet() {
2991       return new KeySet();
2992     }
2993     
2994     static <K, V> boolean removeAllKeys(
2995         Map<K, V> map, Predicate<? super Entry<K, V>> entryPredicate, Collection<?> keyCollection) {
2996       Iterator<Entry<K, V>> entryItr = map.entrySet().iterator();
2997       boolean result = false;
2998       while (entryItr.hasNext()) {
2999         Entry<K, V> entry = entryItr.next();
3000         if (entryPredicate.apply(entry) && keyCollection.contains(entry.getKey())) {
3001           entryItr.remove();
3002           result = true;
3003         }
3004       }
3005       return result;
3006     }
3007     
3008     static <K, V> boolean retainAllKeys(
3009         Map<K, V> map, Predicate<? super Entry<K, V>> entryPredicate, Collection<?> keyCollection) {
3010       Iterator<Entry<K, V>> entryItr = map.entrySet().iterator();
3011       boolean result = false;
3012       while (entryItr.hasNext()) {
3013         Entry<K, V> entry = entryItr.next();
3014         if (entryPredicate.apply(entry) && !keyCollection.contains(entry.getKey())) {
3015           entryItr.remove();
3016           result = true;
3017         }
3018       }
3019       return result;
3020     }
3021 
3022     @WeakOuter
3023     class KeySet extends Maps.KeySet<K, V> {
3024       KeySet() {
3025         super(FilteredEntryMap.this);
3026       }
3027 
3028       @Override
3029       public boolean remove(Object o) {
3030         if (containsKey(o)) {
3031           unfiltered.remove(o);
3032           return true;
3033         }
3034         return false;
3035       }
3036 
3037       @Override
3038       public boolean removeAll(Collection<?> collection) {
3039         return removeAllKeys(unfiltered, predicate, collection);
3040       }
3041 
3042       @Override
3043       public boolean retainAll(Collection<?> collection) {
3044         return retainAllKeys(unfiltered, predicate, collection);
3045       }
3046 
3047       @Override
3048       public Object[] toArray() {
3049         // creating an ArrayList so filtering happens once
3050         return Lists.newArrayList(iterator()).toArray();
3051       }
3052 
3053       @Override
3054       public <T> T[] toArray(T[] array) {
3055         return Lists.newArrayList(iterator()).toArray(array);
3056       }
3057     }
3058   }
3059 
3060   /**
3061    * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
3062    * filtering a filtered sorted map.
3063    */
3064   private static <K, V> SortedMap<K, V> filterFiltered(
3065       FilteredEntrySortedMap<K, V> map, Predicate<? super Entry<K, V>> entryPredicate) {
3066     Predicate<Entry<K, V>> predicate = Predicates.<Entry<K, V>>and(map.predicate, entryPredicate);
3067     return new FilteredEntrySortedMap<>(map.sortedMap(), predicate);
3068   }
3069 
3070   private static class FilteredEntrySortedMap<K, V> extends FilteredEntryMap<K, V>
3071       implements SortedMap<K, V> {
3072 
3073     FilteredEntrySortedMap(
3074         SortedMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
3075       super(unfiltered, entryPredicate);
3076     }
3077 
3078     SortedMap<K, V> sortedMap() {
3079       return (SortedMap<K, V>) unfiltered;
3080     }
3081 
3082     @Override
3083     public SortedSet<K> keySet() {
3084       return (SortedSet<K>) super.keySet();
3085     }
3086 
3087     @Override
3088     SortedSet<K> createKeySet() {
3089       return new SortedKeySet();
3090     }
3091 
3092     @WeakOuter
3093     class SortedKeySet extends KeySet implements SortedSet<K> {
3094       @Override
3095       public Comparator<? super K> comparator() {
3096         return sortedMap().comparator();
3097       }
3098 
3099       @Override
3100       public SortedSet<K> subSet(K fromElement, K toElement) {
3101         return (SortedSet<K>) subMap(fromElement, toElement).keySet();
3102       }
3103 
3104       @Override
3105       public SortedSet<K> headSet(K toElement) {
3106         return (SortedSet<K>) headMap(toElement).keySet();
3107       }
3108 
3109       @Override
3110       public SortedSet<K> tailSet(K fromElement) {
3111         return (SortedSet<K>) tailMap(fromElement).keySet();
3112       }
3113 
3114       @Override
3115       public K first() {
3116         return firstKey();
3117       }
3118 
3119       @Override
3120       public K last() {
3121         return lastKey();
3122       }
3123     }
3124 
3125     @Override
3126     public Comparator<? super K> comparator() {
3127       return sortedMap().comparator();
3128     }
3129 
3130     @Override
3131     public K firstKey() {
3132       // correctly throws NoSuchElementException when filtered map is empty.
3133       return keySet().iterator().next();
3134     }
3135 
3136     @Override
3137     public K lastKey() {
3138       SortedMap<K, V> headMap = sortedMap();
3139       while (true) {
3140         // correctly throws NoSuchElementException when filtered map is empty.
3141         K key = headMap.lastKey();
3142         if (apply(key, unfiltered.get(key))) {
3143           return key;
3144         }
3145         headMap = sortedMap().headMap(key);
3146       }
3147     }
3148 
3149     @Override
3150     public SortedMap<K, V> headMap(K toKey) {
3151       return new FilteredEntrySortedMap<>(sortedMap().headMap(toKey), predicate);
3152     }
3153 
3154     @Override
3155     public SortedMap<K, V> subMap(K fromKey, K toKey) {
3156       return new FilteredEntrySortedMap<>(sortedMap().subMap(fromKey, toKey), predicate);
3157     }
3158 
3159     @Override
3160     public SortedMap<K, V> tailMap(K fromKey) {
3161       return new FilteredEntrySortedMap<>(sortedMap().tailMap(fromKey), predicate);
3162     }
3163   }
3164 
3165   /**
3166    * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
3167    * filtering a filtered navigable map.
3168    */
3169   @GwtIncompatible // NavigableMap
3170   private static <K, V> NavigableMap<K, V> filterFiltered(
3171       FilteredEntryNavigableMap<K, V> map, Predicate<? super Entry<K, V>> entryPredicate) {
3172     Predicate<Entry<K, V>> predicate =
3173         Predicates.<Entry<K, V>>and(map.entryPredicate, entryPredicate);
3174     return new FilteredEntryNavigableMap<>(map.unfiltered, predicate);
3175   }
3176 
3177   @GwtIncompatible // NavigableMap
3178   private static class FilteredEntryNavigableMap<K, V> extends AbstractNavigableMap<K, V> {
3179     /*
3180      * It's less code to extend AbstractNavigableMap and forward the filtering logic to
3181      * FilteredEntryMap than to extend FilteredEntrySortedMap and reimplement all the NavigableMap
3182      * methods.
3183      */
3184 
3185     private final NavigableMap<K, V> unfiltered;
3186     private final Predicate<? super Entry<K, V>> entryPredicate;
3187     private final Map<K, V> filteredDelegate;
3188 
3189     FilteredEntryNavigableMap(
3190         NavigableMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
3191       this.unfiltered = checkNotNull(unfiltered);
3192       this.entryPredicate = entryPredicate;
3193       this.filteredDelegate = new FilteredEntryMap<>(unfiltered, entryPredicate);
3194     }
3195 
3196     @Override
3197     public Comparator<? super K> comparator() {
3198       return unfiltered.comparator();
3199     }
3200 
3201     @Override
3202     public NavigableSet<K> navigableKeySet() {
3203       return new Maps.NavigableKeySet<K, V>(this) {
3204         @Override
3205         public boolean removeAll(Collection<?> collection) {
3206           return FilteredEntryMap.removeAllKeys(unfiltered, entryPredicate, collection);
3207         }
3208 
3209         @Override
3210         public boolean retainAll(Collection<?> collection) {
3211           return FilteredEntryMap.retainAllKeys(unfiltered, entryPredicate, collection);
3212         }
3213       };
3214     }
3215 
3216     @Override
3217     public Collection<V> values() {
3218       return new FilteredMapValues<>(this, unfiltered, entryPredicate);
3219     }
3220 
3221     @Override
3222     Iterator<Entry<K, V>> entryIterator() {
3223       return Iterators.filter(unfiltered.entrySet().iterator(), entryPredicate);
3224     }
3225 
3226     @Override
3227     Iterator<Entry<K, V>> descendingEntryIterator() {
3228       return Iterators.filter(unfiltered.descendingMap().entrySet().iterator(), entryPredicate);
3229     }
3230 
3231     @Override
3232     public int size() {
3233       return filteredDelegate.size();
3234     }
3235 
3236     @Override
3237     public boolean isEmpty() {
3238       return !Iterables.any(unfiltered.entrySet(), entryPredicate);
3239     }
3240 
3241     @Override
3242     @Nullable
3243     public V get(@Nullable Object key) {
3244       return filteredDelegate.get(key);
3245     }
3246 
3247     @Override
3248     public boolean containsKey(@Nullable Object key) {
3249       return filteredDelegate.containsKey(key);
3250     }
3251 
3252     @Override
3253     public V put(K key, V value) {
3254       return filteredDelegate.put(key, value);
3255     }
3256 
3257     @Override
3258     public V remove(@Nullable Object key) {
3259       return filteredDelegate.remove(key);
3260     }
3261 
3262     @Override
3263     public void putAll(Map<? extends K, ? extends V> m) {
3264       filteredDelegate.putAll(m);
3265     }
3266 
3267     @Override
3268     public void clear() {
3269       filteredDelegate.clear();
3270     }
3271 
3272     @Override
3273     public Set<Entry<K, V>> entrySet() {
3274       return filteredDelegate.entrySet();
3275     }
3276 
3277     @Override
3278     public Entry<K, V> pollFirstEntry() {
3279       return Iterables.removeFirstMatching(unfiltered.entrySet(), entryPredicate);
3280     }
3281 
3282     @Override
3283     public Entry<K, V> pollLastEntry() {
3284       return Iterables.removeFirstMatching(unfiltered.descendingMap().entrySet(), entryPredicate);
3285     }
3286 
3287     @Override
3288     public NavigableMap<K, V> descendingMap() {
3289       return filterEntries(unfiltered.descendingMap(), entryPredicate);
3290     }
3291 
3292     @Override
3293     public NavigableMap<K, V> subMap(
3294         K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
3295       return filterEntries(
3296           unfiltered.subMap(fromKey, fromInclusive, toKey, toInclusive), entryPredicate);
3297     }
3298 
3299     @Override
3300     public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
3301       return filterEntries(unfiltered.headMap(toKey, inclusive), entryPredicate);
3302     }
3303 
3304     @Override
3305     public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
3306       return filterEntries(unfiltered.tailMap(fromKey, inclusive), entryPredicate);
3307     }
3308   }
3309 
3310   /**
3311    * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
3312    * filtering a filtered map.
3313    */
3314   private static <K, V> BiMap<K, V> filterFiltered(
3315       FilteredEntryBiMap<K, V> map, Predicate<? super Entry<K, V>> entryPredicate) {
3316     Predicate<Entry<K, V>> predicate = Predicates.<Entry<K, V>>and(map.predicate, entryPredicate);
3317     return new FilteredEntryBiMap<>(map.unfiltered(), predicate);
3318   }
3319 
3320   static final class FilteredEntryBiMap<K, V> extends FilteredEntryMap<K, V>
3321       implements BiMap<K, V> {
3322     @RetainedWith
3323     private final BiMap<V, K> inverse;
3324 
3325     private static <K, V> Predicate<Entry<V, K>> inversePredicate(
3326         final Predicate<? super Entry<K, V>> forwardPredicate) {
3327       return new Predicate<Entry<V, K>>() {
3328         @Override
3329         public boolean apply(Entry<V, K> input) {
3330           return forwardPredicate.apply(Maps.immutableEntry(input.getValue(), input.getKey()));
3331         }
3332       };
3333     }
3334 
3335     FilteredEntryBiMap(BiMap<K, V> delegate, Predicate<? super Entry<K, V>> predicate) {
3336       super(delegate, predicate);
3337       this.inverse =
3338           new FilteredEntryBiMap<>(delegate.inverse(), inversePredicate(predicate), this);
3339     }
3340 
3341     private FilteredEntryBiMap(
3342         BiMap<K, V> delegate, Predicate<? super Entry<K, V>> predicate, BiMap<V, K> inverse) {
3343       super(delegate, predicate);
3344       this.inverse = inverse;
3345     }
3346 
3347     BiMap<K, V> unfiltered() {
3348       return (BiMap<K, V>) unfiltered;
3349     }
3350 
3351     @Override
3352     public V forcePut(@Nullable K key, @Nullable V value) {
3353       checkArgument(apply(key, value));
3354       return unfiltered().forcePut(key, value);
3355     }
3356 
3357     @Override
3358     public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3359       unfiltered()
3360           .replaceAll(
3361               (key, value) ->
3362                   predicate.apply(Maps.immutableEntry(key, value))
3363                       ? function.apply(key, value)
3364                       : value);
3365     }
3366 
3367     @Override
3368     public BiMap<V, K> inverse() {
3369       return inverse;
3370     }
3371 
3372     @Override
3373     public Set<V> values() {
3374       return inverse.keySet();
3375     }
3376   }
3377 
3378   /**
3379    * Returns an unmodifiable view of the specified navigable map. Query operations on the returned
3380    * map read through to the specified map, and attempts to modify the returned map, whether direct
3381    * or via its views, result in an {@code UnsupportedOperationException}.
3382    *
3383    * <p>The returned navigable map will be serializable if the specified navigable map is
3384    * serializable.
3385    *
3386    * <p>This method's signature will not permit you to convert a {@code NavigableMap<? extends K,
3387    * V>} to a {@code NavigableMap<K, V>}. If it permitted this, the returned map's {@code
3388    * comparator()} method might return a {@code Comparator<? extends K>}, which works only on a
3389    * particular subtype of {@code K}, but promise that it's a {@code Comparator<? super K>}, which
3390    * must work on any type of {@code K}.
3391    *
3392    * @param map the navigable map for which an unmodifiable view is to be returned
3393    * @return an unmodifiable view of the specified navigable map
3394    * @since 12.0
3395    */
3396   @GwtIncompatible // NavigableMap
3397   public static <K, V> NavigableMap<K, V> unmodifiableNavigableMap(
3398       NavigableMap<K, ? extends V> map) {
3399     checkNotNull(map);
3400     if (map instanceof UnmodifiableNavigableMap) {
3401       @SuppressWarnings("unchecked") // covariant
3402       NavigableMap<K, V> result = (NavigableMap) map;
3403       return result;
3404     } else {
3405       return new UnmodifiableNavigableMap<>(map);
3406     }
3407   }
3408 
3409   @Nullable
3410   private static <K, V> Entry<K, V> unmodifiableOrNull(@Nullable Entry<K, ? extends V> entry) {
3411     return (entry == null) ? null : Maps.unmodifiableEntry(entry);
3412   }
3413 
3414   @GwtIncompatible // NavigableMap
3415   static class UnmodifiableNavigableMap<K, V> extends ForwardingSortedMap<K, V>
3416       implements NavigableMap<K, V>, Serializable {
3417     private final NavigableMap<K, ? extends V> delegate;
3418 
3419     UnmodifiableNavigableMap(NavigableMap<K, ? extends V> delegate) {
3420       this.delegate = delegate;
3421     }
3422 
3423     UnmodifiableNavigableMap(
3424         NavigableMap<K, ? extends V> delegate, UnmodifiableNavigableMap<K, V> descendingMap) {
3425       this.delegate = delegate;
3426       this.descendingMap = descendingMap;
3427     }
3428 
3429     @Override
3430     protected SortedMap<K, V> delegate() {
3431       return Collections.unmodifiableSortedMap(delegate);
3432     }
3433 
3434     @Override
3435     public Entry<K, V> lowerEntry(K key) {
3436       return unmodifiableOrNull(delegate.lowerEntry(key));
3437     }
3438 
3439     @Override
3440     public K lowerKey(K key) {
3441       return delegate.lowerKey(key);
3442     }
3443 
3444     @Override
3445     public Entry<K, V> floorEntry(K key) {
3446       return unmodifiableOrNull(delegate.floorEntry(key));
3447     }
3448 
3449     @Override
3450     public K floorKey(K key) {
3451       return delegate.floorKey(key);
3452     }
3453 
3454     @Override
3455     public Entry<K, V> ceilingEntry(K key) {
3456       return unmodifiableOrNull(delegate.ceilingEntry(key));
3457     }
3458 
3459     @Override
3460     public K ceilingKey(K key) {
3461       return delegate.ceilingKey(key);
3462     }
3463 
3464     @Override
3465     public Entry<K, V> higherEntry(K key) {
3466       return unmodifiableOrNull(delegate.higherEntry(key));
3467     }
3468 
3469     @Override
3470     public K higherKey(K key) {
3471       return delegate.higherKey(key);
3472     }
3473 
3474     @Override
3475     public Entry<K, V> firstEntry() {
3476       return unmodifiableOrNull(delegate.firstEntry());
3477     }
3478 
3479     @Override
3480     public Entry<K, V> lastEntry() {
3481       return unmodifiableOrNull(delegate.lastEntry());
3482     }
3483 
3484     @Override
3485     public final Entry<K, V> pollFirstEntry() {
3486       throw new UnsupportedOperationException();
3487     }
3488 
3489     @Override
3490     public final Entry<K, V> pollLastEntry() {
3491       throw new UnsupportedOperationException();
3492     }
3493 
3494     private transient UnmodifiableNavigableMap<K, V> descendingMap;
3495 
3496     @Override
3497     public NavigableMap<K, V> descendingMap() {
3498       UnmodifiableNavigableMap<K, V> result = descendingMap;
3499       return (result == null)
3500           ? descendingMap = new UnmodifiableNavigableMap<>(delegate.descendingMap(), this)
3501           : result;
3502     }
3503 
3504     @Override
3505     public Set<K> keySet() {
3506       return navigableKeySet();
3507     }
3508 
3509     @Override
3510     public NavigableSet<K> navigableKeySet() {
3511       return Sets.unmodifiableNavigableSet(delegate.navigableKeySet());
3512     }
3513 
3514     @Override
3515     public NavigableSet<K> descendingKeySet() {
3516       return Sets.unmodifiableNavigableSet(delegate.descendingKeySet());
3517     }
3518 
3519     @Override
3520     public SortedMap<K, V> subMap(K fromKey, K toKey) {
3521       return subMap(fromKey, true, toKey, false);
3522     }
3523 
3524     @Override
3525     public SortedMap<K, V> headMap(K toKey) {
3526       return headMap(toKey, false);
3527     }
3528 
3529     @Override
3530     public SortedMap<K, V> tailMap(K fromKey) {
3531       return tailMap(fromKey, true);
3532     }
3533 
3534     @Override
3535     public NavigableMap<K, V> subMap(
3536         K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
3537       return Maps.unmodifiableNavigableMap(
3538           delegate.subMap(fromKey, fromInclusive, toKey, toInclusive));
3539     }
3540 
3541     @Override
3542     public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
3543       return Maps.unmodifiableNavigableMap(delegate.headMap(toKey, inclusive));
3544     }
3545 
3546     @Override
3547     public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
3548       return Maps.unmodifiableNavigableMap(delegate.tailMap(fromKey, inclusive));
3549     }
3550   }
3551 
3552   /**
3553    * Returns a synchronized (thread-safe) navigable map backed by the specified
3554    * navigable map.  In order to guarantee serial access, it is critical that
3555    * <b>all</b> access to the backing navigable map is accomplished
3556    * through the returned navigable map (or its views).
3557    *
3558    * <p>It is imperative that the user manually synchronize on the returned
3559    * navigable map when iterating over any of its collection views, or the
3560    * collections views of any of its {@code descendingMap}, {@code subMap},
3561    * {@code headMap} or {@code tailMap} views. <pre>   {@code
3562    *
3563    *   NavigableMap<K, V> map = synchronizedNavigableMap(new TreeMap<K, V>());
3564    *
3565    *   // Needn't be in synchronized block
3566    *   NavigableSet<K> set = map.navigableKeySet();
3567    *
3568    *   synchronized (map) { // Synchronizing on map, not set!
3569    *     Iterator<K> it = set.iterator(); // Must be in synchronized block
3570    *     while (it.hasNext()) {
3571    *       foo(it.next());
3572    *     }
3573    *   }}</pre>
3574    *
3575    * <p>or: <pre>   {@code
3576    *
3577    *   NavigableMap<K, V> map = synchronizedNavigableMap(new TreeMap<K, V>());
3578    *   NavigableMap<K, V> map2 = map.subMap(foo, false, bar, true);
3579    *
3580    *   // Needn't be in synchronized block
3581    *   NavigableSet<K> set2 = map2.descendingKeySet();
3582    *
3583    *   synchronized (map) { // Synchronizing on map, not map2 or set2!
3584    *     Iterator<K> it = set2.iterator(); // Must be in synchronized block
3585    *     while (it.hasNext()) {
3586    *       foo(it.next());
3587    *     }
3588    *   }}</pre>
3589    *
3590    * <p>Failure to follow this advice may result in non-deterministic behavior.
3591    *
3592    * <p>The returned navigable map will be serializable if the specified
3593    * navigable map is serializable.
3594    *
3595    * @param navigableMap the navigable map to be "wrapped" in a synchronized
3596    *    navigable map.
3597    * @return a synchronized view of the specified navigable map.
3598    * @since 13.0
3599    */
3600   @GwtIncompatible // NavigableMap
3601   public static <K, V> NavigableMap<K, V> synchronizedNavigableMap(
3602       NavigableMap<K, V> navigableMap) {
3603     return Synchronized.navigableMap(navigableMap);
3604   }
3605 
3606   /**
3607    * {@code AbstractMap} extension that makes it easy to cache customized keySet, values,
3608    * and entrySet views.
3609    */
3610   @GwtCompatible
3611   abstract static class ViewCachingAbstractMap<K, V> extends AbstractMap<K, V> {
3612     /**
3613      * Creates the entry set to be returned by {@link #entrySet()}. This method
3614      * is invoked at most once on a given map, at the time when {@code entrySet}
3615      * is first called.
3616      */
3617     abstract Set<Entry<K, V>> createEntrySet();
3618 
3619     private transient Set<Entry<K, V>> entrySet;
3620 
3621     @Override
3622     public Set<Entry<K, V>> entrySet() {
3623       Set<Entry<K, V>> result = entrySet;
3624       return (result == null) ? entrySet = createEntrySet() : result;
3625     }
3626 
3627     private transient Set<K> keySet;
3628 
3629     @Override
3630     public Set<K> keySet() {
3631       Set<K> result = keySet;
3632       return (result == null) ? keySet = createKeySet() : result;
3633     }
3634 
3635     Set<K> createKeySet() {
3636       return new KeySet<>(this);
3637     }
3638 
3639     private transient Collection<V> values;
3640 
3641     @Override
3642     public Collection<V> values() {
3643       Collection<V> result = values;
3644       return (result == null) ? values = createValues() : result;
3645     }
3646 
3647     Collection<V> createValues() {
3648       return new Values<>(this);
3649     }
3650   }
3651 
3652   abstract static class IteratorBasedAbstractMap<K, V> extends AbstractMap<K, V> {
3653     @Override
3654     public abstract int size();
3655 
3656     abstract Iterator<Entry<K, V>> entryIterator();
3657 
3658     Spliterator<Entry<K, V>> entrySpliterator() {
3659       return Spliterators.spliterator(
3660           entryIterator(), size(), Spliterator.SIZED | Spliterator.DISTINCT);
3661     }
3662 
3663     @Override
3664     public Set<Entry<K, V>> entrySet() {
3665       return new EntrySet<K, V>() {
3666         @Override
3667         Map<K, V> map() {
3668           return IteratorBasedAbstractMap.this;
3669         }
3670 
3671         @Override
3672         public Iterator<Entry<K, V>> iterator() {
3673           return entryIterator();
3674         }
3675 
3676         @Override
3677         public Spliterator<Entry<K, V>> spliterator() {
3678           return entrySpliterator();
3679         }
3680 
3681         @Override
3682         public void forEach(Consumer<? super Entry<K, V>> action) {
3683           forEachEntry(action);
3684         }
3685       };
3686     }
3687 
3688     void forEachEntry(Consumer<? super Entry<K, V>> action) {
3689       entryIterator().forEachRemaining(action);
3690     }
3691 
3692     @Override
3693     public void clear() {
3694       Iterators.clear(entryIterator());
3695     }
3696   }
3697 
3698   /**
3699    * Delegates to {@link Map#get}. Returns {@code null} on {@code
3700    * ClassCastException} and {@code NullPointerException}.
3701    */
3702   static <V> V safeGet(Map<?, V> map, @Nullable Object key) {
3703     checkNotNull(map);
3704     try {
3705       return map.get(key);
3706     } catch (ClassCastException | NullPointerException e) {
3707       return null;
3708     }
3709   }
3710 
3711   /**
3712    * Delegates to {@link Map#containsKey}. Returns {@code false} on {@code
3713    * ClassCastException} and {@code NullPointerException}.
3714    */
3715   static boolean safeContainsKey(Map<?, ?> map, Object key) {
3716     checkNotNull(map);
3717     try {
3718       return map.containsKey(key);
3719     } catch (ClassCastException | NullPointerException e) {
3720       return false;
3721     }
3722   }
3723 
3724   /**
3725    * Delegates to {@link Map#remove}. Returns {@code null} on {@code
3726    * ClassCastException} and {@code NullPointerException}.
3727    */
3728   static <V> V safeRemove(Map<?, V> map, Object key) {
3729     checkNotNull(map);
3730     try {
3731       return map.remove(key);
3732     } catch (ClassCastException | NullPointerException e) {
3733       return null;
3734     }
3735   }
3736 
3737   /**
3738    * An admittedly inefficient implementation of {@link Map#containsKey}.
3739    */
3740   static boolean containsKeyImpl(Map<?, ?> map, @Nullable Object key) {
3741     return Iterators.contains(keyIterator(map.entrySet().iterator()), key);
3742   }
3743 
3744   /**
3745    * An implementation of {@link Map#containsValue}.
3746    */
3747   static boolean containsValueImpl(Map<?, ?> map, @Nullable Object value) {
3748     return Iterators.contains(valueIterator(map.entrySet().iterator()), value);
3749   }
3750 
3751   /**
3752    * Implements {@code Collection.contains} safely for forwarding collections of
3753    * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
3754    * wrapped using {@link #unmodifiableEntry} to protect against a possible
3755    * nefarious equals method.
3756    *
3757    * <p>Note that {@code c} is the backing (delegate) collection, rather than
3758    * the forwarding collection.
3759    *
3760    * @param c the delegate (unwrapped) collection of map entries
3761    * @param o the object that might be contained in {@code c}
3762    * @return {@code true} if {@code c} contains {@code o}
3763    */
3764   static <K, V> boolean containsEntryImpl(Collection<Entry<K, V>> c, Object o) {
3765     if (!(o instanceof Entry)) {
3766       return false;
3767     }
3768     return c.contains(unmodifiableEntry((Entry<?, ?>) o));
3769   }
3770 
3771   /**
3772    * Implements {@code Collection.remove} safely for forwarding collections of
3773    * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
3774    * wrapped using {@link #unmodifiableEntry} to protect against a possible
3775    * nefarious equals method.
3776    *
3777    * <p>Note that {@code c} is backing (delegate) collection, rather than the
3778    * forwarding collection.
3779    *
3780    * @param c the delegate (unwrapped) collection of map entries
3781    * @param o the object to remove from {@code c}
3782    * @return {@code true} if {@code c} was changed
3783    */
3784   static <K, V> boolean removeEntryImpl(Collection<Entry<K, V>> c, Object o) {
3785     if (!(o instanceof Entry)) {
3786       return false;
3787     }
3788     return c.remove(unmodifiableEntry((Entry<?, ?>) o));
3789   }
3790 
3791   /**
3792    * An implementation of {@link Map#equals}.
3793    */
3794   static boolean equalsImpl(Map<?, ?> map, Object object) {
3795     if (map == object) {
3796       return true;
3797     } else if (object instanceof Map) {
3798       Map<?, ?> o = (Map<?, ?>) object;
3799       return map.entrySet().equals(o.entrySet());
3800     }
3801     return false;
3802   }
3803 
3804   /**
3805    * An implementation of {@link Map#toString}.
3806    */
3807   static String toStringImpl(Map<?, ?> map) {
3808     StringBuilder sb = Collections2.newStringBuilderForCollection(map.size()).append('{');
3809     boolean first = true;
3810     for (Map.Entry<?, ?> entry : map.entrySet()) {
3811       if (!first) {
3812         sb.append(", ");
3813       }
3814       first = false;
3815       sb.append(entry.getKey()).append('=').append(entry.getValue());
3816     }
3817     return sb.append('}').toString();
3818   }
3819 
3820   /**
3821    * An implementation of {@link Map#putAll}.
3822    */
3823   static <K, V> void putAllImpl(Map<K, V> self, Map<? extends K, ? extends V> map) {
3824     for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
3825       self.put(entry.getKey(), entry.getValue());
3826     }
3827   }
3828 
3829   static class KeySet<K, V> extends Sets.ImprovedAbstractSet<K> {
3830     @Weak final Map<K, V> map;
3831 
3832     KeySet(Map<K, V> map) {
3833       this.map = checkNotNull(map);
3834     }
3835 
3836     Map<K, V> map() {
3837       return map;
3838     }
3839 
3840     @Override
3841     public Iterator<K> iterator() {
3842       return keyIterator(map().entrySet().iterator());
3843     }
3844 
3845     @Override
3846     public void forEach(Consumer<? super K> action) {
3847       checkNotNull(action);
3848       // avoids entry allocation for those maps that allocate entries on iteration
3849       map.forEach((k, v) -> action.accept(k));
3850     }
3851 
3852     @Override
3853     public int size() {
3854       return map().size();
3855     }
3856 
3857     @Override
3858     public boolean isEmpty() {
3859       return map().isEmpty();
3860     }
3861 
3862     @Override
3863     public boolean contains(Object o) {
3864       return map().containsKey(o);
3865     }
3866 
3867     @Override
3868     public boolean remove(Object o) {
3869       if (contains(o)) {
3870         map().remove(o);
3871         return true;
3872       }
3873       return false;
3874     }
3875 
3876     @Override
3877     public void clear() {
3878       map().clear();
3879     }
3880   }
3881 
3882   @Nullable
3883   static <K> K keyOrNull(@Nullable Entry<K, ?> entry) {
3884     return (entry == null) ? null : entry.getKey();
3885   }
3886 
3887   @Nullable
3888   static <V> V valueOrNull(@Nullable Entry<?, V> entry) {
3889     return (entry == null) ? null : entry.getValue();
3890   }
3891 
3892   static class SortedKeySet<K, V> extends KeySet<K, V> implements SortedSet<K> {
3893     SortedKeySet(SortedMap<K, V> map) {
3894       super(map);
3895     }
3896 
3897     @Override
3898     SortedMap<K, V> map() {
3899       return (SortedMap<K, V>) super.map();
3900     }
3901 
3902     @Override
3903     public Comparator<? super K> comparator() {
3904       return map().comparator();
3905     }
3906 
3907     @Override
3908     public SortedSet<K> subSet(K fromElement, K toElement) {
3909       return new SortedKeySet<>(map().subMap(fromElement, toElement));
3910     }
3911 
3912     @Override
3913     public SortedSet<K> headSet(K toElement) {
3914       return new SortedKeySet<>(map().headMap(toElement));
3915     }
3916 
3917     @Override
3918     public SortedSet<K> tailSet(K fromElement) {
3919       return new SortedKeySet<>(map().tailMap(fromElement));
3920     }
3921 
3922     @Override
3923     public K first() {
3924       return map().firstKey();
3925     }
3926 
3927     @Override
3928     public K last() {
3929       return map().lastKey();
3930     }
3931   }
3932 
3933   @GwtIncompatible // NavigableMap
3934   static class NavigableKeySet<K, V> extends SortedKeySet<K, V> implements NavigableSet<K> {
3935     NavigableKeySet(NavigableMap<K, V> map) {
3936       super(map);
3937     }
3938 
3939     @Override
3940     NavigableMap<K, V> map() {
3941       return (NavigableMap<K, V>) map;
3942     }
3943 
3944     @Override
3945     public K lower(K e) {
3946       return map().lowerKey(e);
3947     }
3948 
3949     @Override
3950     public K floor(K e) {
3951       return map().floorKey(e);
3952     }
3953 
3954     @Override
3955     public K ceiling(K e) {
3956       return map().ceilingKey(e);
3957     }
3958 
3959     @Override
3960     public K higher(K e) {
3961       return map().higherKey(e);
3962     }
3963 
3964     @Override
3965     public K pollFirst() {
3966       return keyOrNull(map().pollFirstEntry());
3967     }
3968 
3969     @Override
3970     public K pollLast() {
3971       return keyOrNull(map().pollLastEntry());
3972     }
3973 
3974     @Override
3975     public NavigableSet<K> descendingSet() {
3976       return map().descendingKeySet();
3977     }
3978 
3979     @Override
3980     public Iterator<K> descendingIterator() {
3981       return descendingSet().iterator();
3982     }
3983 
3984     @Override
3985     public NavigableSet<K> subSet(
3986         K fromElement, boolean fromInclusive, K toElement, boolean toInclusive) {
3987       return map().subMap(fromElement, fromInclusive, toElement, toInclusive).navigableKeySet();
3988     }
3989 
3990     @Override
3991     public NavigableSet<K> headSet(K toElement, boolean inclusive) {
3992       return map().headMap(toElement, inclusive).navigableKeySet();
3993     }
3994 
3995     @Override
3996     public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
3997       return map().tailMap(fromElement, inclusive).navigableKeySet();
3998     }
3999 
4000     @Override
4001     public SortedSet<K> subSet(K fromElement, K toElement) {
4002       return subSet(fromElement, true, toElement, false);
4003     }
4004 
4005     @Override
4006     public SortedSet<K> headSet(K toElement) {
4007       return headSet(toElement, false);
4008     }
4009 
4010     @Override
4011     public SortedSet<K> tailSet(K fromElement) {
4012       return tailSet(fromElement, true);
4013     }
4014   }
4015 
4016   static class Values<K, V> extends AbstractCollection<V> {
4017     @Weak final Map<K, V> map;
4018 
4019     Values(Map<K, V> map) {
4020       this.map = checkNotNull(map);
4021     }
4022 
4023     final Map<K, V> map() {
4024       return map;
4025     }
4026 
4027     @Override
4028     public Iterator<V> iterator() {
4029       return valueIterator(map().entrySet().iterator());
4030     }
4031 
4032     @Override
4033     public void forEach(Consumer<? super V> action) {
4034       checkNotNull(action);
4035       // avoids allocation of entries for those maps that generate fresh entries on iteration
4036       map.forEach((k, v) -> action.accept(v));
4037     }
4038 
4039     @Override
4040     public boolean remove(Object o) {
4041       try {
4042         return super.remove(o);
4043       } catch (UnsupportedOperationException e) {
4044         for (Entry<K, V> entry : map().entrySet()) {
4045           if (Objects.equal(o, entry.getValue())) {
4046             map().remove(entry.getKey());
4047             return true;
4048           }
4049         }
4050         return false;
4051       }
4052     }
4053 
4054     @Override
4055     public boolean removeAll(Collection<?> c) {
4056       try {
4057         return super.removeAll(checkNotNull(c));
4058       } catch (UnsupportedOperationException e) {
4059         Set<K> toRemove = Sets.newHashSet();
4060         for (Entry<K, V> entry : map().entrySet()) {
4061           if (c.contains(entry.getValue())) {
4062             toRemove.add(entry.getKey());
4063           }
4064         }
4065         return map().keySet().removeAll(toRemove);
4066       }
4067     }
4068 
4069     @Override
4070     public boolean retainAll(Collection<?> c) {
4071       try {
4072         return super.retainAll(checkNotNull(c));
4073       } catch (UnsupportedOperationException e) {
4074         Set<K> toRetain = Sets.newHashSet();
4075         for (Entry<K, V> entry : map().entrySet()) {
4076           if (c.contains(entry.getValue())) {
4077             toRetain.add(entry.getKey());
4078           }
4079         }
4080         return map().keySet().retainAll(toRetain);
4081       }
4082     }
4083 
4084     @Override
4085     public int size() {
4086       return map().size();
4087     }
4088 
4089     @Override
4090     public boolean isEmpty() {
4091       return map().isEmpty();
4092     }
4093 
4094     @Override
4095     public boolean contains(@Nullable Object o) {
4096       return map().containsValue(o);
4097     }
4098 
4099     @Override
4100     public void clear() {
4101       map().clear();
4102     }
4103   }
4104 
4105   abstract static class EntrySet<K, V> extends Sets.ImprovedAbstractSet<Entry<K, V>> {
4106     abstract Map<K, V> map();
4107 
4108     @Override
4109     public int size() {
4110       return map().size();
4111     }
4112 
4113     @Override
4114     public void clear() {
4115       map().clear();
4116     }
4117 
4118     @Override
4119     public boolean contains(Object o) {
4120       if (o instanceof Entry) {
4121         Entry<?, ?> entry = (Entry<?, ?>) o;
4122         Object key = entry.getKey();
4123         V value = Maps.safeGet(map(), key);
4124         return Objects.equal(value, entry.getValue()) && (value != null || map().containsKey(key));
4125       }
4126       return false;
4127     }
4128 
4129     @Override
4130     public boolean isEmpty() {
4131       return map().isEmpty();
4132     }
4133 
4134     @Override
4135     public boolean remove(Object o) {
4136       if (contains(o)) {
4137         Entry<?, ?> entry = (Entry<?, ?>) o;
4138         return map().keySet().remove(entry.getKey());
4139       }
4140       return false;
4141     }
4142 
4143     @Override
4144     public boolean removeAll(Collection<?> c) {
4145       try {
4146         return super.removeAll(checkNotNull(c));
4147       } catch (UnsupportedOperationException e) {
4148         // if the iterators don't support remove
4149         return Sets.removeAllImpl(this, c.iterator());
4150       }
4151     }
4152 
4153     @Override
4154     public boolean retainAll(Collection<?> c) {
4155       try {
4156         return super.retainAll(checkNotNull(c));
4157       } catch (UnsupportedOperationException e) {
4158         // if the iterators don't support remove
4159         Set<Object> keys = Sets.newHashSetWithExpectedSize(c.size());
4160         for (Object o : c) {
4161           if (contains(o)) {
4162             Entry<?, ?> entry = (Entry<?, ?>) o;
4163             keys.add(entry.getKey());
4164           }
4165         }
4166         return map().keySet().retainAll(keys);
4167       }
4168     }
4169   }
4170 
4171   @GwtIncompatible // NavigableMap
4172   abstract static class DescendingMap<K, V> extends ForwardingMap<K, V>
4173       implements NavigableMap<K, V> {
4174 
4175     abstract NavigableMap<K, V> forward();
4176 
4177     @Override
4178     protected final Map<K, V> delegate() {
4179       return forward();
4180     }
4181 
4182     private transient Comparator<? super K> comparator;
4183 
4184     @SuppressWarnings("unchecked")
4185     @Override
4186     public Comparator<? super K> comparator() {
4187       Comparator<? super K> result = comparator;
4188       if (result == null) {
4189         Comparator<? super K> forwardCmp = forward().comparator();
4190         if (forwardCmp == null) {
4191           forwardCmp = (Comparator) Ordering.natural();
4192         }
4193         result = comparator = reverse(forwardCmp);
4194       }
4195       return result;
4196     }
4197 
4198     // If we inline this, we get a javac error.
4199     private static <T> Ordering<T> reverse(Comparator<T> forward) {
4200       return Ordering.from(forward).reverse();
4201     }
4202 
4203     @Override
4204     public K firstKey() {
4205       return forward().lastKey();
4206     }
4207 
4208     @Override
4209     public K lastKey() {
4210       return forward().firstKey();
4211     }
4212 
4213     @Override
4214     public Entry<K, V> lowerEntry(K key) {
4215       return forward().higherEntry(key);
4216     }
4217 
4218     @Override
4219     public K lowerKey(K key) {
4220       return forward().higherKey(key);
4221     }
4222 
4223     @Override
4224     public Entry<K, V> floorEntry(K key) {
4225       return forward().ceilingEntry(key);
4226     }
4227 
4228     @Override
4229     public K floorKey(K key) {
4230       return forward().ceilingKey(key);
4231     }
4232 
4233     @Override
4234     public Entry<K, V> ceilingEntry(K key) {
4235       return forward().floorEntry(key);
4236     }
4237 
4238     @Override
4239     public K ceilingKey(K key) {
4240       return forward().floorKey(key);
4241     }
4242 
4243     @Override
4244     public Entry<K, V> higherEntry(K key) {
4245       return forward().lowerEntry(key);
4246     }
4247 
4248     @Override
4249     public K higherKey(K key) {
4250       return forward().lowerKey(key);
4251     }
4252 
4253     @Override
4254     public Entry<K, V> firstEntry() {
4255       return forward().lastEntry();
4256     }
4257 
4258     @Override
4259     public Entry<K, V> lastEntry() {
4260       return forward().firstEntry();
4261     }
4262 
4263     @Override
4264     public Entry<K, V> pollFirstEntry() {
4265       return forward().pollLastEntry();
4266     }
4267 
4268     @Override
4269     public Entry<K, V> pollLastEntry() {
4270       return forward().pollFirstEntry();
4271     }
4272 
4273     @Override
4274     public NavigableMap<K, V> descendingMap() {
4275       return forward();
4276     }
4277 
4278     private transient Set<Entry<K, V>> entrySet;
4279 
4280     @Override
4281     public Set<Entry<K, V>> entrySet() {
4282       Set<Entry<K, V>> result = entrySet;
4283       return (result == null) ? entrySet = createEntrySet() : result;
4284     }
4285 
4286     abstract Iterator<Entry<K, V>> entryIterator();
4287 
4288     Set<Entry<K, V>> createEntrySet() {
4289       @WeakOuter
4290       class EntrySetImpl extends EntrySet<K, V> {
4291         @Override
4292         Map<K, V> map() {
4293           return DescendingMap.this;
4294         }
4295 
4296         @Override
4297         public Iterator<Entry<K, V>> iterator() {
4298           return entryIterator();
4299         }
4300       }
4301       return new EntrySetImpl();
4302     }
4303 
4304     @Override
4305     public Set<K> keySet() {
4306       return navigableKeySet();
4307     }
4308 
4309     private transient NavigableSet<K> navigableKeySet;
4310 
4311     @Override
4312     public NavigableSet<K> navigableKeySet() {
4313       NavigableSet<K> result = navigableKeySet;
4314       return (result == null) ? navigableKeySet = new NavigableKeySet<>(this) : result;
4315     }
4316 
4317     @Override
4318     public NavigableSet<K> descendingKeySet() {
4319       return forward().navigableKeySet();
4320     }
4321 
4322     @Override
4323     public NavigableMap<K, V> subMap(
4324         K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
4325       return forward().subMap(toKey, toInclusive, fromKey, fromInclusive).descendingMap();
4326     }
4327 
4328     @Override
4329     public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
4330       return forward().tailMap(toKey, inclusive).descendingMap();
4331     }
4332 
4333     @Override
4334     public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
4335       return forward().headMap(fromKey, inclusive).descendingMap();
4336     }
4337 
4338     @Override
4339     public SortedMap<K, V> subMap(K fromKey, K toKey) {
4340       return subMap(fromKey, true, toKey, false);
4341     }
4342 
4343     @Override
4344     public SortedMap<K, V> headMap(K toKey) {
4345       return headMap(toKey, false);
4346     }
4347 
4348     @Override
4349     public SortedMap<K, V> tailMap(K fromKey) {
4350       return tailMap(fromKey, true);
4351     }
4352 
4353     @Override
4354     public Collection<V> values() {
4355       return new Values<>(this);
4356     }
4357 
4358     @Override
4359     public String toString() {
4360       return standardToString();
4361     }
4362   }
4363 
4364   /**
4365    * Returns a map from the ith element of list to i.
4366    */
4367   static <E> ImmutableMap<E, Integer> indexMap(Collection<E> list) {
4368     ImmutableMap.Builder<E, Integer> builder = new ImmutableMap.Builder<>(list.size());
4369     int i = 0;
4370     for (E e : list) {
4371       builder.put(e, i++);
4372     }
4373     return builder.build();
4374   }
4375 
4376   /**
4377    * Returns a view of the portion of {@code map} whose keys are contained by {@code range}.
4378    *
4379    * <p>This method delegates to the appropriate methods of {@link NavigableMap} (namely
4380    * {@link NavigableMap#subMap(Object, boolean, Object, boolean) subMap()},
4381    * {@link NavigableMap#tailMap(Object, boolean) tailMap()}, and
4382    * {@link NavigableMap#headMap(Object, boolean) headMap()}) to actually construct the view.
4383    * Consult these methods for a full description of the returned view's behavior.
4384    *
4385    * <p><b>Warning:</b> {@code Range}s always represent a range of values using the values' natural
4386    * ordering. {@code NavigableMap} on the other hand can specify a custom ordering via a
4387    * {@link Comparator}, which can violate the natural ordering. Using this method (or in general
4388    * using {@code Range}) with unnaturally-ordered maps can lead to unexpected and undefined
4389    * behavior.
4390    *
4391    * @since 20.0
4392    */
4393   @Beta
4394   @GwtIncompatible // NavigableMap
4395   public static <K extends Comparable<? super K>, V> NavigableMap<K, V> subMap(
4396       NavigableMap<K, V> map, Range<K> range) {
4397     if (map.comparator() != null
4398         && map.comparator() != Ordering.natural()
4399         && range.hasLowerBound()
4400         && range.hasUpperBound()) {
4401       checkArgument(
4402           map.comparator().compare(range.lowerEndpoint(), range.upperEndpoint()) <= 0,
4403           "map is using a custom comparator which is inconsistent with the natural ordering.");
4404     }
4405     if (range.hasLowerBound() && range.hasUpperBound()) {
4406       return map.subMap(
4407           range.lowerEndpoint(),
4408           range.lowerBoundType() == BoundType.CLOSED,
4409           range.upperEndpoint(),
4410           range.upperBoundType() == BoundType.CLOSED);
4411     } else if (range.hasLowerBound()) {
4412       return map.tailMap(range.lowerEndpoint(), range.lowerBoundType() == BoundType.CLOSED);
4413     } else if (range.hasUpperBound()) {
4414       return map.headMap(range.upperEndpoint(), range.upperBoundType() == BoundType.CLOSED);
4415     }
4416     return checkNotNull(map);
4417   }
4418 }