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