001 /*
002 * Copyright (C) 2007 Google Inc.
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.Function;
026 import com.google.common.base.Joiner.MapJoiner;
027 import com.google.common.base.Objects;
028 import com.google.common.base.Predicate;
029 import com.google.common.base.Predicates;
030 import com.google.common.base.Supplier;
031 import com.google.common.collect.MapDifference.ValueDifference;
032 import com.google.common.primitives.Ints;
033
034 import java.io.Serializable;
035 import java.util.AbstractCollection;
036 import java.util.AbstractMap;
037 import java.util.AbstractSet;
038 import java.util.Collection;
039 import java.util.Collections;
040 import java.util.Comparator;
041 import java.util.EnumMap;
042 import java.util.Enumeration;
043 import java.util.HashMap;
044 import java.util.IdentityHashMap;
045 import java.util.Iterator;
046 import java.util.LinkedHashMap;
047 import java.util.Map;
048 import java.util.Map.Entry;
049 import java.util.Properties;
050 import java.util.Set;
051 import java.util.SortedMap;
052 import java.util.TreeMap;
053 import java.util.concurrent.ConcurrentMap;
054
055 import javax.annotation.Nullable;
056
057 /**
058 * Static utility methods pertaining to {@link Map} instances. Also see this
059 * class's counterparts {@link Lists} and {@link Sets}.
060 *
061 * @author Kevin Bourrillion
062 * @author Mike Bostock
063 * @author Isaac Shum
064 * @author Louis Wasserman
065 * @since 2 (imported from Google Collections Library)
066 */
067 @GwtCompatible(emulated = true)
068 public final class Maps {
069 private Maps() {}
070
071 /**
072 * Creates a <i>mutable</i>, empty {@code HashMap} instance.
073 *
074 * <p><b>Note:</b> if mutability is not required, use {@link
075 * ImmutableMap#of()} instead.
076 *
077 * <p><b>Note:</b> if {@code K} is an {@code enum} type, use {@link
078 * #newEnumMap} instead.
079 *
080 * @return a new, empty {@code HashMap}
081 */
082 public static <K, V> HashMap<K, V> newHashMap() {
083 return new HashMap<K, V>();
084 }
085
086 /**
087 * Creates a {@code HashMap} instance with enough capacity to hold the
088 * specified number of elements without rehashing.
089 *
090 * @param expectedSize the expected size
091 * @return a new, empty {@code HashMap} with enough capacity to hold {@code
092 * expectedSize} elements without rehashing
093 * @throws IllegalArgumentException if {@code expectedSize} is negative
094 */
095 public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(
096 int expectedSize) {
097 /*
098 * The HashMap is constructed with an initialCapacity that's greater than
099 * expectedSize. The larger value is necessary because HashMap resizes its
100 * internal array if the map size exceeds loadFactor * initialCapacity.
101 */
102 return new HashMap<K, V>(capacity(expectedSize));
103 }
104
105 /**
106 * Returns an appropriate value for the "capacity" (in reality, "minimum table
107 * size") parameter of a {@link HashMap} constructor, such that the resulting
108 * table will be between 25% and 50% full when it contains {@code
109 * expectedSize} entries, unless {@code expectedSize} is greater than
110 * {@link Integer#MAX_VALUE} / 2.
111 *
112 * @throws IllegalArgumentException if {@code expectedSize} is negative
113 */
114 static int capacity(int expectedSize) {
115 checkArgument(expectedSize >= 0);
116 // Avoid the int overflow if expectedSize > (Integer.MAX_VALUE / 2)
117 return Ints.saturatedCast(Math.max(expectedSize * 2L, 16L));
118 }
119
120 /**
121 * Creates a <i>mutable</i> {@code HashMap} instance with the same mappings as
122 * the specified map.
123 *
124 * <p><b>Note:</b> if mutability is not required, use {@link
125 * ImmutableMap#copyOf(Map)} instead.
126 *
127 * <p><b>Note:</b> if {@code K} is an {@link Enum} type, use {@link
128 * #newEnumMap} instead.
129 *
130 * @param map the mappings to be placed in the new map
131 * @return a new {@code HashMap} initialized with the mappings from {@code
132 * map}
133 */
134 public static <K, V> HashMap<K, V> newHashMap(
135 Map<? extends K, ? extends V> map) {
136 return new HashMap<K, V>(map);
137 }
138
139 /**
140 * Creates a <i>mutable</i>, empty, insertion-ordered {@code LinkedHashMap}
141 * instance.
142 *
143 * <p><b>Note:</b> if mutability is not required, use {@link
144 * ImmutableMap#of()} instead.
145 *
146 * @return a new, empty {@code LinkedHashMap}
147 */
148 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap() {
149 return new LinkedHashMap<K, V>();
150 }
151
152 /**
153 * Creates a <i>mutable</i>, insertion-ordered {@code LinkedHashMap} instance
154 * with the same mappings as the specified map.
155 *
156 * <p><b>Note:</b> if mutability is not required, use {@link
157 * ImmutableMap#copyOf(Map)} instead.
158 *
159 * @param map the mappings to be placed in the new map
160 * @return a new, {@code LinkedHashMap} initialized with the mappings from
161 * {@code map}
162 */
163 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(
164 Map<? extends K, ? extends V> map) {
165 return new LinkedHashMap<K, V>(map);
166 }
167
168 /**
169 * Returns a general-purpose instance of {@code ConcurrentMap}, which supports
170 * all optional operations of the ConcurrentMap interface. It does not permit
171 * null keys or values. It is serializable.
172 *
173 * <p>This is currently accomplished by calling {@link MapMaker#makeMap()}.
174 *
175 * <p>It is preferable to use {@code MapMaker} directly (rather than through
176 * this method), as it presents numerous useful configuration options,
177 * such as the concurrency level, load factor, key/value reference types,
178 * and value computation.
179 *
180 * @return a new, empty {@code ConcurrentMap}
181 * @since 3
182 */
183 public static <K, V> ConcurrentMap<K, V> newConcurrentMap() {
184 return new MapMaker().<K, V>makeMap();
185 }
186
187 /**
188 * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the natural
189 * ordering of its elements.
190 *
191 * <p><b>Note:</b> if mutability is not required, use {@link
192 * ImmutableSortedMap#of()} instead.
193 *
194 * @return a new, empty {@code TreeMap}
195 */
196 @SuppressWarnings("unchecked") // eclipse doesn't like the raw Comparable
197 public static <K extends Comparable, V> TreeMap<K, V> newTreeMap() {
198 return new TreeMap<K, V>();
199 }
200
201 /**
202 * Creates a <i>mutable</i> {@code TreeMap} instance with the same mappings as
203 * the specified map and using the same ordering as the specified map.
204 *
205 * <p><b>Note:</b> if mutability is not required, use {@link
206 * ImmutableSortedMap#copyOfSorted(SortedMap)} instead.
207 *
208 * @param map the sorted map whose mappings are to be placed in the new map
209 * and whose comparator is to be used to sort the new map
210 * @return a new {@code TreeMap} initialized with the mappings from {@code
211 * map} and using the comparator of {@code map}
212 */
213 public static <K, V> TreeMap<K, V> newTreeMap(SortedMap<K, ? extends V> map) {
214 return new TreeMap<K, V>(map);
215 }
216
217 /**
218 * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the given
219 * comparator.
220 *
221 * <p><b>Note:</b> if mutability is not required, use {@code
222 * ImmutableSortedMap.orderedBy(comparator).build()} instead.
223 *
224 * @param comparator the comparator to sort the keys with
225 * @return a new, empty {@code TreeMap}
226 */
227 public static <C, K extends C, V> TreeMap<K, V> newTreeMap(
228 @Nullable Comparator<C> comparator) {
229 // Ideally, the extra type parameter "C" shouldn't be necessary. It is a
230 // work-around of a compiler type inference quirk that prevents the
231 // following code from being compiled:
232 // Comparator<Class<?>> comparator = null;
233 // Map<Class<? extends Throwable>, String> map = newTreeMap(comparator);
234 return new TreeMap<K, V>(comparator);
235 }
236
237 /**
238 * Creates an {@code EnumMap} instance.
239 *
240 * @param type the key type for this map
241 * @return a new, empty {@code EnumMap}
242 */
243 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(Class<K> type) {
244 return new EnumMap<K, V>(checkNotNull(type));
245 }
246
247 /**
248 * Creates an {@code EnumMap} with the same mappings as the specified map.
249 *
250 * @param map the map from which to initialize this {@code EnumMap}
251 * @return a new {@code EnumMap} initialized with the mappings from {@code
252 * map}
253 * @throws IllegalArgumentException if {@code m} is not an {@code EnumMap}
254 * instance and contains no mappings
255 */
256 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(
257 Map<K, ? extends V> map) {
258 return new EnumMap<K, V>(map);
259 }
260
261 /**
262 * Creates an {@code IdentityHashMap} instance.
263 *
264 * @return a new, empty {@code IdentityHashMap}
265 */
266 public static <K, V> IdentityHashMap<K, V> newIdentityHashMap() {
267 return new IdentityHashMap<K, V>();
268 }
269
270 /**
271 * Returns a synchronized (thread-safe) bimap backed by the specified bimap.
272 * In order to guarantee serial access, it is critical that <b>all</b> access
273 * to the backing bimap is accomplished through the returned bimap.
274 *
275 * <p>It is imperative that the user manually synchronize on the returned map
276 * when accessing any of its collection views: <pre> {@code
277 *
278 * BiMap<Long, String> map = Maps.synchronizedBiMap(
279 * HashBiMap.<Long, String>create());
280 * ...
281 * Set<Long> set = map.keySet(); // Needn't be in synchronized block
282 * ...
283 * synchronized (map) { // Synchronizing on map, not set!
284 * Iterator<Long> it = set.iterator(); // Must be in synchronized block
285 * while (it.hasNext()) {
286 * foo(it.next());
287 * }
288 * }}</pre>
289 *
290 * Failure to follow this advice may result in non-deterministic behavior.
291 *
292 * <p>The returned bimap will be serializable if the specified bimap is
293 * serializable.
294 *
295 * @param bimap the bimap to be wrapped in a synchronized view
296 * @return a sychronized view of the specified bimap
297 */
298 public static <K, V> BiMap<K, V> synchronizedBiMap(BiMap<K, V> bimap) {
299 return Synchronized.biMap(bimap, null);
300 }
301
302 /**
303 * Computes the difference between two maps. This difference is an immutable
304 * snapshot of the state of the maps at the time this method is called. It
305 * will never change, even if the maps change at a later time.
306 *
307 * <p>Since this method uses {@code HashMap} instances internally, the keys of
308 * the supplied maps must be well-behaved with respect to
309 * {@link Object#equals} and {@link Object#hashCode}.
310 *
311 * <p><b>Note:</b>If you only need to know whether two maps have the same
312 * mappings, call {@code left.equals(right)} instead of this method.
313 *
314 * @param left the map to treat as the "left" map for purposes of comparison
315 * @param right the map to treat as the "right" map for purposes of comparison
316 * @return the difference between the two maps
317 */
318 public static <K, V> MapDifference<K, V> difference(
319 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) {
320 Map<K, V> onlyOnLeft = newHashMap();
321 Map<K, V> onlyOnRight = new HashMap<K, V>(right); // will whittle it down
322 Map<K, V> onBoth = newHashMap();
323 Map<K, MapDifference.ValueDifference<V>> differences = newHashMap();
324 boolean eq = true;
325
326 for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
327 K leftKey = entry.getKey();
328 V leftValue = entry.getValue();
329 if (right.containsKey(leftKey)) {
330 V rightValue = onlyOnRight.remove(leftKey);
331 if (Objects.equal(leftValue, rightValue)) {
332 onBoth.put(leftKey, leftValue);
333 } else {
334 eq = false;
335 differences.put(
336 leftKey, new ValueDifferenceImpl<V>(leftValue, rightValue));
337 }
338 } else {
339 eq = false;
340 onlyOnLeft.put(leftKey, leftValue);
341 }
342 }
343
344 boolean areEqual = eq && onlyOnRight.isEmpty();
345 return mapDifference(
346 areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
347 }
348
349 private static <K, V> MapDifference<K, V> mapDifference(boolean areEqual,
350 Map<K, V> onlyOnLeft, Map<K, V> onlyOnRight, Map<K, V> onBoth,
351 Map<K, ValueDifference<V>> differences) {
352 return new MapDifferenceImpl<K, V>(areEqual,
353 Collections.unmodifiableMap(onlyOnLeft),
354 Collections.unmodifiableMap(onlyOnRight),
355 Collections.unmodifiableMap(onBoth),
356 Collections.unmodifiableMap(differences));
357 }
358
359 static class MapDifferenceImpl<K, V> implements MapDifference<K, V> {
360 final boolean areEqual;
361 final Map<K, V> onlyOnLeft;
362 final Map<K, V> onlyOnRight;
363 final Map<K, V> onBoth;
364 final Map<K, ValueDifference<V>> differences;
365
366 MapDifferenceImpl(boolean areEqual, Map<K, V> onlyOnLeft,
367 Map<K, V> onlyOnRight, Map<K, V> onBoth,
368 Map<K, ValueDifference<V>> differences) {
369 this.areEqual = areEqual;
370 this.onlyOnLeft = onlyOnLeft;
371 this.onlyOnRight = onlyOnRight;
372 this.onBoth = onBoth;
373 this.differences = differences;
374 }
375
376 public boolean areEqual() {
377 return areEqual;
378 }
379
380 public Map<K, V> entriesOnlyOnLeft() {
381 return onlyOnLeft;
382 }
383
384 public Map<K, V> entriesOnlyOnRight() {
385 return onlyOnRight;
386 }
387
388 public Map<K, V> entriesInCommon() {
389 return onBoth;
390 }
391
392 public Map<K, ValueDifference<V>> entriesDiffering() {
393 return differences;
394 }
395
396 @Override public boolean equals(Object object) {
397 if (object == this) {
398 return true;
399 }
400 if (object instanceof MapDifference) {
401 MapDifference<?, ?> other = (MapDifference<?, ?>) object;
402 return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft())
403 && entriesOnlyOnRight().equals(other.entriesOnlyOnRight())
404 && entriesInCommon().equals(other.entriesInCommon())
405 && entriesDiffering().equals(other.entriesDiffering());
406 }
407 return false;
408 }
409
410 @Override public int hashCode() {
411 return Objects.hashCode(entriesOnlyOnLeft(), entriesOnlyOnRight(),
412 entriesInCommon(), entriesDiffering());
413 }
414
415 @Override public String toString() {
416 if (areEqual) {
417 return "equal";
418 }
419
420 StringBuilder result = new StringBuilder("not equal");
421 if (!onlyOnLeft.isEmpty()) {
422 result.append(": only on left=").append(onlyOnLeft);
423 }
424 if (!onlyOnRight.isEmpty()) {
425 result.append(": only on right=").append(onlyOnRight);
426 }
427 if (!differences.isEmpty()) {
428 result.append(": value differences=").append(differences);
429 }
430 return result.toString();
431 }
432 }
433
434 static class ValueDifferenceImpl<V>
435 implements MapDifference.ValueDifference<V> {
436 private final V left;
437 private final V right;
438
439 ValueDifferenceImpl(@Nullable V left, @Nullable V right) {
440 this.left = left;
441 this.right = right;
442 }
443
444 public V leftValue() {
445 return left;
446 }
447
448 public V rightValue() {
449 return right;
450 }
451
452 @Override public boolean equals(@Nullable Object object) {
453 if (object instanceof MapDifference.ValueDifference<?>) {
454 MapDifference.ValueDifference<?> that =
455 (MapDifference.ValueDifference<?>) object;
456 return Objects.equal(this.left, that.leftValue())
457 && Objects.equal(this.right, that.rightValue());
458 }
459 return false;
460 }
461
462 @Override public int hashCode() {
463 return Objects.hashCode(left, right);
464 }
465
466 @Override public String toString() {
467 return "(" + left + ", " + right + ")";
468 }
469 }
470
471 /**
472 * Returns an immutable map for which the {@link Map#values} are the given
473 * elements in the given order, and each key is the product of invoking a
474 * supplied function on its corresponding value.
475 *
476 * @param values the values to use when constructing the {@code Map}
477 * @param keyFunction the function used to produce the key for each value
478 * @return a map mapping the result of evaluating the function {@code
479 * keyFunction} on each value in the input collection to that value
480 * @throws IllegalArgumentException if {@code keyFunction} produces the same
481 * key for more than one value in the input collection
482 * @throws NullPointerException if any elements of {@code values} is null, or
483 * if {@code keyFunction} produces {@code null} for any value
484 */
485 public static <K, V> ImmutableMap<K, V> uniqueIndex(
486 Iterable<V> values, Function<? super V, K> keyFunction) {
487 checkNotNull(keyFunction);
488 ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
489 for (V value : values) {
490 builder.put(keyFunction.apply(value), value);
491 }
492 return builder.build();
493 }
494
495 /**
496 * Creates an {@code ImmutableMap<String, String>} from a {@code Properties}
497 * instance. Properties normally derive from {@code Map<Object, Object>}, but
498 * they typically contain strings, which is awkward. This method lets you get
499 * a plain-old-{@code Map} out of a {@code Properties}.
500 *
501 * @param properties a {@code Properties} object to be converted
502 * @return an immutable map containing all the entries in {@code properties}
503 * @throws ClassCastException if any key in {@code Properties} is not a {@code
504 * String}
505 * @throws NullPointerException if any key or value in {@code Properties} is
506 * null
507 */
508 @GwtIncompatible("java.util.Properties")
509 public static ImmutableMap<String, String> fromProperties(
510 Properties properties) {
511 ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
512
513 for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements();) {
514 String key = (String) e.nextElement();
515 builder.put(key, properties.getProperty(key));
516 }
517
518 return builder.build();
519 }
520
521 /**
522 * Returns an immutable map entry with the specified key and value. The {@link
523 * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
524 *
525 * <p>The returned entry is serializable.
526 *
527 * @param key the key to be associated with the returned entry
528 * @param value the value to be associated with the returned entry
529 */
530 @GwtCompatible(serializable = true)
531 public static <K, V> Entry<K, V> immutableEntry(
532 @Nullable K key, @Nullable V value) {
533 return new ImmutableEntry<K, V>(key, value);
534 }
535
536 /**
537 * Returns an unmodifiable view of the specified set of entries. The {@link
538 * Entry#setValue} operation throws an {@link UnsupportedOperationException},
539 * as do any operations that would modify the returned set.
540 *
541 * @param entrySet the entries for which to return an unmodifiable view
542 * @return an unmodifiable view of the entries
543 */
544 static <K, V> Set<Entry<K, V>> unmodifiableEntrySet(
545 Set<Entry<K, V>> entrySet) {
546 return new UnmodifiableEntrySet<K, V>(
547 Collections.unmodifiableSet(entrySet));
548 }
549
550 /**
551 * Returns an unmodifiable view of the specified map entry. The {@link
552 * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
553 * This also has the side-effect of redefining {@code equals} to comply with
554 * the Entry contract, to avoid a possible nefarious implementation of equals.
555 *
556 * @param entry the entry for which to return an unmodifiable view
557 * @return an unmodifiable view of the entry
558 */
559 static <K, V> Entry<K, V> unmodifiableEntry(final Entry<K, V> entry) {
560 checkNotNull(entry);
561 return new AbstractMapEntry<K, V>() {
562 @Override public K getKey() {
563 return entry.getKey();
564 }
565
566 @Override public V getValue() {
567 return entry.getValue();
568 }
569 };
570 }
571
572 /** @see Multimaps#unmodifiableEntries */
573 static class UnmodifiableEntries<K, V>
574 extends ForwardingCollection<Entry<K, V>> {
575 private final Collection<Entry<K, V>> entries;
576
577 UnmodifiableEntries(Collection<Entry<K, V>> entries) {
578 this.entries = entries;
579 }
580
581 @Override protected Collection<Entry<K, V>> delegate() {
582 return entries;
583 }
584
585 @Override public Iterator<Entry<K, V>> iterator() {
586 final Iterator<Entry<K, V>> delegate = super.iterator();
587 return new ForwardingIterator<Entry<K, V>>() {
588 @Override public Entry<K, V> next() {
589 return unmodifiableEntry(super.next());
590 }
591
592 @Override public void remove() {
593 throw new UnsupportedOperationException();
594 }
595
596 @Override protected Iterator<Entry<K, V>> delegate() {
597 return delegate;
598 }
599 };
600 }
601
602 // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
603
604 @Override public boolean add(Entry<K, V> element) {
605 throw new UnsupportedOperationException();
606 }
607
608 @Override public boolean addAll(
609 Collection<? extends Entry<K, V>> collection) {
610 throw new UnsupportedOperationException();
611 }
612
613 @Override public void clear() {
614 throw new UnsupportedOperationException();
615 }
616
617 @Override public boolean remove(Object object) {
618 throw new UnsupportedOperationException();
619 }
620
621 @Override public boolean removeAll(Collection<?> collection) {
622 throw new UnsupportedOperationException();
623 }
624
625 @Override public boolean retainAll(Collection<?> collection) {
626 throw new UnsupportedOperationException();
627 }
628
629 @Override public Object[] toArray() {
630 return standardToArray();
631 }
632
633 @Override public <T> T[] toArray(T[] array) {
634 return standardToArray(array);
635 }
636 }
637
638 /** @see Maps#unmodifiableEntrySet(Set) */
639 static class UnmodifiableEntrySet<K, V>
640 extends UnmodifiableEntries<K, V> implements Set<Entry<K, V>> {
641 UnmodifiableEntrySet(Set<Entry<K, V>> entries) {
642 super(entries);
643 }
644
645 // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
646
647 @Override public boolean equals(@Nullable Object object) {
648 return Sets.equalsImpl(this, object);
649 }
650
651 @Override public int hashCode() {
652 return Sets.hashCodeImpl(this);
653 }
654 }
655
656 /**
657 * Returns an unmodifiable view of the specified bimap. This method allows
658 * modules to provide users with "read-only" access to internal bimaps. Query
659 * operations on the returned bimap "read through" to the specified bimap, and
660 * attemps to modify the returned map, whether direct or via its collection
661 * views, result in an {@code UnsupportedOperationException}.
662 *
663 * <p>The returned bimap will be serializable if the specified bimap is
664 * serializable.
665 *
666 * @param bimap the bimap for which an unmodifiable view is to be returned
667 * @return an unmodifiable view of the specified bimap
668 */
669 public static <K, V> BiMap<K, V> unmodifiableBiMap(
670 BiMap<? extends K, ? extends V> bimap) {
671 return new UnmodifiableBiMap<K, V>(bimap, null);
672 }
673
674 /** @see Maps#unmodifiableBiMap(BiMap) */
675 private static class UnmodifiableBiMap<K, V>
676 extends ForwardingMap<K, V> implements BiMap<K, V>, Serializable {
677 final Map<K, V> unmodifiableMap;
678 final BiMap<? extends K, ? extends V> delegate;
679 transient BiMap<V, K> inverse;
680 transient Set<V> values;
681
682 UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate,
683 @Nullable BiMap<V, K> inverse) {
684 unmodifiableMap = Collections.unmodifiableMap(delegate);
685 this.delegate = delegate;
686 this.inverse = inverse;
687 }
688
689 @Override protected Map<K, V> delegate() {
690 return unmodifiableMap;
691 }
692
693 public V forcePut(K key, V value) {
694 throw new UnsupportedOperationException();
695 }
696
697 public BiMap<V, K> inverse() {
698 BiMap<V, K> result = inverse;
699 return (result == null)
700 ? inverse = new UnmodifiableBiMap<V, K>(delegate.inverse(), this)
701 : result;
702 }
703
704 @Override public Set<V> values() {
705 Set<V> result = values;
706 return (result == null)
707 ? values = Collections.unmodifiableSet(delegate.values())
708 : result;
709 }
710
711 private static final long serialVersionUID = 0;
712 }
713
714 /**
715 * Returns a view of a map where each value is transformed by a function. All
716 * other properties of the map, such as iteration order, are left intact. For
717 * example, the code: <pre> {@code
718 *
719 * Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
720 * Function<Integer, Double> sqrt =
721 * new Function<Integer, Double>() {
722 * public Double apply(Integer in) {
723 * return Math.sqrt((int) in);
724 * }
725 * };
726 * Map<String, Double> transformed = Maps.transformValues(map, sqrt);
727 * System.out.println(transformed);}</pre>
728 *
729 * ... prints {@code {a=2.0, b=3.0}}.
730 *
731 * <p>Changes in the underlying map are reflected in this view. Conversely,
732 * this view supports removal operations, and these are reflected in the
733 * underlying map.
734 *
735 * <p>It's acceptable for the underlying map to contain null keys, and even
736 * null values provided that the function is capable of accepting null input.
737 * The transformed map might contain null values, if the function sometimes
738 * gives a null result.
739 *
740 * <p>The returned map is not thread-safe or serializable, even if the
741 * underlying map is.
742 *
743 * <p>The function is applied lazily, invoked when needed. This is necessary
744 * for the returned map to be a view, but it means that the function will be
745 * applied many times for bulk operations like {@link Map#containsValue} and
746 * {@code Map.toString()}. For this to perform well, {@code function} should
747 * be fast. To avoid lazy evaluation when the returned map doesn't need to be
748 * a view, copy the returned map into a new map of your choosing.
749 */
750 public static <K, V1, V2> Map<K, V2> transformValues(
751 Map<K, V1> fromMap, final Function<? super V1, V2> function) {
752 checkNotNull(function);
753 EntryTransformer<K, V1, V2> transformer =
754 new EntryTransformer<K, V1, V2>() {
755 public V2 transformEntry(K key, V1 value) {
756 return function.apply(value);
757 }
758 };
759 return transformEntries(fromMap, transformer);
760 }
761
762 /**
763 * Returns a view of a map whose values are derived from the original map's
764 * entries. In contrast to {@link #transformValues}, this method's
765 * entry-transformation logic may depend on the key as well as the value.
766 *
767 * <p>All other properties of the transformed map, such as iteration order,
768 * are left intact. For example, the code: <pre> {@code
769 *
770 * Map<String, Boolean> options =
771 * ImmutableMap.of("verbose", true, "sort", false);
772 * EntryTransformer<String, Boolean, String> flagPrefixer =
773 * new EntryTransformer<String, Boolean, String>() {
774 * public String transformEntry(String key, Boolean value) {
775 * return value ? key : "no" + key;
776 * }
777 * };
778 * Map<String, String> transformed =
779 * Maps.transformEntries(options, flagPrefixer);
780 * System.out.println(transformed);}</pre>
781 *
782 * ... prints {@code {verbose=verbose, sort=nosort}}.
783 *
784 * <p>Changes in the underlying map are reflected in this view. Conversely,
785 * this view supports removal operations, and these are reflected in the
786 * underlying map.
787 *
788 * <p>It's acceptable for the underlying map to contain null keys and null
789 * values provided that the transformer is capable of accepting null inputs.
790 * The transformed map might contain null values if the transformer sometimes
791 * gives a null result.
792 *
793 * <p>The returned map is not thread-safe or serializable, even if the
794 * underlying map is.
795 *
796 * <p>The transformer is applied lazily, invoked when needed. This is
797 * necessary for the returned map to be a view, but it means that the
798 * transformer will be applied many times for bulk operations like {@link
799 * Map#containsValue} and {@link Object#toString}. For this to perform well,
800 * {@code transformer} should be fast. To avoid lazy evaluation when the
801 * returned map doesn't need to be a view, copy the returned map into a new
802 * map of your choosing.
803 *
804 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
805 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
806 * that {@code k2} is also of type {@code K}. Using an {@code
807 * EntryTransformer} key type for which this may not hold, such as {@code
808 * ArrayList}, may risk a {@code ClassCastException} when calling methods on
809 * the transformed map.
810 *
811 * @since 7
812 */
813 @Beta
814 public static <K, V1, V2> Map<K, V2> transformEntries(
815 Map<K, V1> fromMap,
816 EntryTransformer<? super K, ? super V1, V2> transformer) {
817 return new TransformedEntriesMap<K, V1, V2>(fromMap, transformer);
818 }
819
820 /**
821 * A transformation of the value of a key-value pair, using both key and value
822 * as inputs. To apply the transformation to a map, use
823 * {@link Maps#transformEntries(Map, EntryTransformer)}.
824 *
825 * @param <K> the key type of the input and output entries
826 * @param <V1> the value type of the input entry
827 * @param <V2> the value type of the output entry
828 * @since 7
829 */
830 @Beta
831 public interface EntryTransformer<K, V1, V2> {
832 /**
833 * Determines an output value based on a key-value pair. This method is
834 * <i>generally expected</i>, but not absolutely required, to have the
835 * following properties:
836 *
837 * <ul>
838 * <li>Its execution does not cause any observable side effects.
839 * <li>The computation is <i>consistent with equals</i>; that is,
840 * {@link Objects#equal Objects.equal}{@code (k1, k2) &&}
841 * {@link Objects#equal}{@code (v1, v2)} implies that {@code
842 * Objects.equal(transformer.transform(k1, v1),
843 * transformer.transform(k2, v2))}.
844 * </ul>
845 *
846 * @throws NullPointerException if the key or value is null and this
847 * transformer does not accept null arguments
848 */
849 V2 transformEntry(@Nullable K key, @Nullable V1 value);
850 }
851
852 static class TransformedEntriesMap<K, V1, V2>
853 extends AbstractMap<K, V2> {
854 final Map<K, V1> fromMap;
855 final EntryTransformer<? super K, ? super V1, V2> transformer;
856
857 TransformedEntriesMap(
858 Map<K, V1> fromMap,
859 EntryTransformer<? super K, ? super V1, V2> transformer) {
860 this.fromMap = checkNotNull(fromMap);
861 this.transformer = checkNotNull(transformer);
862 }
863
864 @Override public int size() {
865 return fromMap.size();
866 }
867
868 @Override public boolean containsKey(Object key) {
869 return fromMap.containsKey(key);
870 }
871
872 // safe as long as the user followed the <b>Warning</b> in the javadoc
873 @SuppressWarnings("unchecked")
874 @Override public V2 get(Object key) {
875 V1 value = fromMap.get(key);
876 return (value != null || fromMap.containsKey(key))
877 ? transformer.transformEntry((K) key, value)
878 : null;
879 }
880
881 // safe as long as the user followed the <b>Warning</b> in the javadoc
882 @SuppressWarnings("unchecked")
883 @Override public V2 remove(Object key) {
884 return fromMap.containsKey(key)
885 ? transformer.transformEntry((K) key, fromMap.remove(key))
886 : null;
887 }
888
889 @Override public void clear() {
890 fromMap.clear();
891 }
892
893 EntrySet entrySet;
894
895 @Override public Set<Entry<K, V2>> entrySet() {
896 EntrySet result = entrySet;
897 if (result == null) {
898 entrySet = result = new EntrySet();
899 }
900 return result;
901 }
902
903 class EntrySet extends AbstractSet<Entry<K, V2>> {
904 @Override public int size() {
905 return TransformedEntriesMap.this.size();
906 }
907
908 @Override public Iterator<Entry<K, V2>> iterator() {
909 final Iterator<Entry<K, V1>> mapIterator =
910 fromMap.entrySet().iterator();
911
912 return new Iterator<Entry<K, V2>>() {
913 public boolean hasNext() {
914 return mapIterator.hasNext();
915 }
916
917 public Entry<K, V2> next() {
918 final Entry<K, V1> entry = mapIterator.next();
919 return new AbstractMapEntry<K, V2>() {
920 @Override public K getKey() {
921 return entry.getKey();
922 }
923
924 @Override public V2 getValue() {
925 return transformer.transformEntry(
926 entry.getKey(), entry.getValue());
927 }
928 };
929 }
930
931 public void remove() {
932 mapIterator.remove();
933 }
934 };
935 }
936
937 @Override public void clear() {
938 fromMap.clear();
939 }
940
941 @Override public boolean contains(Object o) {
942 if (!(o instanceof Entry)) {
943 return false;
944 }
945 Entry<?, ?> entry = (Entry<?, ?>) o;
946 Object entryKey = entry.getKey();
947 Object entryValue = entry.getValue();
948 V2 mapValue = TransformedEntriesMap.this.get(entryKey);
949 if (mapValue != null) {
950 return mapValue.equals(entryValue);
951 }
952 return entryValue == null && containsKey(entryKey);
953 }
954
955 @Override public boolean remove(Object o) {
956 if (contains(o)) {
957 Entry<?, ?> entry = (Entry<?, ?>) o;
958 Object key = entry.getKey();
959 fromMap.remove(key);
960 return true;
961 }
962 return false;
963 }
964 }
965 }
966
967 /**
968 * Returns a map containing the mappings in {@code unfiltered} whose keys
969 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
970 * changes to one affect the other.
971 *
972 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
973 * values()} views have iterators that don't support {@code remove()}, but all
974 * other methods are supported by the map and its views. When given a key that
975 * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
976 * methods throw an {@link IllegalArgumentException}.
977 *
978 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
979 * on the filtered map or its views, only mappings whose keys satisfy the
980 * filter will be removed from the underlying map.
981 *
982 * <p>The returned map isn't threadsafe or serializable, even if {@code
983 * unfiltered} is.
984 *
985 * <p>Many of the filtered map's methods, such as {@code size()},
986 * iterate across every key/value mapping in the underlying map and determine
987 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
988 * faster to copy the filtered map and use the copy.
989 *
990 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
991 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
992 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
993 * inconsistent with equals.
994 */
995 public static <K, V> Map<K, V> filterKeys(
996 Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
997 checkNotNull(keyPredicate);
998 Predicate<Entry<K, V>> entryPredicate =
999 new Predicate<Entry<K, V>>() {
1000 public boolean apply(Entry<K, V> input) {
1001 return keyPredicate.apply(input.getKey());
1002 }
1003 };
1004 return (unfiltered instanceof AbstractFilteredMap)
1005 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1006 : new FilteredKeyMap<K, V>(
1007 checkNotNull(unfiltered), keyPredicate, entryPredicate);
1008 }
1009
1010 /**
1011 * Returns a map containing the mappings in {@code unfiltered} whose values
1012 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
1013 * changes to one affect the other.
1014 *
1015 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1016 * values()} views have iterators that don't support {@code remove()}, but all
1017 * other methods are supported by the map and its views. When given a value
1018 * that doesn't satisfy the predicate, the map's {@code put()}, {@code
1019 * putAll()}, and {@link Entry#setValue} methods throw an {@link
1020 * IllegalArgumentException}.
1021 *
1022 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1023 * on the filtered map or its views, only mappings whose values satisfy the
1024 * filter will be removed from the underlying map.
1025 *
1026 * <p>The returned map isn't threadsafe or serializable, even if {@code
1027 * unfiltered} is.
1028 *
1029 * <p>Many of the filtered map's methods, such as {@code size()},
1030 * iterate across every key/value mapping in the underlying map and determine
1031 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1032 * faster to copy the filtered map and use the copy.
1033 *
1034 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
1035 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1036 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1037 * inconsistent with equals.
1038 */
1039 public static <K, V> Map<K, V> filterValues(
1040 Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
1041 checkNotNull(valuePredicate);
1042 Predicate<Entry<K, V>> entryPredicate =
1043 new Predicate<Entry<K, V>>() {
1044 public boolean apply(Entry<K, V> input) {
1045 return valuePredicate.apply(input.getValue());
1046 }
1047 };
1048 return filterEntries(unfiltered, entryPredicate);
1049 }
1050
1051 /**
1052 * Returns a map containing the mappings in {@code unfiltered} that satisfy a
1053 * predicate. The returned map is a live view of {@code unfiltered}; changes
1054 * to one affect the other.
1055 *
1056 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1057 * values()} views have iterators that don't support {@code remove()}, but all
1058 * other methods are supported by the map and its views. When given a
1059 * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
1060 * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
1061 * Similarly, the map's entries have a {@link Entry#setValue} method that
1062 * throws an {@link IllegalArgumentException} when the existing key and the
1063 * provided value don't satisfy the predicate.
1064 *
1065 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1066 * on the filtered map or its views, only mappings that satisfy the filter
1067 * will be removed from the underlying map.
1068 *
1069 * <p>The returned map isn't threadsafe or serializable, even if {@code
1070 * unfiltered} is.
1071 *
1072 * <p>Many of the filtered map's methods, such as {@code size()},
1073 * iterate across every key/value mapping in the underlying map and determine
1074 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1075 * faster to copy the filtered map and use the copy.
1076 *
1077 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
1078 * equals</i>, as documented at {@link Predicate#apply}.
1079 */
1080 public static <K, V> Map<K, V> filterEntries(
1081 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1082 checkNotNull(entryPredicate);
1083 return (unfiltered instanceof AbstractFilteredMap)
1084 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1085 : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate);
1086 }
1087
1088 /**
1089 * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
1090 * filtering a filtered map.
1091 */
1092 private static <K, V> Map<K, V> filterFiltered(AbstractFilteredMap<K, V> map,
1093 Predicate<? super Entry<K, V>> entryPredicate) {
1094 Predicate<Entry<K, V>> predicate =
1095 Predicates.and(map.predicate, entryPredicate);
1096 return new FilteredEntryMap<K, V>(map.unfiltered, predicate);
1097 }
1098
1099 private abstract static class AbstractFilteredMap<K, V>
1100 extends AbstractMap<K, V> {
1101 final Map<K, V> unfiltered;
1102 final Predicate<? super Entry<K, V>> predicate;
1103
1104 AbstractFilteredMap(
1105 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
1106 this.unfiltered = unfiltered;
1107 this.predicate = predicate;
1108 }
1109
1110 boolean apply(Object key, V value) {
1111 // This method is called only when the key is in the map, implying that
1112 // key is a K.
1113 @SuppressWarnings("unchecked")
1114 K k = (K) key;
1115 return predicate.apply(Maps.immutableEntry(k, value));
1116 }
1117
1118 @Override public V put(K key, V value) {
1119 checkArgument(apply(key, value));
1120 return unfiltered.put(key, value);
1121 }
1122
1123 @Override public void putAll(Map<? extends K, ? extends V> map) {
1124 for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
1125 checkArgument(apply(entry.getKey(), entry.getValue()));
1126 }
1127 unfiltered.putAll(map);
1128 }
1129
1130 @Override public boolean containsKey(Object key) {
1131 return unfiltered.containsKey(key) && apply(key, unfiltered.get(key));
1132 }
1133
1134 @Override public V get(Object key) {
1135 V value = unfiltered.get(key);
1136 return ((value != null) && apply(key, value)) ? value : null;
1137 }
1138
1139 @Override public boolean isEmpty() {
1140 return entrySet().isEmpty();
1141 }
1142
1143 @Override public V remove(Object key) {
1144 return containsKey(key) ? unfiltered.remove(key) : null;
1145 }
1146
1147 Collection<V> values;
1148
1149 @Override public Collection<V> values() {
1150 Collection<V> result = values;
1151 return (result == null) ? values = new Values() : result;
1152 }
1153
1154 class Values extends AbstractCollection<V> {
1155 @Override public Iterator<V> iterator() {
1156 final Iterator<Entry<K, V>> entryIterator = entrySet().iterator();
1157 return new UnmodifiableIterator<V>() {
1158 public boolean hasNext() {
1159 return entryIterator.hasNext();
1160 }
1161
1162 public V next() {
1163 return entryIterator.next().getValue();
1164 }
1165 };
1166 }
1167
1168 @Override public int size() {
1169 return entrySet().size();
1170 }
1171
1172 @Override public void clear() {
1173 entrySet().clear();
1174 }
1175
1176 @Override public boolean isEmpty() {
1177 return entrySet().isEmpty();
1178 }
1179
1180 @Override public boolean remove(Object o) {
1181 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1182 while (iterator.hasNext()) {
1183 Entry<K, V> entry = iterator.next();
1184 if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) {
1185 iterator.remove();
1186 return true;
1187 }
1188 }
1189 return false;
1190 }
1191
1192 @Override public boolean removeAll(Collection<?> collection) {
1193 checkNotNull(collection);
1194 boolean changed = false;
1195 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1196 while (iterator.hasNext()) {
1197 Entry<K, V> entry = iterator.next();
1198 if (collection.contains(entry.getValue()) && predicate.apply(entry)) {
1199 iterator.remove();
1200 changed = true;
1201 }
1202 }
1203 return changed;
1204 }
1205
1206 @Override public boolean retainAll(Collection<?> collection) {
1207 checkNotNull(collection);
1208 boolean changed = false;
1209 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1210 while (iterator.hasNext()) {
1211 Entry<K, V> entry = iterator.next();
1212 if (!collection.contains(entry.getValue())
1213 && predicate.apply(entry)) {
1214 iterator.remove();
1215 changed = true;
1216 }
1217 }
1218 return changed;
1219 }
1220
1221 @Override public Object[] toArray() {
1222 // creating an ArrayList so filtering happens once
1223 return Lists.newArrayList(iterator()).toArray();
1224 }
1225
1226 @Override public <T> T[] toArray(T[] array) {
1227 return Lists.newArrayList(iterator()).toArray(array);
1228 }
1229 }
1230 }
1231
1232 private static class FilteredKeyMap<K, V> extends AbstractFilteredMap<K, V> {
1233 Predicate<? super K> keyPredicate;
1234
1235 FilteredKeyMap(Map<K, V> unfiltered, Predicate<? super K> keyPredicate,
1236 Predicate<Entry<K, V>> entryPredicate) {
1237 super(unfiltered, entryPredicate);
1238 this.keyPredicate = keyPredicate;
1239 }
1240
1241 Set<Entry<K, V>> entrySet;
1242
1243 @Override public Set<Entry<K, V>> entrySet() {
1244 Set<Entry<K, V>> result = entrySet;
1245 return (result == null)
1246 ? entrySet = Sets.filter(unfiltered.entrySet(), predicate)
1247 : result;
1248 }
1249
1250 Set<K> keySet;
1251
1252 @Override public Set<K> keySet() {
1253 Set<K> result = keySet;
1254 return (result == null)
1255 ? keySet = Sets.filter(unfiltered.keySet(), keyPredicate)
1256 : result;
1257 }
1258
1259 // The cast is called only when the key is in the unfiltered map, implying
1260 // that key is a K.
1261 @Override
1262 @SuppressWarnings("unchecked")
1263 public boolean containsKey(Object key) {
1264 return unfiltered.containsKey(key) && keyPredicate.apply((K) key);
1265 }
1266 }
1267
1268 static class FilteredEntryMap<K, V> extends AbstractFilteredMap<K, V> {
1269 /**
1270 * Entries in this set satisfy the predicate, but they don't validate the
1271 * input to {@code Entry.setValue()}.
1272 */
1273 final Set<Entry<K, V>> filteredEntrySet;
1274
1275 FilteredEntryMap(
1276 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1277 super(unfiltered, entryPredicate);
1278 filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate);
1279 }
1280
1281 Set<Entry<K, V>> entrySet;
1282
1283 @Override public Set<Entry<K, V>> entrySet() {
1284 Set<Entry<K, V>> result = entrySet;
1285 return (result == null) ? entrySet = new EntrySet() : result;
1286 }
1287
1288 private class EntrySet extends ForwardingSet<Entry<K, V>> {
1289 @Override protected Set<Entry<K, V>> delegate() {
1290 return filteredEntrySet;
1291 }
1292
1293 @Override public Iterator<Entry<K, V>> iterator() {
1294 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1295 return new UnmodifiableIterator<Entry<K, V>>() {
1296 public boolean hasNext() {
1297 return iterator.hasNext();
1298 }
1299
1300 public Entry<K, V> next() {
1301 final Entry<K, V> entry = iterator.next();
1302 return new ForwardingMapEntry<K, V>() {
1303 @Override protected Entry<K, V> delegate() {
1304 return entry;
1305 }
1306
1307 @Override public V setValue(V value) {
1308 checkArgument(apply(entry.getKey(), value));
1309 return super.setValue(value);
1310 }
1311 };
1312 }
1313 };
1314 }
1315 }
1316
1317 Set<K> keySet;
1318
1319 @Override public Set<K> keySet() {
1320 Set<K> result = keySet;
1321 return (result == null) ? keySet = new KeySet() : result;
1322 }
1323
1324 private class KeySet extends AbstractSet<K> {
1325 @Override public Iterator<K> iterator() {
1326 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1327 return new UnmodifiableIterator<K>() {
1328 public boolean hasNext() {
1329 return iterator.hasNext();
1330 }
1331
1332 public K next() {
1333 return iterator.next().getKey();
1334 }
1335 };
1336 }
1337
1338 @Override public int size() {
1339 return filteredEntrySet.size();
1340 }
1341
1342 @Override public void clear() {
1343 filteredEntrySet.clear();
1344 }
1345
1346 @Override public boolean contains(Object o) {
1347 return containsKey(o);
1348 }
1349
1350 @Override public boolean remove(Object o) {
1351 if (containsKey(o)) {
1352 unfiltered.remove(o);
1353 return true;
1354 }
1355 return false;
1356 }
1357
1358 @Override public boolean removeAll(Collection<?> collection) {
1359 checkNotNull(collection); // for GWT
1360 boolean changed = false;
1361 for (Object obj : collection) {
1362 changed |= remove(obj);
1363 }
1364 return changed;
1365 }
1366
1367 @Override public boolean retainAll(Collection<?> collection) {
1368 checkNotNull(collection); // for GWT
1369 boolean changed = false;
1370 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1371 while (iterator.hasNext()) {
1372 Entry<K, V> entry = iterator.next();
1373 if (!collection.contains(entry.getKey()) && predicate.apply(entry)) {
1374 iterator.remove();
1375 changed = true;
1376 }
1377 }
1378 return changed;
1379 }
1380
1381 @Override public Object[] toArray() {
1382 // creating an ArrayList so filtering happens once
1383 return Lists.newArrayList(iterator()).toArray();
1384 }
1385
1386 @Override public <T> T[] toArray(T[] array) {
1387 return Lists.newArrayList(iterator()).toArray(array);
1388 }
1389 }
1390 }
1391
1392 /**
1393 * {@code AbstractMap} extension that implements {@link #isEmpty()} as {@code
1394 * entrySet().isEmpty()} instead of {@code size() == 0} to speed up
1395 * implementations where {@code size()} is O(n), and it delegates the {@code
1396 * isEmpty()} methods of its key set and value collection to this
1397 * implementation.
1398 */
1399 @GwtCompatible
1400 abstract static class ImprovedAbstractMap<K, V> extends AbstractMap<K, V> {
1401 /**
1402 * Creates the entry set to be returned by {@link #entrySet()}. This method
1403 * is invoked at most once on a given map, at the time when {@code entrySet}
1404 * is first called.
1405 */
1406 protected abstract Set<Entry<K, V>> createEntrySet();
1407
1408 private Set<Entry<K, V>> entrySet;
1409
1410 @Override public Set<Entry<K, V>> entrySet() {
1411 Set<Entry<K, V>> result = entrySet;
1412 if (result == null) {
1413 entrySet = result = createEntrySet();
1414 }
1415 return result;
1416 }
1417
1418 private Set<K> keySet;
1419
1420 @Override public Set<K> keySet() {
1421 Set<K> result = keySet;
1422 if (result == null) {
1423 final Set<K> delegate = super.keySet();
1424 keySet = result = new ForwardingSet<K>() {
1425 @Override protected Set<K> delegate() {
1426 return delegate;
1427 }
1428
1429 @Override public boolean isEmpty() {
1430 return ImprovedAbstractMap.this.isEmpty();
1431 }
1432
1433 @Override public boolean remove(Object object) {
1434 if (contains(object)) {
1435 ImprovedAbstractMap.this.remove(object);
1436 return true;
1437 }
1438 return false;
1439 }
1440 };
1441 }
1442 return result;
1443 }
1444
1445 private Collection<V> values;
1446
1447 @Override public Collection<V> values() {
1448 Collection<V> result = values;
1449 if (result == null) {
1450 final Collection<V> delegate = super.values();
1451 values = result = new ForwardingCollection<V>() {
1452 @Override protected Collection<V> delegate() {
1453 return delegate;
1454 }
1455
1456 @Override public boolean isEmpty() {
1457 return ImprovedAbstractMap.this.isEmpty();
1458 }
1459 };
1460 }
1461 return result;
1462 }
1463
1464 /**
1465 * Returns {@code true} if this map contains no key-value mappings.
1466 *
1467 * <p>The implementation returns {@code entrySet().isEmpty()}.
1468 *
1469 * @return {@code true} if this map contains no key-value mappings
1470 */
1471 @Override public boolean isEmpty() {
1472 return entrySet().isEmpty();
1473 }
1474 }
1475
1476 static final MapJoiner STANDARD_JOINER =
1477 Collections2.STANDARD_JOINER.withKeyValueSeparator("=");
1478
1479 /**
1480 * Delegates to {@link Map#get}. Returns {@code null} on {@code
1481 * ClassCastException}.
1482 */
1483 static <V> V safeGet(Map<?, V> map, Object key) {
1484 try {
1485 return map.get(key);
1486 } catch (ClassCastException e) {
1487 return null;
1488 }
1489 }
1490
1491 /**
1492 * Delegates to {@link Map#containsKey}. Returns {@code false} on {@code
1493 * ClassCastException}
1494 */
1495 static boolean safeContainsKey(Map<?, ?> map, Object key) {
1496 try {
1497 return map.containsKey(key);
1498 } catch (ClassCastException e) {
1499 return false;
1500 }
1501 }
1502
1503 /**
1504 * An implementation of {@link Map#entrySet}.
1505 */
1506 static <K, V> Set<Entry<K, V>> entrySetImpl(
1507 Map<K, V> map, Supplier<Iterator<Entry<K, V>>> entryIteratorSupplier) {
1508 return new EntrySetImpl<K, V>(map, entryIteratorSupplier);
1509 }
1510
1511 private static class EntrySetImpl<K, V> extends AbstractSet<Entry<K, V>> {
1512 private final Map<K, V> map;
1513 private final Supplier<Iterator<Entry<K, V>>> entryIteratorSupplier;
1514
1515 EntrySetImpl(
1516 Map<K, V> map, Supplier<Iterator<Entry<K, V>>> entryIteratorSupplier) {
1517 this.map = checkNotNull(map);
1518 this.entryIteratorSupplier = checkNotNull(entryIteratorSupplier);
1519 }
1520
1521 @Override public Iterator<Entry<K, V>> iterator() {
1522 return entryIteratorSupplier.get();
1523 }
1524
1525 @Override public int size() {
1526 return map.size();
1527 }
1528
1529 @Override public void clear() {
1530 map.clear();
1531 }
1532
1533 @Override public boolean contains(Object o) {
1534 if (o instanceof Entry) {
1535 Entry<?, ?> entry = (Entry<?, ?>) o;
1536 Object key = entry.getKey();
1537 if (map.containsKey(key)) {
1538 V value = map.get(entry.getKey());
1539 return Objects.equal(value, entry.getValue());
1540 }
1541 }
1542 return false;
1543 }
1544
1545 @Override public boolean isEmpty() {
1546 return map.isEmpty();
1547 }
1548
1549 @Override public boolean remove(Object o) {
1550 if (contains(o)) {
1551 Entry<?, ?> entry = (Entry<?, ?>) o;
1552 map.remove(entry.getKey());
1553 return true;
1554 }
1555 return false;
1556 }
1557
1558 @Override public int hashCode() {
1559 return map.hashCode();
1560 }
1561 }
1562
1563 /**
1564 * Implements {@code Collection.contains} safely for forwarding collections of
1565 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
1566 * wrapped using {@link #unmodifiableEntry} to protect against a possible
1567 * nefarious equals method.
1568 *
1569 * <p>Note that {@code c} is the backing (delegate) collection, rather than
1570 * the forwarding collection.
1571 *
1572 * @param c the delegate (unwrapped) collection of map entries
1573 * @param o the object that might be contained in {@code c}
1574 * @return {@code true} if {@code c} contains {@code o}
1575 */
1576 static <K, V> boolean containsEntryImpl(Collection<Entry<K, V>> c, Object o) {
1577 if (!(o instanceof Entry)) {
1578 return false;
1579 }
1580 return c.contains(unmodifiableEntry((Entry<?, ?>) o));
1581 }
1582
1583 /**
1584 * Implements {@code Collection.remove} safely for forwarding collections of
1585 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
1586 * wrapped using {@link #unmodifiableEntry} to protect against a possible
1587 * nefarious equals method.
1588 *
1589 * <p>Note that {@code c} is backing (delegate) collection, rather than the
1590 * forwarding collection.
1591 *
1592 * @param c the delegate (unwrapped) collection of map entries
1593 * @param o the object to remove from {@code c}
1594 * @return {@code true} if {@code c} was changed
1595 */
1596 static <K, V> boolean removeEntryImpl(Collection<Entry<K, V>> c, Object o) {
1597 if (!(o instanceof Entry)) {
1598 return false;
1599 }
1600 return c.remove(unmodifiableEntry((Entry<?, ?>) o));
1601 }
1602
1603 /**
1604 * An implementation of {@link Map#equals}.
1605 */
1606 static boolean equalsImpl(Map<?, ?> map, Object object) {
1607 if (map == object) {
1608 return true;
1609 }
1610 if (object instanceof Map) {
1611 Map<?, ?> o = (Map<?, ?>) object;
1612 return map.entrySet().equals(o.entrySet());
1613 }
1614 return false;
1615 }
1616
1617 /**
1618 * An implementation of {@link Map#hashCode}.
1619 */
1620 static int hashCodeImpl(Map<?, ?> map) {
1621 return Sets.hashCodeImpl(map.entrySet());
1622 }
1623
1624 /**
1625 * An implementation of {@link Map#toString}.
1626 */
1627 static String toStringImpl(Map<?, ?> map) {
1628 StringBuilder sb
1629 = Collections2.newStringBuilderForCollection(map.size()).append('{');
1630 STANDARD_JOINER.appendTo(sb, map);
1631 return sb.append('}').toString();
1632 }
1633
1634 /**
1635 * An implementation of {@link Map#putAll}.
1636 */
1637 static <K, V> void putAllImpl(
1638 Map<K, V> self, Map<? extends K, ? extends V> map) {
1639 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
1640 self.put(entry.getKey(), entry.getValue());
1641 }
1642 }
1643
1644 /**
1645 * An implementation of {@link Map#keySet}.
1646 */
1647 static <K, V> Set<K> keySetImpl(final Map<K, V> map) {
1648 return new AbstractMapWrapper<K, V>(map).keySet();
1649 }
1650
1651 /**
1652 * An admittedly inefficient implementation of {@link Map#containsKey}.
1653 */
1654 static boolean containsKeyImpl(Map<?, ?> map, @Nullable Object key) {
1655 for (Entry<?, ?> entry : map.entrySet()) {
1656 if (Objects.equal(entry.getKey(), key)) {
1657 return true;
1658 }
1659 }
1660 return false;
1661 }
1662
1663 /**
1664 * An implementation of {@link Map#values}.
1665 */
1666 static <K, V> Collection<V> valuesImpl(Map<K, V> map) {
1667 return new AbstractMapWrapper<K, V>(map).values();
1668 }
1669
1670 /**
1671 * An implementation of {@link Map#containsValue}.
1672 */
1673 static boolean containsValueImpl(Map<?, ?> map, @Nullable Object value) {
1674 for (Entry<?, ?> entry : map.entrySet()) {
1675 if (Objects.equal(entry.getValue(), value)) {
1676 return true;
1677 }
1678 }
1679 return false;
1680 }
1681
1682 /**
1683 * A wrapper on a map that supplies the {@code ImprovedAbstractMap}
1684 * implementations of {@code keySet()} and {@code values()}.
1685 */
1686 private static final class AbstractMapWrapper<K, V>
1687 extends ImprovedAbstractMap<K, V>{
1688 private final Map<K, V> map;
1689
1690 AbstractMapWrapper(Map<K, V> map) {
1691 this.map = checkNotNull(map);
1692 }
1693
1694 @Override public void clear() {
1695 map.clear();
1696 }
1697
1698 @Override public boolean containsKey(Object key) {
1699 return map.containsKey(key);
1700 }
1701
1702 @Override public V remove(Object key) {
1703 return map.remove(key);
1704 }
1705
1706 @Override public boolean containsValue(Object value) {
1707 return map.containsValue(value);
1708 }
1709
1710 @Override protected Set<Entry<K, V>> createEntrySet() {
1711 return map.entrySet();
1712 }
1713
1714 @Override public boolean isEmpty() {
1715 return map.isEmpty();
1716 }
1717
1718 @Override public int size() {
1719 return map.size();
1720 }
1721 }
1722 }