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