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