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