1 /*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
22
23 import com.google.common.annotations.GwtCompatible;
24 import com.google.common.annotations.GwtIncompatible;
25 import com.google.errorprone.annotations.CanIgnoreReturnValue;
26 import com.google.errorprone.annotations.DoNotCall;
27 import com.google.errorprone.annotations.concurrent.LazyInit;
28 import java.io.InvalidObjectException;
29 import java.io.ObjectInputStream;
30 import java.io.Serializable;
31 import java.util.Arrays;
32 import java.util.Collection;
33 import java.util.Collections;
34 import java.util.Comparator;
35 import java.util.Iterator;
36 import java.util.NavigableSet;
37 import java.util.SortedSet;
38 import java.util.Spliterator;
39 import java.util.Spliterators;
40 import java.util.function.Consumer;
41 import java.util.stream.Collector;
42 import org.checkerframework.checker.nullness.qual.Nullable;
43
44 /**
45 * A {@link NavigableSet} whose contents will never change, with many other important properties
46 * detailed at {@link ImmutableCollection}.
47 *
48 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
49 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
50 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
51 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting
52 * collection will not correctly obey its specification.
53 *
54 * <p>See the Guava User Guide article on <a href=
55 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>.
56 *
57 * @author Jared Levy
58 * @author Louis Wasserman
59 * @since 2.0 (implements {@code NavigableSet} since 12.0)
60 */
61 // TODO(benyu): benchmark and optimize all creation paths, which are a mess now
62 @GwtCompatible(serializable = true, emulated = true)
63 @SuppressWarnings("serial") // we're overriding default serialization
64 public abstract class ImmutableSortedSet<E> extends ImmutableSortedSetFauxverideShim<E>
65 implements NavigableSet<E>, SortedIterable<E> {
66 static final int SPLITERATOR_CHARACTERISTICS =
67 ImmutableSet.SPLITERATOR_CHARACTERISTICS | Spliterator.SORTED;
68
69 /**
70 * Returns a {@code Collector} that accumulates the input elements into a new {@code
71 * ImmutableSortedSet}, ordered by the specified comparator.
72 *
73 * <p>If the elements contain duplicates (according to the comparator), only the first duplicate
74 * in encounter order will appear in the result.
75 *
76 * @since 21.0
77 */
78 public static <E> Collector<E, ?, ImmutableSortedSet<E>> toImmutableSortedSet(
79 Comparator<? super E> comparator) {
80 return CollectCollectors.toImmutableSortedSet(comparator);
81 }
82
83 static <E> RegularImmutableSortedSet<E> emptySet(Comparator<? super E> comparator) {
84 if (Ordering.natural().equals(comparator)) {
85 return (RegularImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET;
86 } else {
87 return new RegularImmutableSortedSet<E>(ImmutableList.<E>of(), comparator);
88 }
89 }
90
91 /**
92 * Returns the empty immutable sorted set.
93 *
94 * <p><b>Performance note:</b> the instance returned is a singleton.
95 */
96 public static <E> ImmutableSortedSet<E> of() {
97 return (ImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET;
98 }
99
100 /** Returns an immutable sorted set containing a single element. */
101 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E element) {
102 return new RegularImmutableSortedSet<E>(ImmutableList.of(element), Ordering.natural());
103 }
104
105 /**
106 * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
107 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
108 * one specified is included.
109 *
110 * @throws NullPointerException if any element is null
111 */
112 @SuppressWarnings("unchecked")
113 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2) {
114 return construct(Ordering.natural(), 2, e1, e2);
115 }
116
117 /**
118 * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
119 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
120 * one specified is included.
121 *
122 * @throws NullPointerException if any element is null
123 */
124 @SuppressWarnings("unchecked")
125 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2, E e3) {
126 return construct(Ordering.natural(), 3, e1, e2, e3);
127 }
128
129 /**
130 * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
131 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
132 * one specified is included.
133 *
134 * @throws NullPointerException if any element is null
135 */
136 @SuppressWarnings("unchecked")
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 @SuppressWarnings("unchecked")
149 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
150 E e1, E e2, E e3, E e4, E e5) {
151 return construct(Ordering.natural(), 5, e1, e2, e3, e4, e5);
152 }
153
154 /**
155 * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
156 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
157 * one specified is included.
158 *
159 * @throws NullPointerException if any element is null
160 * @since 3.0 (source-compatible since 2.0)
161 */
162 @SuppressWarnings("unchecked")
163 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
164 E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
165 Comparable[] contents = new Comparable[6 + remaining.length];
166 contents[0] = e1;
167 contents[1] = e2;
168 contents[2] = e3;
169 contents[3] = e4;
170 contents[4] = e5;
171 contents[5] = e6;
172 System.arraycopy(remaining, 0, contents, 6, remaining.length);
173 return construct(Ordering.natural(), contents.length, (E[]) contents);
174 }
175
176 // TODO(kevinb): Consider factory methods that reject duplicates
177
178 /**
179 * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
180 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
181 * one specified is included.
182 *
183 * @throws NullPointerException if any of {@code elements} is null
184 * @since 3.0
185 */
186 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(E[] elements) {
187 return construct(Ordering.natural(), elements.length, elements.clone());
188 }
189
190 /**
191 * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
192 * When multiple elements are equivalent according to {@code compareTo()}, only the first one
193 * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator,
194 * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once.
195 *
196 * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)}
197 * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s},
198 * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>}
199 * containing one element (the given set itself).
200 *
201 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
202 * safe to do so. The exact circumstances under which a copy will or will not be performed are
203 * undocumented and subject to change.
204 *
205 * <p>This method is not type-safe, as it may be called on elements that are not mutually
206 * comparable.
207 *
208 * @throws ClassCastException if the elements are not mutually comparable
209 * @throws NullPointerException if any of {@code elements} is null
210 */
211 public static <E> ImmutableSortedSet<E> copyOf(Iterable<? extends E> elements) {
212 // Hack around E not being a subtype of Comparable.
213 // Unsafe, see ImmutableSortedSetFauxverideShim.
214 @SuppressWarnings("unchecked")
215 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
216 return copyOf(naturalOrder, elements);
217 }
218
219 /**
220 * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
221 * When multiple elements are equivalent according to {@code compareTo()}, only the first one
222 * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator,
223 * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once.
224 *
225 * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)}
226 * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s},
227 * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>}
228 * containing one element (the given set itself).
229 *
230 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements} is an {@code
231 * ImmutableSortedSet}, it may be returned instead of a copy.
232 *
233 * <p>This method is not type-safe, as it may be called on elements that are not mutually
234 * comparable.
235 *
236 * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent
237 * collection that is currently being modified by another thread.
238 *
239 * @throws ClassCastException if the elements are not mutually comparable
240 * @throws NullPointerException if any of {@code elements} is null
241 * @since 7.0 (source-compatible since 2.0)
242 */
243 public static <E> ImmutableSortedSet<E> copyOf(Collection<? extends E> elements) {
244 // Hack around E not being a subtype of Comparable.
245 // Unsafe, see ImmutableSortedSetFauxverideShim.
246 @SuppressWarnings("unchecked")
247 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
248 return copyOf(naturalOrder, elements);
249 }
250
251 /**
252 * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
253 * When multiple elements are equivalent according to {@code compareTo()}, only the first one
254 * specified is included.
255 *
256 * <p>This method is not type-safe, as it may be called on elements that are not mutually
257 * comparable.
258 *
259 * @throws ClassCastException if the elements are not mutually comparable
260 * @throws NullPointerException if any of {@code elements} is null
261 */
262 public static <E> ImmutableSortedSet<E> copyOf(Iterator<? extends E> elements) {
263 // Hack around E not being a subtype of Comparable.
264 // Unsafe, see ImmutableSortedSetFauxverideShim.
265 @SuppressWarnings("unchecked")
266 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
267 return copyOf(naturalOrder, elements);
268 }
269
270 /**
271 * Returns an immutable sorted set containing the given elements sorted by the given {@code
272 * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the
273 * first one specified is included.
274 *
275 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
276 */
277 public static <E> ImmutableSortedSet<E> copyOf(
278 Comparator<? super E> comparator, Iterator<? extends E> elements) {
279 return new Builder<E>(comparator).addAll(elements).build();
280 }
281
282 /**
283 * Returns an immutable sorted set containing the given elements sorted by the given {@code
284 * Comparator}. When multiple elements are equivalent according to {@code compare()}, only the
285 * first one specified is included. This method iterates over {@code elements} at most once.
286 *
287 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
288 * safe to do so. The exact circumstances under which a copy will or will not be performed are
289 * undocumented and subject to change.
290 *
291 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
292 */
293 public static <E> ImmutableSortedSet<E> copyOf(
294 Comparator<? super E> comparator, Iterable<? extends E> elements) {
295 checkNotNull(comparator);
296 boolean hasSameComparator = SortedIterables.hasSameComparator(comparator, elements);
297
298 if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
299 @SuppressWarnings("unchecked")
300 ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
301 if (!original.isPartialView()) {
302 return original;
303 }
304 }
305 @SuppressWarnings("unchecked") // elements only contains E's; it's safe.
306 E[] array = (E[]) Iterables.toArray(elements);
307 return construct(comparator, array.length, array);
308 }
309
310 /**
311 * Returns an immutable sorted set containing the given elements sorted by the given {@code
312 * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the
313 * first one specified is included.
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 safe to use even when {@code elements} is a synchronized or concurrent
320 * collection that is currently being modified by another thread.
321 *
322 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
323 * @since 7.0 (source-compatible since 2.0)
324 */
325 public static <E> ImmutableSortedSet<E> copyOf(
326 Comparator<? super E> comparator, Collection<? extends E> elements) {
327 return copyOf(comparator, (Iterable<? extends E>) elements);
328 }
329
330 /**
331 * Returns an immutable sorted set containing the elements of a sorted set, sorted by the same
332 * {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which always uses the
333 * natural ordering of the elements.
334 *
335 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
336 * safe to do so. The exact circumstances under which a copy will or will not be performed are
337 * undocumented and subject to change.
338 *
339 * <p>This method is safe to use even when {@code sortedSet} is a synchronized or concurrent
340 * collection that is currently being modified by another thread.
341 *
342 * @throws NullPointerException if {@code sortedSet} or any of its elements is null
343 */
344 public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
345 Comparator<? super E> comparator = SortedIterables.comparator(sortedSet);
346 ImmutableList<E> list = ImmutableList.copyOf(sortedSet);
347 if (list.isEmpty()) {
348 return emptySet(comparator);
349 } else {
350 return new RegularImmutableSortedSet<E>(list, comparator);
351 }
352 }
353
354 /**
355 * Constructs an {@code ImmutableSortedSet} from the first {@code n} elements of {@code contents}.
356 * If {@code k} is the size of the returned {@code ImmutableSortedSet}, then the sorted unique
357 * elements are in the first {@code k} positions of {@code contents}, and {@code contents[i] ==
358 * null} for {@code k <= i < n}.
359 *
360 * <p>If {@code k == contents.length}, then {@code contents} may no longer be safe for
361 * modification.
362 *
363 * @throws NullPointerException if any of the first {@code n} elements of {@code contents} is null
364 */
365 static <E> ImmutableSortedSet<E> construct(
366 Comparator<? super E> comparator, int n, E... contents) {
367 if (n == 0) {
368 return emptySet(comparator);
369 }
370 checkElementsNotNull(contents, n);
371 Arrays.sort(contents, 0, n, comparator);
372 int uniques = 1;
373 for (int i = 1; i < n; i++) {
374 E cur = contents[i];
375 E prev = contents[uniques - 1];
376 if (comparator.compare(cur, prev) != 0) {
377 contents[uniques++] = cur;
378 }
379 }
380 Arrays.fill(contents, uniques, n, null);
381 return new RegularImmutableSortedSet<E>(
382 ImmutableList.<E>asImmutableList(contents, uniques), comparator);
383 }
384
385 /**
386 * Returns a builder that creates immutable sorted sets with an explicit comparator. If the
387 * comparator has a more general type than the set being generated, such as creating a {@code
388 * SortedSet<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} constructor
389 * instead.
390 *
391 * @throws NullPointerException if {@code comparator} is null
392 */
393 public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
394 return new Builder<E>(comparator);
395 }
396
397 /**
398 * Returns a builder that creates immutable sorted sets whose elements are ordered by the reverse
399 * of their natural ordering.
400 */
401 public static <E extends Comparable<?>> Builder<E> reverseOrder() {
402 return new Builder<E>(Collections.reverseOrder());
403 }
404
405 /**
406 * Returns a builder that creates immutable sorted sets whose elements are ordered by their
407 * natural ordering. The sorted sets use {@link Ordering#natural()} as the comparator. This method
408 * provides more type-safety than {@link #builder}, as it can be called only for classes that
409 * implement {@link Comparable}.
410 */
411 public static <E extends Comparable<?>> Builder<E> naturalOrder() {
412 return new Builder<E>(Ordering.natural());
413 }
414
415 /**
416 * A builder for creating immutable sorted set instances, especially {@code public static final}
417 * sets ("constant sets"), with a given comparator. Example:
418 *
419 * <pre>{@code
420 * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
421 * new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
422 * .addAll(SINGLE_DIGIT_PRIMES)
423 * .add(42)
424 * .build();
425 * }</pre>
426 *
427 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
428 * multiple sets in series. Each set is a superset of the set created before it.
429 *
430 * @since 2.0
431 */
432 public static final class Builder<E> extends ImmutableSet.Builder<E> {
433 private final Comparator<? super E> comparator;
434 private E[] elements;
435 private int n;
436
437 /**
438 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
439 * ImmutableSortedSet#orderedBy}.
440 */
441 public Builder(Comparator<? super E> comparator) {
442 super(true); // don't construct guts of hash-based set builder
443 this.comparator = checkNotNull(comparator);
444 this.elements = (E[]) new Object[ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY];
445 this.n = 0;
446 }
447
448 @Override
449 void copy() {
450 elements = Arrays.copyOf(elements, elements.length);
451 }
452
453 private void sortAndDedup() {
454 if (n == 0) {
455 return;
456 }
457 Arrays.sort(elements, 0, n, comparator);
458 int unique = 1;
459 for (int i = 1; i < n; i++) {
460 int cmp = comparator.compare(elements[unique - 1], elements[i]);
461 if (cmp < 0) {
462 elements[unique++] = elements[i];
463 } else if (cmp > 0) {
464 throw new AssertionError(
465 "Comparator " + comparator + " compare method violates its contract");
466 }
467 }
468 Arrays.fill(elements, unique, n, null);
469 n = unique;
470 }
471
472 /**
473 * Adds {@code element} to the {@code ImmutableSortedSet}. If the {@code ImmutableSortedSet}
474 * already contains {@code element}, then {@code add} has no effect. (only the previously added
475 * element is retained).
476 *
477 * @param element the element to add
478 * @return this {@code Builder} object
479 * @throws NullPointerException if {@code element} is null
480 */
481 @CanIgnoreReturnValue
482 @Override
483 public Builder<E> add(E element) {
484 checkNotNull(element);
485 copyIfNecessary();
486 if (n == elements.length) {
487 sortAndDedup();
488 /*
489 * Sorting operations can only be allowed to occur once every O(n) operations to keep
490 * amortized O(n log n) performance. Therefore, ensure there are at least O(n) *unused*
491 * spaces in the builder array.
492 */
493 int newLength = ImmutableCollection.Builder.expandedCapacity(n, n + 1);
494 if (newLength > elements.length) {
495 elements = Arrays.copyOf(elements, newLength);
496 }
497 }
498 elements[n++] = element;
499 return this;
500 }
501
502 /**
503 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
504 * elements (only the first duplicate element is added).
505 *
506 * @param elements the elements to add
507 * @return this {@code Builder} object
508 * @throws NullPointerException if {@code elements} contains a null element
509 */
510 @CanIgnoreReturnValue
511 @Override
512 public Builder<E> add(E... elements) {
513 checkElementsNotNull(elements);
514 for (E e : elements) {
515 add(e);
516 }
517 return this;
518 }
519
520 /**
521 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
522 * elements (only the first duplicate element is added).
523 *
524 * @param elements the elements to add to the {@code ImmutableSortedSet}
525 * @return this {@code Builder} object
526 * @throws NullPointerException if {@code elements} contains a null element
527 */
528 @CanIgnoreReturnValue
529 @Override
530 public Builder<E> addAll(Iterable<? extends E> elements) {
531 super.addAll(elements);
532 return this;
533 }
534
535 /**
536 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
537 * elements (only the first duplicate element is added).
538 *
539 * @param elements the elements to add to the {@code ImmutableSortedSet}
540 * @return this {@code Builder} object
541 * @throws NullPointerException if {@code elements} contains a null element
542 */
543 @CanIgnoreReturnValue
544 @Override
545 public Builder<E> addAll(Iterator<? extends E> elements) {
546 super.addAll(elements);
547 return this;
548 }
549
550 @CanIgnoreReturnValue
551 @Override
552 Builder<E> combine(ImmutableSet.Builder<E> builder) {
553 copyIfNecessary();
554 Builder<E> other = (Builder<E>) builder;
555 for (int i = 0; i < other.n; i++) {
556 add(other.elements[i]);
557 }
558 return this;
559 }
560
561 /**
562 * Returns a newly-created {@code ImmutableSortedSet} based on the contents of the {@code
563 * Builder} and its comparator.
564 */
565 @Override
566 public ImmutableSortedSet<E> build() {
567 sortAndDedup();
568 if (n == 0) {
569 return emptySet(comparator);
570 } else {
571 forceCopy = true;
572 return new RegularImmutableSortedSet<E>(
573 ImmutableList.asImmutableList(elements, n), comparator);
574 }
575 }
576 }
577
578 int unsafeCompare(Object a, Object b) {
579 return unsafeCompare(comparator, a, b);
580 }
581
582 static int unsafeCompare(Comparator<?> comparator, Object a, Object b) {
583 // Pretend the comparator can compare anything. If it turns out it can't
584 // compare a and b, we should get a CCE on the subsequent line. Only methods
585 // that are spec'd to throw CCE should call this.
586 @SuppressWarnings("unchecked")
587 Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
588 return unsafeComparator.compare(a, b);
589 }
590
591 final transient Comparator<? super E> comparator;
592
593 ImmutableSortedSet(Comparator<? super E> comparator) {
594 this.comparator = comparator;
595 }
596
597 /**
598 * Returns the comparator that orders the elements, which is {@link Ordering#natural()} when the
599 * natural ordering of the elements is used. Note that its behavior is not consistent with {@link
600 * SortedSet#comparator()}, which returns {@code null} to indicate natural ordering.
601 */
602 @Override
603 public Comparator<? super E> comparator() {
604 return comparator;
605 }
606
607 @Override // needed to unify the iterator() methods in Collection and SortedIterable
608 public abstract UnmodifiableIterator<E> iterator();
609
610 /**
611 * {@inheritDoc}
612 *
613 * <p>This method returns a serializable {@code ImmutableSortedSet}.
614 *
615 * <p>The {@link SortedSet#headSet} documentation states that a subset of a subset throws an
616 * {@link IllegalArgumentException} if passed a {@code toElement} greater than an earlier {@code
617 * toElement}. However, this method doesn't throw an exception in that situation, but instead
618 * keeps the original {@code toElement}.
619 */
620 @Override
621 public ImmutableSortedSet<E> headSet(E toElement) {
622 return headSet(toElement, false);
623 }
624
625 /** @since 12.0 */
626 @Override
627 public ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) {
628 return headSetImpl(checkNotNull(toElement), inclusive);
629 }
630
631 /**
632 * {@inheritDoc}
633 *
634 * <p>This method returns a serializable {@code ImmutableSortedSet}.
635 *
636 * <p>The {@link SortedSet#subSet} documentation states that a subset of a subset throws an {@link
637 * IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code
638 * fromElement}. However, this method doesn't throw an exception in that situation, but instead
639 * keeps the original {@code fromElement}. Similarly, this method keeps the original {@code
640 * toElement}, instead of throwing an exception, if passed a {@code toElement} greater than an
641 * earlier {@code toElement}.
642 */
643 @Override
644 public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
645 return subSet(fromElement, true, toElement, false);
646 }
647
648 /** @since 12.0 */
649 @GwtIncompatible // NavigableSet
650 @Override
651 public ImmutableSortedSet<E> subSet(
652 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
653 checkNotNull(fromElement);
654 checkNotNull(toElement);
655 checkArgument(comparator.compare(fromElement, toElement) <= 0);
656 return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
657 }
658
659 /**
660 * {@inheritDoc}
661 *
662 * <p>This method returns a serializable {@code ImmutableSortedSet}.
663 *
664 * <p>The {@link SortedSet#tailSet} documentation states that a subset of a subset throws an
665 * {@link IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code
666 * fromElement}. However, this method doesn't throw an exception in that situation, but instead
667 * keeps the original {@code fromElement}.
668 */
669 @Override
670 public ImmutableSortedSet<E> tailSet(E fromElement) {
671 return tailSet(fromElement, true);
672 }
673
674 /** @since 12.0 */
675 @Override
676 public ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) {
677 return tailSetImpl(checkNotNull(fromElement), inclusive);
678 }
679
680 /*
681 * These methods perform most headSet, subSet, and tailSet logic, besides
682 * parameter validation.
683 */
684 abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive);
685
686 abstract ImmutableSortedSet<E> subSetImpl(
687 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
688
689 abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive);
690
691 /** @since 12.0 */
692 @GwtIncompatible // NavigableSet
693 @Override
694 public E lower(E e) {
695 return Iterators.getNext(headSet(e, false).descendingIterator(), null);
696 }
697
698 /** @since 12.0 */
699 @Override
700 public E floor(E e) {
701 return Iterators.getNext(headSet(e, true).descendingIterator(), null);
702 }
703
704 /** @since 12.0 */
705 @Override
706 public E ceiling(E e) {
707 return Iterables.getFirst(tailSet(e, true), null);
708 }
709
710 /** @since 12.0 */
711 @GwtIncompatible // NavigableSet
712 @Override
713 public E higher(E e) {
714 return Iterables.getFirst(tailSet(e, false), null);
715 }
716
717 @Override
718 public E first() {
719 return iterator().next();
720 }
721
722 @Override
723 public E last() {
724 return descendingIterator().next();
725 }
726
727 /**
728 * Guaranteed to throw an exception and leave the set unmodified.
729 *
730 * @since 12.0
731 * @throws UnsupportedOperationException always
732 * @deprecated Unsupported operation.
733 */
734 @CanIgnoreReturnValue
735 @Deprecated
736 @GwtIncompatible // NavigableSet
737 @Override
738 @DoNotCall("Always throws UnsupportedOperationException")
739 public final E pollFirst() {
740 throw new UnsupportedOperationException();
741 }
742
743 /**
744 * Guaranteed to throw an exception and leave the set unmodified.
745 *
746 * @since 12.0
747 * @throws UnsupportedOperationException always
748 * @deprecated Unsupported operation.
749 */
750 @CanIgnoreReturnValue
751 @Deprecated
752 @GwtIncompatible // NavigableSet
753 @Override
754 @DoNotCall("Always throws UnsupportedOperationException")
755 public final E pollLast() {
756 throw new UnsupportedOperationException();
757 }
758
759 @GwtIncompatible // NavigableSet
760 @LazyInit
761 transient ImmutableSortedSet<E> descendingSet;
762
763 /** @since 12.0 */
764 @GwtIncompatible // NavigableSet
765 @Override
766 public ImmutableSortedSet<E> descendingSet() {
767 // racy single-check idiom
768 ImmutableSortedSet<E> result = descendingSet;
769 if (result == null) {
770 result = descendingSet = createDescendingSet();
771 result.descendingSet = this;
772 }
773 return result;
774 }
775
776 // Most classes should implement this as new DescendingImmutableSortedSet<E>(this),
777 // but we push down that implementation because ProGuard can't eliminate it even when it's always
778 // overridden.
779 @GwtIncompatible // NavigableSet
780 abstract ImmutableSortedSet<E> createDescendingSet();
781
782 @Override
783 public Spliterator<E> spliterator() {
784 return new Spliterators.AbstractSpliterator<E>(
785 size(), SPLITERATOR_CHARACTERISTICS | Spliterator.SIZED) {
786 final UnmodifiableIterator<E> iterator = iterator();
787
788 @Override
789 public boolean tryAdvance(Consumer<? super E> action) {
790 if (iterator.hasNext()) {
791 action.accept(iterator.next());
792 return true;
793 } else {
794 return false;
795 }
796 }
797
798 @Override
799 public Comparator<? super E> getComparator() {
800 return comparator;
801 }
802 };
803 }
804
805 /** @since 12.0 */
806 @GwtIncompatible // NavigableSet
807 @Override
808 public abstract UnmodifiableIterator<E> descendingIterator();
809
810 /** Returns the position of an element within the set, or -1 if not present. */
811 abstract int indexOf(@Nullable Object target);
812
813 /*
814 * This class is used to serialize all ImmutableSortedSet instances,
815 * regardless of implementation type. It captures their "logical contents"
816 * only. This is necessary to ensure that the existence of a particular
817 * implementation type is an implementation detail.
818 */
819 private static class SerializedForm<E> implements Serializable {
820 final Comparator<? super E> comparator;
821 final Object[] elements;
822
823 public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
824 this.comparator = comparator;
825 this.elements = elements;
826 }
827
828 @SuppressWarnings("unchecked")
829 Object readResolve() {
830 return new Builder<E>(comparator).add((E[]) elements).build();
831 }
832
833 private static final long serialVersionUID = 0;
834 }
835
836 private void readObject(ObjectInputStream unused) throws InvalidObjectException {
837 throw new InvalidObjectException("Use SerializedForm");
838 }
839
840 @Override
841 Object writeReplace() {
842 return new SerializedForm<E>(comparator, toArray());
843 }
844 }