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    @CanIgnoreReturnValue
484    @Override
485    Builder<E> combine(ImmutableSet.Builder<E> builder) {
486      super.combine(builder);
487      return this;
488    }
489
490    /**
491     * Returns a newly-created {@code ImmutableSortedSet} based on the contents of the {@code
492     * Builder} and its comparator.
493     */
494    @Override
495    public ImmutableSortedSet<E> build() {
496      @SuppressWarnings("unchecked") // we're careful to put only E's in here
497      E[] contentsArray = (E[]) contents;
498      ImmutableSortedSet<E> result = construct(comparator, size, contentsArray);
499      this.size = result.size(); // we eliminated duplicates in-place in contentsArray
500      this.forceCopy = true;
501      return result;
502    }
503  }
504
505  int unsafeCompare(Object a, Object b) {
506    return unsafeCompare(comparator, a, b);
507  }
508
509  static int unsafeCompare(Comparator<?> comparator, Object a, Object b) {
510    // Pretend the comparator can compare anything. If it turns out it can't
511    // compare a and b, we should get a CCE on the subsequent line. Only methods
512    // that are spec'd to throw CCE should call this.
513    @SuppressWarnings("unchecked")
514    Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
515    return unsafeComparator.compare(a, b);
516  }
517
518  final transient Comparator<? super E> comparator;
519
520  ImmutableSortedSet(Comparator<? super E> comparator) {
521    this.comparator = comparator;
522  }
523
524  /**
525   * Returns the comparator that orders the elements, which is {@link Ordering#natural()} when the
526   * natural ordering of the elements is used. Note that its behavior is not consistent with {@link
527   * SortedSet#comparator()}, which returns {@code null} to indicate natural ordering.
528   */
529  @Override
530  public Comparator<? super E> comparator() {
531    return comparator;
532  }
533
534  @Override // needed to unify the iterator() methods in Collection and SortedIterable
535  public abstract UnmodifiableIterator<E> iterator();
536
537  /**
538   * {@inheritDoc}
539   *
540   * <p>This method returns a serializable {@code ImmutableSortedSet}.
541   *
542   * <p>The {@link SortedSet#headSet} documentation states that a subset of a subset throws an
543   * {@link IllegalArgumentException} if passed a {@code toElement} greater than an earlier {@code
544   * toElement}. However, this method doesn't throw an exception in that situation, but instead
545   * keeps the original {@code toElement}.
546   */
547  @Override
548  public ImmutableSortedSet<E> headSet(E toElement) {
549    return headSet(toElement, false);
550  }
551
552  /** @since 12.0 */
553  @Override
554  public ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) {
555    return headSetImpl(checkNotNull(toElement), inclusive);
556  }
557
558  /**
559   * {@inheritDoc}
560   *
561   * <p>This method returns a serializable {@code ImmutableSortedSet}.
562   *
563   * <p>The {@link SortedSet#subSet} documentation states that a subset of a subset throws an {@link
564   * IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code
565   * fromElement}. However, this method doesn't throw an exception in that situation, but instead
566   * keeps the original {@code fromElement}. Similarly, this method keeps the original {@code
567   * toElement}, instead of throwing an exception, if passed a {@code toElement} greater than an
568   * earlier {@code toElement}.
569   */
570  @Override
571  public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
572    return subSet(fromElement, true, toElement, false);
573  }
574
575  /** @since 12.0 */
576  @GwtIncompatible // NavigableSet
577  @Override
578  public ImmutableSortedSet<E> subSet(
579      E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
580    checkNotNull(fromElement);
581    checkNotNull(toElement);
582    checkArgument(comparator.compare(fromElement, toElement) <= 0);
583    return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
584  }
585
586  /**
587   * {@inheritDoc}
588   *
589   * <p>This method returns a serializable {@code ImmutableSortedSet}.
590   *
591   * <p>The {@link SortedSet#tailSet} documentation states that a subset of a subset throws an
592   * {@link IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code
593   * fromElement}. However, this method doesn't throw an exception in that situation, but instead
594   * keeps the original {@code fromElement}.
595   */
596  @Override
597  public ImmutableSortedSet<E> tailSet(E fromElement) {
598    return tailSet(fromElement, true);
599  }
600
601  /** @since 12.0 */
602  @Override
603  public ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) {
604    return tailSetImpl(checkNotNull(fromElement), inclusive);
605  }
606
607  /*
608   * These methods perform most headSet, subSet, and tailSet logic, besides
609   * parameter validation.
610   */
611  abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive);
612
613  abstract ImmutableSortedSet<E> subSetImpl(
614      E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
615
616  abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive);
617
618  /** @since 12.0 */
619  @GwtIncompatible // NavigableSet
620  @Override
621  public E lower(E e) {
622    return Iterators.getNext(headSet(e, false).descendingIterator(), null);
623  }
624
625  /** @since 12.0 */
626  @Override
627  public E floor(E e) {
628    return Iterators.getNext(headSet(e, true).descendingIterator(), null);
629  }
630
631  /** @since 12.0 */
632  @Override
633  public E ceiling(E e) {
634    return Iterables.getFirst(tailSet(e, true), null);
635  }
636
637  /** @since 12.0 */
638  @GwtIncompatible // NavigableSet
639  @Override
640  public E higher(E e) {
641    return Iterables.getFirst(tailSet(e, false), null);
642  }
643
644  @Override
645  public E first() {
646    return iterator().next();
647  }
648
649  @Override
650  public E last() {
651    return descendingIterator().next();
652  }
653
654  /**
655   * Guaranteed to throw an exception and leave the set unmodified.
656   *
657   * @since 12.0
658   * @throws UnsupportedOperationException always
659   * @deprecated Unsupported operation.
660   */
661  @CanIgnoreReturnValue
662  @Deprecated
663  @GwtIncompatible // NavigableSet
664  @Override
665  public final E pollFirst() {
666    throw new UnsupportedOperationException();
667  }
668
669  /**
670   * Guaranteed to throw an exception and leave the set unmodified.
671   *
672   * @since 12.0
673   * @throws UnsupportedOperationException always
674   * @deprecated Unsupported operation.
675   */
676  @CanIgnoreReturnValue
677  @Deprecated
678  @GwtIncompatible // NavigableSet
679  @Override
680  public final E pollLast() {
681    throw new UnsupportedOperationException();
682  }
683
684  @GwtIncompatible // NavigableSet
685  @LazyInit
686  transient ImmutableSortedSet<E> descendingSet;
687
688  /** @since 12.0 */
689  @GwtIncompatible // NavigableSet
690  @Override
691  public ImmutableSortedSet<E> descendingSet() {
692    // racy single-check idiom
693    ImmutableSortedSet<E> result = descendingSet;
694    if (result == null) {
695      result = descendingSet = createDescendingSet();
696      result.descendingSet = this;
697    }
698    return result;
699  }
700
701  // Most classes should implement this as new DescendingImmutableSortedSet<E>(this),
702  // but we push down that implementation because ProGuard can't eliminate it even when it's always
703  // overridden.
704  @GwtIncompatible // NavigableSet
705  abstract ImmutableSortedSet<E> createDescendingSet();
706
707  /** @since 12.0 */
708  @GwtIncompatible // NavigableSet
709  @Override
710  public abstract UnmodifiableIterator<E> descendingIterator();
711
712  /** Returns the position of an element within the set, or -1 if not present. */
713  abstract int indexOf(@NullableDecl Object target);
714
715  /*
716   * This class is used to serialize all ImmutableSortedSet instances,
717   * regardless of implementation type. It captures their "logical contents"
718   * only. This is necessary to ensure that the existence of a particular
719   * implementation type is an implementation detail.
720   */
721  private static class SerializedForm<E> implements Serializable {
722    final Comparator<? super E> comparator;
723    final Object[] elements;
724
725    public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
726      this.comparator = comparator;
727      this.elements = elements;
728    }
729
730    @SuppressWarnings("unchecked")
731    Object readResolve() {
732      return new Builder<E>(comparator).add((E[]) elements).build();
733    }
734
735    private static final long serialVersionUID = 0;
736  }
737
738  private void readObject(ObjectInputStream unused) throws InvalidObjectException {
739    throw new InvalidObjectException("Use SerializedForm");
740  }
741
742  @Override
743  Object writeReplace() {
744    return new SerializedForm<E>(comparator, toArray());
745  }
746}