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