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