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