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