001/*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkNotNull;
021import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
022
023import com.google.common.annotations.GwtCompatible;
024import com.google.common.annotations.GwtIncompatible;
025import com.google.errorprone.annotations.CanIgnoreReturnValue;
026import com.google.errorprone.annotations.concurrent.LazyInit;
027import java.io.InvalidObjectException;
028import java.io.ObjectInputStream;
029import java.io.Serializable;
030import java.util.Arrays;
031import java.util.Collection;
032import java.util.Collections;
033import java.util.Comparator;
034import java.util.Iterator;
035import java.util.NavigableSet;
036import java.util.SortedSet;
037import org.checkerframework.checker.nullness.compatqual.NullableDecl;
038
039/**
040 * A {@link NavigableSet} whose contents will never change, with many other important properties
041 * detailed at {@link ImmutableCollection}.
042 *
043 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
044 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
045 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
046 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting
047 * collection will not correctly obey its specification.
048 *
049 * <p>See the Guava User Guide article on <a href=
050 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>.
051 *
052 * @author Jared Levy
053 * @author Louis Wasserman
054 * @since 2.0 (implements {@code NavigableSet} since 12.0)
055 */
056// TODO(benyu): benchmark and optimize all creation paths, which are a mess now
057@GwtCompatible(serializable = true, emulated = true)
058@SuppressWarnings("serial") // we're overriding default serialization
059public abstract class ImmutableSortedSet<E> extends ImmutableSortedSetFauxverideShim<E>
060    implements NavigableSet<E>, SortedIterable<E> {
061  static <E> RegularImmutableSortedSet<E> emptySet(Comparator<? super E> comparator) {
062    if (Ordering.natural().equals(comparator)) {
063      return (RegularImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET;
064    } else {
065      return new RegularImmutableSortedSet<E>(ImmutableList.<E>of(), comparator);
066    }
067  }
068
069  /** Returns the empty immutable sorted set. */
070  public static <E> ImmutableSortedSet<E> of() {
071    return (ImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET;
072  }
073
074  /** Returns an immutable sorted set containing a single element. */
075  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E element) {
076    return new RegularImmutableSortedSet<E>(ImmutableList.of(element), Ordering.natural());
077  }
078
079  /**
080   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
081   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
082   * one specified is included.
083   *
084   * @throws NullPointerException if any element is null
085   */
086  @SuppressWarnings("unchecked")
087  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2) {
088    return construct(Ordering.natural(), 2, e1, e2);
089  }
090
091  /**
092   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
093   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
094   * one specified is included.
095   *
096   * @throws NullPointerException if any element is null
097   */
098  @SuppressWarnings("unchecked")
099  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2, E e3) {
100    return construct(Ordering.natural(), 3, e1, e2, e3);
101  }
102
103  /**
104   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
105   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
106   * one specified is included.
107   *
108   * @throws NullPointerException if any element is null
109   */
110  @SuppressWarnings("unchecked")
111  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4) {
112    return construct(Ordering.natural(), 4, e1, e2, e3, e4);
113  }
114
115  /**
116   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
117   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
118   * one specified is included.
119   *
120   * @throws NullPointerException if any element is null
121   */
122  @SuppressWarnings("unchecked")
123  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
124      E e1, E e2, E e3, E e4, E e5) {
125    return construct(Ordering.natural(), 5, e1, e2, e3, e4, e5);
126  }
127
128  /**
129   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
130   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
131   * one specified is included.
132   *
133   * @throws NullPointerException if any element is null
134   * @since 3.0 (source-compatible since 2.0)
135   */
136  @SuppressWarnings("unchecked")
137  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
138      E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
139    Comparable[] contents = new Comparable[6 + remaining.length];
140    contents[0] = e1;
141    contents[1] = e2;
142    contents[2] = e3;
143    contents[3] = e4;
144    contents[4] = e5;
145    contents[5] = e6;
146    System.arraycopy(remaining, 0, contents, 6, remaining.length);
147    return construct(Ordering.natural(), contents.length, (E[]) contents);
148  }
149
150  // TODO(kevinb): Consider factory methods that reject duplicates
151
152  /**
153   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
154   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
155   * one specified is included.
156   *
157   * @throws NullPointerException if any of {@code elements} is null
158   * @since 3.0
159   */
160  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(E[] elements) {
161    return construct(Ordering.natural(), elements.length, elements.clone());
162  }
163
164  /**
165   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
166   * When multiple elements are equivalent according to {@code compareTo()}, only the first one
167   * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator,
168   * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once.
169   *
170   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)}
171   * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s},
172   * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>}
173   * containing one element (the given set itself).
174   *
175   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
176   * safe to do so. The exact circumstances under which a copy will or will not be performed are
177   * undocumented and subject to change.
178   *
179   * <p>This method is not type-safe, as it may be called on elements that are not mutually
180   * comparable.
181   *
182   * @throws ClassCastException if the elements are not mutually comparable
183   * @throws NullPointerException if any of {@code elements} is null
184   */
185  public static <E> ImmutableSortedSet<E> copyOf(Iterable<? extends E> elements) {
186    // Hack around E not being a subtype of Comparable.
187    // Unsafe, see ImmutableSortedSetFauxverideShim.
188    @SuppressWarnings("unchecked")
189    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
190    return copyOf(naturalOrder, elements);
191  }
192
193  /**
194   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
195   * When multiple elements are equivalent according to {@code compareTo()}, only the first one
196   * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator,
197   * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once.
198   *
199   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)}
200   * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s},
201   * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>}
202   * containing one element (the given set itself).
203   *
204   * <p><b>Note:</b> Despite what the method name suggests, if {@code elements} is an {@code
205   * ImmutableSortedSet}, it may be returned instead of a copy.
206   *
207   * <p>This method is not type-safe, as it may be called on elements that are not mutually
208   * comparable.
209   *
210   * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent
211   * collection that is currently being modified by another thread.
212   *
213   * @throws ClassCastException if the elements are not mutually comparable
214   * @throws NullPointerException if any of {@code elements} is null
215   * @since 7.0 (source-compatible since 2.0)
216   */
217  public static <E> ImmutableSortedSet<E> copyOf(Collection<? 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 their natural ordering.
227   * When multiple elements are equivalent according to {@code compareTo()}, only the first one
228   * specified is included.
229   *
230   * <p>This method is not type-safe, as it may be called on elements that are not mutually
231   * comparable.
232   *
233   * @throws ClassCastException if the elements are not mutually comparable
234   * @throws NullPointerException if any of {@code elements} is null
235   */
236  public static <E> ImmutableSortedSet<E> copyOf(Iterator<? extends E> elements) {
237    // Hack around E not being a subtype of Comparable.
238    // Unsafe, see ImmutableSortedSetFauxverideShim.
239    @SuppressWarnings("unchecked")
240    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
241    return copyOf(naturalOrder, elements);
242  }
243
244  /**
245   * Returns an immutable sorted set containing the given elements sorted by the given {@code
246   * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the
247   * first one specified is included.
248   *
249   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
250   */
251  public static <E> ImmutableSortedSet<E> copyOf(
252      Comparator<? super E> comparator, Iterator<? extends E> elements) {
253    return new Builder<E>(comparator).addAll(elements).build();
254  }
255
256  /**
257   * Returns an immutable sorted set containing the given elements sorted by the given {@code
258   * Comparator}. When multiple elements are equivalent according to {@code compare()}, only the
259   * first one specified is included. This method iterates over {@code elements} at most once.
260   *
261   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
262   * safe to do so. The exact circumstances under which a copy will or will not be performed are
263   * undocumented and subject to change.
264   *
265   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
266   */
267  public static <E> ImmutableSortedSet<E> copyOf(
268      Comparator<? super E> comparator, Iterable<? extends E> elements) {
269    checkNotNull(comparator);
270    boolean hasSameComparator = SortedIterables.hasSameComparator(comparator, elements);
271
272    if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
273      @SuppressWarnings("unchecked")
274      ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
275      if (!original.isPartialView()) {
276        return original;
277      }
278    }
279    @SuppressWarnings("unchecked") // elements only contains E's; it's safe.
280    E[] array = (E[]) Iterables.toArray(elements);
281    return construct(comparator, array.length, array);
282  }
283
284  /**
285   * Returns an immutable sorted set containing the given elements sorted by the given {@code
286   * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the
287   * first one specified is included.
288   *
289   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
290   * safe to do so. The exact circumstances under which a copy will or will not be performed are
291   * undocumented and subject to change.
292   *
293   * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent
294   * collection that is currently being modified by another thread.
295   *
296   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
297   * @since 7.0 (source-compatible since 2.0)
298   */
299  public static <E> ImmutableSortedSet<E> copyOf(
300      Comparator<? super E> comparator, Collection<? extends E> elements) {
301    return copyOf(comparator, (Iterable<? extends E>) elements);
302  }
303
304  /**
305   * Returns an immutable sorted set containing the elements of a sorted set, sorted by the same
306   * {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which always uses the
307   * natural ordering of the elements.
308   *
309   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
310   * safe to do so. The exact circumstances under which a copy will or will not be performed are
311   * undocumented and subject to change.
312   *
313   * <p>This method is safe to use even when {@code sortedSet} is a synchronized or concurrent
314   * collection that is currently being modified by another thread.
315   *
316   * @throws NullPointerException if {@code sortedSet} or any of its elements is null
317   */
318  public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
319    Comparator<? super E> comparator = SortedIterables.comparator(sortedSet);
320    ImmutableList<E> list = ImmutableList.copyOf(sortedSet);
321    if (list.isEmpty()) {
322      return emptySet(comparator);
323    } else {
324      return new RegularImmutableSortedSet<E>(list, comparator);
325    }
326  }
327
328  /**
329   * Constructs an {@code ImmutableSortedSet} from the first {@code n} elements of {@code contents}.
330   * If {@code k} is the size of the returned {@code ImmutableSortedSet}, then the sorted unique
331   * elements are in the first {@code k} positions of {@code contents}, and {@code contents[i] ==
332   * null} for {@code k <= i < n}.
333   *
334   * <p>This method takes ownership of {@code contents}; do not modify {@code contents} after this
335   * returns.
336   *
337   * @throws NullPointerException if any of the first {@code n} elements of {@code contents} is null
338   */
339  static <E> ImmutableSortedSet<E> construct(
340      Comparator<? super E> comparator, int n, E... contents) {
341    if (n == 0) {
342      return emptySet(comparator);
343    }
344    checkElementsNotNull(contents, n);
345    Arrays.sort(contents, 0, n, comparator);
346    int uniques = 1;
347    for (int i = 1; i < n; i++) {
348      E cur = contents[i];
349      E prev = contents[uniques - 1];
350      if (comparator.compare(cur, prev) != 0) {
351        contents[uniques++] = cur;
352      }
353    }
354    Arrays.fill(contents, uniques, n, null);
355    if (uniques < contents.length / 2) {
356      // Deduplication eliminated many of the elements.  We don't want to retain an arbitrarily
357      // large array relative to the number of elements, so we cap the ratio.
358      contents = Arrays.copyOf(contents, uniques);
359    }
360    return new RegularImmutableSortedSet<E>(
361        ImmutableList.<E>asImmutableList(contents, uniques), comparator);
362  }
363
364  /**
365   * Returns a builder that creates immutable sorted sets with an explicit comparator. If the
366   * comparator has a more general type than the set being generated, such as creating a {@code
367   * SortedSet<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} constructor
368   * instead.
369   *
370   * @throws NullPointerException if {@code comparator} is null
371   */
372  public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
373    return new Builder<E>(comparator);
374  }
375
376  /**
377   * Returns a builder that creates immutable sorted sets whose elements are ordered by the reverse
378   * of their natural ordering.
379   */
380  public static <E extends Comparable<?>> Builder<E> reverseOrder() {
381    return new Builder<E>(Collections.reverseOrder());
382  }
383
384  /**
385   * Returns a builder that creates immutable sorted sets whose elements are ordered by their
386   * natural ordering. The sorted sets use {@link Ordering#natural()} as the comparator. This method
387   * provides more type-safety than {@link #builder}, as it can be called only for classes that
388   * implement {@link Comparable}.
389   */
390  public static <E extends Comparable<?>> Builder<E> naturalOrder() {
391    return new Builder<E>(Ordering.natural());
392  }
393
394  /**
395   * A builder for creating immutable sorted set instances, especially {@code public static final}
396   * sets ("constant sets"), with a given comparator. Example:
397   *
398   * <pre>{@code
399   * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
400   *     new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
401   *         .addAll(SINGLE_DIGIT_PRIMES)
402   *         .add(42)
403   *         .build();
404   * }</pre>
405   *
406   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
407   * multiple sets in series. Each set is a superset of the set created before it.
408   *
409   * @since 2.0
410   */
411  public static final class Builder<E> extends ImmutableSet.Builder<E> {
412    private final Comparator<? super E> comparator;
413
414    /**
415     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
416     * ImmutableSortedSet#orderedBy}.
417     */
418    public Builder(Comparator<? super E> comparator) {
419      this.comparator = checkNotNull(comparator);
420    }
421
422    /**
423     * Adds {@code element} to the {@code ImmutableSortedSet}. If the {@code ImmutableSortedSet}
424     * already contains {@code element}, then {@code add} has no effect. (only the previously added
425     * element is retained).
426     *
427     * @param element the element to add
428     * @return this {@code Builder} object
429     * @throws NullPointerException if {@code element} is null
430     */
431    @CanIgnoreReturnValue
432    @Override
433    public Builder<E> add(E element) {
434      super.add(element);
435      return this;
436    }
437
438    /**
439     * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
440     * elements (only the first duplicate element is added).
441     *
442     * @param elements the elements to add
443     * @return this {@code Builder} object
444     * @throws NullPointerException if {@code elements} contains a null element
445     */
446    @CanIgnoreReturnValue
447    @Override
448    public Builder<E> add(E... elements) {
449      super.add(elements);
450      return this;
451    }
452
453    /**
454     * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
455     * elements (only the first duplicate element is added).
456     *
457     * @param elements the elements to add to the {@code ImmutableSortedSet}
458     * @return this {@code Builder} object
459     * @throws NullPointerException if {@code elements} contains a null element
460     */
461    @CanIgnoreReturnValue
462    @Override
463    public Builder<E> addAll(Iterable<? extends E> elements) {
464      super.addAll(elements);
465      return this;
466    }
467
468    /**
469     * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
470     * elements (only the first duplicate element is added).
471     *
472     * @param elements the elements to add to the {@code ImmutableSortedSet}
473     * @return this {@code Builder} object
474     * @throws NullPointerException if {@code elements} contains a null element
475     */
476    @CanIgnoreReturnValue
477    @Override
478    public Builder<E> addAll(Iterator<? extends E> elements) {
479      super.addAll(elements);
480      return this;
481    }
482
483    /**
484     * Returns a newly-created {@code ImmutableSortedSet} based on the contents of the {@code
485     * Builder} and its comparator.
486     */
487    @Override
488    public ImmutableSortedSet<E> build() {
489      @SuppressWarnings("unchecked") // we're careful to put only E's in here
490      E[] contentsArray = (E[]) contents;
491      ImmutableSortedSet<E> result = construct(comparator, size, contentsArray);
492      this.size = result.size(); // we eliminated duplicates in-place in contentsArray
493      this.forceCopy = true;
494      return result;
495    }
496  }
497
498  int unsafeCompare(Object a, Object b) {
499    return unsafeCompare(comparator, a, b);
500  }
501
502  static int unsafeCompare(Comparator<?> comparator, Object a, Object b) {
503    // Pretend the comparator can compare anything. If it turns out it can't
504    // compare a and b, we should get a CCE on the subsequent line. Only methods
505    // that are spec'd to throw CCE should call this.
506    @SuppressWarnings("unchecked")
507    Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
508    return unsafeComparator.compare(a, b);
509  }
510
511  final transient Comparator<? super E> comparator;
512
513  ImmutableSortedSet(Comparator<? super E> comparator) {
514    this.comparator = comparator;
515  }
516
517  /**
518   * Returns the comparator that orders the elements, which is {@link Ordering#natural()} when the
519   * natural ordering of the elements is used. Note that its behavior is not consistent with {@link
520   * SortedSet#comparator()}, which returns {@code null} to indicate natural ordering.
521   */
522  @Override
523  public Comparator<? super E> comparator() {
524    return comparator;
525  }
526
527  @Override // needed to unify the iterator() methods in Collection and SortedIterable
528  public abstract UnmodifiableIterator<E> iterator();
529
530  /**
531   * {@inheritDoc}
532   *
533   * <p>This method returns a serializable {@code ImmutableSortedSet}.
534   *
535   * <p>The {@link SortedSet#headSet} documentation states that a subset of a subset throws an
536   * {@link IllegalArgumentException} if passed a {@code toElement} greater than an earlier {@code
537   * toElement}. However, this method doesn't throw an exception in that situation, but instead
538   * keeps the original {@code toElement}.
539   */
540  @Override
541  public ImmutableSortedSet<E> headSet(E toElement) {
542    return headSet(toElement, false);
543  }
544
545  /** @since 12.0 */
546  @GwtIncompatible // NavigableSet
547  @Override
548  public ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) {
549    return headSetImpl(checkNotNull(toElement), inclusive);
550  }
551
552  /**
553   * {@inheritDoc}
554   *
555   * <p>This method returns a serializable {@code ImmutableSortedSet}.
556   *
557   * <p>The {@link SortedSet#subSet} documentation states that a subset of a subset throws an {@link
558   * IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code
559   * fromElement}. However, this method doesn't throw an exception in that situation, but instead
560   * keeps the original {@code fromElement}. Similarly, this method keeps the original {@code
561   * toElement}, instead of throwing an exception, if passed a {@code toElement} greater than an
562   * earlier {@code toElement}.
563   */
564  @Override
565  public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
566    return subSet(fromElement, true, toElement, false);
567  }
568
569  /** @since 12.0 */
570  @GwtIncompatible // NavigableSet
571  @Override
572  public ImmutableSortedSet<E> subSet(
573      E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
574    checkNotNull(fromElement);
575    checkNotNull(toElement);
576    checkArgument(comparator.compare(fromElement, toElement) <= 0);
577    return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
578  }
579
580  /**
581   * {@inheritDoc}
582   *
583   * <p>This method returns a serializable {@code ImmutableSortedSet}.
584   *
585   * <p>The {@link SortedSet#tailSet} documentation states that a subset of a subset throws an
586   * {@link IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code
587   * fromElement}. However, this method doesn't throw an exception in that situation, but instead
588   * keeps the original {@code fromElement}.
589   */
590  @Override
591  public ImmutableSortedSet<E> tailSet(E fromElement) {
592    return tailSet(fromElement, true);
593  }
594
595  /** @since 12.0 */
596  @GwtIncompatible // NavigableSet
597  @Override
598  public ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) {
599    return tailSetImpl(checkNotNull(fromElement), inclusive);
600  }
601
602  /*
603   * These methods perform most headSet, subSet, and tailSet logic, besides
604   * parameter validation.
605   */
606  abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive);
607
608  abstract ImmutableSortedSet<E> subSetImpl(
609      E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
610
611  abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive);
612
613  /** @since 12.0 */
614  @GwtIncompatible // NavigableSet
615  @Override
616  public E lower(E e) {
617    return Iterators.getNext(headSet(e, false).descendingIterator(), null);
618  }
619
620  /** @since 12.0 */
621  @GwtIncompatible // NavigableSet
622  @Override
623  public E floor(E e) {
624    return Iterators.getNext(headSet(e, true).descendingIterator(), null);
625  }
626
627  /** @since 12.0 */
628  @GwtIncompatible // NavigableSet
629  @Override
630  public E ceiling(E e) {
631    return Iterables.getFirst(tailSet(e, true), null);
632  }
633
634  /** @since 12.0 */
635  @GwtIncompatible // NavigableSet
636  @Override
637  public E higher(E e) {
638    return Iterables.getFirst(tailSet(e, false), null);
639  }
640
641  @Override
642  public E first() {
643    return iterator().next();
644  }
645
646  @Override
647  public E last() {
648    return descendingIterator().next();
649  }
650
651  /**
652   * Guaranteed to throw an exception and leave the set unmodified.
653   *
654   * @since 12.0
655   * @throws UnsupportedOperationException always
656   * @deprecated Unsupported operation.
657   */
658  @CanIgnoreReturnValue
659  @Deprecated
660  @GwtIncompatible // NavigableSet
661  @Override
662  public final E pollFirst() {
663    throw new UnsupportedOperationException();
664  }
665
666  /**
667   * Guaranteed to throw an exception and leave the set unmodified.
668   *
669   * @since 12.0
670   * @throws UnsupportedOperationException always
671   * @deprecated Unsupported operation.
672   */
673  @CanIgnoreReturnValue
674  @Deprecated
675  @GwtIncompatible // NavigableSet
676  @Override
677  public final E pollLast() {
678    throw new UnsupportedOperationException();
679  }
680
681  @GwtIncompatible // NavigableSet
682  @LazyInit
683  transient ImmutableSortedSet<E> descendingSet;
684
685  /** @since 12.0 */
686  @GwtIncompatible // NavigableSet
687  @Override
688  public ImmutableSortedSet<E> descendingSet() {
689    // racy single-check idiom
690    ImmutableSortedSet<E> result = descendingSet;
691    if (result == null) {
692      result = descendingSet = createDescendingSet();
693      result.descendingSet = this;
694    }
695    return result;
696  }
697
698  // Most classes should implement this as new DescendingImmutableSortedSet<E>(this),
699  // but we push down that implementation because ProGuard can't eliminate it even when it's always
700  // overridden.
701  @GwtIncompatible // NavigableSet
702  abstract ImmutableSortedSet<E> createDescendingSet();
703
704  /** @since 12.0 */
705  @GwtIncompatible // NavigableSet
706  @Override
707  public abstract UnmodifiableIterator<E> descendingIterator();
708
709  /** Returns the position of an element within the set, or -1 if not present. */
710  abstract int indexOf(@NullableDecl Object target);
711
712  /*
713   * This class is used to serialize all ImmutableSortedSet instances,
714   * regardless of implementation type. It captures their "logical contents"
715   * only. This is necessary to ensure that the existence of a particular
716   * implementation type is an implementation detail.
717   */
718  private static class SerializedForm<E> implements Serializable {
719    final Comparator<? super E> comparator;
720    final Object[] elements;
721
722    public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
723      this.comparator = comparator;
724      this.elements = elements;
725    }
726
727    @SuppressWarnings("unchecked")
728    Object readResolve() {
729      return new Builder<E>(comparator).add((E[]) elements).build();
730    }
731
732    private static final long serialVersionUID = 0;
733  }
734
735  private void readObject(ObjectInputStream unused) throws InvalidObjectException {
736    throw new InvalidObjectException("Use SerializedForm");
737  }
738
739  @Override
740  Object writeReplace() {
741    return new SerializedForm<E>(comparator, toArray());
742  }
743}