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