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