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 public static <K, V> MapDifference<K, V> difference(
320 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) {
321 return difference(left, right, Equivalences.equals());
322 }
323
324 /**
325 * Computes the difference between two maps. This difference is an immutable
326 * snapshot of the state of the maps at the time this method is called. It
327 * will never change, even if the maps change at a later time.
328 *
329 * <p>Values are compared using a provided equivalence, in the case of
330 * equality, the value on the 'left' is returned in the difference.
331 *
332 * <p>Since this method uses {@code HashMap} instances internally, the keys of
333 * the supplied maps must be well-behaved with respect to
334 * {@link Object#equals} and {@link Object#hashCode}.
335 *
336 * @param left the map to treat as the "left" map for purposes of comparison
337 * @param right the map to treat as the "right" map for purposes of comparison
338 * @param valueEquivalence the equivalence relationship to use to compare
339 * values
340 * @return the difference between the two maps
341 * @since 10.0
342 */
343 @Beta
344 public static <K, V> MapDifference<K, V> difference(
345 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right,
346 Equivalence<? super V> valueEquivalence) {
347 Preconditions.checkNotNull(valueEquivalence);
348
349 Map<K, V> onlyOnLeft = newHashMap();
350 Map<K, V> onlyOnRight = new HashMap<K, V>(right); // will whittle it down
351 Map<K, V> onBoth = newHashMap();
352 Map<K, MapDifference.ValueDifference<V>> differences = newHashMap();
353 boolean eq = true;
354
355 for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
356 K leftKey = entry.getKey();
357 V leftValue = entry.getValue();
358 if (right.containsKey(leftKey)) {
359 V rightValue = onlyOnRight.remove(leftKey);
360 if (valueEquivalence.equivalent(leftValue, rightValue)) {
361 onBoth.put(leftKey, leftValue);
362 } else {
363 eq = false;
364 differences.put(
365 leftKey, ValueDifferenceImpl.create(leftValue, rightValue));
366 }
367 } else {
368 eq = false;
369 onlyOnLeft.put(leftKey, leftValue);
370 }
371 }
372
373 boolean areEqual = eq && onlyOnRight.isEmpty();
374 return mapDifference(
375 areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
376 }
377
378 private static <K, V> MapDifference<K, V> mapDifference(boolean areEqual,
379 Map<K, V> onlyOnLeft, Map<K, V> onlyOnRight, Map<K, V> onBoth,
380 Map<K, ValueDifference<V>> differences) {
381 return new MapDifferenceImpl<K, V>(areEqual,
382 Collections.unmodifiableMap(onlyOnLeft),
383 Collections.unmodifiableMap(onlyOnRight),
384 Collections.unmodifiableMap(onBoth),
385 Collections.unmodifiableMap(differences));
386 }
387
388 static class MapDifferenceImpl<K, V> implements MapDifference<K, V> {
389 final boolean areEqual;
390 final Map<K, V> onlyOnLeft;
391 final Map<K, V> onlyOnRight;
392 final Map<K, V> onBoth;
393 final Map<K, ValueDifference<V>> differences;
394
395 MapDifferenceImpl(boolean areEqual, Map<K, V> onlyOnLeft,
396 Map<K, V> onlyOnRight, Map<K, V> onBoth,
397 Map<K, ValueDifference<V>> differences) {
398 this.areEqual = areEqual;
399 this.onlyOnLeft = onlyOnLeft;
400 this.onlyOnRight = onlyOnRight;
401 this.onBoth = onBoth;
402 this.differences = differences;
403 }
404
405 @Override
406 public boolean areEqual() {
407 return areEqual;
408 }
409
410 @Override
411 public Map<K, V> entriesOnlyOnLeft() {
412 return onlyOnLeft;
413 }
414
415 @Override
416 public Map<K, V> entriesOnlyOnRight() {
417 return onlyOnRight;
418 }
419
420 @Override
421 public Map<K, V> entriesInCommon() {
422 return onBoth;
423 }
424
425 @Override
426 public Map<K, ValueDifference<V>> entriesDiffering() {
427 return differences;
428 }
429
430 @Override public boolean equals(Object object) {
431 if (object == this) {
432 return true;
433 }
434 if (object instanceof MapDifference) {
435 MapDifference<?, ?> other = (MapDifference<?, ?>) object;
436 return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft())
437 && entriesOnlyOnRight().equals(other.entriesOnlyOnRight())
438 && entriesInCommon().equals(other.entriesInCommon())
439 && entriesDiffering().equals(other.entriesDiffering());
440 }
441 return false;
442 }
443
444 @Override public int hashCode() {
445 return Objects.hashCode(entriesOnlyOnLeft(), entriesOnlyOnRight(),
446 entriesInCommon(), entriesDiffering());
447 }
448
449 @Override public String toString() {
450 if (areEqual) {
451 return "equal";
452 }
453
454 StringBuilder result = new StringBuilder("not equal");
455 if (!onlyOnLeft.isEmpty()) {
456 result.append(": only on left=").append(onlyOnLeft);
457 }
458 if (!onlyOnRight.isEmpty()) {
459 result.append(": only on right=").append(onlyOnRight);
460 }
461 if (!differences.isEmpty()) {
462 result.append(": value differences=").append(differences);
463 }
464 return result.toString();
465 }
466 }
467
468 static class ValueDifferenceImpl<V>
469 implements MapDifference.ValueDifference<V> {
470 private final V left;
471 private final V right;
472
473 static <V> ValueDifference<V> create(@Nullable V left, @Nullable V right) {
474 return new ValueDifferenceImpl<V>(left, right);
475 }
476
477 private ValueDifferenceImpl(@Nullable V left, @Nullable V right) {
478 this.left = left;
479 this.right = right;
480 }
481
482 @Override
483 public V leftValue() {
484 return left;
485 }
486
487 @Override
488 public V rightValue() {
489 return right;
490 }
491
492 @Override public boolean equals(@Nullable Object object) {
493 if (object instanceof MapDifference.ValueDifference<?>) {
494 MapDifference.ValueDifference<?> that =
495 (MapDifference.ValueDifference<?>) object;
496 return Objects.equal(this.left, that.leftValue())
497 && Objects.equal(this.right, that.rightValue());
498 }
499 return false;
500 }
501
502 @Override public int hashCode() {
503 return Objects.hashCode(left, right);
504 }
505
506 @Override public String toString() {
507 return "(" + left + ", " + right + ")";
508 }
509 }
510
511 /**
512 * Returns an immutable map for which the {@link Map#values} are the given
513 * elements in the given order, and each key is the product of invoking a
514 * supplied function on its corresponding value.
515 *
516 * @param values the values to use when constructing the {@code Map}
517 * @param keyFunction the function used to produce the key for each value
518 * @return a map mapping the result of evaluating the function {@code
519 * keyFunction} on each value in the input collection to that value
520 * @throws IllegalArgumentException if {@code keyFunction} produces the same
521 * key for more than one value in the input collection
522 * @throws NullPointerException if any elements of {@code values} is null, or
523 * if {@code keyFunction} produces {@code null} for any value
524 */
525 public static <K, V> ImmutableMap<K, V> uniqueIndex(
526 Iterable<V> values, Function<? super V, K> keyFunction) {
527 return uniqueIndex(values.iterator(), keyFunction);
528 }
529
530 /**
531 * <b>Deprecated.</b>
532 *
533 * @since 10.0
534 * @deprecated use {@link #uniqueIndex(Iterator, Function)} by casting {@code
535 * values} to {@code Iterator<V>}, or better yet, by implementing only
536 * {@code Iterator} and not {@code Iterable}. <b>This method is scheduled
537 * for deletion in March 2012.</b>
538 */
539 @Beta
540 @Deprecated
541 public static <K, V, I extends Object & Iterable<V> & Iterator<V>>
542 ImmutableMap<K, V> uniqueIndex(
543 I values, Function<? super V, K> keyFunction) {
544 Iterable<V> valuesIterable = checkNotNull(values);
545 return uniqueIndex(valuesIterable, keyFunction);
546 }
547
548 /**
549 * Returns an immutable map for which the {@link Map#values} are the given
550 * elements in the given order, and each key is the product of invoking a
551 * supplied function on its corresponding value.
552 *
553 * @param values the values to use when constructing the {@code Map}
554 * @param keyFunction the function used to produce the key for each value
555 * @return a map mapping the result of evaluating the function {@code
556 * keyFunction} on each value in the input collection to that value
557 * @throws IllegalArgumentException if {@code keyFunction} produces the same
558 * key for more than one value in the input collection
559 * @throws NullPointerException if any elements of {@code values} is null, or
560 * if {@code keyFunction} produces {@code null} for any value
561 * @since 10.0
562 */
563 public static <K, V> ImmutableMap<K, V> uniqueIndex(
564 Iterator<V> values, Function<? super V, K> keyFunction) {
565 checkNotNull(keyFunction);
566 ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
567 while (values.hasNext()) {
568 V value = values.next();
569 builder.put(keyFunction.apply(value), value);
570 }
571 return builder.build();
572 }
573
574 /**
575 * Creates an {@code ImmutableMap<String, String>} from a {@code Properties}
576 * instance. Properties normally derive from {@code Map<Object, Object>}, but
577 * they typically contain strings, which is awkward. This method lets you get
578 * a plain-old-{@code Map} out of a {@code Properties}.
579 *
580 * @param properties a {@code Properties} object to be converted
581 * @return an immutable map containing all the entries in {@code properties}
582 * @throws ClassCastException if any key in {@code Properties} is not a {@code
583 * String}
584 * @throws NullPointerException if any key or value in {@code Properties} is
585 * null
586 */
587 @GwtIncompatible("java.util.Properties")
588 public static ImmutableMap<String, String> fromProperties(
589 Properties properties) {
590 ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
591
592 for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements();) {
593 String key = (String) e.nextElement();
594 builder.put(key, properties.getProperty(key));
595 }
596
597 return builder.build();
598 }
599
600 /**
601 * Returns an immutable map entry with the specified key and value. The {@link
602 * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
603 *
604 * <p>The returned entry is serializable.
605 *
606 * @param key the key to be associated with the returned entry
607 * @param value the value to be associated with the returned entry
608 */
609 @GwtCompatible(serializable = true)
610 public static <K, V> Entry<K, V> immutableEntry(
611 @Nullable K key, @Nullable V value) {
612 return new ImmutableEntry<K, V>(key, value);
613 }
614
615 /**
616 * Returns an unmodifiable view of the specified set of entries. The {@link
617 * Entry#setValue} operation throws an {@link UnsupportedOperationException},
618 * as do any operations that would modify the returned set.
619 *
620 * @param entrySet the entries for which to return an unmodifiable view
621 * @return an unmodifiable view of the entries
622 */
623 static <K, V> Set<Entry<K, V>> unmodifiableEntrySet(
624 Set<Entry<K, V>> entrySet) {
625 return new UnmodifiableEntrySet<K, V>(
626 Collections.unmodifiableSet(entrySet));
627 }
628
629 /**
630 * Returns an unmodifiable view of the specified map entry. The {@link
631 * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
632 * This also has the side-effect of redefining {@code equals} to comply with
633 * the Entry contract, to avoid a possible nefarious implementation of equals.
634 *
635 * @param entry the entry for which to return an unmodifiable view
636 * @return an unmodifiable view of the entry
637 */
638 static <K, V> Entry<K, V> unmodifiableEntry(final Entry<K, V> entry) {
639 checkNotNull(entry);
640 return new AbstractMapEntry<K, V>() {
641 @Override public K getKey() {
642 return entry.getKey();
643 }
644
645 @Override public V getValue() {
646 return entry.getValue();
647 }
648 };
649 }
650
651 /** @see Multimaps#unmodifiableEntries */
652 static class UnmodifiableEntries<K, V>
653 extends ForwardingCollection<Entry<K, V>> {
654 private final Collection<Entry<K, V>> entries;
655
656 UnmodifiableEntries(Collection<Entry<K, V>> entries) {
657 this.entries = entries;
658 }
659
660 @Override protected Collection<Entry<K, V>> delegate() {
661 return entries;
662 }
663
664 @Override public Iterator<Entry<K, V>> iterator() {
665 final Iterator<Entry<K, V>> delegate = super.iterator();
666 return new ForwardingIterator<Entry<K, V>>() {
667 @Override public Entry<K, V> next() {
668 return unmodifiableEntry(super.next());
669 }
670
671 @Override public void remove() {
672 throw new UnsupportedOperationException();
673 }
674
675 @Override protected Iterator<Entry<K, V>> delegate() {
676 return delegate;
677 }
678 };
679 }
680
681 // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
682
683 @Override public boolean add(Entry<K, V> element) {
684 throw new UnsupportedOperationException();
685 }
686
687 @Override public boolean addAll(
688 Collection<? extends Entry<K, V>> collection) {
689 throw new UnsupportedOperationException();
690 }
691
692 @Override public void clear() {
693 throw new UnsupportedOperationException();
694 }
695
696 @Override public boolean remove(Object object) {
697 throw new UnsupportedOperationException();
698 }
699
700 @Override public boolean removeAll(Collection<?> collection) {
701 throw new UnsupportedOperationException();
702 }
703
704 @Override public boolean retainAll(Collection<?> collection) {
705 throw new UnsupportedOperationException();
706 }
707
708 @Override public Object[] toArray() {
709 return standardToArray();
710 }
711
712 @Override public <T> T[] toArray(T[] array) {
713 return standardToArray(array);
714 }
715 }
716
717 /** @see Maps#unmodifiableEntrySet(Set) */
718 static class UnmodifiableEntrySet<K, V>
719 extends UnmodifiableEntries<K, V> implements Set<Entry<K, V>> {
720 UnmodifiableEntrySet(Set<Entry<K, V>> entries) {
721 super(entries);
722 }
723
724 // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
725
726 @Override public boolean equals(@Nullable Object object) {
727 return Sets.equalsImpl(this, object);
728 }
729
730 @Override public int hashCode() {
731 return Sets.hashCodeImpl(this);
732 }
733 }
734
735 /**
736 * Returns an unmodifiable view of the specified bimap. This method allows
737 * modules to provide users with "read-only" access to internal bimaps. Query
738 * operations on the returned bimap "read through" to the specified bimap, and
739 * attemps to modify the returned map, whether direct or via its collection
740 * views, result in an {@code UnsupportedOperationException}.
741 *
742 * <p>The returned bimap will be serializable if the specified bimap is
743 * serializable.
744 *
745 * @param bimap the bimap for which an unmodifiable view is to be returned
746 * @return an unmodifiable view of the specified bimap
747 */
748 public static <K, V> BiMap<K, V> unmodifiableBiMap(
749 BiMap<? extends K, ? extends V> bimap) {
750 return new UnmodifiableBiMap<K, V>(bimap, null);
751 }
752
753 /** @see Maps#unmodifiableBiMap(BiMap) */
754 private static class UnmodifiableBiMap<K, V>
755 extends ForwardingMap<K, V> implements BiMap<K, V>, Serializable {
756 final Map<K, V> unmodifiableMap;
757 final BiMap<? extends K, ? extends V> delegate;
758 transient BiMap<V, K> inverse;
759 transient Set<V> values;
760
761 UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate,
762 @Nullable BiMap<V, K> inverse) {
763 unmodifiableMap = Collections.unmodifiableMap(delegate);
764 this.delegate = delegate;
765 this.inverse = inverse;
766 }
767
768 @Override protected Map<K, V> delegate() {
769 return unmodifiableMap;
770 }
771
772 @Override
773 public V forcePut(K key, V value) {
774 throw new UnsupportedOperationException();
775 }
776
777 @Override
778 public BiMap<V, K> inverse() {
779 BiMap<V, K> result = inverse;
780 return (result == null)
781 ? inverse = new UnmodifiableBiMap<V, K>(delegate.inverse(), this)
782 : result;
783 }
784
785 @Override public Set<V> values() {
786 Set<V> result = values;
787 return (result == null)
788 ? values = Collections.unmodifiableSet(delegate.values())
789 : result;
790 }
791
792 private static final long serialVersionUID = 0;
793 }
794
795 /**
796 * Returns a view of a map where each value is transformed by a function. All
797 * other properties of the map, such as iteration order, are left intact. For
798 * example, the code: <pre> {@code
799 *
800 * Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
801 * Function<Integer, Double> sqrt =
802 * new Function<Integer, Double>() {
803 * public Double apply(Integer in) {
804 * return Math.sqrt((int) in);
805 * }
806 * };
807 * Map<String, Double> transformed = Maps.transformValues(map, sqrt);
808 * System.out.println(transformed);}</pre>
809 *
810 * ... prints {@code {a=2.0, b=3.0}}.
811 *
812 * <p>Changes in the underlying map are reflected in this view. Conversely,
813 * this view supports removal operations, and these are reflected in the
814 * underlying map.
815 *
816 * <p>It's acceptable for the underlying map to contain null keys, and even
817 * null values provided that the function is capable of accepting null input.
818 * The transformed map might contain null values, if the function sometimes
819 * gives a null result.
820 *
821 * <p>The returned map is not thread-safe or serializable, even if the
822 * underlying map is.
823 *
824 * <p>The function is applied lazily, invoked when needed. This is necessary
825 * for the returned map to be a view, but it means that the function will be
826 * applied many times for bulk operations like {@link Map#containsValue} and
827 * {@code Map.toString()}. For this to perform well, {@code function} should
828 * be fast. To avoid lazy evaluation when the returned map doesn't need to be
829 * a view, copy the returned map into a new map of your choosing.
830 */
831 public static <K, V1, V2> Map<K, V2> transformValues(
832 Map<K, V1> fromMap, final Function<? super V1, V2> function) {
833 checkNotNull(function);
834 EntryTransformer<K, V1, V2> transformer =
835 new EntryTransformer<K, V1, V2>() {
836 @Override
837 public V2 transformEntry(K key, V1 value) {
838 return function.apply(value);
839 }
840 };
841 return transformEntries(fromMap, transformer);
842 }
843
844 /**
845 * Returns a view of a map whose values are derived from the original map's
846 * entries. In contrast to {@link #transformValues}, this method's
847 * entry-transformation logic may depend on the key as well as the value.
848 *
849 * <p>All other properties of the transformed map, such as iteration order,
850 * are left intact. For example, the code: <pre> {@code
851 *
852 * Map<String, Boolean> options =
853 * ImmutableMap.of("verbose", true, "sort", false);
854 * EntryTransformer<String, Boolean, String> flagPrefixer =
855 * new EntryTransformer<String, Boolean, String>() {
856 * public String transformEntry(String key, Boolean value) {
857 * return value ? key : "no" + key;
858 * }
859 * };
860 * Map<String, String> transformed =
861 * Maps.transformEntries(options, flagPrefixer);
862 * System.out.println(transformed);}</pre>
863 *
864 * ... prints {@code {verbose=verbose, sort=nosort}}.
865 *
866 * <p>Changes in the underlying map are reflected in this view. Conversely,
867 * this view supports removal operations, and these are reflected in the
868 * underlying map.
869 *
870 * <p>It's acceptable for the underlying map to contain null keys and null
871 * values provided that the transformer is capable of accepting null inputs.
872 * The transformed map might contain null values if the transformer sometimes
873 * gives a null result.
874 *
875 * <p>The returned map is not thread-safe or serializable, even if the
876 * underlying map is.
877 *
878 * <p>The transformer is applied lazily, invoked when needed. This is
879 * necessary for the returned map to be a view, but it means that the
880 * transformer will be applied many times for bulk operations like {@link
881 * Map#containsValue} and {@link Object#toString}. For this to perform well,
882 * {@code transformer} should be fast. To avoid lazy evaluation when the
883 * returned map doesn't need to be a view, copy the returned map into a new
884 * map of your choosing.
885 *
886 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
887 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
888 * that {@code k2} is also of type {@code K}. Using an {@code
889 * EntryTransformer} key type for which this may not hold, such as {@code
890 * ArrayList}, may risk a {@code ClassCastException} when calling methods on
891 * the transformed map.
892 *
893 * @since 7.0
894 */
895 public static <K, V1, V2> Map<K, V2> transformEntries(
896 Map<K, V1> fromMap,
897 EntryTransformer<? super K, ? super V1, V2> transformer) {
898 return new TransformedEntriesMap<K, V1, V2>(fromMap, transformer);
899 }
900
901 /**
902 * A transformation of the value of a key-value pair, using both key and value
903 * as inputs. To apply the transformation to a map, use
904 * {@link Maps#transformEntries(Map, EntryTransformer)}.
905 *
906 * @param <K> the key type of the input and output entries
907 * @param <V1> the value type of the input entry
908 * @param <V2> the value type of the output entry
909 * @since 7.0
910 */
911 public interface EntryTransformer<K, V1, V2> {
912 /**
913 * Determines an output value based on a key-value pair. This method is
914 * <i>generally expected</i>, but not absolutely required, to have the
915 * following properties:
916 *
917 * <ul>
918 * <li>Its execution does not cause any observable side effects.
919 * <li>The computation is <i>consistent with equals</i>; that is,
920 * {@link Objects#equal Objects.equal}{@code (k1, k2) &&}
921 * {@link Objects#equal}{@code (v1, v2)} implies that {@code
922 * Objects.equal(transformer.transform(k1, v1),
923 * transformer.transform(k2, v2))}.
924 * </ul>
925 *
926 * @throws NullPointerException if the key or value is null and this
927 * transformer does not accept null arguments
928 */
929 V2 transformEntry(@Nullable K key, @Nullable V1 value);
930 }
931
932 static class TransformedEntriesMap<K, V1, V2>
933 extends AbstractMap<K, V2> {
934 final Map<K, V1> fromMap;
935 final EntryTransformer<? super K, ? super V1, V2> transformer;
936
937 TransformedEntriesMap(
938 Map<K, V1> fromMap,
939 EntryTransformer<? super K, ? super V1, V2> transformer) {
940 this.fromMap = checkNotNull(fromMap);
941 this.transformer = checkNotNull(transformer);
942 }
943
944 @Override public int size() {
945 return fromMap.size();
946 }
947
948 @Override public boolean containsKey(Object key) {
949 return fromMap.containsKey(key);
950 }
951
952 // safe as long as the user followed the <b>Warning</b> in the javadoc
953 @SuppressWarnings("unchecked")
954 @Override public V2 get(Object key) {
955 V1 value = fromMap.get(key);
956 return (value != null || fromMap.containsKey(key))
957 ? transformer.transformEntry((K) key, value)
958 : null;
959 }
960
961 // safe as long as the user followed the <b>Warning</b> in the javadoc
962 @SuppressWarnings("unchecked")
963 @Override public V2 remove(Object key) {
964 return fromMap.containsKey(key)
965 ? transformer.transformEntry((K) key, fromMap.remove(key))
966 : null;
967 }
968
969 @Override public void clear() {
970 fromMap.clear();
971 }
972
973 @Override public Set<K> keySet() {
974 return fromMap.keySet();
975 }
976
977 Set<Entry<K, V2>> entrySet;
978
979 @Override public Set<Entry<K, V2>> entrySet() {
980 Set<Entry<K, V2>> result = entrySet;
981 if (result == null) {
982 entrySet = result = new EntrySet<K, V2>() {
983 @Override Map<K, V2> map() {
984 return TransformedEntriesMap.this;
985 }
986
987 @Override public Iterator<Entry<K, V2>> iterator() {
988 final Iterator<Entry<K, V1>> backingIterator =
989 fromMap.entrySet().iterator();
990 return Iterators.transform(backingIterator,
991 new Function<Entry<K, V1>, Entry<K, V2>>() {
992 @Override public Entry<K, V2> apply(Entry<K, V1> entry) {
993 return immutableEntry(
994 entry.getKey(),
995 transformer.transformEntry(entry.getKey(),
996 entry.getValue()));
997 }
998 });
999 }
1000 };
1001 }
1002 return result;
1003 }
1004
1005 Collection<V2> values;
1006
1007 @Override public Collection<V2> values() {
1008 Collection<V2> result = values;
1009 if (result == null) {
1010 return values = new Values<K, V2>() {
1011 @Override Map<K, V2> map() {
1012 return TransformedEntriesMap.this;
1013 }
1014 };
1015 }
1016 return result;
1017 }
1018 }
1019
1020 /**
1021 * Returns a map containing the mappings in {@code unfiltered} whose keys
1022 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
1023 * changes to one affect the other.
1024 *
1025 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1026 * values()} views have iterators that don't support {@code remove()}, but all
1027 * other methods are supported by the map and its views. When given a key that
1028 * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
1029 * methods throw an {@link IllegalArgumentException}.
1030 *
1031 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1032 * on the filtered map or its views, only mappings whose keys satisfy the
1033 * filter will be removed from the underlying map.
1034 *
1035 * <p>The returned map isn't threadsafe or serializable, even if {@code
1036 * unfiltered} is.
1037 *
1038 * <p>Many of the filtered map's methods, such as {@code size()},
1039 * iterate across every key/value mapping in the underlying map and determine
1040 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1041 * faster to copy the filtered map and use the copy.
1042 *
1043 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
1044 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1045 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1046 * inconsistent with equals.
1047 */
1048 public static <K, V> Map<K, V> filterKeys(
1049 Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1050 checkNotNull(keyPredicate);
1051 Predicate<Entry<K, V>> entryPredicate =
1052 new Predicate<Entry<K, V>>() {
1053 @Override
1054 public boolean apply(Entry<K, V> input) {
1055 return keyPredicate.apply(input.getKey());
1056 }
1057 };
1058 return (unfiltered instanceof AbstractFilteredMap)
1059 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1060 : new FilteredKeyMap<K, V>(
1061 checkNotNull(unfiltered), keyPredicate, entryPredicate);
1062 }
1063
1064 /**
1065 * Returns a map containing the mappings in {@code unfiltered} whose values
1066 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
1067 * changes to one affect the other.
1068 *
1069 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1070 * values()} views have iterators that don't support {@code remove()}, but all
1071 * other methods are supported by the map and its views. When given a value
1072 * that doesn't satisfy the predicate, the map's {@code put()}, {@code
1073 * putAll()}, and {@link Entry#setValue} methods throw an {@link
1074 * IllegalArgumentException}.
1075 *
1076 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1077 * on the filtered map or its views, only mappings whose values satisfy the
1078 * filter will be removed from the underlying map.
1079 *
1080 * <p>The returned map isn't threadsafe or serializable, even if {@code
1081 * unfiltered} is.
1082 *
1083 * <p>Many of the filtered map's methods, such as {@code size()},
1084 * iterate across every key/value mapping in the underlying map and determine
1085 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1086 * faster to copy the filtered map and use the copy.
1087 *
1088 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
1089 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1090 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1091 * inconsistent with equals.
1092 */
1093 public static <K, V> Map<K, V> filterValues(
1094 Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
1095 checkNotNull(valuePredicate);
1096 Predicate<Entry<K, V>> entryPredicate =
1097 new Predicate<Entry<K, V>>() {
1098 @Override
1099 public boolean apply(Entry<K, V> input) {
1100 return valuePredicate.apply(input.getValue());
1101 }
1102 };
1103 return filterEntries(unfiltered, entryPredicate);
1104 }
1105
1106 /**
1107 * Returns a map containing the mappings in {@code unfiltered} that satisfy a
1108 * predicate. The returned map is a live view of {@code unfiltered}; changes
1109 * to one affect the other.
1110 *
1111 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1112 * values()} views have iterators that don't support {@code remove()}, but all
1113 * other methods are supported by the map and its views. When given a
1114 * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
1115 * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
1116 * Similarly, the map's entries have a {@link Entry#setValue} method that
1117 * throws an {@link IllegalArgumentException} when the existing key and the
1118 * provided value don't satisfy the predicate.
1119 *
1120 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1121 * on the filtered map or its views, only mappings that satisfy the filter
1122 * will be removed from the underlying map.
1123 *
1124 * <p>The returned map isn't threadsafe or serializable, even if {@code
1125 * unfiltered} is.
1126 *
1127 * <p>Many of the filtered map's methods, such as {@code size()},
1128 * iterate across every key/value mapping in the underlying map and determine
1129 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1130 * faster to copy the filtered map and use the copy.
1131 *
1132 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
1133 * equals</i>, as documented at {@link Predicate#apply}.
1134 */
1135 public static <K, V> Map<K, V> filterEntries(
1136 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1137 checkNotNull(entryPredicate);
1138 return (unfiltered instanceof AbstractFilteredMap)
1139 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1140 : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate);
1141 }
1142
1143 /**
1144 * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
1145 * filtering a filtered map.
1146 */
1147 private static <K, V> Map<K, V> filterFiltered(AbstractFilteredMap<K, V> map,
1148 Predicate<? super Entry<K, V>> entryPredicate) {
1149 Predicate<Entry<K, V>> predicate =
1150 Predicates.and(map.predicate, entryPredicate);
1151 return new FilteredEntryMap<K, V>(map.unfiltered, predicate);
1152 }
1153
1154 private abstract static class AbstractFilteredMap<K, V>
1155 extends AbstractMap<K, V> {
1156 final Map<K, V> unfiltered;
1157 final Predicate<? super Entry<K, V>> predicate;
1158
1159 AbstractFilteredMap(
1160 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
1161 this.unfiltered = unfiltered;
1162 this.predicate = predicate;
1163 }
1164
1165 boolean apply(Object key, V value) {
1166 // This method is called only when the key is in the map, implying that
1167 // key is a K.
1168 @SuppressWarnings("unchecked")
1169 K k = (K) key;
1170 return predicate.apply(Maps.immutableEntry(k, value));
1171 }
1172
1173 @Override public V put(K key, V value) {
1174 checkArgument(apply(key, value));
1175 return unfiltered.put(key, value);
1176 }
1177
1178 @Override public void putAll(Map<? extends K, ? extends V> map) {
1179 for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
1180 checkArgument(apply(entry.getKey(), entry.getValue()));
1181 }
1182 unfiltered.putAll(map);
1183 }
1184
1185 @Override public boolean containsKey(Object key) {
1186 return unfiltered.containsKey(key) && apply(key, unfiltered.get(key));
1187 }
1188
1189 @Override public V get(Object key) {
1190 V value = unfiltered.get(key);
1191 return ((value != null) && apply(key, value)) ? value : null;
1192 }
1193
1194 @Override public boolean isEmpty() {
1195 return entrySet().isEmpty();
1196 }
1197
1198 @Override public V remove(Object key) {
1199 return containsKey(key) ? unfiltered.remove(key) : null;
1200 }
1201
1202 Collection<V> values;
1203
1204 @Override public Collection<V> values() {
1205 Collection<V> result = values;
1206 return (result == null) ? values = new Values() : result;
1207 }
1208
1209 class Values extends AbstractCollection<V> {
1210 @Override public Iterator<V> iterator() {
1211 final Iterator<Entry<K, V>> entryIterator = entrySet().iterator();
1212 return new UnmodifiableIterator<V>() {
1213 @Override
1214 public boolean hasNext() {
1215 return entryIterator.hasNext();
1216 }
1217
1218 @Override
1219 public V next() {
1220 return entryIterator.next().getValue();
1221 }
1222 };
1223 }
1224
1225 @Override public int size() {
1226 return entrySet().size();
1227 }
1228
1229 @Override public void clear() {
1230 entrySet().clear();
1231 }
1232
1233 @Override public boolean isEmpty() {
1234 return entrySet().isEmpty();
1235 }
1236
1237 @Override public boolean remove(Object o) {
1238 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1239 while (iterator.hasNext()) {
1240 Entry<K, V> entry = iterator.next();
1241 if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) {
1242 iterator.remove();
1243 return true;
1244 }
1245 }
1246 return false;
1247 }
1248
1249 @Override public boolean removeAll(Collection<?> collection) {
1250 checkNotNull(collection);
1251 boolean changed = false;
1252 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1253 while (iterator.hasNext()) {
1254 Entry<K, V> entry = iterator.next();
1255 if (collection.contains(entry.getValue()) && predicate.apply(entry)) {
1256 iterator.remove();
1257 changed = true;
1258 }
1259 }
1260 return changed;
1261 }
1262
1263 @Override public boolean retainAll(Collection<?> collection) {
1264 checkNotNull(collection);
1265 boolean changed = false;
1266 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1267 while (iterator.hasNext()) {
1268 Entry<K, V> entry = iterator.next();
1269 if (!collection.contains(entry.getValue())
1270 && predicate.apply(entry)) {
1271 iterator.remove();
1272 changed = true;
1273 }
1274 }
1275 return changed;
1276 }
1277
1278 @Override public Object[] toArray() {
1279 // creating an ArrayList so filtering happens once
1280 return Lists.newArrayList(iterator()).toArray();
1281 }
1282
1283 @Override public <T> T[] toArray(T[] array) {
1284 return Lists.newArrayList(iterator()).toArray(array);
1285 }
1286 }
1287 }
1288
1289 private static class FilteredKeyMap<K, V> extends AbstractFilteredMap<K, V> {
1290 Predicate<? super K> keyPredicate;
1291
1292 FilteredKeyMap(Map<K, V> unfiltered, Predicate<? super K> keyPredicate,
1293 Predicate<Entry<K, V>> entryPredicate) {
1294 super(unfiltered, entryPredicate);
1295 this.keyPredicate = keyPredicate;
1296 }
1297
1298 Set<Entry<K, V>> entrySet;
1299
1300 @Override public Set<Entry<K, V>> entrySet() {
1301 Set<Entry<K, V>> result = entrySet;
1302 return (result == null)
1303 ? entrySet = Sets.filter(unfiltered.entrySet(), predicate)
1304 : result;
1305 }
1306
1307 Set<K> keySet;
1308
1309 @Override public Set<K> keySet() {
1310 Set<K> result = keySet;
1311 return (result == null)
1312 ? keySet = Sets.filter(unfiltered.keySet(), keyPredicate)
1313 : result;
1314 }
1315
1316 // The cast is called only when the key is in the unfiltered map, implying
1317 // that key is a K.
1318 @Override
1319 @SuppressWarnings("unchecked")
1320 public boolean containsKey(Object key) {
1321 return unfiltered.containsKey(key) && keyPredicate.apply((K) key);
1322 }
1323 }
1324
1325 static class FilteredEntryMap<K, V> extends AbstractFilteredMap<K, V> {
1326 /**
1327 * Entries in this set satisfy the predicate, but they don't validate the
1328 * input to {@code Entry.setValue()}.
1329 */
1330 final Set<Entry<K, V>> filteredEntrySet;
1331
1332 FilteredEntryMap(
1333 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1334 super(unfiltered, entryPredicate);
1335 filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate);
1336 }
1337
1338 Set<Entry<K, V>> entrySet;
1339
1340 @Override public Set<Entry<K, V>> entrySet() {
1341 Set<Entry<K, V>> result = entrySet;
1342 return (result == null) ? entrySet = new EntrySet() : result;
1343 }
1344
1345 private class EntrySet extends ForwardingSet<Entry<K, V>> {
1346 @Override protected Set<Entry<K, V>> delegate() {
1347 return filteredEntrySet;
1348 }
1349
1350 @Override public Iterator<Entry<K, V>> iterator() {
1351 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1352 return new UnmodifiableIterator<Entry<K, V>>() {
1353 @Override
1354 public boolean hasNext() {
1355 return iterator.hasNext();
1356 }
1357
1358 @Override
1359 public Entry<K, V> next() {
1360 final Entry<K, V> entry = iterator.next();
1361 return new ForwardingMapEntry<K, V>() {
1362 @Override protected Entry<K, V> delegate() {
1363 return entry;
1364 }
1365
1366 @Override public V setValue(V value) {
1367 checkArgument(apply(entry.getKey(), value));
1368 return super.setValue(value);
1369 }
1370 };
1371 }
1372 };
1373 }
1374 }
1375
1376 Set<K> keySet;
1377
1378 @Override public Set<K> keySet() {
1379 Set<K> result = keySet;
1380 return (result == null) ? keySet = new KeySet() : result;
1381 }
1382
1383 private class KeySet extends AbstractSet<K> {
1384 @Override public Iterator<K> iterator() {
1385 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1386 return new UnmodifiableIterator<K>() {
1387 @Override
1388 public boolean hasNext() {
1389 return iterator.hasNext();
1390 }
1391
1392 @Override
1393 public K next() {
1394 return iterator.next().getKey();
1395 }
1396 };
1397 }
1398
1399 @Override public int size() {
1400 return filteredEntrySet.size();
1401 }
1402
1403 @Override public void clear() {
1404 filteredEntrySet.clear();
1405 }
1406
1407 @Override public boolean contains(Object o) {
1408 return containsKey(o);
1409 }
1410
1411 @Override public boolean remove(Object o) {
1412 if (containsKey(o)) {
1413 unfiltered.remove(o);
1414 return true;
1415 }
1416 return false;
1417 }
1418
1419 @Override public boolean removeAll(Collection<?> collection) {
1420 checkNotNull(collection); // for GWT
1421 boolean changed = false;
1422 for (Object obj : collection) {
1423 changed |= remove(obj);
1424 }
1425 return changed;
1426 }
1427
1428 @Override public boolean retainAll(Collection<?> collection) {
1429 checkNotNull(collection); // for GWT
1430 boolean changed = false;
1431 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1432 while (iterator.hasNext()) {
1433 Entry<K, V> entry = iterator.next();
1434 if (!collection.contains(entry.getKey()) && predicate.apply(entry)) {
1435 iterator.remove();
1436 changed = true;
1437 }
1438 }
1439 return changed;
1440 }
1441
1442 @Override public Object[] toArray() {
1443 // creating an ArrayList so filtering happens once
1444 return Lists.newArrayList(iterator()).toArray();
1445 }
1446
1447 @Override public <T> T[] toArray(T[] array) {
1448 return Lists.newArrayList(iterator()).toArray(array);
1449 }
1450 }
1451 }
1452
1453 /**
1454 * {@code AbstractMap} extension that implements {@link #isEmpty()} as {@code
1455 * entrySet().isEmpty()} instead of {@code size() == 0} to speed up
1456 * implementations where {@code size()} is O(n), and it delegates the {@code
1457 * isEmpty()} methods of its key set and value collection to this
1458 * implementation.
1459 */
1460 @GwtCompatible
1461 static abstract class ImprovedAbstractMap<K, V> extends AbstractMap<K, V> {
1462 /**
1463 * Creates the entry set to be returned by {@link #entrySet()}. This method
1464 * is invoked at most once on a given map, at the time when {@code entrySet}
1465 * is first called.
1466 */
1467 protected abstract Set<Entry<K, V>> createEntrySet();
1468
1469 private Set<Entry<K, V>> entrySet;
1470
1471 @Override public Set<Entry<K, V>> entrySet() {
1472 Set<Entry<K, V>> result = entrySet;
1473 if (result == null) {
1474 entrySet = result = createEntrySet();
1475 }
1476 return result;
1477 }
1478
1479 private Set<K> keySet;
1480
1481 @Override public Set<K> keySet() {
1482 Set<K> result = keySet;
1483 if (result == null) {
1484 return keySet = new KeySet<K, V>() {
1485 @Override Map<K, V> map() {
1486 return ImprovedAbstractMap.this;
1487 }
1488 };
1489 }
1490 return result;
1491 }
1492
1493 private Collection<V> values;
1494
1495 @Override public Collection<V> values() {
1496 Collection<V> result = values;
1497 if (result == null) {
1498 return values = new Values<K, V>(){
1499 @Override Map<K, V> map() {
1500 return ImprovedAbstractMap.this;
1501 }
1502 };
1503 }
1504 return result;
1505 }
1506
1507 /**
1508 * Returns {@code true} if this map contains no key-value mappings.
1509 *
1510 * <p>The implementation returns {@code entrySet().isEmpty()}.
1511 *
1512 * @return {@code true} if this map contains no key-value mappings
1513 */
1514 @Override public boolean isEmpty() {
1515 return entrySet().isEmpty();
1516 }
1517 }
1518
1519 static final MapJoiner STANDARD_JOINER =
1520 Collections2.STANDARD_JOINER.withKeyValueSeparator("=");
1521
1522 /**
1523 * Delegates to {@link Map#get}. Returns {@code null} on {@code
1524 * ClassCastException}.
1525 */
1526 static <V> V safeGet(Map<?, V> map, Object key) {
1527 try {
1528 return map.get(key);
1529 } catch (ClassCastException e) {
1530 return null;
1531 }
1532 }
1533
1534 /**
1535 * Delegates to {@link Map#containsKey}. Returns {@code false} on {@code
1536 * ClassCastException}
1537 */
1538 static boolean safeContainsKey(Map<?, ?> map, Object key) {
1539 try {
1540 return map.containsKey(key);
1541 } catch (ClassCastException e) {
1542 return false;
1543 }
1544 }
1545
1546 /**
1547 * Implements {@code Collection.contains} safely for forwarding collections of
1548 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
1549 * wrapped using {@link #unmodifiableEntry} to protect against a possible
1550 * nefarious equals method.
1551 *
1552 * <p>Note that {@code c} is the backing (delegate) collection, rather than
1553 * the forwarding collection.
1554 *
1555 * @param c the delegate (unwrapped) collection of map entries
1556 * @param o the object that might be contained in {@code c}
1557 * @return {@code true} if {@code c} contains {@code o}
1558 */
1559 static <K, V> boolean containsEntryImpl(Collection<Entry<K, V>> c, Object o) {
1560 if (!(o instanceof Entry)) {
1561 return false;
1562 }
1563 return c.contains(unmodifiableEntry((Entry<?, ?>) o));
1564 }
1565
1566 /**
1567 * Implements {@code Collection.remove} safely for forwarding collections of
1568 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
1569 * wrapped using {@link #unmodifiableEntry} to protect against a possible
1570 * nefarious equals method.
1571 *
1572 * <p>Note that {@code c} is backing (delegate) collection, rather than the
1573 * forwarding collection.
1574 *
1575 * @param c the delegate (unwrapped) collection of map entries
1576 * @param o the object to remove from {@code c}
1577 * @return {@code true} if {@code c} was changed
1578 */
1579 static <K, V> boolean removeEntryImpl(Collection<Entry<K, V>> c, Object o) {
1580 if (!(o instanceof Entry)) {
1581 return false;
1582 }
1583 return c.remove(unmodifiableEntry((Entry<?, ?>) o));
1584 }
1585
1586 /**
1587 * An implementation of {@link Map#equals}.
1588 */
1589 static boolean equalsImpl(Map<?, ?> map, Object object) {
1590 if (map == object) {
1591 return true;
1592 }
1593 if (object instanceof Map) {
1594 Map<?, ?> o = (Map<?, ?>) object;
1595 return map.entrySet().equals(o.entrySet());
1596 }
1597 return false;
1598 }
1599
1600 /**
1601 * An implementation of {@link Map#hashCode}.
1602 */
1603 static int hashCodeImpl(Map<?, ?> map) {
1604 return Sets.hashCodeImpl(map.entrySet());
1605 }
1606
1607 /**
1608 * An implementation of {@link Map#toString}.
1609 */
1610 static String toStringImpl(Map<?, ?> map) {
1611 StringBuilder sb
1612 = Collections2.newStringBuilderForCollection(map.size()).append('{');
1613 STANDARD_JOINER.appendTo(sb, map);
1614 return sb.append('}').toString();
1615 }
1616
1617 /**
1618 * An implementation of {@link Map#putAll}.
1619 */
1620 static <K, V> void putAllImpl(
1621 Map<K, V> self, Map<? extends K, ? extends V> map) {
1622 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
1623 self.put(entry.getKey(), entry.getValue());
1624 }
1625 }
1626
1627 /**
1628 * An admittedly inefficient implementation of {@link Map#containsKey}.
1629 */
1630 static boolean containsKeyImpl(Map<?, ?> map, @Nullable Object key) {
1631 for (Entry<?, ?> entry : map.entrySet()) {
1632 if (Objects.equal(entry.getKey(), key)) {
1633 return true;
1634 }
1635 }
1636 return false;
1637 }
1638
1639 /**
1640 * An implementation of {@link Map#containsValue}.
1641 */
1642 static boolean containsValueImpl(Map<?, ?> map, @Nullable Object value) {
1643 for (Entry<?, ?> entry : map.entrySet()) {
1644 if (Objects.equal(entry.getValue(), value)) {
1645 return true;
1646 }
1647 }
1648 return false;
1649 }
1650
1651 abstract static class KeySet<K, V> extends AbstractSet<K> {
1652 abstract Map<K, V> map();
1653
1654 @Override public Iterator<K> iterator() {
1655 return Iterators.transform(map().entrySet().iterator(),
1656 new Function<Map.Entry<K, V>, K>() {
1657 @Override public K apply(Entry<K, V> entry) {
1658 return entry.getKey();
1659 }
1660 });
1661 }
1662
1663 @Override public int size() {
1664 return map().size();
1665 }
1666
1667 @Override public boolean isEmpty() {
1668 return map().isEmpty();
1669 }
1670
1671 @Override public boolean contains(Object o) {
1672 return map().containsKey(o);
1673 }
1674
1675 @Override public boolean remove(Object o) {
1676 if (contains(o)) {
1677 map().remove(o);
1678 return true;
1679 }
1680 return false;
1681 }
1682
1683 @Override
1684 public boolean removeAll(Collection<?> c) {
1685 // TODO(user): find out why this is necessary to make GWT tests pass.
1686 return super.removeAll(checkNotNull(c));
1687 }
1688
1689 @Override public void clear() {
1690 map().clear();
1691 }
1692 }
1693
1694 abstract static class Values<K, V> extends AbstractCollection<V> {
1695 abstract Map<K, V> map();
1696
1697 @Override public Iterator<V> iterator() {
1698 return Iterators.transform(map().entrySet().iterator(),
1699 new Function<Entry<K, V>, V>() {
1700 @Override public V apply(Entry<K, V> entry) {
1701 return entry.getValue();
1702 }
1703 });
1704 }
1705
1706 @Override public boolean remove(Object o) {
1707 try {
1708 return super.remove(o);
1709 } catch (UnsupportedOperationException e) {
1710 for (Entry<K, V> entry : map().entrySet()) {
1711 if (Objects.equal(o, entry.getValue())) {
1712 map().remove(entry.getKey());
1713 return true;
1714 }
1715 }
1716 return false;
1717 }
1718 }
1719
1720 @Override public boolean removeAll(Collection<?> c) {
1721 try {
1722 return super.removeAll(checkNotNull(c));
1723 } catch (UnsupportedOperationException e) {
1724 Set<K> toRemove = Sets.newHashSet();
1725 for (Entry<K, V> entry : map().entrySet()) {
1726 if (c.contains(entry.getValue())) {
1727 toRemove.add(entry.getKey());
1728 }
1729 }
1730 return map().keySet().removeAll(toRemove);
1731 }
1732 }
1733
1734 @Override public boolean retainAll(Collection<?> c) {
1735 try {
1736 return super.retainAll(checkNotNull(c));
1737 } catch (UnsupportedOperationException e) {
1738 Set<K> toRetain = Sets.newHashSet();
1739 for (Entry<K, V> entry : map().entrySet()) {
1740 if (c.contains(entry.getValue())) {
1741 toRetain.add(entry.getKey());
1742 }
1743 }
1744 return map().keySet().retainAll(toRetain);
1745 }
1746 }
1747
1748 @Override public int size() {
1749 return map().size();
1750 }
1751
1752 @Override public boolean isEmpty() {
1753 return map().isEmpty();
1754 }
1755
1756 @Override public boolean contains(@Nullable Object o) {
1757 return map().containsValue(o);
1758 }
1759
1760 @Override public void clear() {
1761 map().clear();
1762 }
1763 }
1764
1765 abstract static class EntrySet<K, V> extends AbstractSet<Entry<K, V>> {
1766 abstract Map<K, V> map();
1767
1768 @Override public int size() {
1769 return map().size();
1770 }
1771
1772 @Override public void clear() {
1773 map().clear();
1774 }
1775
1776 @Override public boolean contains(Object o) {
1777 if (o instanceof Entry) {
1778 Entry<?, ?> entry = (Entry<?, ?>) o;
1779 Object key = entry.getKey();
1780 V value = map().get(key);
1781 return Objects.equal(value, entry.getValue())
1782 && (value != null || map().containsKey(key));
1783 }
1784 return false;
1785 }
1786
1787 @Override public boolean isEmpty() {
1788 return map().isEmpty();
1789 }
1790
1791 @Override public boolean remove(Object o) {
1792 if (contains(o)) {
1793 Entry<?, ?> entry = (Entry<?, ?>) o;
1794 return map().keySet().remove(entry.getKey());
1795 }
1796 return false;
1797 }
1798
1799 @Override public boolean removeAll(Collection<?> c) {
1800 try {
1801 return super.removeAll(checkNotNull(c));
1802 } catch (UnsupportedOperationException e) {
1803 // if the iterators don't support remove
1804 boolean changed = true;
1805 for (Object o : c) {
1806 changed |= remove(o);
1807 }
1808 return changed;
1809 }
1810 }
1811
1812 @Override public boolean retainAll(Collection<?> c) {
1813 try {
1814 return super.retainAll(checkNotNull(c));
1815 } catch (UnsupportedOperationException e) {
1816 // if the iterators don't support remove
1817 Set<Object> keys = Sets.newHashSetWithExpectedSize(c.size());
1818 for (Object o : c) {
1819 if (contains(o)) {
1820 Entry<?, ?> entry = (Entry<?, ?>) o;
1821 keys.add(entry.getKey());
1822 }
1823 }
1824 return map().keySet().retainAll(keys);
1825 }
1826 }
1827 }
1828 }