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