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