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