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