001    /*
002     * Copyright (C) 2007 The Guava Authors
003     *
004     * Licensed under the Apache License, Version 2.0 (the "License");
005     * you may not use this file except in compliance with the License.
006     * You may obtain a copy of the License at
007     *
008     * http://www.apache.org/licenses/LICENSE-2.0
009     *
010     * Unless required by applicable law or agreed to in writing, software
011     * distributed under the License is distributed on an "AS IS" BASIS,
012     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013     * See the License for the specific language governing permissions and
014     * limitations under the License.
015     */
016    
017    package com.google.common.collect;
018    
019    import static com.google.common.base.Preconditions.checkArgument;
020    import static com.google.common.base.Preconditions.checkNotNull;
021    
022    import com.google.common.annotations.Beta;
023    import com.google.common.annotations.GwtCompatible;
024    import com.google.common.annotations.GwtIncompatible;
025    import com.google.common.base.Equivalence;
026    import com.google.common.base.Equivalences;
027    import com.google.common.base.Function;
028    import com.google.common.base.Joiner.MapJoiner;
029    import com.google.common.base.Objects;
030    import com.google.common.base.Preconditions;
031    import com.google.common.base.Predicate;
032    import com.google.common.base.Predicates;
033    import com.google.common.collect.MapDifference.ValueDifference;
034    import com.google.common.primitives.Ints;
035    
036    import java.io.Serializable;
037    import java.util.AbstractCollection;
038    import java.util.AbstractMap;
039    import java.util.AbstractSet;
040    import java.util.Collection;
041    import java.util.Collections;
042    import java.util.Comparator;
043    import java.util.EnumMap;
044    import java.util.Enumeration;
045    import java.util.HashMap;
046    import java.util.IdentityHashMap;
047    import java.util.Iterator;
048    import java.util.LinkedHashMap;
049    import java.util.Map;
050    import java.util.Map.Entry;
051    import java.util.NavigableMap;
052    import java.util.NavigableSet;
053    import java.util.Properties;
054    import java.util.Set;
055    import java.util.SortedMap;
056    import java.util.SortedSet;
057    import java.util.TreeMap;
058    import java.util.concurrent.ConcurrentMap;
059    
060    import javax.annotation.Nullable;
061    
062    /**
063     * Static utility methods pertaining to {@link Map} instances (including instances of
064     * {@link SortedMap}, {@link BiMap}, etc.). Also see this class's counterparts
065     * {@link Lists}, {@link Sets} and {@link Queues}.
066     *
067     * <p>See the Guava User Guide article on <a href=
068     * "http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Maps">
069     * {@code Maps}</a>.
070     *
071     * @author Kevin Bourrillion
072     * @author Mike Bostock
073     * @author Isaac Shum
074     * @author Louis Wasserman
075     * @since 2.0 (imported from Google Collections Library)
076     */
077    @GwtCompatible(emulated = true)
078    public final class Maps {
079      private Maps() {}
080    
081      /**
082       * Creates a <i>mutable</i>, empty {@code HashMap} instance.
083       *
084       * <p><b>Note:</b> if mutability is not required, use {@link
085       * ImmutableMap#of()} instead.
086       *
087       * <p><b>Note:</b> if {@code K} is an {@code enum} type, use {@link
088       * #newEnumMap} instead.
089       *
090       * @return a new, empty {@code HashMap}
091       */
092      public static <K, V> HashMap<K, V> newHashMap() {
093        return new HashMap<K, V>();
094      }
095    
096      /**
097       * Creates a {@code HashMap} instance, with a high enough "initial capacity"
098       * that it <i>should</i> hold {@code expectedSize} elements without growth.
099       * This behavior cannot be broadly guaranteed, but it is observed to be true
100       * for OpenJDK 1.6. It also can't be guaranteed that the method isn't
101       * inadvertently <i>oversizing</i> the returned map.
102       *
103       * @param expectedSize the number of elements you expect to add to the
104       *        returned map
105       * @return a new, empty {@code HashMap} with enough capacity to hold {@code
106       *         expectedSize} elements without resizing
107       * @throws IllegalArgumentException if {@code expectedSize} is negative
108       */
109      public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(
110          int expectedSize) {
111        return new HashMap<K, V>(capacity(expectedSize));
112      }
113    
114      /**
115       * Returns a capacity that is sufficient to keep the map from being resized as
116       * long as it grows no larger than expectedSize and the load factor is >= its
117       * default (0.75).
118       */
119      static int capacity(int expectedSize) {
120        if (expectedSize < 3) {
121          checkArgument(expectedSize >= 0);
122          return expectedSize + 1;
123        }
124        if (expectedSize < Ints.MAX_POWER_OF_TWO) {
125          return expectedSize + expectedSize / 3;
126        }
127        return Integer.MAX_VALUE; // any large value
128      }
129    
130      /**
131       * Creates a <i>mutable</i> {@code HashMap} instance with the same mappings as
132       * the specified map.
133       *
134       * <p><b>Note:</b> if mutability is not required, use {@link
135       * ImmutableMap#copyOf(Map)} instead.
136       *
137       * <p><b>Note:</b> if {@code K} is an {@link Enum} type, use {@link
138       * #newEnumMap} instead.
139       *
140       * @param map the mappings to be placed in the new map
141       * @return a new {@code HashMap} initialized with the mappings from {@code
142       *         map}
143       */
144      public static <K, V> HashMap<K, V> newHashMap(
145          Map<? extends K, ? extends V> map) {
146        return new HashMap<K, V>(map);
147      }
148    
149      /**
150       * Creates a <i>mutable</i>, empty, insertion-ordered {@code LinkedHashMap}
151       * instance.
152       *
153       * <p><b>Note:</b> if mutability is not required, use {@link
154       * ImmutableMap#of()} instead.
155       *
156       * @return a new, empty {@code LinkedHashMap}
157       */
158      public static <K, V> LinkedHashMap<K, V> newLinkedHashMap() {
159        return new LinkedHashMap<K, V>();
160      }
161    
162      /**
163       * Creates a <i>mutable</i>, insertion-ordered {@code LinkedHashMap} instance
164       * with the same mappings as the specified map.
165       *
166       * <p><b>Note:</b> if mutability is not required, use {@link
167       * ImmutableMap#copyOf(Map)} instead.
168       *
169       * @param map the mappings to be placed in the new map
170       * @return a new, {@code LinkedHashMap} initialized with the mappings from
171       *         {@code map}
172       */
173      public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(
174          Map<? extends K, ? extends V> map) {
175        return new LinkedHashMap<K, V>(map);
176      }
177    
178      /**
179       * Returns a general-purpose instance of {@code ConcurrentMap}, which supports
180       * all optional operations of the ConcurrentMap interface. It does not permit
181       * null keys or values. It is serializable.
182       *
183       * <p>This is currently accomplished by calling {@link MapMaker#makeMap()}.
184       *
185       * <p>It is preferable to use {@code MapMaker} directly (rather than through
186       * this method), as it presents numerous useful configuration options,
187       * such as the concurrency level, load factor, key/value reference types,
188       * and value computation.
189       *
190       * @return a new, empty {@code ConcurrentMap}
191       * @since 3.0
192       */
193      public static <K, V> ConcurrentMap<K, V> newConcurrentMap() {
194        return new MapMaker().<K, V>makeMap();
195      }
196    
197      /**
198       * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the natural
199       * ordering of its elements.
200       *
201       * <p><b>Note:</b> if mutability is not required, use {@link
202       * ImmutableSortedMap#of()} instead.
203       *
204       * @return a new, empty {@code TreeMap}
205       */
206      public static <K extends Comparable, V> TreeMap<K, V> newTreeMap() {
207        return new TreeMap<K, V>();
208      }
209    
210      /**
211       * Creates a <i>mutable</i> {@code TreeMap} instance with the same mappings as
212       * the specified map and using the same ordering as the specified map.
213       *
214       * <p><b>Note:</b> if mutability is not required, use {@link
215       * ImmutableSortedMap#copyOfSorted(SortedMap)} instead.
216       *
217       * @param map the sorted map whose mappings are to be placed in the new map
218       *        and whose comparator is to be used to sort the new map
219       * @return a new {@code TreeMap} initialized with the mappings from {@code
220       *         map} and using the comparator of {@code map}
221       */
222      public static <K, V> TreeMap<K, V> newTreeMap(SortedMap<K, ? extends V> map) {
223        return new TreeMap<K, V>(map);
224      }
225    
226      /**
227       * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the given
228       * comparator.
229       *
230       * <p><b>Note:</b> if mutability is not required, use {@code
231       * ImmutableSortedMap.orderedBy(comparator).build()} instead.
232       *
233       * @param comparator the comparator to sort the keys with
234       * @return a new, empty {@code TreeMap}
235       */
236      public static <C, K extends C, V> TreeMap<K, V> newTreeMap(
237          @Nullable Comparator<C> comparator) {
238        // Ideally, the extra type parameter "C" shouldn't be necessary. It is a
239        // work-around of a compiler type inference quirk that prevents the
240        // following code from being compiled:
241        // Comparator<Class<?>> comparator = null;
242        // Map<Class<? extends Throwable>, String> map = newTreeMap(comparator);
243        return new TreeMap<K, V>(comparator);
244      }
245    
246      /**
247       * Creates an {@code EnumMap} instance.
248       *
249       * @param type the key type for this map
250       * @return a new, empty {@code EnumMap}
251       */
252      public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(Class<K> type) {
253        return new EnumMap<K, V>(checkNotNull(type));
254      }
255    
256      /**
257       * Creates an {@code EnumMap} with the same mappings as the specified map.
258       *
259       * @param map the map from which to initialize this {@code EnumMap}
260       * @return a new {@code EnumMap} initialized with the mappings from {@code
261       *         map}
262       * @throws IllegalArgumentException if {@code m} is not an {@code EnumMap}
263       *         instance and contains no mappings
264       */
265      public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(
266          Map<K, ? extends V> map) {
267        return new EnumMap<K, V>(map);
268      }
269    
270      /**
271       * Creates an {@code IdentityHashMap} instance.
272       *
273       * @return a new, empty {@code IdentityHashMap}
274       */
275      public static <K, V> IdentityHashMap<K, V> newIdentityHashMap() {
276        return new IdentityHashMap<K, V>();
277      }
278    
279      /**
280       * Computes the difference between two maps. This difference is an immutable
281       * snapshot of the state of the maps at the time this method is called. It
282       * will never change, even if the maps change at a later time.
283       *
284       * <p>Since this method uses {@code HashMap} instances internally, the keys of
285       * the supplied maps must be well-behaved with respect to
286       * {@link Object#equals} and {@link Object#hashCode}.
287       *
288       * <p><b>Note:</b>If you only need to know whether two maps have the same
289       * mappings, call {@code left.equals(right)} instead of this method.
290       *
291       * @param left the map to treat as the "left" map for purposes of comparison
292       * @param right the map to treat as the "right" map for purposes of comparison
293       * @return the difference between the two maps
294       */
295      @SuppressWarnings("unchecked")
296      public static <K, V> MapDifference<K, V> difference(
297          Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) {
298        if (left instanceof SortedMap) {
299          SortedMap<K, ? extends V> sortedLeft = (SortedMap<K, ? extends V>) left;
300          SortedMapDifference<K, V> result = difference(sortedLeft, right);
301          return result;
302        }
303        return difference(left, right, Equivalences.equals());
304      }
305    
306      /**
307       * Computes the difference between two maps. This difference is an immutable
308       * snapshot of the state of the maps at the time this method is called. It
309       * will never change, even if the maps change at a later time.
310       *
311       * <p>Values are compared using a provided equivalence, in the case of
312       * equality, the value on the 'left' is returned in the difference.
313       *
314       * <p>Since this method uses {@code HashMap} instances internally, the keys of
315       * the supplied maps must be well-behaved with respect to
316       * {@link Object#equals} and {@link Object#hashCode}.
317       *
318       * @param left the map to treat as the "left" map for purposes of comparison
319       * @param right the map to treat as the "right" map for purposes of comparison
320       * @param valueEquivalence the equivalence relationship to use to compare
321       *    values
322       * @return the difference between the two maps
323       * @since 10.0
324       */
325      @Beta
326      public static <K, V> MapDifference<K, V> difference(
327          Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right,
328          Equivalence<? super V> valueEquivalence) {
329        Preconditions.checkNotNull(valueEquivalence);
330    
331        Map<K, V> onlyOnLeft = newHashMap();
332        Map<K, V> onlyOnRight = new HashMap<K, V>(right); // will whittle it down
333        Map<K, V> onBoth = newHashMap();
334        Map<K, MapDifference.ValueDifference<V>> differences = newHashMap();
335        boolean eq = true;
336    
337        for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
338          K leftKey = entry.getKey();
339          V leftValue = entry.getValue();
340          if (right.containsKey(leftKey)) {
341            V rightValue = onlyOnRight.remove(leftKey);
342            if (valueEquivalence.equivalent(leftValue, rightValue)) {
343              onBoth.put(leftKey, leftValue);
344            } else {
345              eq = false;
346              differences.put(
347                  leftKey, ValueDifferenceImpl.create(leftValue, rightValue));
348            }
349          } else {
350            eq = false;
351            onlyOnLeft.put(leftKey, leftValue);
352          }
353        }
354    
355        boolean areEqual = eq && onlyOnRight.isEmpty();
356        return mapDifference(
357            areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
358      }
359    
360      private static <K, V> MapDifference<K, V> mapDifference(boolean areEqual,
361          Map<K, V> onlyOnLeft, Map<K, V> onlyOnRight, Map<K, V> onBoth,
362          Map<K, ValueDifference<V>> differences) {
363        return new MapDifferenceImpl<K, V>(areEqual,
364            Collections.unmodifiableMap(onlyOnLeft),
365            Collections.unmodifiableMap(onlyOnRight),
366            Collections.unmodifiableMap(onBoth),
367            Collections.unmodifiableMap(differences));
368      }
369    
370      static class MapDifferenceImpl<K, V> implements MapDifference<K, V> {
371        final boolean areEqual;
372        final Map<K, V> onlyOnLeft;
373        final Map<K, V> onlyOnRight;
374        final Map<K, V> onBoth;
375        final Map<K, ValueDifference<V>> differences;
376    
377        MapDifferenceImpl(boolean areEqual, Map<K, V> onlyOnLeft,
378            Map<K, V> onlyOnRight, Map<K, V> onBoth,
379            Map<K, ValueDifference<V>> differences) {
380          this.areEqual = areEqual;
381          this.onlyOnLeft = onlyOnLeft;
382          this.onlyOnRight = onlyOnRight;
383          this.onBoth = onBoth;
384          this.differences = differences;
385        }
386    
387        @Override
388        public boolean areEqual() {
389          return areEqual;
390        }
391    
392        @Override
393        public Map<K, V> entriesOnlyOnLeft() {
394          return onlyOnLeft;
395        }
396    
397        @Override
398        public Map<K, V> entriesOnlyOnRight() {
399          return onlyOnRight;
400        }
401    
402        @Override
403        public Map<K, V> entriesInCommon() {
404          return onBoth;
405        }
406    
407        @Override
408        public Map<K, ValueDifference<V>> entriesDiffering() {
409          return differences;
410        }
411    
412        @Override public boolean equals(Object object) {
413          if (object == this) {
414            return true;
415          }
416          if (object instanceof MapDifference) {
417            MapDifference<?, ?> other = (MapDifference<?, ?>) object;
418            return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft())
419                && entriesOnlyOnRight().equals(other.entriesOnlyOnRight())
420                && entriesInCommon().equals(other.entriesInCommon())
421                && entriesDiffering().equals(other.entriesDiffering());
422          }
423          return false;
424        }
425    
426        @Override public int hashCode() {
427          return Objects.hashCode(entriesOnlyOnLeft(), entriesOnlyOnRight(),
428              entriesInCommon(), entriesDiffering());
429        }
430    
431        @Override public String toString() {
432          if (areEqual) {
433            return "equal";
434          }
435    
436          StringBuilder result = new StringBuilder("not equal");
437          if (!onlyOnLeft.isEmpty()) {
438            result.append(": only on left=").append(onlyOnLeft);
439          }
440          if (!onlyOnRight.isEmpty()) {
441            result.append(": only on right=").append(onlyOnRight);
442          }
443          if (!differences.isEmpty()) {
444            result.append(": value differences=").append(differences);
445          }
446          return result.toString();
447        }
448      }
449    
450      static class ValueDifferenceImpl<V>
451          implements MapDifference.ValueDifference<V> {
452        private final V left;
453        private final V right;
454    
455        static <V> ValueDifference<V> create(@Nullable V left, @Nullable V right) {
456          return new ValueDifferenceImpl<V>(left, right);
457        }
458    
459        private ValueDifferenceImpl(@Nullable V left, @Nullable V right) {
460          this.left = left;
461          this.right = right;
462        }
463    
464        @Override
465        public V leftValue() {
466          return left;
467        }
468    
469        @Override
470        public V rightValue() {
471          return right;
472        }
473    
474        @Override public boolean equals(@Nullable Object object) {
475          if (object instanceof MapDifference.ValueDifference<?>) {
476            MapDifference.ValueDifference<?> that =
477                (MapDifference.ValueDifference<?>) object;
478            return Objects.equal(this.left, that.leftValue())
479                && Objects.equal(this.right, that.rightValue());
480          }
481          return false;
482        }
483    
484        @Override public int hashCode() {
485          return Objects.hashCode(left, right);
486        }
487    
488        @Override public String toString() {
489          return "(" + left + ", " + right + ")";
490        }
491      }
492    
493      /**
494       * Computes the difference between two sorted maps, using the comparator of
495       * the left map, or {@code Ordering.natural()} if the left map uses the
496       * natural ordering of its elements. This difference is an immutable snapshot
497       * of the state of the maps at the time this method is called. It will never
498       * change, even if the maps change at a later time.
499       *
500       * <p>Since this method uses {@code TreeMap} instances internally, the keys of
501       * the right map must all compare as distinct according to the comparator
502       * of the left map.
503       *
504       * <p><b>Note:</b>If you only need to know whether two sorted maps have the
505       * same mappings, call {@code left.equals(right)} instead of this method.
506       *
507       * @param left the map to treat as the "left" map for purposes of comparison
508       * @param right the map to treat as the "right" map for purposes of comparison
509       * @return the difference between the two maps
510       * @since 11.0
511       */
512      public static <K, V> SortedMapDifference<K, V> difference(
513          SortedMap<K, ? extends V> left, Map<? extends K, ? extends V> right) {
514        checkNotNull(left);
515        checkNotNull(right);
516        Comparator<? super K> comparator = orNaturalOrder(left.comparator());
517        SortedMap<K, V> onlyOnLeft = Maps.newTreeMap(comparator);
518        SortedMap<K, V> onlyOnRight = Maps.newTreeMap(comparator);
519        onlyOnRight.putAll(right); // will whittle it down
520        SortedMap<K, V> onBoth = Maps.newTreeMap(comparator);
521        SortedMap<K, MapDifference.ValueDifference<V>> differences =
522            Maps.newTreeMap(comparator);
523        boolean eq = true;
524    
525        for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
526          K leftKey = entry.getKey();
527          V leftValue = entry.getValue();
528          if (right.containsKey(leftKey)) {
529            V rightValue = onlyOnRight.remove(leftKey);
530            if (Objects.equal(leftValue, rightValue)) {
531              onBoth.put(leftKey, leftValue);
532            } else {
533              eq = false;
534              differences.put(
535                  leftKey, ValueDifferenceImpl.create(leftValue, rightValue));
536            }
537          } else {
538            eq = false;
539            onlyOnLeft.put(leftKey, leftValue);
540          }
541        }
542    
543        boolean areEqual = eq && onlyOnRight.isEmpty();
544        return sortedMapDifference(
545            areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
546      }
547    
548      private static <K, V> SortedMapDifference<K, V> sortedMapDifference(
549          boolean areEqual, SortedMap<K, V> onlyOnLeft, SortedMap<K, V> onlyOnRight,
550          SortedMap<K, V> onBoth, SortedMap<K, ValueDifference<V>> differences) {
551        return new SortedMapDifferenceImpl<K, V>(areEqual,
552            Collections.unmodifiableSortedMap(onlyOnLeft),
553            Collections.unmodifiableSortedMap(onlyOnRight),
554            Collections.unmodifiableSortedMap(onBoth),
555            Collections.unmodifiableSortedMap(differences));
556      }
557    
558      static class SortedMapDifferenceImpl<K, V> extends MapDifferenceImpl<K, V>
559          implements SortedMapDifference<K, V> {
560        SortedMapDifferenceImpl(boolean areEqual, SortedMap<K, V> onlyOnLeft,
561            SortedMap<K, V> onlyOnRight, SortedMap<K, V> onBoth,
562            SortedMap<K, ValueDifference<V>> differences) {
563          super(areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
564        }
565    
566        @Override public SortedMap<K, ValueDifference<V>> entriesDiffering() {
567          return (SortedMap<K, ValueDifference<V>>) super.entriesDiffering();
568        }
569    
570        @Override public SortedMap<K, V> entriesInCommon() {
571          return (SortedMap<K, V>) super.entriesInCommon();
572        }
573    
574        @Override public SortedMap<K, V> entriesOnlyOnLeft() {
575          return (SortedMap<K, V>) super.entriesOnlyOnLeft();
576        }
577    
578        @Override public SortedMap<K, V> entriesOnlyOnRight() {
579          return (SortedMap<K, V>) super.entriesOnlyOnRight();
580        }
581      }
582    
583      /**
584       * Returns the specified comparator if not null; otherwise returns {@code
585       * Ordering.natural()}. This method is an abomination of generics; the only
586       * purpose of this method is to contain the ugly type-casting in one place.
587       */
588      @SuppressWarnings("unchecked")
589      static <E> Comparator<? super E> orNaturalOrder(
590          @Nullable Comparator<? super E> comparator) {
591        if (comparator != null) { // can't use ? : because of javac bug 5080917
592          return comparator;
593        }
594        return (Comparator<E>) Ordering.natural();
595      }
596      /**
597       * Returns an immutable map for which the {@link Map#values} are the given
598       * elements in the given order, and each key is the product of invoking a
599       * supplied function on its corresponding value.
600       *
601       * @param values the values to use when constructing the {@code Map}
602       * @param keyFunction the function used to produce the key for each value
603       * @return a map mapping the result of evaluating the function {@code
604       *         keyFunction} on each value in the input collection to that value
605       * @throws IllegalArgumentException if {@code keyFunction} produces the same
606       *         key for more than one value in the input collection
607       * @throws NullPointerException if any elements of {@code values} is null, or
608       *         if {@code keyFunction} produces {@code null} for any value
609       */
610      public static <K, V> ImmutableMap<K, V> uniqueIndex(
611          Iterable<V> values, Function<? super V, K> keyFunction) {
612        return uniqueIndex(values.iterator(), keyFunction);
613      }
614    
615      /**
616       * Returns an immutable map for which the {@link Map#values} are the given
617       * elements in the given order, and each key is the product of invoking a
618       * supplied function on its corresponding value.
619       *
620       * @param values the values to use when constructing the {@code Map}
621       * @param keyFunction the function used to produce the key for each value
622       * @return a map mapping the result of evaluating the function {@code
623       *         keyFunction} on each value in the input collection to that value
624       * @throws IllegalArgumentException if {@code keyFunction} produces the same
625       *         key for more than one value in the input collection
626       * @throws NullPointerException if any elements of {@code values} is null, or
627       *         if {@code keyFunction} produces {@code null} for any value
628       * @since 10.0
629       */
630      public static <K, V> ImmutableMap<K, V> uniqueIndex(
631          Iterator<V> values, Function<? super V, K> keyFunction) {
632        checkNotNull(keyFunction);
633        ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
634        while (values.hasNext()) {
635          V value = values.next();
636          builder.put(keyFunction.apply(value), value);
637        }
638        return builder.build();
639      }
640    
641      /**
642       * Creates an {@code ImmutableMap<String, String>} from a {@code Properties}
643       * instance. Properties normally derive from {@code Map<Object, Object>}, but
644       * they typically contain strings, which is awkward. This method lets you get
645       * a plain-old-{@code Map} out of a {@code Properties}.
646       *
647       * @param properties a {@code Properties} object to be converted
648       * @return an immutable map containing all the entries in {@code properties}
649       * @throws ClassCastException if any key in {@code Properties} is not a {@code
650       *         String}
651       * @throws NullPointerException if any key or value in {@code Properties} is
652       *         null
653       */
654      @GwtIncompatible("java.util.Properties")
655      public static ImmutableMap<String, String> fromProperties(
656          Properties properties) {
657        ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
658    
659        for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements();) {
660          String key = (String) e.nextElement();
661          builder.put(key, properties.getProperty(key));
662        }
663    
664        return builder.build();
665      }
666    
667      /**
668       * Returns an immutable map entry with the specified key and value. The {@link
669       * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
670       *
671       * <p>The returned entry is serializable.
672       *
673       * @param key the key to be associated with the returned entry
674       * @param value the value to be associated with the returned entry
675       */
676      @GwtCompatible(serializable = true)
677      public static <K, V> Entry<K, V> immutableEntry(
678          @Nullable K key, @Nullable V value) {
679        return new ImmutableEntry<K, V>(key, value);
680      }
681    
682      /**
683       * Returns an unmodifiable view of the specified set of entries. The {@link
684       * Entry#setValue} operation throws an {@link UnsupportedOperationException},
685       * as do any operations that would modify the returned set.
686       *
687       * @param entrySet the entries for which to return an unmodifiable view
688       * @return an unmodifiable view of the entries
689       */
690      static <K, V> Set<Entry<K, V>> unmodifiableEntrySet(
691          Set<Entry<K, V>> entrySet) {
692        return new UnmodifiableEntrySet<K, V>(
693            Collections.unmodifiableSet(entrySet));
694      }
695    
696      /**
697       * Returns an unmodifiable view of the specified map entry. The {@link
698       * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
699       * This also has the side-effect of redefining {@code equals} to comply with
700       * the Entry contract, to avoid a possible nefarious implementation of equals.
701       *
702       * @param entry the entry for which to return an unmodifiable view
703       * @return an unmodifiable view of the entry
704       */
705      static <K, V> Entry<K, V> unmodifiableEntry(final Entry<K, V> entry) {
706        checkNotNull(entry);
707        return new AbstractMapEntry<K, V>() {
708          @Override public K getKey() {
709            return entry.getKey();
710          }
711    
712          @Override public V getValue() {
713            return entry.getValue();
714          }
715        };
716      }
717    
718      /** @see Multimaps#unmodifiableEntries */
719      static class UnmodifiableEntries<K, V>
720          extends ForwardingCollection<Entry<K, V>> {
721        private final Collection<Entry<K, V>> entries;
722    
723        UnmodifiableEntries(Collection<Entry<K, V>> entries) {
724          this.entries = entries;
725        }
726    
727        @Override protected Collection<Entry<K, V>> delegate() {
728          return entries;
729        }
730    
731        @Override public Iterator<Entry<K, V>> iterator() {
732          final Iterator<Entry<K, V>> delegate = super.iterator();
733          return new ForwardingIterator<Entry<K, V>>() {
734            @Override public Entry<K, V> next() {
735              return unmodifiableEntry(super.next());
736            }
737    
738            @Override public void remove() {
739              throw new UnsupportedOperationException();
740            }
741    
742            @Override protected Iterator<Entry<K, V>> delegate() {
743              return delegate;
744            }
745          };
746        }
747    
748        // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
749    
750        @Override public boolean add(Entry<K, V> element) {
751          throw new UnsupportedOperationException();
752        }
753    
754        @Override public boolean addAll(
755            Collection<? extends Entry<K, V>> collection) {
756          throw new UnsupportedOperationException();
757        }
758    
759        @Override public void clear() {
760          throw new UnsupportedOperationException();
761        }
762    
763        @Override public boolean remove(Object object) {
764          throw new UnsupportedOperationException();
765        }
766    
767        @Override public boolean removeAll(Collection<?> collection) {
768          throw new UnsupportedOperationException();
769        }
770    
771        @Override public boolean retainAll(Collection<?> collection) {
772          throw new UnsupportedOperationException();
773        }
774    
775        @Override public Object[] toArray() {
776          return standardToArray();
777        }
778    
779        @Override public <T> T[] toArray(T[] array) {
780          return standardToArray(array);
781        }
782      }
783    
784      /** @see Maps#unmodifiableEntrySet(Set) */
785      static class UnmodifiableEntrySet<K, V>
786          extends UnmodifiableEntries<K, V> implements Set<Entry<K, V>> {
787        UnmodifiableEntrySet(Set<Entry<K, V>> entries) {
788          super(entries);
789        }
790    
791        // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
792    
793        @Override public boolean equals(@Nullable Object object) {
794          return Sets.equalsImpl(this, object);
795        }
796    
797        @Override public int hashCode() {
798          return Sets.hashCodeImpl(this);
799        }
800      }
801    
802      /**
803       * Returns a synchronized (thread-safe) bimap backed by the specified bimap.
804       * In order to guarantee serial access, it is critical that <b>all</b> access
805       * to the backing bimap is accomplished through the returned bimap.
806       *
807       * <p>It is imperative that the user manually synchronize on the returned map
808       * when accessing any of its collection views: <pre>   {@code
809       *
810       *   BiMap<Long, String> map = Maps.synchronizedBiMap(
811       *       HashBiMap.<Long, String>create());
812       *   ...
813       *   Set<Long> set = map.keySet();  // Needn't be in synchronized block
814       *   ...
815       *   synchronized (map) {  // Synchronizing on map, not set!
816       *     Iterator<Long> it = set.iterator(); // Must be in synchronized block
817       *     while (it.hasNext()) {
818       *       foo(it.next());
819       *     }
820       *   }}</pre>
821       *
822       * Failure to follow this advice may result in non-deterministic behavior.
823       *
824       * <p>The returned bimap will be serializable if the specified bimap is
825       * serializable.
826       *
827       * @param bimap the bimap to be wrapped in a synchronized view
828       * @return a sychronized view of the specified bimap
829       */
830      public static <K, V> BiMap<K, V> synchronizedBiMap(BiMap<K, V> bimap) {
831        return Synchronized.biMap(bimap, null);
832      }
833    
834      /**
835       * Returns an unmodifiable view of the specified bimap. This method allows
836       * modules to provide users with "read-only" access to internal bimaps. Query
837       * operations on the returned bimap "read through" to the specified bimap, and
838       * attempts to modify the returned map, whether direct or via its collection
839       * views, result in an {@code UnsupportedOperationException}.
840       *
841       * <p>The returned bimap will be serializable if the specified bimap is
842       * serializable.
843       *
844       * @param bimap the bimap for which an unmodifiable view is to be returned
845       * @return an unmodifiable view of the specified bimap
846       */
847      public static <K, V> BiMap<K, V> unmodifiableBiMap(
848          BiMap<? extends K, ? extends V> bimap) {
849        return new UnmodifiableBiMap<K, V>(bimap, null);
850      }
851    
852      /** @see Maps#unmodifiableBiMap(BiMap) */
853      private static class UnmodifiableBiMap<K, V>
854          extends ForwardingMap<K, V> implements BiMap<K, V>, Serializable {
855        final Map<K, V> unmodifiableMap;
856        final BiMap<? extends K, ? extends V> delegate;
857        transient BiMap<V, K> inverse;
858        transient Set<V> values;
859    
860        UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate,
861            @Nullable BiMap<V, K> inverse) {
862          unmodifiableMap = Collections.unmodifiableMap(delegate);
863          this.delegate = delegate;
864          this.inverse = inverse;
865        }
866    
867        @Override protected Map<K, V> delegate() {
868          return unmodifiableMap;
869        }
870    
871        @Override
872        public V forcePut(K key, V value) {
873          throw new UnsupportedOperationException();
874        }
875    
876        @Override
877        public BiMap<V, K> inverse() {
878          BiMap<V, K> result = inverse;
879          return (result == null)
880              ? inverse = new UnmodifiableBiMap<V, K>(delegate.inverse(), this)
881              : result;
882        }
883    
884        @Override public Set<V> values() {
885          Set<V> result = values;
886          return (result == null)
887              ? values = Collections.unmodifiableSet(delegate.values())
888              : result;
889        }
890    
891        private static final long serialVersionUID = 0;
892      }
893    
894      /**
895       * Returns a view of a map where each value is transformed by a function. All
896       * other properties of the map, such as iteration order, are left intact. For
897       * example, the code: <pre>   {@code
898       *
899       *   Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
900       *   Function<Integer, Double> sqrt =
901       *       new Function<Integer, Double>() {
902       *         public Double apply(Integer in) {
903       *           return Math.sqrt((int) in);
904       *         }
905       *       };
906       *   Map<String, Double> transformed = Maps.transformValues(map, sqrt);
907       *   System.out.println(transformed);}</pre>
908       *
909       * ... prints {@code {a=2.0, b=3.0}}.
910       *
911       * <p>Changes in the underlying map are reflected in this view. Conversely,
912       * this view supports removal operations, and these are reflected in the
913       * underlying map.
914       *
915       * <p>It's acceptable for the underlying map to contain null keys, and even
916       * null values provided that the function is capable of accepting null input.
917       * The transformed map might contain null values, if the function sometimes
918       * gives a null result.
919       *
920       * <p>The returned map is not thread-safe or serializable, even if the
921       * underlying map is.
922       *
923       * <p>The function is applied lazily, invoked when needed. This is necessary
924       * for the returned map to be a view, but it means that the function will be
925       * applied many times for bulk operations like {@link Map#containsValue} and
926       * {@code Map.toString()}. For this to perform well, {@code function} should
927       * be fast. To avoid lazy evaluation when the returned map doesn't need to be
928       * a view, copy the returned map into a new map of your choosing.
929       */
930      public static <K, V1, V2> Map<K, V2> transformValues(
931          Map<K, V1> fromMap, final Function<? super V1, V2> function) {
932        checkNotNull(function);
933        EntryTransformer<K, V1, V2> transformer =
934            new EntryTransformer<K, V1, V2>() {
935              @Override
936              public V2 transformEntry(K key, V1 value) {
937                return function.apply(value);
938              }
939            };
940        return transformEntries(fromMap, transformer);
941      }
942    
943      /**
944       * Returns a view of a sorted map where each value is transformed by a
945       * function. All other properties of the map, such as iteration order, are
946       * left intact. For example, the code: <pre>   {@code
947       *
948       *   SortedMap<String, Integer> map = ImmutableSortedMap.of("a", 4, "b", 9);
949       *   Function<Integer, Double> sqrt =
950       *       new Function<Integer, Double>() {
951       *         public Double apply(Integer in) {
952       *           return Math.sqrt((int) in);
953       *         }
954       *       };
955       *   SortedMap<String, Double> transformed =
956       *        Maps.transformSortedValues(map, sqrt);
957       *   System.out.println(transformed);}</pre>
958       *
959       * ... prints {@code {a=2.0, b=3.0}}.
960       *
961       * <p>Changes in the underlying map are reflected in this view. Conversely,
962       * this view supports removal operations, and these are reflected in the
963       * underlying map.
964       *
965       * <p>It's acceptable for the underlying map to contain null keys, and even
966       * null values provided that the function is capable of accepting null input.
967       * The transformed map might contain null values, if the function sometimes
968       * gives a null result.
969       *
970       * <p>The returned map is not thread-safe or serializable, even if the
971       * underlying map is.
972       *
973       * <p>The function is applied lazily, invoked when needed. This is necessary
974       * for the returned map to be a view, but it means that the function will be
975       * applied many times for bulk operations like {@link Map#containsValue} and
976       * {@code Map.toString()}. For this to perform well, {@code function} should
977       * be fast. To avoid lazy evaluation when the returned map doesn't need to be
978       * a view, copy the returned map into a new map of your choosing.
979       *
980       * @since 11.0
981       */
982      @Beta
983      public static <K, V1, V2> SortedMap<K, V2> transformValues(
984          SortedMap<K, V1> fromMap, final Function<? super V1, V2> function) {
985        checkNotNull(function);
986        EntryTransformer<K, V1, V2> transformer =
987            new EntryTransformer<K, V1, V2>() {
988              @Override
989              public V2 transformEntry(K key, V1 value) {
990                return function.apply(value);
991              }
992            };
993        return transformEntries(fromMap, transformer);
994      }
995    
996      /**
997       * Returns a view of a map whose values are derived from the original map's
998       * entries. In contrast to {@link #transformValues}, this method's
999       * entry-transformation logic may depend on the key as well as the value.
1000       *
1001       * <p>All other properties of the transformed map, such as iteration order,
1002       * are left intact. For example, the code: <pre>   {@code
1003       *
1004       *   Map<String, Boolean> options =
1005       *       ImmutableMap.of("verbose", true, "sort", false);
1006       *   EntryTransformer<String, Boolean, String> flagPrefixer =
1007       *       new EntryTransformer<String, Boolean, String>() {
1008       *         public String transformEntry(String key, Boolean value) {
1009       *           return value ? key : "no" + key;
1010       *         }
1011       *       };
1012       *   Map<String, String> transformed =
1013       *       Maps.transformEntries(options, flagPrefixer);
1014       *   System.out.println(transformed);}</pre>
1015       *
1016       * ... prints {@code {verbose=verbose, sort=nosort}}.
1017       *
1018       * <p>Changes in the underlying map are reflected in this view. Conversely,
1019       * this view supports removal operations, and these are reflected in the
1020       * underlying map.
1021       *
1022       * <p>It's acceptable for the underlying map to contain null keys and null
1023       * values provided that the transformer is capable of accepting null inputs.
1024       * The transformed map might contain null values if the transformer sometimes
1025       * gives a null result.
1026       *
1027       * <p>The returned map is not thread-safe or serializable, even if the
1028       * underlying map is.
1029       *
1030       * <p>The transformer is applied lazily, invoked when needed. This is
1031       * necessary for the returned map to be a view, but it means that the
1032       * transformer will be applied many times for bulk operations like {@link
1033       * Map#containsValue} and {@link Object#toString}. For this to perform well,
1034       * {@code transformer} should be fast. To avoid lazy evaluation when the
1035       * returned map doesn't need to be a view, copy the returned map into a new
1036       * map of your choosing.
1037       *
1038       * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1039       * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1040       * that {@code k2} is also of type {@code K}. Using an {@code
1041       * EntryTransformer} key type for which this may not hold, such as {@code
1042       * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1043       * the transformed map.
1044       *
1045       * @since 7.0
1046       */
1047      public static <K, V1, V2> Map<K, V2> transformEntries(
1048          Map<K, V1> fromMap,
1049          EntryTransformer<? super K, ? super V1, V2> transformer) {
1050        if (fromMap instanceof SortedMap) {
1051          return transformEntries((SortedMap<K, V1>) fromMap, transformer);
1052        }
1053        return new TransformedEntriesMap<K, V1, V2>(fromMap, transformer);
1054      }
1055    
1056      /**
1057       * Returns a view of a sorted map whose values are derived from the original
1058       * sorted map's entries. In contrast to {@link #transformValues}, this
1059       * method's entry-transformation logic may depend on the key as well as the
1060       * value.
1061       *
1062       * <p>All other properties of the transformed map, such as iteration order,
1063       * are left intact. For example, the code: <pre>   {@code
1064       *
1065       *   Map<String, Boolean> options =
1066       *       ImmutableSortedMap.of("verbose", true, "sort", false);
1067       *   EntryTransformer<String, Boolean, String> flagPrefixer =
1068       *       new EntryTransformer<String, Boolean, String>() {
1069       *         public String transformEntry(String key, Boolean value) {
1070       *           return value ? key : "yes" + key;
1071       *         }
1072       *       };
1073       *   SortedMap<String, String> transformed =
1074       *       LabsMaps.transformSortedEntries(options, flagPrefixer);
1075       *   System.out.println(transformed);}</pre>
1076       *
1077       * ... prints {@code {sort=yessort, verbose=verbose}}.
1078       *
1079       * <p>Changes in the underlying map are reflected in this view. Conversely,
1080       * this view supports removal operations, and these are reflected in the
1081       * underlying map.
1082       *
1083       * <p>It's acceptable for the underlying map to contain null keys and null
1084       * values provided that the transformer is capable of accepting null inputs.
1085       * The transformed map might contain null values if the transformer sometimes
1086       * gives a null result.
1087       *
1088       * <p>The returned map is not thread-safe or serializable, even if the
1089       * underlying map is.
1090       *
1091       * <p>The transformer is applied lazily, invoked when needed. This is
1092       * necessary for the returned map to be a view, but it means that the
1093       * transformer will be applied many times for bulk operations like {@link
1094       * Map#containsValue} and {@link Object#toString}. For this to perform well,
1095       * {@code transformer} should be fast. To avoid lazy evaluation when the
1096       * returned map doesn't need to be a view, copy the returned map into a new
1097       * map of your choosing.
1098       *
1099       * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1100       * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1101       * that {@code k2} is also of type {@code K}. Using an {@code
1102       * EntryTransformer} key type for which this may not hold, such as {@code
1103       * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1104       * the transformed map.
1105       *
1106       * @since 11.0
1107       */
1108      @Beta
1109      public static <K, V1, V2> SortedMap<K, V2> transformEntries(
1110          final SortedMap<K, V1> fromMap,
1111          EntryTransformer<? super K, ? super V1, V2> transformer) {
1112        return new TransformedEntriesSortedMap<K, V1, V2>(fromMap, transformer);
1113      }
1114    
1115      /**
1116       * A transformation of the value of a key-value pair, using both key and value
1117       * as inputs. To apply the transformation to a map, use
1118       * {@link Maps#transformEntries(Map, EntryTransformer)}.
1119       *
1120       * @param <K> the key type of the input and output entries
1121       * @param <V1> the value type of the input entry
1122       * @param <V2> the value type of the output entry
1123       * @since 7.0
1124       */
1125      public interface EntryTransformer<K, V1, V2> {
1126        /**
1127         * Determines an output value based on a key-value pair. This method is
1128         * <i>generally expected</i>, but not absolutely required, to have the
1129         * following properties:
1130         *
1131         * <ul>
1132         * <li>Its execution does not cause any observable side effects.
1133         * <li>The computation is <i>consistent with equals</i>; that is,
1134         *     {@link Objects#equal Objects.equal}{@code (k1, k2) &&}
1135         *     {@link Objects#equal}{@code (v1, v2)} implies that {@code
1136         *     Objects.equal(transformer.transform(k1, v1),
1137         *     transformer.transform(k2, v2))}.
1138         * </ul>
1139         *
1140         * @throws NullPointerException if the key or value is null and this
1141         *     transformer does not accept null arguments
1142         */
1143        V2 transformEntry(@Nullable K key, @Nullable V1 value);
1144      }
1145    
1146      static class TransformedEntriesMap<K, V1, V2>
1147          extends AbstractMap<K, V2> {
1148        final Map<K, V1> fromMap;
1149        final EntryTransformer<? super K, ? super V1, V2> transformer;
1150    
1151        TransformedEntriesMap(
1152            Map<K, V1> fromMap,
1153            EntryTransformer<? super K, ? super V1, V2> transformer) {
1154          this.fromMap = checkNotNull(fromMap);
1155          this.transformer = checkNotNull(transformer);
1156        }
1157    
1158        @Override public int size() {
1159          return fromMap.size();
1160        }
1161    
1162        @Override public boolean containsKey(Object key) {
1163          return fromMap.containsKey(key);
1164        }
1165    
1166        // safe as long as the user followed the <b>Warning</b> in the javadoc
1167        @SuppressWarnings("unchecked")
1168        @Override public V2 get(Object key) {
1169          V1 value = fromMap.get(key);
1170          return (value != null || fromMap.containsKey(key))
1171              ? transformer.transformEntry((K) key, value)
1172              : null;
1173        }
1174    
1175        // safe as long as the user followed the <b>Warning</b> in the javadoc
1176        @SuppressWarnings("unchecked")
1177        @Override public V2 remove(Object key) {
1178          return fromMap.containsKey(key)
1179              ? transformer.transformEntry((K) key, fromMap.remove(key))
1180              : null;
1181        }
1182    
1183        @Override public void clear() {
1184          fromMap.clear();
1185        }
1186    
1187        @Override public Set<K> keySet() {
1188          return fromMap.keySet();
1189        }
1190    
1191        Set<Entry<K, V2>> entrySet;
1192    
1193        @Override public Set<Entry<K, V2>> entrySet() {
1194          Set<Entry<K, V2>> result = entrySet;
1195          if (result == null) {
1196            entrySet = result = new EntrySet<K, V2>() {
1197              @Override Map<K, V2> map() {
1198                return TransformedEntriesMap.this;
1199              }
1200    
1201              @Override public Iterator<Entry<K, V2>> iterator() {
1202                return new TransformedIterator<Entry<K, V1>, Entry<K, V2>>(
1203                    fromMap.entrySet().iterator()) {
1204                  @Override
1205                  Entry<K, V2> transform(final Entry<K, V1> entry) {
1206                    return new AbstractMapEntry<K, V2>() {
1207                      @Override
1208                      public K getKey() {
1209                        return entry.getKey();
1210                      }
1211    
1212                      @Override
1213                      public V2 getValue() {
1214                        return transformer.transformEntry(entry.getKey(), entry.getValue());
1215                      }
1216                    };
1217                  }
1218                };
1219              }
1220            };
1221          }
1222          return result;
1223        }
1224    
1225        Collection<V2> values;
1226    
1227        @Override public Collection<V2> values() {
1228          Collection<V2> result = values;
1229          if (result == null) {
1230            return values = new Values<K, V2>() {
1231              @Override Map<K, V2> map() {
1232                return TransformedEntriesMap.this;
1233              }
1234            };
1235          }
1236          return result;
1237        }
1238      }
1239    
1240      static class TransformedEntriesSortedMap<K, V1, V2>
1241          extends TransformedEntriesMap<K, V1, V2> implements SortedMap<K, V2> {
1242    
1243        protected SortedMap<K, V1> fromMap() {
1244          return (SortedMap<K, V1>) fromMap;
1245        }
1246    
1247        TransformedEntriesSortedMap(SortedMap<K, V1> fromMap,
1248            EntryTransformer<? super K, ? super V1, V2> transformer) {
1249          super(fromMap, transformer);
1250        }
1251    
1252        @Override public Comparator<? super K> comparator() {
1253          return fromMap().comparator();
1254        }
1255    
1256        @Override public K firstKey() {
1257          return fromMap().firstKey();
1258        }
1259    
1260        @Override public SortedMap<K, V2> headMap(K toKey) {
1261          return transformEntries(fromMap().headMap(toKey), transformer);
1262        }
1263    
1264        @Override public K lastKey() {
1265          return fromMap().lastKey();
1266        }
1267    
1268        @Override public SortedMap<K, V2> subMap(K fromKey, K toKey) {
1269          return transformEntries(
1270              fromMap().subMap(fromKey, toKey), transformer);
1271        }
1272    
1273        @Override public SortedMap<K, V2> tailMap(K fromKey) {
1274          return transformEntries(fromMap().tailMap(fromKey), transformer);
1275        }
1276    
1277      }
1278    
1279      /**
1280       * Returns a map containing the mappings in {@code unfiltered} whose keys
1281       * satisfy a predicate. The returned map is a live view of {@code unfiltered};
1282       * changes to one affect the other.
1283       *
1284       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1285       * values()} views have iterators that don't support {@code remove()}, but all
1286       * other methods are supported by the map and its views. When given a key that
1287       * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
1288       * methods throw an {@link IllegalArgumentException}.
1289       *
1290       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1291       * on the filtered map or its views, only mappings whose keys satisfy the
1292       * filter will be removed from the underlying map.
1293       *
1294       * <p>The returned map isn't threadsafe or serializable, even if {@code
1295       * unfiltered} is.
1296       *
1297       * <p>Many of the filtered map's methods, such as {@code size()},
1298       * iterate across every key/value mapping in the underlying map and determine
1299       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1300       * faster to copy the filtered map and use the copy.
1301       *
1302       * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
1303       * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1304       * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1305       * inconsistent with equals.
1306       */
1307      public static <K, V> Map<K, V> filterKeys(
1308          Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1309        if (unfiltered instanceof SortedMap) {
1310          return filterKeys((SortedMap<K, V>) unfiltered, keyPredicate);
1311        }
1312        checkNotNull(keyPredicate);
1313        Predicate<Entry<K, V>> entryPredicate =
1314            new Predicate<Entry<K, V>>() {
1315              @Override
1316              public boolean apply(Entry<K, V> input) {
1317                return keyPredicate.apply(input.getKey());
1318              }
1319            };
1320        return (unfiltered instanceof AbstractFilteredMap)
1321            ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1322            : new FilteredKeyMap<K, V>(
1323                checkNotNull(unfiltered), keyPredicate, entryPredicate);
1324      }
1325    
1326      /**
1327       * Returns a sorted map containing the mappings in {@code unfiltered} whose
1328       * keys satisfy a predicate. The returned map is a live view of {@code
1329       * unfiltered}; changes to one affect the other.
1330       *
1331       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1332       * values()} views have iterators that don't support {@code remove()}, but all
1333       * other methods are supported by the map and its views. When given a key that
1334       * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
1335       * methods throw an {@link IllegalArgumentException}.
1336       *
1337       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1338       * on the filtered map or its views, only mappings whose keys satisfy the
1339       * filter will be removed from the underlying map.
1340       *
1341       * <p>The returned map isn't threadsafe or serializable, even if {@code
1342       * unfiltered} is.
1343       *
1344       * <p>Many of the filtered map's methods, such as {@code size()},
1345       * iterate across every key/value mapping in the underlying map and determine
1346       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1347       * faster to copy the filtered map and use the copy.
1348       *
1349       * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
1350       * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1351       * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1352       * inconsistent with equals.
1353       *
1354       * @since 11.0
1355       */
1356      @Beta
1357      public static <K, V> SortedMap<K, V> filterKeys(
1358          SortedMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1359        // TODO: Return a subclass of Maps.FilteredKeyMap for slightly better
1360        // performance.
1361        checkNotNull(keyPredicate);
1362        Predicate<Entry<K, V>> entryPredicate = new Predicate<Entry<K, V>>() {
1363          @Override
1364          public boolean apply(Entry<K, V> input) {
1365            return keyPredicate.apply(input.getKey());
1366          }
1367        };
1368        return filterEntries(unfiltered, entryPredicate);
1369      }
1370    
1371      /**
1372       * Returns a map containing the mappings in {@code unfiltered} whose values
1373       * satisfy a predicate. The returned map is a live view of {@code unfiltered};
1374       * changes to one affect the other.
1375       *
1376       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1377       * values()} views have iterators that don't support {@code remove()}, but all
1378       * other methods are supported by the map and its views. When given a value
1379       * that doesn't satisfy the predicate, the map's {@code put()}, {@code
1380       * putAll()}, and {@link Entry#setValue} methods throw an {@link
1381       * IllegalArgumentException}.
1382       *
1383       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1384       * on the filtered map or its views, only mappings whose values satisfy the
1385       * filter will be removed from the underlying map.
1386       *
1387       * <p>The returned map isn't threadsafe or serializable, even if {@code
1388       * unfiltered} is.
1389       *
1390       * <p>Many of the filtered map's methods, such as {@code size()},
1391       * iterate across every key/value mapping in the underlying map and determine
1392       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1393       * faster to copy the filtered map and use the copy.
1394       *
1395       * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
1396       * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1397       * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1398       * inconsistent with equals.
1399       */
1400      public static <K, V> Map<K, V> filterValues(
1401          Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
1402        if (unfiltered instanceof SortedMap) {
1403          return filterValues((SortedMap<K, V>) unfiltered, valuePredicate);
1404        }
1405        checkNotNull(valuePredicate);
1406        Predicate<Entry<K, V>> entryPredicate =
1407            new Predicate<Entry<K, V>>() {
1408              @Override
1409              public boolean apply(Entry<K, V> input) {
1410                return valuePredicate.apply(input.getValue());
1411              }
1412            };
1413        return filterEntries(unfiltered, entryPredicate);
1414      }
1415    
1416      /**
1417       * Returns a sorted map containing the mappings in {@code unfiltered} whose
1418       * values satisfy a predicate. The returned map is a live view of {@code
1419       * unfiltered}; changes to one affect the other.
1420       *
1421       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1422       * values()} views have iterators that don't support {@code remove()}, but all
1423       * other methods are supported by the map and its views. When given a value
1424       * that doesn't satisfy the predicate, the map's {@code put()}, {@code
1425       * putAll()}, and {@link Entry#setValue} methods throw an {@link
1426       * IllegalArgumentException}.
1427       *
1428       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1429       * on the filtered map or its views, only mappings whose values satisfy the
1430       * filter will be removed from the underlying map.
1431       *
1432       * <p>The returned map isn't threadsafe or serializable, even if {@code
1433       * unfiltered} is.
1434       *
1435       * <p>Many of the filtered map's methods, such as {@code size()},
1436       * iterate across every key/value mapping in the underlying map and determine
1437       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1438       * faster to copy the filtered map and use the copy.
1439       *
1440       * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
1441       * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1442       * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1443       * inconsistent with equals.
1444       *
1445       * @since 11.0
1446       */
1447      @Beta
1448      public static <K, V> SortedMap<K, V> filterValues(
1449          SortedMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
1450        checkNotNull(valuePredicate);
1451        Predicate<Entry<K, V>> entryPredicate =
1452            new Predicate<Entry<K, V>>() {
1453              @Override
1454              public boolean apply(Entry<K, V> input) {
1455                return valuePredicate.apply(input.getValue());
1456              }
1457            };
1458        return filterEntries(unfiltered, entryPredicate);
1459      }
1460    
1461      /**
1462       * Returns a map containing the mappings in {@code unfiltered} that satisfy a
1463       * predicate. The returned map is a live view of {@code unfiltered}; changes
1464       * to one affect the other.
1465       *
1466       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1467       * values()} views have iterators that don't support {@code remove()}, but all
1468       * other methods are supported by the map and its views. When given a
1469       * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
1470       * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
1471       * Similarly, the map's entries have a {@link Entry#setValue} method that
1472       * throws an {@link IllegalArgumentException} when the existing key and the
1473       * provided value don't satisfy the predicate.
1474       *
1475       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1476       * on the filtered map or its views, only mappings that satisfy the filter
1477       * will be removed from the underlying map.
1478       *
1479       * <p>The returned map isn't threadsafe or serializable, even if {@code
1480       * unfiltered} is.
1481       *
1482       * <p>Many of the filtered map's methods, such as {@code size()},
1483       * iterate across every key/value mapping in the underlying map and determine
1484       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1485       * faster to copy the filtered map and use the copy.
1486       *
1487       * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
1488       * equals</i>, as documented at {@link Predicate#apply}.
1489       */
1490      public static <K, V> Map<K, V> filterEntries(
1491          Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1492        if (unfiltered instanceof SortedMap) {
1493          return filterEntries((SortedMap<K, V>) unfiltered, entryPredicate);
1494        }
1495        checkNotNull(entryPredicate);
1496        return (unfiltered instanceof AbstractFilteredMap)
1497            ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1498            : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate);
1499      }
1500    
1501      /**
1502       * Returns a sorted map containing the mappings in {@code unfiltered} that
1503       * satisfy a predicate. The returned map is a live view of {@code unfiltered};
1504       * changes to one affect the other.
1505       *
1506       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1507       * values()} views have iterators that don't support {@code remove()}, but all
1508       * other methods are supported by the map and its views. When given a
1509       * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
1510       * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
1511       * Similarly, the map's entries have a {@link Entry#setValue} method that
1512       * throws an {@link IllegalArgumentException} when the existing key and the
1513       * provided value don't satisfy the predicate.
1514       *
1515       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1516       * on the filtered map or its views, only mappings that satisfy the filter
1517       * will be removed from the underlying map.
1518       *
1519       * <p>The returned map isn't threadsafe or serializable, even if {@code
1520       * unfiltered} is.
1521       *
1522       * <p>Many of the filtered map's methods, such as {@code size()},
1523       * iterate across every key/value mapping in the underlying map and determine
1524       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1525       * faster to copy the filtered map and use the copy.
1526       *
1527       * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
1528       * equals</i>, as documented at {@link Predicate#apply}.
1529       *
1530       * @since 11.0
1531       */
1532      @Beta
1533      public static <K, V> SortedMap<K, V> filterEntries(
1534          SortedMap<K, V> unfiltered,
1535          Predicate<? super Entry<K, V>> entryPredicate) {
1536        checkNotNull(entryPredicate);
1537        return (unfiltered instanceof FilteredEntrySortedMap)
1538            ? filterFiltered((FilteredEntrySortedMap<K, V>) unfiltered, entryPredicate)
1539            : new FilteredEntrySortedMap<K, V>(checkNotNull(unfiltered), entryPredicate);
1540      }
1541    
1542      /**
1543       * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
1544       * filtering a filtered map.
1545       */
1546      private static <K, V> Map<K, V> filterFiltered(AbstractFilteredMap<K, V> map,
1547          Predicate<? super Entry<K, V>> entryPredicate) {
1548        Predicate<Entry<K, V>> predicate =
1549            Predicates.and(map.predicate, entryPredicate);
1550        return new FilteredEntryMap<K, V>(map.unfiltered, predicate);
1551      }
1552    
1553      private abstract static class AbstractFilteredMap<K, V>
1554          extends AbstractMap<K, V> {
1555        final Map<K, V> unfiltered;
1556        final Predicate<? super Entry<K, V>> predicate;
1557    
1558        AbstractFilteredMap(
1559            Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
1560          this.unfiltered = unfiltered;
1561          this.predicate = predicate;
1562        }
1563    
1564        boolean apply(Object key, V value) {
1565          // This method is called only when the key is in the map, implying that
1566          // key is a K.
1567          @SuppressWarnings("unchecked")
1568          K k = (K) key;
1569          return predicate.apply(Maps.immutableEntry(k, value));
1570        }
1571    
1572        @Override public V put(K key, V value) {
1573          checkArgument(apply(key, value));
1574          return unfiltered.put(key, value);
1575        }
1576    
1577        @Override public void putAll(Map<? extends K, ? extends V> map) {
1578          for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
1579            checkArgument(apply(entry.getKey(), entry.getValue()));
1580          }
1581          unfiltered.putAll(map);
1582        }
1583    
1584        @Override public boolean containsKey(Object key) {
1585          return unfiltered.containsKey(key) && apply(key, unfiltered.get(key));
1586        }
1587    
1588        @Override public V get(Object key) {
1589          V value = unfiltered.get(key);
1590          return ((value != null) && apply(key, value)) ? value : null;
1591        }
1592    
1593        @Override public boolean isEmpty() {
1594          return entrySet().isEmpty();
1595        }
1596    
1597        @Override public V remove(Object key) {
1598          return containsKey(key) ? unfiltered.remove(key) : null;
1599        }
1600    
1601        Collection<V> values;
1602    
1603        @Override public Collection<V> values() {
1604          Collection<V> result = values;
1605          return (result == null) ? values = new Values() : result;
1606        }
1607    
1608        class Values extends AbstractCollection<V> {
1609          @Override public Iterator<V> iterator() {
1610            final Iterator<Entry<K, V>> entryIterator = entrySet().iterator();
1611            return new UnmodifiableIterator<V>() {
1612              @Override
1613              public boolean hasNext() {
1614                return entryIterator.hasNext();
1615              }
1616    
1617              @Override
1618              public V next() {
1619                return entryIterator.next().getValue();
1620              }
1621            };
1622          }
1623    
1624          @Override public int size() {
1625            return entrySet().size();
1626          }
1627    
1628          @Override public void clear() {
1629            entrySet().clear();
1630          }
1631    
1632          @Override public boolean isEmpty() {
1633            return entrySet().isEmpty();
1634          }
1635    
1636          @Override public boolean remove(Object o) {
1637            Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1638            while (iterator.hasNext()) {
1639              Entry<K, V> entry = iterator.next();
1640              if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) {
1641                iterator.remove();
1642                return true;
1643              }
1644            }
1645            return false;
1646          }
1647    
1648          @Override public boolean removeAll(Collection<?> collection) {
1649            checkNotNull(collection);
1650            boolean changed = false;
1651            Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1652            while (iterator.hasNext()) {
1653              Entry<K, V> entry = iterator.next();
1654              if (collection.contains(entry.getValue()) && predicate.apply(entry)) {
1655                iterator.remove();
1656                changed = true;
1657              }
1658            }
1659            return changed;
1660          }
1661    
1662          @Override public boolean retainAll(Collection<?> collection) {
1663            checkNotNull(collection);
1664            boolean changed = false;
1665            Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1666            while (iterator.hasNext()) {
1667              Entry<K, V> entry = iterator.next();
1668              if (!collection.contains(entry.getValue())
1669                  && predicate.apply(entry)) {
1670                iterator.remove();
1671                changed = true;
1672              }
1673            }
1674            return changed;
1675          }
1676    
1677          @Override public Object[] toArray() {
1678            // creating an ArrayList so filtering happens once
1679            return Lists.newArrayList(iterator()).toArray();
1680          }
1681    
1682          @Override public <T> T[] toArray(T[] array) {
1683            return Lists.newArrayList(iterator()).toArray(array);
1684          }
1685        }
1686      }
1687      /**
1688       * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
1689       * filtering a filtered sorted map.
1690       */
1691      private static <K, V> SortedMap<K, V> filterFiltered(
1692          FilteredEntrySortedMap<K, V> map,
1693          Predicate<? super Entry<K, V>> entryPredicate) {
1694        Predicate<Entry<K, V>> predicate
1695            = Predicates.and(map.predicate, entryPredicate);
1696        return new FilteredEntrySortedMap<K, V>(map.sortedMap(), predicate);
1697      }
1698    
1699      private static class FilteredEntrySortedMap<K, V>
1700          extends FilteredEntryMap<K, V> implements SortedMap<K, V> {
1701    
1702        FilteredEntrySortedMap(SortedMap<K, V> unfiltered,
1703            Predicate<? super Entry<K, V>> entryPredicate) {
1704          super(unfiltered, entryPredicate);
1705        }
1706    
1707        SortedMap<K, V> sortedMap() {
1708          return (SortedMap<K, V>) unfiltered;
1709        }
1710    
1711        @Override public Comparator<? super K> comparator() {
1712          return sortedMap().comparator();
1713        }
1714    
1715        @Override public K firstKey() {
1716          // correctly throws NoSuchElementException when filtered map is empty.
1717          return keySet().iterator().next();
1718        }
1719    
1720        @Override public K lastKey() {
1721          SortedMap<K, V> headMap = sortedMap();
1722          while (true) {
1723            // correctly throws NoSuchElementException when filtered map is empty.
1724            K key = headMap.lastKey();
1725            if (apply(key, unfiltered.get(key))) {
1726              return key;
1727            }
1728            headMap = sortedMap().headMap(key);
1729          }
1730        }
1731    
1732        @Override public SortedMap<K, V> headMap(K toKey) {
1733          return new FilteredEntrySortedMap<K, V>(sortedMap().headMap(toKey), predicate);
1734        }
1735    
1736        @Override public SortedMap<K, V> subMap(K fromKey, K toKey) {
1737          return new FilteredEntrySortedMap<K, V>(
1738              sortedMap().subMap(fromKey, toKey), predicate);
1739        }
1740    
1741        @Override public SortedMap<K, V> tailMap(K fromKey) {
1742          return new FilteredEntrySortedMap<K, V>(
1743              sortedMap().tailMap(fromKey), predicate);
1744        }
1745      }
1746    
1747      private static class FilteredKeyMap<K, V> extends AbstractFilteredMap<K, V> {
1748        Predicate<? super K> keyPredicate;
1749    
1750        FilteredKeyMap(Map<K, V> unfiltered, Predicate<? super K> keyPredicate,
1751            Predicate<Entry<K, V>> entryPredicate) {
1752          super(unfiltered, entryPredicate);
1753          this.keyPredicate = keyPredicate;
1754        }
1755    
1756        Set<Entry<K, V>> entrySet;
1757    
1758        @Override public Set<Entry<K, V>> entrySet() {
1759          Set<Entry<K, V>> result = entrySet;
1760          return (result == null)
1761              ? entrySet = Sets.filter(unfiltered.entrySet(), predicate)
1762              : result;
1763        }
1764    
1765        Set<K> keySet;
1766    
1767        @Override public Set<K> keySet() {
1768          Set<K> result = keySet;
1769          return (result == null)
1770              ? keySet = Sets.filter(unfiltered.keySet(), keyPredicate)
1771              : result;
1772        }
1773    
1774        // The cast is called only when the key is in the unfiltered map, implying
1775        // that key is a K.
1776        @Override
1777        @SuppressWarnings("unchecked")
1778        public boolean containsKey(Object key) {
1779          return unfiltered.containsKey(key) && keyPredicate.apply((K) key);
1780        }
1781      }
1782    
1783      static class FilteredEntryMap<K, V> extends AbstractFilteredMap<K, V> {
1784        /**
1785         * Entries in this set satisfy the predicate, but they don't validate the
1786         * input to {@code Entry.setValue()}.
1787         */
1788        final Set<Entry<K, V>> filteredEntrySet;
1789    
1790        FilteredEntryMap(
1791            Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1792          super(unfiltered, entryPredicate);
1793          filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate);
1794        }
1795    
1796        Set<Entry<K, V>> entrySet;
1797    
1798        @Override public Set<Entry<K, V>> entrySet() {
1799          Set<Entry<K, V>> result = entrySet;
1800          return (result == null) ? entrySet = new EntrySet() : result;
1801        }
1802    
1803        private class EntrySet extends ForwardingSet<Entry<K, V>> {
1804          @Override protected Set<Entry<K, V>> delegate() {
1805            return filteredEntrySet;
1806          }
1807    
1808          @Override public Iterator<Entry<K, V>> iterator() {
1809            final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1810            return new UnmodifiableIterator<Entry<K, V>>() {
1811              @Override
1812              public boolean hasNext() {
1813                return iterator.hasNext();
1814              }
1815    
1816              @Override
1817              public Entry<K, V> next() {
1818                final Entry<K, V> entry = iterator.next();
1819                return new ForwardingMapEntry<K, V>() {
1820                  @Override protected Entry<K, V> delegate() {
1821                    return entry;
1822                  }
1823    
1824                  @Override public V setValue(V value) {
1825                    checkArgument(apply(entry.getKey(), value));
1826                    return super.setValue(value);
1827                  }
1828                };
1829              }
1830            };
1831          }
1832        }
1833    
1834        Set<K> keySet;
1835    
1836        @Override public Set<K> keySet() {
1837          Set<K> result = keySet;
1838          return (result == null) ? keySet = new KeySet() : result;
1839        }
1840    
1841        private class KeySet extends AbstractSet<K> {
1842          @Override public Iterator<K> iterator() {
1843            final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1844            return new UnmodifiableIterator<K>() {
1845              @Override
1846              public boolean hasNext() {
1847                return iterator.hasNext();
1848              }
1849    
1850              @Override
1851              public K next() {
1852                return iterator.next().getKey();
1853              }
1854            };
1855          }
1856    
1857          @Override public int size() {
1858            return filteredEntrySet.size();
1859          }
1860    
1861          @Override public void clear() {
1862            filteredEntrySet.clear();
1863          }
1864    
1865          @Override public boolean contains(Object o) {
1866            return containsKey(o);
1867          }
1868    
1869          @Override public boolean remove(Object o) {
1870            if (containsKey(o)) {
1871              unfiltered.remove(o);
1872              return true;
1873            }
1874            return false;
1875          }
1876    
1877          @Override public boolean removeAll(Collection<?> collection) {
1878            checkNotNull(collection); // for GWT
1879            boolean changed = false;
1880            for (Object obj : collection) {
1881              changed |= remove(obj);
1882            }
1883            return changed;
1884          }
1885    
1886          @Override public boolean retainAll(Collection<?> collection) {
1887            checkNotNull(collection); // for GWT
1888            boolean changed = false;
1889            Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1890            while (iterator.hasNext()) {
1891              Entry<K, V> entry = iterator.next();
1892              if (!collection.contains(entry.getKey()) && predicate.apply(entry)) {
1893                iterator.remove();
1894                changed = true;
1895              }
1896            }
1897            return changed;
1898          }
1899    
1900          @Override public Object[] toArray() {
1901            // creating an ArrayList so filtering happens once
1902            return Lists.newArrayList(iterator()).toArray();
1903          }
1904    
1905          @Override public <T> T[] toArray(T[] array) {
1906            return Lists.newArrayList(iterator()).toArray(array);
1907          }
1908        }
1909      }
1910    
1911      /**
1912       * Returns an unmodifiable view of the specified navigable map. Query operations on the returned
1913       * map read through to the specified map, and attempts to modify the returned map, whether direct
1914       * or via its views, result in an {@code UnsupportedOperationException}.
1915       *
1916       * <p>The returned navigable map will be serializable if the specified navigable map is
1917       * serializable.
1918       *
1919       * @param map the navigable map for which an unmodifiable view is to be returned
1920       * @return an unmodifiable view of the specified navigable map
1921       * @since 12.0
1922       */
1923      @GwtIncompatible("NavigableMap")
1924      public static <K, V> NavigableMap<K, V> unmodifiableNavigableMap(NavigableMap<K, V> map) {
1925        checkNotNull(map);
1926        if (map instanceof UnmodifiableNavigableMap) {
1927          return map;
1928        } else {
1929          return new UnmodifiableNavigableMap<K, V>(map);
1930        }
1931      }
1932    
1933      @Nullable private static <K, V> Entry<K, V> unmodifiableOrNull(@Nullable Entry<K, V> entry) {
1934        return (entry == null) ? null : Maps.unmodifiableEntry(entry);
1935      }
1936    
1937      @GwtIncompatible("NavigableMap")
1938      static class UnmodifiableNavigableMap<K, V>
1939          extends ForwardingSortedMap<K, V> implements NavigableMap<K, V>, Serializable {
1940        private final NavigableMap<K, V> delegate;
1941    
1942        UnmodifiableNavigableMap(NavigableMap<K, V> delegate) {
1943          this.delegate = delegate;
1944        }
1945    
1946        @Override
1947        protected SortedMap<K, V> delegate() {
1948          return Collections.unmodifiableSortedMap(delegate);
1949        }
1950    
1951        @Override
1952        public Entry<K, V> lowerEntry(K key) {
1953          return unmodifiableOrNull(delegate.lowerEntry(key));
1954        }
1955    
1956        @Override
1957        public K lowerKey(K key) {
1958          return delegate.lowerKey(key);
1959        }
1960    
1961        @Override
1962        public Entry<K, V> floorEntry(K key) {
1963          return unmodifiableOrNull(delegate.floorEntry(key));
1964        }
1965    
1966        @Override
1967        public K floorKey(K key) {
1968          return delegate.floorKey(key);
1969        }
1970    
1971        @Override
1972        public Entry<K, V> ceilingEntry(K key) {
1973          return unmodifiableOrNull(delegate.ceilingEntry(key));
1974        }
1975    
1976        @Override
1977        public K ceilingKey(K key) {
1978          return delegate.ceilingKey(key);
1979        }
1980    
1981        @Override
1982        public Entry<K, V> higherEntry(K key) {
1983          return unmodifiableOrNull(delegate.higherEntry(key));
1984        }
1985    
1986        @Override
1987        public K higherKey(K key) {
1988          return delegate.higherKey(key);
1989        }
1990    
1991        @Override
1992        public Entry<K, V> firstEntry() {
1993          return unmodifiableOrNull(delegate.firstEntry());
1994        }
1995    
1996        @Override
1997        public Entry<K, V> lastEntry() {
1998          return unmodifiableOrNull(delegate.lastEntry());
1999        }
2000    
2001        @Override
2002        public final Entry<K, V> pollFirstEntry() {
2003          throw new UnsupportedOperationException();
2004        }
2005    
2006        @Override
2007        public final Entry<K, V> pollLastEntry() {
2008          throw new UnsupportedOperationException();
2009        }
2010    
2011        private transient UnmodifiableNavigableMap<K, V> descendingMap;
2012    
2013        @Override
2014        public NavigableMap<K, V> descendingMap() {
2015          UnmodifiableNavigableMap<K, V> result = descendingMap;
2016          if (result == null) {
2017            descendingMap = result = new UnmodifiableNavigableMap<K, V>(delegate.descendingMap());
2018            result.descendingMap = this;
2019          }
2020          return result;
2021        }
2022    
2023        @Override
2024        public Set<K> keySet() {
2025          return navigableKeySet();
2026        }
2027    
2028        @Override
2029        public NavigableSet<K> navigableKeySet() {
2030          return Sets.unmodifiableNavigableSet(delegate.navigableKeySet());
2031        }
2032    
2033        @Override
2034        public NavigableSet<K> descendingKeySet() {
2035          return Sets.unmodifiableNavigableSet(delegate.descendingKeySet());
2036        }
2037    
2038        @Override
2039        public SortedMap<K, V> subMap(K fromKey, K toKey) {
2040          return subMap(fromKey, true, toKey, false);
2041        }
2042    
2043        @Override
2044        public SortedMap<K, V> headMap(K toKey) {
2045          return headMap(toKey, false);
2046        }
2047    
2048        @Override
2049        public SortedMap<K, V> tailMap(K fromKey) {
2050          return tailMap(fromKey, true);
2051        }
2052    
2053        @Override
2054        public
2055            NavigableMap<K, V>
2056            subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
2057          return Maps.unmodifiableNavigableMap(delegate.subMap(
2058              fromKey,
2059              fromInclusive,
2060              toKey,
2061              toInclusive));
2062        }
2063    
2064        @Override
2065        public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
2066          return Maps.unmodifiableNavigableMap(delegate.headMap(toKey, inclusive));
2067        }
2068    
2069        @Override
2070        public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
2071          return Maps.unmodifiableNavigableMap(delegate.tailMap(fromKey, inclusive));
2072        }
2073      }
2074    
2075      /**
2076       * {@code AbstractMap} extension that implements {@link #isEmpty()} as {@code
2077       * entrySet().isEmpty()} instead of {@code size() == 0} to speed up
2078       * implementations where {@code size()} is O(n), and it delegates the {@code
2079       * isEmpty()} methods of its key set and value collection to this
2080       * implementation.
2081       */
2082      @GwtCompatible
2083      static abstract class ImprovedAbstractMap<K, V> extends AbstractMap<K, V> {
2084        /**
2085         * Creates the entry set to be returned by {@link #entrySet()}. This method
2086         * is invoked at most once on a given map, at the time when {@code entrySet}
2087         * is first called.
2088         */
2089        protected abstract Set<Entry<K, V>> createEntrySet();
2090    
2091        private Set<Entry<K, V>> entrySet;
2092    
2093        @Override public Set<Entry<K, V>> entrySet() {
2094          Set<Entry<K, V>> result = entrySet;
2095          if (result == null) {
2096            entrySet = result = createEntrySet();
2097          }
2098          return result;
2099        }
2100    
2101        private Set<K> keySet;
2102    
2103        @Override public Set<K> keySet() {
2104          Set<K> result = keySet;
2105          if (result == null) {
2106            return keySet = new KeySet<K, V>() {
2107              @Override Map<K, V> map() {
2108                return ImprovedAbstractMap.this;
2109              }
2110            };
2111          }
2112          return result;
2113        }
2114    
2115        private Collection<V> values;
2116    
2117        @Override public Collection<V> values() {
2118          Collection<V> result = values;
2119          if (result == null) {
2120            return values = new Values<K, V>(){
2121              @Override Map<K, V> map() {
2122                return ImprovedAbstractMap.this;
2123              }
2124            };
2125          }
2126          return result;
2127        }
2128    
2129        /**
2130         * Returns {@code true} if this map contains no key-value mappings.
2131         *
2132         * <p>The implementation returns {@code entrySet().isEmpty()}.
2133         *
2134         * @return {@code true} if this map contains no key-value mappings
2135         */
2136        @Override public boolean isEmpty() {
2137          return entrySet().isEmpty();
2138        }
2139      }
2140    
2141      static final MapJoiner STANDARD_JOINER =
2142          Collections2.STANDARD_JOINER.withKeyValueSeparator("=");
2143    
2144      /**
2145       * Delegates to {@link Map#get}. Returns {@code null} on {@code
2146       * ClassCastException}.
2147       */
2148      static <V> V safeGet(Map<?, V> map, Object key) {
2149        try {
2150          return map.get(key);
2151        } catch (ClassCastException e) {
2152          return null;
2153        }
2154      }
2155    
2156      /**
2157       * Delegates to {@link Map#containsKey}. Returns {@code false} on {@code
2158       * ClassCastException}
2159       */
2160      static boolean safeContainsKey(Map<?, ?> map, Object key) {
2161        try {
2162          return map.containsKey(key);
2163        } catch (ClassCastException e) {
2164          return false;
2165        }
2166      }
2167    
2168      /**
2169       * Implements {@code Collection.contains} safely for forwarding collections of
2170       * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
2171       * wrapped using {@link #unmodifiableEntry} to protect against a possible
2172       * nefarious equals method.
2173       *
2174       * <p>Note that {@code c} is the backing (delegate) collection, rather than
2175       * the forwarding collection.
2176       *
2177       * @param c the delegate (unwrapped) collection of map entries
2178       * @param o the object that might be contained in {@code c}
2179       * @return {@code true} if {@code c} contains {@code o}
2180       */
2181      static <K, V> boolean containsEntryImpl(Collection<Entry<K, V>> c, Object o) {
2182        if (!(o instanceof Entry)) {
2183          return false;
2184        }
2185        return c.contains(unmodifiableEntry((Entry<?, ?>) o));
2186      }
2187    
2188      /**
2189       * Implements {@code Collection.remove} safely for forwarding collections of
2190       * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
2191       * wrapped using {@link #unmodifiableEntry} to protect against a possible
2192       * nefarious equals method.
2193       *
2194       * <p>Note that {@code c} is backing (delegate) collection, rather than the
2195       * forwarding collection.
2196       *
2197       * @param c the delegate (unwrapped) collection of map entries
2198       * @param o the object to remove from {@code c}
2199       * @return {@code true} if {@code c} was changed
2200       */
2201      static <K, V> boolean removeEntryImpl(Collection<Entry<K, V>> c, Object o) {
2202        if (!(o instanceof Entry)) {
2203          return false;
2204        }
2205        return c.remove(unmodifiableEntry((Entry<?, ?>) o));
2206      }
2207    
2208      /**
2209       * An implementation of {@link Map#equals}.
2210       */
2211      static boolean equalsImpl(Map<?, ?> map, Object object) {
2212        if (map == object) {
2213          return true;
2214        }
2215        if (object instanceof Map) {
2216          Map<?, ?> o = (Map<?, ?>) object;
2217          return map.entrySet().equals(o.entrySet());
2218        }
2219        return false;
2220      }
2221    
2222      /**
2223       * An implementation of {@link Map#hashCode}.
2224       */
2225      static int hashCodeImpl(Map<?, ?> map) {
2226        return Sets.hashCodeImpl(map.entrySet());
2227      }
2228    
2229      /**
2230       * An implementation of {@link Map#toString}.
2231       */
2232      static String toStringImpl(Map<?, ?> map) {
2233        StringBuilder sb
2234            = Collections2.newStringBuilderForCollection(map.size()).append('{');
2235        STANDARD_JOINER.appendTo(sb, map);
2236        return sb.append('}').toString();
2237      }
2238    
2239      /**
2240       * An implementation of {@link Map#putAll}.
2241       */
2242      static <K, V> void putAllImpl(
2243          Map<K, V> self, Map<? extends K, ? extends V> map) {
2244        for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
2245          self.put(entry.getKey(), entry.getValue());
2246        }
2247      }
2248    
2249      /**
2250       * An admittedly inefficient implementation of {@link Map#containsKey}.
2251       */
2252      static boolean containsKeyImpl(Map<?, ?> map, @Nullable Object key) {
2253        for (Entry<?, ?> entry : map.entrySet()) {
2254          if (Objects.equal(entry.getKey(), key)) {
2255            return true;
2256          }
2257        }
2258        return false;
2259      }
2260    
2261      /**
2262       * An implementation of {@link Map#containsValue}.
2263       */
2264      static boolean containsValueImpl(Map<?, ?> map, @Nullable Object value) {
2265        for (Entry<?, ?> entry : map.entrySet()) {
2266          if (Objects.equal(entry.getValue(), value)) {
2267            return true;
2268          }
2269        }
2270        return false;
2271      }
2272    
2273      static <K, V> Iterator<K> keyIterator(Iterator<Entry<K, V>> entryIterator) {
2274        return new TransformedIterator<Entry<K, V>, K>(entryIterator) {
2275          @Override
2276          K transform(Entry<K, V> entry) {
2277            return entry.getKey();
2278          }
2279        };
2280      }
2281    
2282      abstract static class KeySet<K, V> extends AbstractSet<K> {
2283        abstract Map<K, V> map();
2284    
2285        @Override public Iterator<K> iterator() {
2286          return keyIterator(map().entrySet().iterator());
2287        }
2288    
2289        @Override public int size() {
2290          return map().size();
2291        }
2292    
2293        @Override public boolean isEmpty() {
2294          return map().isEmpty();
2295        }
2296    
2297        @Override public boolean contains(Object o) {
2298          return map().containsKey(o);
2299        }
2300    
2301        @Override public boolean remove(Object o) {
2302          if (contains(o)) {
2303            map().remove(o);
2304            return true;
2305          }
2306          return false;
2307        }
2308    
2309        @Override
2310        public boolean removeAll(Collection<?> c) {
2311          // TODO(user): find out why this is necessary to make GWT tests pass.
2312          return super.removeAll(checkNotNull(c));
2313        }
2314    
2315        @Override public void clear() {
2316          map().clear();
2317        }
2318      }
2319    
2320      @Nullable
2321      static <K> K keyOrNull(@Nullable Entry<K, ?> entry) {
2322        return (entry == null) ? null : entry.getKey();
2323      }
2324    
2325      @GwtIncompatible("NavigableMap")
2326      abstract static class NavigableKeySet<K, V> extends KeySet<K, V> implements NavigableSet<K> {
2327        @Override
2328        abstract NavigableMap<K, V> map();
2329    
2330        @Override
2331        public Comparator<? super K> comparator() {
2332          return map().comparator();
2333        }
2334    
2335        @Override
2336        public K first() {
2337          return map().firstKey();
2338        }
2339    
2340        @Override
2341        public K last() {
2342          return map().lastKey();
2343        }
2344    
2345        @Override
2346        public K lower(K e) {
2347          return map().lowerKey(e);
2348        }
2349    
2350        @Override
2351        public K floor(K e) {
2352          return map().floorKey(e);
2353        }
2354    
2355        @Override
2356        public K ceiling(K e) {
2357          return map().ceilingKey(e);
2358        }
2359    
2360        @Override
2361        public K higher(K e) {
2362          return map().higherKey(e);
2363        }
2364    
2365        @Override
2366        public K pollFirst() {
2367          return keyOrNull(map().pollFirstEntry());
2368        }
2369    
2370        @Override
2371        public K pollLast() {
2372          return keyOrNull(map().pollLastEntry());
2373        }
2374    
2375        @Override
2376        public NavigableSet<K> descendingSet() {
2377          return map().descendingKeySet();
2378        }
2379    
2380        @Override
2381        public Iterator<K> descendingIterator() {
2382          return descendingSet().iterator();
2383        }
2384    
2385        @Override
2386        public NavigableSet<K> subSet(
2387            K fromElement,
2388            boolean fromInclusive,
2389            K toElement,
2390            boolean toInclusive) {
2391          return map().subMap(fromElement, fromInclusive, toElement, toInclusive).navigableKeySet();
2392        }
2393    
2394        @Override
2395        public NavigableSet<K> headSet(K toElement, boolean inclusive) {
2396          return map().headMap(toElement, inclusive).navigableKeySet();
2397        }
2398    
2399        @Override
2400        public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
2401          return map().tailMap(fromElement, inclusive).navigableKeySet();
2402        }
2403    
2404        @Override
2405        public SortedSet<K> subSet(K fromElement, K toElement) {
2406          return subSet(fromElement, true, toElement, false);
2407        }
2408    
2409        @Override
2410        public SortedSet<K> headSet(K toElement) {
2411          return headSet(toElement, false);
2412        }
2413    
2414        @Override
2415        public SortedSet<K> tailSet(K fromElement) {
2416          return tailSet(fromElement, true);
2417        }
2418      }
2419    
2420      static <K, V> Iterator<V> valueIterator(Iterator<Entry<K, V>> entryIterator) {
2421        return new TransformedIterator<Entry<K, V>, V>(entryIterator) {
2422          @Override
2423          V transform(Entry<K, V> entry) {
2424            return entry.getValue();
2425          }
2426        };
2427      }
2428    
2429      static <K, V> UnmodifiableIterator<V> valueIterator(
2430          final UnmodifiableIterator<Entry<K, V>> entryIterator) {
2431        return new UnmodifiableIterator<V>() {
2432          @Override
2433          public boolean hasNext() {
2434            return entryIterator.hasNext();
2435          }
2436    
2437          @Override
2438          public V next() {
2439            return entryIterator.next().getValue();
2440          }
2441        };
2442      }
2443    
2444      abstract static class Values<K, V> extends AbstractCollection<V> {
2445        abstract Map<K, V> map();
2446    
2447        @Override public Iterator<V> iterator() {
2448          return valueIterator(map().entrySet().iterator());
2449        }
2450    
2451        @Override public boolean remove(Object o) {
2452          try {
2453            return super.remove(o);
2454          } catch (UnsupportedOperationException e) {
2455            for (Entry<K, V> entry : map().entrySet()) {
2456              if (Objects.equal(o, entry.getValue())) {
2457                map().remove(entry.getKey());
2458                return true;
2459              }
2460            }
2461            return false;
2462          }
2463        }
2464    
2465        @Override public boolean removeAll(Collection<?> c) {
2466          try {
2467            return super.removeAll(checkNotNull(c));
2468          } catch (UnsupportedOperationException e) {
2469            Set<K> toRemove = Sets.newHashSet();
2470            for (Entry<K, V> entry : map().entrySet()) {
2471              if (c.contains(entry.getValue())) {
2472                toRemove.add(entry.getKey());
2473              }
2474            }
2475            return map().keySet().removeAll(toRemove);
2476          }
2477        }
2478    
2479        @Override public boolean retainAll(Collection<?> c) {
2480          try {
2481            return super.retainAll(checkNotNull(c));
2482          } catch (UnsupportedOperationException e) {
2483            Set<K> toRetain = Sets.newHashSet();
2484            for (Entry<K, V> entry : map().entrySet()) {
2485              if (c.contains(entry.getValue())) {
2486                toRetain.add(entry.getKey());
2487              }
2488            }
2489            return map().keySet().retainAll(toRetain);
2490          }
2491        }
2492    
2493        @Override public int size() {
2494          return map().size();
2495        }
2496    
2497        @Override public boolean isEmpty() {
2498          return map().isEmpty();
2499        }
2500    
2501        @Override public boolean contains(@Nullable Object o) {
2502          return map().containsValue(o);
2503        }
2504    
2505        @Override public void clear() {
2506          map().clear();
2507        }
2508      }
2509    
2510      abstract static class EntrySet<K, V> extends AbstractSet<Entry<K, V>> {
2511        abstract Map<K, V> map();
2512    
2513        @Override public int size() {
2514          return map().size();
2515        }
2516    
2517        @Override public void clear() {
2518          map().clear();
2519        }
2520    
2521        @Override public boolean contains(Object o) {
2522          if (o instanceof Entry) {
2523            Entry<?, ?> entry = (Entry<?, ?>) o;
2524            Object key = entry.getKey();
2525            V value = map().get(key);
2526            return Objects.equal(value, entry.getValue())
2527                && (value != null || map().containsKey(key));
2528          }
2529          return false;
2530        }
2531    
2532        @Override public boolean isEmpty() {
2533          return map().isEmpty();
2534        }
2535    
2536        @Override public boolean remove(Object o) {
2537          if (contains(o)) {
2538            Entry<?, ?> entry = (Entry<?, ?>) o;
2539            return map().keySet().remove(entry.getKey());
2540          }
2541          return false;
2542        }
2543    
2544        @Override public boolean removeAll(Collection<?> c) {
2545          try {
2546            return super.removeAll(checkNotNull(c));
2547          } catch (UnsupportedOperationException e) {
2548            // if the iterators don't support remove
2549            boolean changed = true;
2550            for (Object o : c) {
2551              changed |= remove(o);
2552            }
2553            return changed;
2554          }
2555        }
2556    
2557        @Override public boolean retainAll(Collection<?> c) {
2558          try {
2559            return super.retainAll(checkNotNull(c));
2560          } catch (UnsupportedOperationException e) {
2561            // if the iterators don't support remove
2562            Set<Object> keys = Sets.newHashSetWithExpectedSize(c.size());
2563            for (Object o : c) {
2564              if (contains(o)) {
2565                Entry<?, ?> entry = (Entry<?, ?>) o;
2566                keys.add(entry.getKey());
2567              }
2568            }
2569            return map().keySet().retainAll(keys);
2570          }
2571        }
2572      }
2573    
2574      @GwtIncompatible("NavigableMap")
2575      static abstract class DescendingMap<K, V> extends ForwardingMap<K, V>
2576          implements NavigableMap<K, V> {
2577    
2578        abstract NavigableMap<K, V> forward();
2579    
2580        @Override
2581        protected final Map<K, V> delegate() {
2582          return forward();
2583        }
2584    
2585        private transient Comparator<? super K> comparator;
2586    
2587        @SuppressWarnings("unchecked")
2588        @Override
2589        public Comparator<? super K> comparator() {
2590          Comparator<? super K> result = comparator;
2591          if (result == null) {
2592            Comparator<? super K> forwardCmp = forward().comparator();
2593            if (forwardCmp == null) {
2594              forwardCmp = (Comparator) Ordering.natural();
2595            }
2596            result = comparator = reverse(forwardCmp);
2597          }
2598          return result;
2599        }
2600    
2601        // If we inline this, we get a javac error.
2602        private static <T> Ordering<T> reverse(Comparator<T> forward) {
2603          return Ordering.from(forward).reverse();
2604        }
2605    
2606        @Override
2607        public K firstKey() {
2608          return forward().lastKey();
2609        }
2610    
2611        @Override
2612        public K lastKey() {
2613          return forward().firstKey();
2614        }
2615    
2616        @Override
2617        public Entry<K, V> lowerEntry(K key) {
2618          return forward().higherEntry(key);
2619        }
2620    
2621        @Override
2622        public K lowerKey(K key) {
2623          return forward().higherKey(key);
2624        }
2625    
2626        @Override
2627        public Entry<K, V> floorEntry(K key) {
2628          return forward().ceilingEntry(key);
2629        }
2630    
2631        @Override
2632        public K floorKey(K key) {
2633          return forward().ceilingKey(key);
2634        }
2635    
2636        @Override
2637        public Entry<K, V> ceilingEntry(K key) {
2638          return forward().floorEntry(key);
2639        }
2640    
2641        @Override
2642        public K ceilingKey(K key) {
2643          return forward().floorKey(key);
2644        }
2645    
2646        @Override
2647        public Entry<K, V> higherEntry(K key) {
2648          return forward().lowerEntry(key);
2649        }
2650    
2651        @Override
2652        public K higherKey(K key) {
2653          return forward().lowerKey(key);
2654        }
2655    
2656        @Override
2657        public Entry<K, V> firstEntry() {
2658          return forward().lastEntry();
2659        }
2660    
2661        @Override
2662        public Entry<K, V> lastEntry() {
2663          return forward().firstEntry();
2664        }
2665    
2666        @Override
2667        public Entry<K, V> pollFirstEntry() {
2668          return forward().pollLastEntry();
2669        }
2670    
2671        @Override
2672        public Entry<K, V> pollLastEntry() {
2673          return forward().pollFirstEntry();
2674        }
2675    
2676        @Override
2677        public NavigableMap<K, V> descendingMap() {
2678          return forward();
2679        }
2680    
2681        private transient Set<Entry<K, V>> entrySet;
2682    
2683        @Override
2684        public Set<Entry<K, V>> entrySet() {
2685          Set<Entry<K, V>> result = entrySet;
2686          return (result == null) ? entrySet = createEntrySet() : result;
2687        }
2688    
2689        abstract Iterator<Entry<K, V>> entryIterator();
2690    
2691        Set<Entry<K, V>> createEntrySet() {
2692          return new EntrySet<K, V>() {
2693    
2694            @Override
2695            Map<K, V> map() {
2696              return DescendingMap.this;
2697            }
2698    
2699            @Override
2700            public Iterator<Entry<K, V>> iterator() {
2701              return entryIterator();
2702            }
2703          };
2704        }
2705    
2706        @Override
2707        public Set<K> keySet() {
2708          return navigableKeySet();
2709        }
2710    
2711        private transient NavigableSet<K> navigableKeySet;
2712    
2713        @Override
2714        public NavigableSet<K> navigableKeySet() {
2715          NavigableSet<K> result = navigableKeySet;
2716          if (result == null) {
2717            result = navigableKeySet = new NavigableKeySet<K, V>() {
2718              @Override
2719              NavigableMap<K, V> map() {
2720                return DescendingMap.this;
2721              }
2722            };
2723          }
2724          return result;
2725        }
2726    
2727        @Override
2728        public NavigableSet<K> descendingKeySet() {
2729          return forward().navigableKeySet();
2730        }
2731    
2732        @Override
2733        public
2734            NavigableMap<K, V>
2735            subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
2736          return forward().subMap(toKey, toInclusive, fromKey, fromInclusive).descendingMap();
2737        }
2738    
2739        @Override
2740        public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
2741          return forward().tailMap(toKey, inclusive).descendingMap();
2742        }
2743    
2744        @Override
2745        public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
2746          return forward().headMap(fromKey, inclusive).descendingMap();
2747        }
2748    
2749        @Override
2750        public SortedMap<K, V> subMap(K fromKey, K toKey) {
2751          return subMap(fromKey, true, toKey, false);
2752        }
2753    
2754        @Override
2755        public SortedMap<K, V> headMap(K toKey) {
2756          return headMap(toKey, false);
2757        }
2758    
2759        @Override
2760        public SortedMap<K, V> tailMap(K fromKey) {
2761          return tailMap(fromKey, true);
2762        }
2763    
2764        @Override
2765        public Collection<V> values() {
2766          return new Values<K, V>() {
2767            @Override
2768            Map<K, V> map() {
2769              return DescendingMap.this;
2770            }
2771          };
2772        }
2773      }
2774    }