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