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