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