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