001/* 002 * Copyright (C) 2008 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.ObjectArrays.checkElementsNotNull; 022 023import com.google.common.annotations.GwtCompatible; 024import com.google.common.annotations.GwtIncompatible; 025import com.google.common.annotations.J2ktIncompatible; 026import com.google.errorprone.annotations.CanIgnoreReturnValue; 027import com.google.errorprone.annotations.DoNotCall; 028import com.google.errorprone.annotations.concurrent.LazyInit; 029import java.io.InvalidObjectException; 030import java.io.ObjectInputStream; 031import java.io.Serializable; 032import java.util.Arrays; 033import java.util.Collection; 034import java.util.Collections; 035import java.util.Comparator; 036import java.util.Iterator; 037import java.util.NavigableSet; 038import java.util.SortedSet; 039import java.util.Spliterator; 040import java.util.Spliterators; 041import java.util.function.Consumer; 042import java.util.stream.Collector; 043import javax.annotation.CheckForNull; 044import org.checkerframework.checker.nullness.qual.Nullable; 045 046/** 047 * A {@link NavigableSet} whose contents will never change, with many other important properties 048 * detailed at {@link ImmutableCollection}. 049 * 050 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link 051 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with 052 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero 053 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting 054 * collection will not correctly obey its specification. 055 * 056 * <p>See the Guava User Guide article on <a href= 057 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>. 058 * 059 * @author Jared Levy 060 * @author Louis Wasserman 061 * @since 2.0 (implements {@code NavigableSet} since 12.0) 062 */ 063// TODO(benyu): benchmark and optimize all creation paths, which are a mess now 064@GwtCompatible(serializable = true, emulated = true) 065@SuppressWarnings("serial") // we're overriding default serialization 066@ElementTypesAreNonnullByDefault 067public abstract class ImmutableSortedSet<E> extends ImmutableSet.CachingAsList<E> 068 implements NavigableSet<E>, SortedIterable<E> { 069 static final int SPLITERATOR_CHARACTERISTICS = 070 ImmutableSet.SPLITERATOR_CHARACTERISTICS | Spliterator.SORTED; 071 072 /** 073 * Returns a {@code Collector} that accumulates the input elements into a new {@code 074 * ImmutableSortedSet}, ordered by the specified comparator. 075 * 076 * <p>If the elements contain duplicates (according to the comparator), only the first duplicate 077 * in encounter order will appear in the result. 078 * 079 * @since 21.0 080 */ 081 public static <E> Collector<E, ?, ImmutableSortedSet<E>> toImmutableSortedSet( 082 Comparator<? super E> comparator) { 083 return CollectCollectors.toImmutableSortedSet(comparator); 084 } 085 086 static <E> RegularImmutableSortedSet<E> emptySet(Comparator<? super E> comparator) { 087 if (Ordering.natural().equals(comparator)) { 088 @SuppressWarnings("unchecked") // The natural-ordered empty set supports all types. 089 RegularImmutableSortedSet<E> result = 090 (RegularImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET; 091 return result; 092 } else { 093 return new RegularImmutableSortedSet<E>(ImmutableList.<E>of(), comparator); 094 } 095 } 096 097 /** 098 * Returns the empty immutable sorted set. 099 * 100 * <p><b>Performance note:</b> the instance returned is a singleton. 101 */ 102 @SuppressWarnings("unchecked") // The natural-ordered empty set supports all types. 103 public static <E> ImmutableSortedSet<E> of() { 104 return (ImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET; 105 } 106 107 /** Returns an immutable sorted set containing a single element. */ 108 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E element) { 109 return new RegularImmutableSortedSet<E>(ImmutableList.of(element), Ordering.natural()); 110 } 111 112 /** 113 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 114 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 115 * one specified is included. 116 * 117 * @throws NullPointerException if any element is null 118 */ 119 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2) { 120 return construct(Ordering.natural(), 2, e1, e2); 121 } 122 123 /** 124 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 125 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 126 * one specified is included. 127 * 128 * @throws NullPointerException if any element is null 129 */ 130 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2, E e3) { 131 return construct(Ordering.natural(), 3, e1, e2, e3); 132 } 133 134 /** 135 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 136 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 137 * one specified is included. 138 * 139 * @throws NullPointerException if any element is null 140 */ 141 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4) { 142 return construct(Ordering.natural(), 4, e1, e2, e3, e4); 143 } 144 145 /** 146 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 147 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 148 * one specified is included. 149 * 150 * @throws NullPointerException if any element is null 151 */ 152 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 153 E e1, E e2, E e3, E e4, E e5) { 154 return construct(Ordering.natural(), 5, e1, e2, e3, e4, e5); 155 } 156 157 /** 158 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 159 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 160 * one specified is included. 161 * 162 * @throws NullPointerException if any element is null 163 * @since 3.0 (source-compatible since 2.0) 164 */ 165 @SuppressWarnings("unchecked") 166 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 167 E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) { 168 Comparable<?>[] contents = new Comparable<?>[6 + remaining.length]; 169 contents[0] = e1; 170 contents[1] = e2; 171 contents[2] = e3; 172 contents[3] = e4; 173 contents[4] = e5; 174 contents[5] = e6; 175 System.arraycopy(remaining, 0, contents, 6, remaining.length); 176 return construct(Ordering.natural(), contents.length, (E[]) contents); 177 } 178 179 // TODO(kevinb): Consider factory methods that reject duplicates 180 181 /** 182 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 183 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 184 * one specified is included. 185 * 186 * @throws NullPointerException if any of {@code elements} is null 187 * @since 3.0 188 */ 189 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(E[] elements) { 190 return construct(Ordering.natural(), elements.length, elements.clone()); 191 } 192 193 /** 194 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 195 * When multiple elements are equivalent according to {@code compareTo()}, only the first one 196 * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator, 197 * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once. 198 * 199 * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)} 200 * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s}, 201 * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>} 202 * containing one element (the given set itself). 203 * 204 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 205 * safe to do so. The exact circumstances under which a copy will or will not be performed are 206 * undocumented and subject to change. 207 * 208 * <p>This method is not type-safe, as it may be called on elements that are not mutually 209 * comparable. 210 * 211 * @throws ClassCastException if the elements are not mutually comparable 212 * @throws NullPointerException if any of {@code elements} is null 213 */ 214 public static <E> ImmutableSortedSet<E> copyOf(Iterable<? extends E> elements) { 215 // Hack around E not being a subtype of Comparable. 216 // Unsafe, see ImmutableSortedSetFauxverideShim. 217 @SuppressWarnings("unchecked") 218 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable<?>>natural(); 219 return copyOf(naturalOrder, elements); 220 } 221 222 /** 223 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 224 * When multiple elements are equivalent according to {@code compareTo()}, only the first one 225 * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator, 226 * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once. 227 * 228 * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)} 229 * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s}, 230 * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>} 231 * containing one element (the given set itself). 232 * 233 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements} is an {@code 234 * ImmutableSortedSet}, it may be returned instead of a copy. 235 * 236 * <p>This method is not type-safe, as it may be called on elements that are not mutually 237 * comparable. 238 * 239 * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent 240 * collection that is currently being modified by another thread. 241 * 242 * @throws ClassCastException if the elements are not mutually comparable 243 * @throws NullPointerException if any of {@code elements} is null 244 * @since 7.0 (source-compatible since 2.0) 245 */ 246 public static <E> ImmutableSortedSet<E> copyOf(Collection<? extends E> elements) { 247 // Hack around E not being a subtype of Comparable. 248 // Unsafe, see ImmutableSortedSetFauxverideShim. 249 @SuppressWarnings("unchecked") 250 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable<?>>natural(); 251 return copyOf(naturalOrder, elements); 252 } 253 254 /** 255 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 256 * When multiple elements are equivalent according to {@code compareTo()}, only the first one 257 * specified is included. 258 * 259 * <p>This method is not type-safe, as it may be called on elements that are not mutually 260 * comparable. 261 * 262 * @throws ClassCastException if the elements are not mutually comparable 263 * @throws NullPointerException if any of {@code elements} is null 264 */ 265 public static <E> ImmutableSortedSet<E> copyOf(Iterator<? extends E> elements) { 266 // Hack around E not being a subtype of Comparable. 267 // Unsafe, see ImmutableSortedSetFauxverideShim. 268 @SuppressWarnings("unchecked") 269 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable<?>>natural(); 270 return copyOf(naturalOrder, elements); 271 } 272 273 /** 274 * Returns an immutable sorted set containing the given elements sorted by the given {@code 275 * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the 276 * first one specified is included. 277 * 278 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 279 */ 280 public static <E> ImmutableSortedSet<E> copyOf( 281 Comparator<? super E> comparator, Iterator<? extends E> elements) { 282 return new Builder<E>(comparator).addAll(elements).build(); 283 } 284 285 /** 286 * Returns an immutable sorted set containing the given elements sorted by the given {@code 287 * Comparator}. When multiple elements are equivalent according to {@code compare()}, only the 288 * first one specified is included. This method iterates over {@code elements} at most once. 289 * 290 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 291 * safe to do so. The exact circumstances under which a copy will or will not be performed are 292 * undocumented and subject to change. 293 * 294 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 295 */ 296 public static <E> ImmutableSortedSet<E> copyOf( 297 Comparator<? super E> comparator, Iterable<? extends E> elements) { 298 checkNotNull(comparator); 299 boolean hasSameComparator = SortedIterables.hasSameComparator(comparator, elements); 300 301 if (hasSameComparator && (elements instanceof ImmutableSortedSet)) { 302 @SuppressWarnings("unchecked") 303 ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements; 304 if (!original.isPartialView()) { 305 return original; 306 } 307 } 308 @SuppressWarnings("unchecked") // elements only contains E's; it's safe. 309 E[] array = (E[]) Iterables.toArray(elements); 310 return construct(comparator, array.length, array); 311 } 312 313 /** 314 * Returns an immutable sorted set containing the given elements sorted by the given {@code 315 * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the 316 * first one specified is included. 317 * 318 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 319 * safe to do so. The exact circumstances under which a copy will or will not be performed are 320 * undocumented and subject to change. 321 * 322 * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent 323 * collection that is currently being modified by another thread. 324 * 325 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 326 * @since 7.0 (source-compatible since 2.0) 327 */ 328 public static <E> ImmutableSortedSet<E> copyOf( 329 Comparator<? super E> comparator, Collection<? extends E> elements) { 330 return copyOf(comparator, (Iterable<? extends E>) elements); 331 } 332 333 /** 334 * Returns an immutable sorted set containing the elements of a sorted set, sorted by the same 335 * {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which always uses the 336 * natural ordering of the elements. 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 * <p>This method is safe to use even when {@code sortedSet} is a synchronized or concurrent 343 * collection that is currently being modified by another thread. 344 * 345 * @throws NullPointerException if {@code sortedSet} or any of its elements is null 346 */ 347 public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) { 348 Comparator<? super E> comparator = SortedIterables.comparator(sortedSet); 349 ImmutableList<E> list = ImmutableList.copyOf(sortedSet); 350 if (list.isEmpty()) { 351 return emptySet(comparator); 352 } else { 353 return new RegularImmutableSortedSet<E>(list, comparator); 354 } 355 } 356 357 /** 358 * Constructs an {@code ImmutableSortedSet} from the first {@code n} elements of {@code contents}. 359 * If {@code k} is the size of the returned {@code ImmutableSortedSet}, then the sorted unique 360 * elements are in the first {@code k} positions of {@code contents}, and {@code contents[i] == 361 * null} for {@code k <= i < n}. 362 * 363 * <p>This method takes ownership of {@code contents}; do not modify {@code contents} after this 364 * returns. 365 * 366 * @throws NullPointerException if any of the first {@code n} elements of {@code contents} is null 367 */ 368 static <E> ImmutableSortedSet<E> construct( 369 Comparator<? super E> comparator, int n, E... contents) { 370 if (n == 0) { 371 return emptySet(comparator); 372 } 373 checkElementsNotNull(contents, n); 374 Arrays.sort(contents, 0, n, comparator); 375 int uniques = 1; 376 for (int i = 1; i < n; i++) { 377 E cur = contents[i]; 378 E prev = contents[uniques - 1]; 379 if (comparator.compare(cur, prev) != 0) { 380 contents[uniques++] = cur; 381 } 382 } 383 Arrays.fill(contents, uniques, n, null); 384 return new RegularImmutableSortedSet<E>( 385 ImmutableList.<E>asImmutableList(contents, uniques), comparator); 386 } 387 388 /** 389 * Returns a builder that creates immutable sorted sets with an explicit comparator. If the 390 * comparator has a more general type than the set being generated, such as creating a {@code 391 * SortedSet<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} constructor 392 * instead. 393 * 394 * @throws NullPointerException if {@code comparator} is null 395 */ 396 public static <E> Builder<E> orderedBy(Comparator<E> comparator) { 397 return new Builder<E>(comparator); 398 } 399 400 /** 401 * Returns a builder that creates immutable sorted sets whose elements are ordered by the reverse 402 * of their natural ordering. 403 */ 404 public static <E extends Comparable<?>> Builder<E> reverseOrder() { 405 return new Builder<E>(Collections.reverseOrder()); 406 } 407 408 /** 409 * Returns a builder that creates immutable sorted sets whose elements are ordered by their 410 * natural ordering. The sorted sets use {@link Ordering#natural()} as the comparator. This method 411 * provides more type-safety than {@link #builder}, as it can be called only for classes that 412 * implement {@link Comparable}. 413 */ 414 public static <E extends Comparable<?>> Builder<E> naturalOrder() { 415 return new Builder<E>(Ordering.natural()); 416 } 417 418 /** 419 * A builder for creating immutable sorted set instances, especially {@code public static final} 420 * sets ("constant sets"), with a given comparator. Example: 421 * 422 * <pre>{@code 423 * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS = 424 * new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR) 425 * .addAll(SINGLE_DIGIT_PRIMES) 426 * .add(42) 427 * .build(); 428 * }</pre> 429 * 430 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 431 * multiple sets in series. Each set is a superset of the set created before it. 432 * 433 * @since 2.0 434 */ 435 public static final class Builder<E> extends ImmutableSet.Builder<E> { 436 private final Comparator<? super E> comparator; 437 private E[] elements; 438 private int n; 439 440 /** 441 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 442 * ImmutableSortedSet#orderedBy}. 443 */ 444 /* 445 * TODO(cpovirk): use Object[] instead of E[] in the mainline? (The backport is different and 446 * doesn't need this suppression, but we keep it to minimize diffs.) Generally be more clear 447 * about when we have an Object[] vs. a Comparable[] or other array type in internalArray? If we 448 * used Object[], we might be able to optimize toArray() to use clone() sometimes. (See 449 * cl/592273615 and cl/592273683.) 450 */ 451 @SuppressWarnings("unchecked") 452 public Builder(Comparator<? super E> comparator) { 453 super(true); // don't construct guts of hash-based set builder 454 this.comparator = checkNotNull(comparator); 455 this.elements = (E[]) new Object[ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY]; 456 this.n = 0; 457 } 458 459 @Override 460 void copy() { 461 elements = Arrays.copyOf(elements, elements.length); 462 } 463 464 private void sortAndDedup() { 465 if (n == 0) { 466 return; 467 } 468 Arrays.sort(elements, 0, n, comparator); 469 int unique = 1; 470 for (int i = 1; i < n; i++) { 471 int cmp = comparator.compare(elements[unique - 1], elements[i]); 472 if (cmp < 0) { 473 elements[unique++] = elements[i]; 474 } else if (cmp > 0) { 475 throw new AssertionError( 476 "Comparator " + comparator + " compare method violates its contract"); 477 } 478 } 479 Arrays.fill(elements, unique, n, null); 480 n = unique; 481 } 482 483 /** 484 * Adds {@code element} to the {@code ImmutableSortedSet}. If the {@code ImmutableSortedSet} 485 * already contains {@code element}, then {@code add} has no effect. (only the previously added 486 * element is retained). 487 * 488 * @param element the element to add 489 * @return this {@code Builder} object 490 * @throws NullPointerException if {@code element} is null 491 */ 492 @CanIgnoreReturnValue 493 @Override 494 public Builder<E> add(E element) { 495 checkNotNull(element); 496 copyIfNecessary(); 497 if (n == elements.length) { 498 sortAndDedup(); 499 /* 500 * Sorting operations can only be allowed to occur once every O(n) operations to keep 501 * amortized O(n log n) performance. Therefore, ensure there are at least O(n) *unused* 502 * spaces in the builder array. 503 */ 504 int newLength = ImmutableCollection.Builder.expandedCapacity(n, n + 1); 505 if (newLength > elements.length) { 506 elements = Arrays.copyOf(elements, newLength); 507 } 508 } 509 elements[n++] = element; 510 return this; 511 } 512 513 /** 514 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate 515 * elements (only the first duplicate element is added). 516 * 517 * @param elements the elements to add 518 * @return this {@code Builder} object 519 * @throws NullPointerException if {@code elements} contains a null element 520 */ 521 @CanIgnoreReturnValue 522 @Override 523 public Builder<E> add(E... elements) { 524 checkElementsNotNull(elements); 525 for (E e : elements) { 526 add(e); 527 } 528 return this; 529 } 530 531 /** 532 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate 533 * elements (only the first duplicate element is added). 534 * 535 * @param elements the elements to add to the {@code ImmutableSortedSet} 536 * @return this {@code Builder} object 537 * @throws NullPointerException if {@code elements} contains a null element 538 */ 539 @CanIgnoreReturnValue 540 @Override 541 public Builder<E> addAll(Iterable<? extends E> elements) { 542 super.addAll(elements); 543 return this; 544 } 545 546 /** 547 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate 548 * elements (only the first duplicate element is added). 549 * 550 * @param elements the elements to add to the {@code ImmutableSortedSet} 551 * @return this {@code Builder} object 552 * @throws NullPointerException if {@code elements} contains a null element 553 */ 554 @CanIgnoreReturnValue 555 @Override 556 public Builder<E> addAll(Iterator<? extends E> elements) { 557 super.addAll(elements); 558 return this; 559 } 560 561 @CanIgnoreReturnValue 562 @Override 563 Builder<E> combine(ImmutableSet.Builder<E> builder) { 564 copyIfNecessary(); 565 Builder<E> other = (Builder<E>) builder; 566 for (int i = 0; i < other.n; i++) { 567 add(other.elements[i]); 568 } 569 return this; 570 } 571 572 /** 573 * Returns a newly-created {@code ImmutableSortedSet} based on the contents of the {@code 574 * Builder} and its comparator. 575 */ 576 @Override 577 public ImmutableSortedSet<E> build() { 578 sortAndDedup(); 579 if (n == 0) { 580 return emptySet(comparator); 581 } else { 582 forceCopy = true; 583 return new RegularImmutableSortedSet<E>( 584 ImmutableList.asImmutableList(elements, n), comparator); 585 } 586 } 587 } 588 589 int unsafeCompare(Object a, @CheckForNull Object b) { 590 return unsafeCompare(comparator, a, b); 591 } 592 593 static int unsafeCompare(Comparator<?> comparator, Object a, @CheckForNull Object b) { 594 // Pretend the comparator can compare anything. If it turns out it can't 595 // compare a and b, we should get a CCE or NPE on the subsequent line. Only methods 596 // that are spec'd to throw CCE and NPE should call this. 597 @SuppressWarnings({"unchecked", "nullness"}) 598 Comparator<@Nullable Object> unsafeComparator = (Comparator<@Nullable Object>) comparator; 599 return unsafeComparator.compare(a, b); 600 } 601 602 final transient Comparator<? super E> comparator; 603 604 ImmutableSortedSet(Comparator<? super E> comparator) { 605 this.comparator = comparator; 606 } 607 608 /** 609 * Returns the comparator that orders the elements, which is {@link Ordering#natural()} when the 610 * natural ordering of the elements is used. Note that its behavior is not consistent with {@link 611 * SortedSet#comparator()}, which returns {@code null} to indicate natural ordering. 612 */ 613 @Override 614 public Comparator<? super E> comparator() { 615 return comparator; 616 } 617 618 @Override // needed to unify the iterator() methods in Collection and SortedIterable 619 public abstract UnmodifiableIterator<E> iterator(); 620 621 /** 622 * {@inheritDoc} 623 * 624 * <p>This method returns a serializable {@code ImmutableSortedSet}. 625 * 626 * <p>The {@link SortedSet#headSet} documentation states that a subset of a subset throws an 627 * {@link IllegalArgumentException} if passed a {@code toElement} greater than an earlier {@code 628 * toElement}. However, this method doesn't throw an exception in that situation, but instead 629 * keeps the original {@code toElement}. 630 */ 631 @Override 632 public ImmutableSortedSet<E> headSet(E toElement) { 633 return headSet(toElement, false); 634 } 635 636 /** @since 12.0 */ 637 @Override 638 public ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) { 639 return headSetImpl(checkNotNull(toElement), inclusive); 640 } 641 642 /** 643 * {@inheritDoc} 644 * 645 * <p>This method returns a serializable {@code ImmutableSortedSet}. 646 * 647 * <p>The {@link SortedSet#subSet} documentation states that a subset of a subset throws an {@link 648 * IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code 649 * fromElement}. However, this method doesn't throw an exception in that situation, but instead 650 * keeps the original {@code fromElement}. Similarly, this method keeps the original {@code 651 * toElement}, instead of throwing an exception, if passed a {@code toElement} greater than an 652 * earlier {@code toElement}. 653 */ 654 @Override 655 public ImmutableSortedSet<E> subSet(E fromElement, E toElement) { 656 return subSet(fromElement, true, toElement, false); 657 } 658 659 /** @since 12.0 */ 660 @GwtIncompatible // NavigableSet 661 @Override 662 public ImmutableSortedSet<E> subSet( 663 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 664 checkNotNull(fromElement); 665 checkNotNull(toElement); 666 checkArgument(comparator.compare(fromElement, toElement) <= 0); 667 return subSetImpl(fromElement, fromInclusive, toElement, toInclusive); 668 } 669 670 /** 671 * {@inheritDoc} 672 * 673 * <p>This method returns a serializable {@code ImmutableSortedSet}. 674 * 675 * <p>The {@link SortedSet#tailSet} documentation states that a subset of a subset throws an 676 * {@link IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code 677 * fromElement}. However, this method doesn't throw an exception in that situation, but instead 678 * keeps the original {@code fromElement}. 679 */ 680 @Override 681 public ImmutableSortedSet<E> tailSet(E fromElement) { 682 return tailSet(fromElement, true); 683 } 684 685 /** @since 12.0 */ 686 @Override 687 public ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) { 688 return tailSetImpl(checkNotNull(fromElement), inclusive); 689 } 690 691 /* 692 * These methods perform most headSet, subSet, and tailSet logic, besides 693 * parameter validation. 694 */ 695 abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive); 696 697 abstract ImmutableSortedSet<E> subSetImpl( 698 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive); 699 700 abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive); 701 702 /** @since 12.0 */ 703 @GwtIncompatible // NavigableSet 704 @Override 705 @CheckForNull 706 public E lower(E e) { 707 return Iterators.<@Nullable E>getNext(headSet(e, false).descendingIterator(), null); 708 } 709 710 /** @since 12.0 */ 711 @Override 712 @CheckForNull 713 public E floor(E e) { 714 return Iterators.<@Nullable E>getNext(headSet(e, true).descendingIterator(), null); 715 } 716 717 /** @since 12.0 */ 718 @Override 719 @CheckForNull 720 public E ceiling(E e) { 721 return Iterables.<@Nullable E>getFirst(tailSet(e, true), null); 722 } 723 724 /** @since 12.0 */ 725 @GwtIncompatible // NavigableSet 726 @Override 727 @CheckForNull 728 public E higher(E e) { 729 return Iterables.<@Nullable E>getFirst(tailSet(e, false), null); 730 } 731 732 @Override 733 public E first() { 734 return iterator().next(); 735 } 736 737 @Override 738 public E last() { 739 return descendingIterator().next(); 740 } 741 742 /** 743 * Guaranteed to throw an exception and leave the set unmodified. 744 * 745 * @since 12.0 746 * @throws UnsupportedOperationException always 747 * @deprecated Unsupported operation. 748 */ 749 @CanIgnoreReturnValue 750 @Deprecated 751 @GwtIncompatible // NavigableSet 752 @Override 753 @DoNotCall("Always throws UnsupportedOperationException") 754 @CheckForNull 755 public final E pollFirst() { 756 throw new UnsupportedOperationException(); 757 } 758 759 /** 760 * Guaranteed to throw an exception and leave the set unmodified. 761 * 762 * @since 12.0 763 * @throws UnsupportedOperationException always 764 * @deprecated Unsupported operation. 765 */ 766 @CanIgnoreReturnValue 767 @Deprecated 768 @GwtIncompatible // NavigableSet 769 @Override 770 @DoNotCall("Always throws UnsupportedOperationException") 771 @CheckForNull 772 public final E pollLast() { 773 throw new UnsupportedOperationException(); 774 } 775 776 @GwtIncompatible // NavigableSet 777 @LazyInit 778 @CheckForNull 779 transient ImmutableSortedSet<E> descendingSet; 780 781 /** @since 12.0 */ 782 @GwtIncompatible // NavigableSet 783 @Override 784 public ImmutableSortedSet<E> descendingSet() { 785 // racy single-check idiom 786 ImmutableSortedSet<E> result = descendingSet; 787 if (result == null) { 788 result = descendingSet = createDescendingSet(); 789 result.descendingSet = this; 790 } 791 return result; 792 } 793 794 // Most classes should implement this as new DescendingImmutableSortedSet<E>(this), 795 // but we push down that implementation because ProGuard can't eliminate it even when it's always 796 // overridden. 797 @GwtIncompatible // NavigableSet 798 abstract ImmutableSortedSet<E> createDescendingSet(); 799 800 @Override 801 public Spliterator<E> spliterator() { 802 return new Spliterators.AbstractSpliterator<E>( 803 size(), SPLITERATOR_CHARACTERISTICS | Spliterator.SIZED) { 804 final UnmodifiableIterator<E> iterator = iterator(); 805 806 @Override 807 public boolean tryAdvance(Consumer<? super E> action) { 808 if (iterator.hasNext()) { 809 action.accept(iterator.next()); 810 return true; 811 } else { 812 return false; 813 } 814 } 815 816 @Override 817 public Comparator<? super E> getComparator() { 818 return comparator; 819 } 820 }; 821 } 822 823 /** @since 12.0 */ 824 @GwtIncompatible // NavigableSet 825 @Override 826 public abstract UnmodifiableIterator<E> descendingIterator(); 827 828 /** Returns the position of an element within the set, or -1 if not present. */ 829 abstract int indexOf(@CheckForNull Object target); 830 831 /* 832 * This class is used to serialize all ImmutableSortedSet instances, 833 * regardless of implementation type. It captures their "logical contents" 834 * only. This is necessary to ensure that the existence of a particular 835 * implementation type is an implementation detail. 836 */ 837 @J2ktIncompatible // serialization 838 private static class SerializedForm<E> implements Serializable { 839 final Comparator<? super E> comparator; 840 final Object[] elements; 841 842 public SerializedForm(Comparator<? super E> comparator, Object[] elements) { 843 this.comparator = comparator; 844 this.elements = elements; 845 } 846 847 @SuppressWarnings("unchecked") 848 Object readResolve() { 849 return new Builder<E>(comparator).add((E[]) elements).build(); 850 } 851 852 private static final long serialVersionUID = 0; 853 } 854 855 @J2ktIncompatible // serialization 856 private void readObject(ObjectInputStream unused) throws InvalidObjectException { 857 throw new InvalidObjectException("Use SerializedForm"); 858 } 859 860 @Override 861 @J2ktIncompatible // serialization 862 Object writeReplace() { 863 return new SerializedForm<E>(comparator, toArray()); 864 } 865 866 /** 867 * Not supported. Use {@link #toImmutableSortedSet} instead. This method exists only to hide 868 * {@link ImmutableSet#toImmutableSet} from consumers of {@code ImmutableSortedSet}. 869 * 870 * @throws UnsupportedOperationException always 871 * @deprecated Use {@link ImmutableSortedSet#toImmutableSortedSet}. 872 * @since 21.0 873 */ 874 @DoNotCall("Use toImmutableSortedSet") 875 @Deprecated 876 public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() { 877 throw new UnsupportedOperationException(); 878 } 879 880 /** 881 * Not supported. Use {@link #naturalOrder}, which offers better type-safety, instead. This method 882 * exists only to hide {@link ImmutableSet#builder} from consumers of {@code ImmutableSortedSet}. 883 * 884 * @throws UnsupportedOperationException always 885 * @deprecated Use {@link ImmutableSortedSet#naturalOrder}, which offers better type-safety. 886 */ 887 @DoNotCall("Use naturalOrder") 888 @Deprecated 889 public static <E> ImmutableSortedSet.Builder<E> builder() { 890 throw new UnsupportedOperationException(); 891 } 892 893 /** 894 * Not supported. This method exists only to hide {@link ImmutableSet#builderWithExpectedSize} 895 * from consumers of {@code ImmutableSortedSet}. 896 * 897 * @throws UnsupportedOperationException always 898 * @deprecated Not supported by ImmutableSortedSet. 899 */ 900 @DoNotCall("Use naturalOrder (which does not accept an expected size)") 901 @Deprecated 902 public static <E> ImmutableSortedSet.Builder<E> builderWithExpectedSize(int expectedSize) { 903 throw new UnsupportedOperationException(); 904 } 905 906 /** 907 * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable} 908 * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this 909 * dummy version. 910 * 911 * @throws UnsupportedOperationException always 912 * @deprecated <b>Pass a parameter of type {@code Comparable} to use {@link 913 * ImmutableSortedSet#of(Comparable)}.</b> 914 */ 915 @DoNotCall("Pass a parameter of type Comparable") 916 @Deprecated 917 public static <E> ImmutableSortedSet<E> of(E element) { 918 throw new UnsupportedOperationException(); 919 } 920 921 /** 922 * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable} 923 * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this 924 * dummy version. 925 * 926 * @throws UnsupportedOperationException always 927 * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link 928 * ImmutableSortedSet#of(Comparable, Comparable)}.</b> 929 */ 930 @DoNotCall("Pass parameters of type Comparable") 931 @Deprecated 932 public static <E> ImmutableSortedSet<E> of(E e1, E e2) { 933 throw new UnsupportedOperationException(); 934 } 935 936 /** 937 * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable} 938 * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this 939 * dummy version. 940 * 941 * @throws UnsupportedOperationException always 942 * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link 943 * ImmutableSortedSet#of(Comparable, Comparable, Comparable)}.</b> 944 */ 945 @DoNotCall("Pass parameters of type Comparable") 946 @Deprecated 947 public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3) { 948 throw new UnsupportedOperationException(); 949 } 950 951 /** 952 * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable} 953 * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this 954 * dummy version. 955 * 956 * @throws UnsupportedOperationException always 957 * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link 958 * ImmutableSortedSet#of(Comparable, Comparable, Comparable, Comparable)}. </b> 959 */ 960 @DoNotCall("Pass parameters of type Comparable") 961 @Deprecated 962 public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4) { 963 throw new UnsupportedOperationException(); 964 } 965 966 /** 967 * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable} 968 * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this 969 * dummy version. 970 * 971 * @throws UnsupportedOperationException always 972 * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link 973 * ImmutableSortedSet#of( Comparable, Comparable, Comparable, Comparable, Comparable)}. </b> 974 */ 975 @DoNotCall("Pass parameters of type Comparable") 976 @Deprecated 977 public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4, E e5) { 978 throw new UnsupportedOperationException(); 979 } 980 981 /** 982 * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable} 983 * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this 984 * dummy version. 985 * 986 * @throws UnsupportedOperationException always 987 * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link 988 * ImmutableSortedSet#of(Comparable, Comparable, Comparable, Comparable, Comparable, 989 * Comparable, Comparable...)}. </b> 990 */ 991 @DoNotCall("Pass parameters of type Comparable") 992 @Deprecated 993 public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) { 994 throw new UnsupportedOperationException(); 995 } 996 997 /** 998 * Not supported. <b>You are attempting to create a set that may contain non-{@code Comparable} 999 * elements.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this 1000 * dummy version. 1001 * 1002 * @throws UnsupportedOperationException always 1003 * @deprecated <b>Pass parameters of type {@code Comparable} to use {@link 1004 * ImmutableSortedSet#copyOf(Comparable[])}.</b> 1005 */ 1006 @DoNotCall("Pass parameters of type Comparable") 1007 @Deprecated 1008 // The usage of "Z" here works around bugs in Javadoc (JDK-8318093) and JDiff. 1009 public static <Z> ImmutableSortedSet<Z> copyOf(Z[] elements) { 1010 throw new UnsupportedOperationException(); 1011 } 1012 1013 private static final long serialVersionUID = 0xcafebabe; 1014}