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