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