001/* 002 * Copyright (C) 2009 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021import static com.google.common.collect.CollectPreconditions.checkEntryNotNull; 022import static com.google.common.collect.Maps.keyOrNull; 023 024import com.google.common.annotations.Beta; 025import com.google.common.annotations.GwtCompatible; 026import com.google.errorprone.annotations.CanIgnoreReturnValue; 027import com.google.j2objc.annotations.WeakOuter; 028import java.util.AbstractMap; 029import java.util.Arrays; 030import java.util.Comparator; 031import java.util.Map; 032import java.util.NavigableMap; 033import java.util.SortedMap; 034import java.util.Spliterator; 035import java.util.TreeMap; 036import java.util.function.BiConsumer; 037import java.util.function.BinaryOperator; 038import java.util.function.Consumer; 039import java.util.function.Function; 040import java.util.stream.Collector; 041import java.util.stream.Collectors; 042import javax.annotation.Nullable; 043 044/** 045 * A {@link NavigableMap} whose contents will never change, with many other important properties 046 * detailed at {@link ImmutableCollection}. 047 * 048 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link 049 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with 050 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero 051 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting map will 052 * not correctly obey its specification. 053 * 054 * <p>See the Guava User Guide article on <a href= 055 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> 056 * immutable collections</a>. 057 * 058 * @author Jared Levy 059 * @author Louis Wasserman 060 * @since 2.0 (implements {@code NavigableMap} since 12.0) 061 */ 062@GwtCompatible(serializable = true, emulated = true) 063public final class ImmutableSortedMap<K, V> extends ImmutableSortedMapFauxverideShim<K, V> 064 implements NavigableMap<K, V> { 065 /** 066 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} 067 * whose keys and values are the result of applying the provided mapping functions to the input 068 * elements. The generated map is sorted by the specified comparator. 069 * 070 * <p>If the mapped keys contain duplicates (according to the specified comparator), an 071 * {@code IllegalArgumentException} is thrown when the collection operation is performed. 072 * (This differs from the {@code Collector} returned by 073 * {@link Collectors#toMap(Function, Function)}, which throws an {@code IllegalStateException}.) 074 * 075 * @since 21.0 076 */ 077 @Beta 078 public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap( 079 Comparator<? super K> comparator, 080 Function<? super T, ? extends K> keyFunction, 081 Function<? super T, ? extends V> valueFunction) { 082 return CollectCollectors.toImmutableSortedMap(comparator, keyFunction, valueFunction); 083 } 084 085 /** 086 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} whose 087 * keys and values are the result of applying the provided mapping functions to the input 088 * elements. 089 * 090 * <p>If the mapped keys contain duplicates (according to the comparator), the the values are 091 * merged using the specified merging function. Entries will appear in the encounter order of the 092 * first occurrence of the key. 093 * 094 * @since 21.0 095 */ 096 @Beta 097 public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap( 098 Comparator<? super K> comparator, 099 Function<? super T, ? extends K> keyFunction, 100 Function<? super T, ? extends V> valueFunction, 101 BinaryOperator<V> mergeFunction) { 102 checkNotNull(comparator); 103 checkNotNull(keyFunction); 104 checkNotNull(valueFunction); 105 checkNotNull(mergeFunction); 106 return Collectors.collectingAndThen( 107 Collectors.toMap( 108 keyFunction, valueFunction, mergeFunction, () -> new TreeMap<K, V>(comparator)), 109 ImmutableSortedMap::copyOfSorted); 110 } 111 112 /* 113 * TODO(kevinb): Confirm that ImmutableSortedMap is faster to construct and 114 * uses less memory than TreeMap; then say so in the class Javadoc. 115 */ 116 private static final Comparator<Comparable> NATURAL_ORDER = Ordering.natural(); 117 118 private static final ImmutableSortedMap<Comparable, Object> NATURAL_EMPTY_MAP = 119 new ImmutableSortedMap<Comparable, Object>( 120 ImmutableSortedSet.emptySet(Ordering.natural()), ImmutableList.<Object>of()); 121 122 static <K, V> ImmutableSortedMap<K, V> emptyMap(Comparator<? super K> comparator) { 123 if (Ordering.natural().equals(comparator)) { 124 return of(); 125 } else { 126 return new ImmutableSortedMap<K, V>( 127 ImmutableSortedSet.emptySet(comparator), ImmutableList.<V>of()); 128 } 129 } 130 131 /** 132 * Returns the empty sorted map. 133 */ 134 @SuppressWarnings("unchecked") 135 // unsafe, comparator() returns a comparator on the specified type 136 // TODO(kevinb): evaluate whether or not of().comparator() should return null 137 public static <K, V> ImmutableSortedMap<K, V> of() { 138 return (ImmutableSortedMap<K, V>) NATURAL_EMPTY_MAP; 139 } 140 141 /** 142 * Returns an immutable map containing a single entry. 143 */ 144 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(K k1, V v1) { 145 return of(Ordering.natural(), k1, v1); 146 } 147 148 /** 149 * Returns an immutable map containing a single entry. 150 */ 151 private static <K, V> ImmutableSortedMap<K, V> of(Comparator<? super K> comparator, K k1, V v1) { 152 return new ImmutableSortedMap<K, V>( 153 new RegularImmutableSortedSet<K>(ImmutableList.of(k1), checkNotNull(comparator)), 154 ImmutableList.of(v1)); 155 } 156 157 private static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> ofEntries( 158 Entry<K, V>... entries) { 159 return fromEntries(Ordering.natural(), false, entries, entries.length); 160 } 161 162 /** 163 * Returns an immutable sorted map containing the given entries, sorted by the 164 * natural ordering of their keys. 165 * 166 * @throws IllegalArgumentException if the two keys are equal according to 167 * their natural ordering 168 */ 169 @SuppressWarnings("unchecked") 170 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 171 K k1, V v1, K k2, V v2) { 172 return ofEntries(entryOf(k1, v1), entryOf(k2, v2)); 173 } 174 175 /** 176 * Returns an immutable sorted map containing the given entries, sorted by the 177 * natural ordering of their keys. 178 * 179 * @throws IllegalArgumentException if any two keys are equal according to 180 * their natural ordering 181 */ 182 @SuppressWarnings("unchecked") 183 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 184 K k1, V v1, K k2, V v2, K k3, V v3) { 185 return ofEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3)); 186 } 187 188 /** 189 * Returns an immutable sorted map containing the given entries, sorted by the 190 * natural ordering of their keys. 191 * 192 * @throws IllegalArgumentException if any two keys are equal according to 193 * their natural ordering 194 */ 195 @SuppressWarnings("unchecked") 196 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 197 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 198 return ofEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4)); 199 } 200 201 /** 202 * Returns an immutable sorted map containing the given entries, sorted by the 203 * natural ordering of their keys. 204 * 205 * @throws IllegalArgumentException if any two keys are equal according to 206 * their natural ordering 207 */ 208 @SuppressWarnings("unchecked") 209 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 210 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 211 return ofEntries( 212 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5)); 213 } 214 215 /** 216 * Returns an immutable map containing the same entries as {@code map}, sorted 217 * by the natural ordering of the keys. 218 * 219 * <p>Despite the method name, this method attempts to avoid actually copying 220 * the data when it is safe to do so. The exact circumstances under which a 221 * copy will or will not be performed are undocumented and subject to change. 222 * 223 * <p>This method is not type-safe, as it may be called on a map with keys 224 * that are not mutually comparable. 225 * 226 * @throws ClassCastException if the keys in {@code map} are not mutually 227 * comparable 228 * @throws NullPointerException if any key or value in {@code map} is null 229 * @throws IllegalArgumentException if any two keys are equal according to 230 * their natural ordering 231 */ 232 public static <K, V> ImmutableSortedMap<K, V> copyOf(Map<? extends K, ? extends V> map) { 233 // Hack around K not being a subtype of Comparable. 234 // Unsafe, see ImmutableSortedSetFauxverideShim. 235 @SuppressWarnings("unchecked") 236 Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER; 237 return copyOfInternal(map, naturalOrder); 238 } 239 240 /** 241 * Returns an immutable map containing the same entries as {@code map}, with 242 * keys sorted by the provided comparator. 243 * 244 * <p>Despite the method name, this method attempts to avoid actually copying 245 * the data when it is safe to do so. The exact circumstances under which a 246 * copy will or will not be performed are undocumented and subject to change. 247 * 248 * @throws NullPointerException if any key or value in {@code map} is null 249 * @throws IllegalArgumentException if any two keys are equal according to the 250 * comparator 251 */ 252 public static <K, V> ImmutableSortedMap<K, V> copyOf( 253 Map<? extends K, ? extends V> map, Comparator<? super K> comparator) { 254 return copyOfInternal(map, checkNotNull(comparator)); 255 } 256 257 /** 258 * Returns an immutable map containing the given entries, with keys sorted 259 * by the provided comparator. 260 * 261 * <p>This method is not type-safe, as it may be called on a map with keys 262 * that are not mutually comparable. 263 * 264 * @throws NullPointerException if any key or value in {@code map} is null 265 * @throws IllegalArgumentException if any two keys are equal according to the 266 * comparator 267 * @since 19.0 268 */ 269 @Beta 270 public static <K, V> ImmutableSortedMap<K, V> copyOf( 271 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 272 // Hack around K not being a subtype of Comparable. 273 // Unsafe, see ImmutableSortedSetFauxverideShim. 274 @SuppressWarnings("unchecked") 275 Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER; 276 return copyOf(entries, naturalOrder); 277 } 278 279 /** 280 * Returns an immutable map containing the given entries, with keys sorted 281 * by the provided comparator. 282 * 283 * @throws NullPointerException if any key or value in {@code map} is null 284 * @throws IllegalArgumentException if any two keys are equal according to the 285 * comparator 286 * @since 19.0 287 */ 288 @Beta 289 public static <K, V> ImmutableSortedMap<K, V> copyOf( 290 Iterable<? extends Entry<? extends K, ? extends V>> entries, 291 Comparator<? super K> comparator) { 292 return fromEntries(checkNotNull(comparator), false, entries); 293 } 294 295 /** 296 * Returns an immutable map containing the same entries as the provided sorted 297 * map, with the same ordering. 298 * 299 * <p>Despite the method name, this method attempts to avoid actually copying 300 * the data when it is safe to do so. The exact circumstances under which a 301 * copy will or will not be performed are undocumented and subject to change. 302 * 303 * @throws NullPointerException if any key or value in {@code map} is null 304 */ 305 @SuppressWarnings("unchecked") 306 public static <K, V> ImmutableSortedMap<K, V> copyOfSorted(SortedMap<K, ? extends V> map) { 307 Comparator<? super K> comparator = map.comparator(); 308 if (comparator == null) { 309 // If map has a null comparator, the keys should have a natural ordering, 310 // even though K doesn't explicitly implement Comparable. 311 comparator = (Comparator<? super K>) NATURAL_ORDER; 312 } 313 if (map instanceof ImmutableSortedMap) { 314 // TODO(kevinb): Prove that this cast is safe, even though 315 // Collections.unmodifiableSortedMap requires the same key type. 316 @SuppressWarnings("unchecked") 317 ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map; 318 if (!kvMap.isPartialView()) { 319 return kvMap; 320 } 321 } 322 return fromEntries(comparator, true, map.entrySet()); 323 } 324 325 private static <K, V> ImmutableSortedMap<K, V> copyOfInternal( 326 Map<? extends K, ? extends V> map, Comparator<? super K> comparator) { 327 boolean sameComparator = false; 328 if (map instanceof SortedMap) { 329 SortedMap<?, ?> sortedMap = (SortedMap<?, ?>) map; 330 Comparator<?> comparator2 = sortedMap.comparator(); 331 sameComparator = 332 (comparator2 == null) 333 ? comparator == NATURAL_ORDER 334 : comparator.equals(comparator2); 335 } 336 337 if (sameComparator && (map instanceof ImmutableSortedMap)) { 338 // TODO(kevinb): Prove that this cast is safe, even though 339 // Collections.unmodifiableSortedMap requires the same key type. 340 @SuppressWarnings("unchecked") 341 ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map; 342 if (!kvMap.isPartialView()) { 343 return kvMap; 344 } 345 } 346 return fromEntries(comparator, sameComparator, map.entrySet()); 347 } 348 349 /** 350 * Accepts a collection of possibly-null entries. If {@code sameComparator}, then it is assumed 351 * that they do not need to be sorted or checked for dupes. 352 */ 353 private static <K, V> ImmutableSortedMap<K, V> fromEntries( 354 Comparator<? super K> comparator, 355 boolean sameComparator, 356 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 357 // "adding" type params to an array of a raw type should be safe as 358 // long as no one can ever cast that same array instance back to a 359 // raw type. 360 @SuppressWarnings("unchecked") 361 Entry<K, V>[] entryArray = (Entry[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY); 362 return fromEntries(comparator, sameComparator, entryArray, entryArray.length); 363 } 364 365 private static <K, V> ImmutableSortedMap<K, V> fromEntries( 366 final Comparator<? super K> comparator, 367 boolean sameComparator, 368 Entry<K, V>[] entryArray, 369 int size) { 370 switch (size) { 371 case 0: 372 return emptyMap(comparator); 373 case 1: 374 return ImmutableSortedMap.<K, V>of( 375 comparator, entryArray[0].getKey(), entryArray[0].getValue()); 376 default: 377 Object[] keys = new Object[size]; 378 Object[] values = new Object[size]; 379 if (sameComparator) { 380 // Need to check for nulls, but don't need to sort or validate. 381 for (int i = 0; i < size; i++) { 382 Object key = entryArray[i].getKey(); 383 Object value = entryArray[i].getValue(); 384 checkEntryNotNull(key, value); 385 keys[i] = key; 386 values[i] = value; 387 } 388 } else { 389 // Need to sort and check for nulls and dupes. 390 // Inline the Comparator implementation rather than transforming with a Function 391 // to save code size. 392 Arrays.sort(entryArray, 0, size, new Comparator<Entry<K, V>>() { 393 @Override 394 public int compare(Entry<K, V> e1, Entry<K, V> e2) { 395 return comparator.compare(e1.getKey(), e2.getKey()); 396 } 397 }); 398 K prevKey = entryArray[0].getKey(); 399 keys[0] = prevKey; 400 values[0] = entryArray[0].getValue(); 401 for (int i = 1; i < size; i++) { 402 K key = entryArray[i].getKey(); 403 V value = entryArray[i].getValue(); 404 checkEntryNotNull(key, value); 405 keys[i] = key; 406 values[i] = value; 407 checkNoConflict( 408 comparator.compare(prevKey, key) != 0, "key", entryArray[i - 1], entryArray[i]); 409 prevKey = key; 410 } 411 } 412 return new ImmutableSortedMap<K, V>( 413 new RegularImmutableSortedSet<K>(new RegularImmutableList<K>(keys), comparator), 414 new RegularImmutableList<V>(values)); 415 } 416 } 417 418 /** 419 * Returns a builder that creates immutable sorted maps whose keys are 420 * ordered by their natural ordering. The sorted maps use {@link 421 * Ordering#natural()} as the comparator. 422 */ 423 public static <K extends Comparable<?>, V> Builder<K, V> naturalOrder() { 424 return new Builder<K, V>(Ordering.natural()); 425 } 426 427 /** 428 * Returns a builder that creates immutable sorted maps with an explicit 429 * comparator. If the comparator has a more general type than the map's keys, 430 * such as creating a {@code SortedMap<Integer, String>} with a {@code 431 * Comparator<Number>}, use the {@link Builder} constructor instead. 432 * 433 * @throws NullPointerException if {@code comparator} is null 434 */ 435 public static <K, V> Builder<K, V> orderedBy(Comparator<K> comparator) { 436 return new Builder<K, V>(comparator); 437 } 438 439 /** 440 * Returns a builder that creates immutable sorted maps whose keys are 441 * ordered by the reverse of their natural ordering. 442 */ 443 public static <K extends Comparable<?>, V> Builder<K, V> reverseOrder() { 444 return new Builder<K, V>(Ordering.natural().reverse()); 445 } 446 447 /** 448 * A builder for creating immutable sorted map instances, especially {@code 449 * public static final} maps ("constant maps"). Example: <pre> {@code 450 * 451 * static final ImmutableSortedMap<Integer, String> INT_TO_WORD = 452 * new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural()) 453 * .put(1, "one") 454 * .put(2, "two") 455 * .put(3, "three") 456 * .build();}</pre> 457 * 458 * <p>For <i>small</i> immutable sorted maps, the {@code ImmutableSortedMap.of()} 459 * methods are even more convenient. 460 * 461 * <p>Builder instances can be reused - it is safe to call {@link #build} 462 * multiple times to build multiple maps in series. Each map is a superset of 463 * the maps created before it. 464 * 465 * @since 2.0 466 */ 467 public static class Builder<K, V> extends ImmutableMap.Builder<K, V> { 468 private final Comparator<? super K> comparator; 469 470 /** 471 * Creates a new builder. The returned builder is equivalent to the builder 472 * generated by {@link ImmutableSortedMap#orderedBy}. 473 */ 474 @SuppressWarnings("unchecked") 475 public Builder(Comparator<? super K> comparator) { 476 this.comparator = checkNotNull(comparator); 477 } 478 479 /** 480 * Associates {@code key} with {@code value} in the built map. Duplicate 481 * keys, according to the comparator (which might be the keys' natural 482 * order), are not allowed, and will cause {@link #build} to fail. 483 */ 484 @CanIgnoreReturnValue 485 @Override 486 public Builder<K, V> put(K key, V value) { 487 super.put(key, value); 488 return this; 489 } 490 491 /** 492 * Adds the given {@code entry} to the map, making it immutable if 493 * necessary. Duplicate keys, according to the comparator (which might be 494 * the keys' natural order), are not allowed, and will cause {@link #build} 495 * to fail. 496 * 497 * @since 11.0 498 */ 499 @CanIgnoreReturnValue 500 @Override 501 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { 502 super.put(entry); 503 return this; 504 } 505 506 /** 507 * Associates all of the given map's keys and values in the built map. 508 * Duplicate keys, according to the comparator (which might be the keys' 509 * natural order), are not allowed, and will cause {@link #build} to fail. 510 * 511 * @throws NullPointerException if any key or value in {@code map} is null 512 */ 513 @CanIgnoreReturnValue 514 @Override 515 public Builder<K, V> putAll(Map<? extends K, ? extends V> map) { 516 super.putAll(map); 517 return this; 518 } 519 520 /** 521 * Adds all the given entries to the built map. Duplicate keys, according 522 * to the comparator (which might be the keys' natural order), are not 523 * allowed, and will cause {@link #build} to fail. 524 * 525 * @throws NullPointerException if any key, value, or entry is null 526 * @since 19.0 527 */ 528 @CanIgnoreReturnValue 529 @Beta 530 @Override 531 public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) { 532 super.putAll(entries); 533 return this; 534 } 535 536 /** 537 * Throws an {@code UnsupportedOperationException}. 538 * 539 * @since 19.0 540 * @deprecated Unsupported by ImmutableSortedMap.Builder. 541 */ 542 @CanIgnoreReturnValue 543 @Beta 544 @Override 545 @Deprecated 546 public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) { 547 throw new UnsupportedOperationException("Not available on ImmutableSortedMap.Builder"); 548 } 549 550 @Override 551 Builder<K, V> combine(ImmutableMap.Builder<K, V> other) { 552 super.combine(other); 553 return this; 554 } 555 556 /** 557 * Returns a newly-created immutable sorted map. 558 * 559 * @throws IllegalArgumentException if any two keys are equal according to 560 * the comparator (which might be the keys' natural order) 561 */ 562 @Override 563 public ImmutableSortedMap<K, V> build() { 564 switch (size) { 565 case 0: 566 return emptyMap(comparator); 567 case 1: 568 return of(comparator, entries[0].getKey(), entries[0].getValue()); 569 default: 570 return fromEntries(comparator, false, entries, size); 571 } 572 } 573 } 574 575 private final transient RegularImmutableSortedSet<K> keySet; 576 private final transient ImmutableList<V> valueList; 577 private transient ImmutableSortedMap<K, V> descendingMap; 578 579 ImmutableSortedMap(RegularImmutableSortedSet<K> keySet, ImmutableList<V> valueList) { 580 this(keySet, valueList, null); 581 } 582 583 ImmutableSortedMap( 584 RegularImmutableSortedSet<K> keySet, 585 ImmutableList<V> valueList, 586 ImmutableSortedMap<K, V> descendingMap) { 587 this.keySet = keySet; 588 this.valueList = valueList; 589 this.descendingMap = descendingMap; 590 } 591 592 @Override 593 public int size() { 594 return valueList.size(); 595 } 596 597 @Override 598 public void forEach(BiConsumer<? super K, ? super V> action) { 599 checkNotNull(action); 600 ImmutableList<K> keyList = keySet.asList(); 601 for (int i = 0; i < size(); i++) { 602 action.accept(keyList.get(i), valueList.get(i)); 603 } 604 } 605 606 @Override 607 public V get(@Nullable Object key) { 608 int index = keySet.indexOf(key); 609 return (index == -1) ? null : valueList.get(index); 610 } 611 612 @Override 613 boolean isPartialView() { 614 return keySet.isPartialView() || valueList.isPartialView(); 615 } 616 617 /** 618 * Returns an immutable set of the mappings in this map, sorted by the key 619 * ordering. 620 */ 621 @Override 622 public ImmutableSet<Entry<K, V>> entrySet() { 623 return super.entrySet(); 624 } 625 626 @Override 627 ImmutableSet<Entry<K, V>> createEntrySet() { 628 @WeakOuter 629 class EntrySet extends ImmutableMapEntrySet<K, V> { 630 @Override 631 public UnmodifiableIterator<Entry<K, V>> iterator() { 632 return asList().iterator(); 633 } 634 635 @Override 636 public Spliterator<Entry<K, V>> spliterator() { 637 return asList().spliterator(); 638 } 639 640 @Override 641 public void forEach(Consumer<? super Entry<K, V>> action) { 642 asList().forEach(action); 643 } 644 645 @Override 646 ImmutableList<Entry<K, V>> createAsList() { 647 return new ImmutableAsList<Entry<K, V>>() { 648 @Override 649 public Entry<K, V> get(int index) { 650 return new AbstractMap.SimpleImmutableEntry<K, V>( 651 keySet.asList().get(index), valueList.get(index)); 652 } 653 654 @Override 655 public Spliterator<Entry<K, V>> spliterator() { 656 return CollectSpliterators.indexed( 657 size(), ImmutableSet.SPLITERATOR_CHARACTERISTICS, this::get); 658 } 659 660 @Override 661 ImmutableCollection<Entry<K, V>> delegateCollection() { 662 return EntrySet.this; 663 } 664 }; 665 } 666 667 @Override 668 ImmutableMap<K, V> map() { 669 return ImmutableSortedMap.this; 670 } 671 } 672 return isEmpty() ? ImmutableSet.<Entry<K, V>>of() : new EntrySet(); 673 } 674 675 /** 676 * Returns an immutable sorted set of the keys in this map. 677 */ 678 @Override 679 public ImmutableSortedSet<K> keySet() { 680 return keySet; 681 } 682 683 @Override 684 ImmutableSet<K> createKeySet() { 685 throw new AssertionError("should never be called"); 686 } 687 688 /** 689 * Returns an immutable collection of the values in this map, sorted by the 690 * ordering of the corresponding keys. 691 */ 692 @Override 693 public ImmutableCollection<V> values() { 694 return valueList; 695 } 696 697 @Override 698 ImmutableCollection<V> createValues() { 699 throw new AssertionError("should never be called"); 700 } 701 702 /** 703 * Returns the comparator that orders the keys, which is 704 * {@link Ordering#natural()} when the natural ordering of the keys is used. 705 * Note that its behavior is not consistent with {@link TreeMap#comparator()}, 706 * which returns {@code null} to indicate natural ordering. 707 */ 708 @Override 709 public Comparator<? super K> comparator() { 710 return keySet().comparator(); 711 } 712 713 @Override 714 public K firstKey() { 715 return keySet().first(); 716 } 717 718 @Override 719 public K lastKey() { 720 return keySet().last(); 721 } 722 723 private ImmutableSortedMap<K, V> getSubMap(int fromIndex, int toIndex) { 724 if (fromIndex == 0 && toIndex == size()) { 725 return this; 726 } else if (fromIndex == toIndex) { 727 return emptyMap(comparator()); 728 } else { 729 return new ImmutableSortedMap<K, V>( 730 keySet.getSubSet(fromIndex, toIndex), valueList.subList(fromIndex, toIndex)); 731 } 732 } 733 734 /** 735 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 736 * whose keys are less than {@code toKey}. 737 * 738 * <p>The {@link SortedMap#headMap} documentation states that a submap of a 739 * submap throws an {@link IllegalArgumentException} if passed a {@code toKey} 740 * greater than an earlier {@code toKey}. However, this method doesn't throw 741 * an exception in that situation, but instead keeps the original {@code 742 * toKey}. 743 */ 744 @Override 745 public ImmutableSortedMap<K, V> headMap(K toKey) { 746 return headMap(toKey, false); 747 } 748 749 /** 750 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 751 * whose keys are less than (or equal to, if {@code inclusive}) {@code toKey}. 752 * 753 * <p>The {@link SortedMap#headMap} documentation states that a submap of a 754 * submap throws an {@link IllegalArgumentException} if passed a {@code toKey} 755 * greater than an earlier {@code toKey}. However, this method doesn't throw 756 * an exception in that situation, but instead keeps the original {@code 757 * toKey}. 758 * 759 * @since 12.0 760 */ 761 @Override 762 public ImmutableSortedMap<K, V> headMap(K toKey, boolean inclusive) { 763 return getSubMap(0, keySet.headIndex(checkNotNull(toKey), inclusive)); 764 } 765 766 /** 767 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 768 * whose keys ranges from {@code fromKey}, inclusive, to {@code toKey}, 769 * exclusive. 770 * 771 * <p>The {@link SortedMap#subMap} documentation states that a submap of a 772 * submap throws an {@link IllegalArgumentException} if passed a {@code 773 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 774 * throw an exception in that situation, but instead keeps the original {@code 775 * fromKey}. Similarly, this method keeps the original {@code toKey}, instead 776 * of throwing an exception, if passed a {@code toKey} greater than an earlier 777 * {@code toKey}. 778 */ 779 @Override 780 public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) { 781 return subMap(fromKey, true, toKey, false); 782 } 783 784 /** 785 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 786 * whose keys ranges from {@code fromKey} to {@code toKey}, inclusive or 787 * exclusive as indicated by the boolean flags. 788 * 789 * <p>The {@link SortedMap#subMap} documentation states that a submap of a 790 * submap throws an {@link IllegalArgumentException} if passed a {@code 791 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 792 * throw an exception in that situation, but instead keeps the original {@code 793 * fromKey}. Similarly, this method keeps the original {@code toKey}, instead 794 * of throwing an exception, if passed a {@code toKey} greater than an earlier 795 * {@code toKey}. 796 * 797 * @since 12.0 798 */ 799 @Override 800 public ImmutableSortedMap<K, V> subMap( 801 K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { 802 checkNotNull(fromKey); 803 checkNotNull(toKey); 804 checkArgument( 805 comparator().compare(fromKey, toKey) <= 0, 806 "expected fromKey <= toKey but %s > %s", 807 fromKey, 808 toKey); 809 return headMap(toKey, toInclusive).tailMap(fromKey, fromInclusive); 810 } 811 812 /** 813 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 814 * whose keys are greater than or equals to {@code fromKey}. 815 * 816 * <p>The {@link SortedMap#tailMap} documentation states that a submap of a 817 * submap throws an {@link IllegalArgumentException} if passed a {@code 818 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 819 * throw an exception in that situation, but instead keeps the original {@code 820 * fromKey}. 821 */ 822 @Override 823 public ImmutableSortedMap<K, V> tailMap(K fromKey) { 824 return tailMap(fromKey, true); 825 } 826 827 /** 828 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 829 * whose keys are greater than (or equal to, if {@code inclusive}) 830 * {@code fromKey}. 831 * 832 * <p>The {@link SortedMap#tailMap} documentation states that a submap of a 833 * submap throws an {@link IllegalArgumentException} if passed a {@code 834 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 835 * throw an exception in that situation, but instead keeps the original {@code 836 * fromKey}. 837 * 838 * @since 12.0 839 */ 840 @Override 841 public ImmutableSortedMap<K, V> tailMap(K fromKey, boolean inclusive) { 842 return getSubMap(keySet.tailIndex(checkNotNull(fromKey), inclusive), size()); 843 } 844 845 @Override 846 public Entry<K, V> lowerEntry(K key) { 847 return headMap(key, false).lastEntry(); 848 } 849 850 @Override 851 public K lowerKey(K key) { 852 return keyOrNull(lowerEntry(key)); 853 } 854 855 @Override 856 public Entry<K, V> floorEntry(K key) { 857 return headMap(key, true).lastEntry(); 858 } 859 860 @Override 861 public K floorKey(K key) { 862 return keyOrNull(floorEntry(key)); 863 } 864 865 @Override 866 public Entry<K, V> ceilingEntry(K key) { 867 return tailMap(key, true).firstEntry(); 868 } 869 870 @Override 871 public K ceilingKey(K key) { 872 return keyOrNull(ceilingEntry(key)); 873 } 874 875 @Override 876 public Entry<K, V> higherEntry(K key) { 877 return tailMap(key, false).firstEntry(); 878 } 879 880 @Override 881 public K higherKey(K key) { 882 return keyOrNull(higherEntry(key)); 883 } 884 885 @Override 886 public Entry<K, V> firstEntry() { 887 return isEmpty() ? null : entrySet().asList().get(0); 888 } 889 890 @Override 891 public Entry<K, V> lastEntry() { 892 return isEmpty() ? null : entrySet().asList().get(size() - 1); 893 } 894 895 /** 896 * Guaranteed to throw an exception and leave the map unmodified. 897 * 898 * @throws UnsupportedOperationException always 899 * @deprecated Unsupported operation. 900 */ 901 @CanIgnoreReturnValue 902 @Deprecated 903 @Override 904 public final Entry<K, V> pollFirstEntry() { 905 throw new UnsupportedOperationException(); 906 } 907 908 /** 909 * Guaranteed to throw an exception and leave the map unmodified. 910 * 911 * @throws UnsupportedOperationException always 912 * @deprecated Unsupported operation. 913 */ 914 @CanIgnoreReturnValue 915 @Deprecated 916 @Override 917 public final Entry<K, V> pollLastEntry() { 918 throw new UnsupportedOperationException(); 919 } 920 921 @Override 922 public ImmutableSortedMap<K, V> descendingMap() { 923 // TODO(kevinb): the descendingMap is never actually cached at all. Either it should be or the 924 // code below simplified. 925 ImmutableSortedMap<K, V> result = descendingMap; 926 if (result == null) { 927 if (isEmpty()) { 928 return result = emptyMap(Ordering.from(comparator()).reverse()); 929 } else { 930 return result = 931 new ImmutableSortedMap<K, V>( 932 (RegularImmutableSortedSet<K>) keySet.descendingSet(), valueList.reverse(), this); 933 } 934 } 935 return result; 936 } 937 938 @Override 939 public ImmutableSortedSet<K> navigableKeySet() { 940 return keySet; 941 } 942 943 @Override 944 public ImmutableSortedSet<K> descendingKeySet() { 945 return keySet.descendingSet(); 946 } 947 948 /** 949 * Serialized type for all ImmutableSortedMap instances. It captures the 950 * logical contents and they are reconstructed using public factory methods. 951 * This ensures that the implementation types remain as implementation 952 * details. 953 */ 954 private static class SerializedForm extends ImmutableMap.SerializedForm { 955 private final Comparator<Object> comparator; 956 957 @SuppressWarnings("unchecked") 958 SerializedForm(ImmutableSortedMap<?, ?> sortedMap) { 959 super(sortedMap); 960 comparator = (Comparator<Object>) sortedMap.comparator(); 961 } 962 963 @Override 964 Object readResolve() { 965 Builder<Object, Object> builder = new Builder<Object, Object>(comparator); 966 return createMap(builder); 967 } 968 969 private static final long serialVersionUID = 0; 970 } 971 972 @Override 973 Object writeReplace() { 974 return new SerializedForm(this); 975 } 976 977 // This class is never actually serialized directly, but we have to make the 978 // warning go away (and suppressing would suppress for all nested classes too) 979 private static final long serialVersionUID = 0; 980}