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.common.annotations.J2ktIncompatible;
026import com.google.errorprone.annotations.CanIgnoreReturnValue;
027import com.google.errorprone.annotations.DoNotCall;
028import com.google.errorprone.annotations.concurrent.LazyInit;
029import java.io.InvalidObjectException;
030import java.io.ObjectInputStream;
031import java.io.Serializable;
032import java.util.Arrays;
033import java.util.Collection;
034import java.util.Collections;
035import java.util.Comparator;
036import java.util.Iterator;
037import java.util.NavigableSet;
038import java.util.SortedSet;
039import java.util.Spliterator;
040import java.util.Spliterators;
041import java.util.function.Consumer;
042import java.util.stream.Collector;
043import javax.annotation.CheckForNull;
044import org.checkerframework.checker.nullness.qual.Nullable;
045
046/**
047 * A {@link NavigableSet} whose contents will never change, with many other important properties
048 * detailed at {@link ImmutableCollection}.
049 *
050 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
051 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
052 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
053 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting
054 * collection will not correctly obey its specification.
055 *
056 * <p>See the Guava User Guide article on <a href=
057 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>.
058 *
059 * @author Jared Levy
060 * @author Louis Wasserman
061 * @since 2.0 (implements {@code NavigableSet} since 12.0)
062 */
063// TODO(benyu): benchmark and optimize all creation paths, which are a mess now
064@GwtCompatible(serializable = true, emulated = true)
065@SuppressWarnings("serial") // we're overriding default serialization
066@ElementTypesAreNonnullByDefault
067public abstract class ImmutableSortedSet<E> extends ImmutableSet.CachingAsList<E>
068    implements NavigableSet<E>, SortedIterable<E> {
069  static final int SPLITERATOR_CHARACTERISTICS =
070      ImmutableSet.SPLITERATOR_CHARACTERISTICS | Spliterator.SORTED;
071
072  /**
073   * Returns a {@code Collector} that accumulates the input elements into a new {@code
074   * ImmutableSortedSet}, ordered by the specified comparator.
075   *
076   * <p>If the elements contain duplicates (according to the comparator), only the first duplicate
077   * in encounter order will appear in the result.
078   *
079   * @since 21.0
080   */
081  public static <E> Collector<E, ?, ImmutableSortedSet<E>> toImmutableSortedSet(
082      Comparator<? super E> comparator) {
083    return CollectCollectors.toImmutableSortedSet(comparator);
084  }
085
086  static <E> RegularImmutableSortedSet<E> emptySet(Comparator<? super E> comparator) {
087    if (Ordering.natural().equals(comparator)) {
088      @SuppressWarnings("unchecked") // The natural-ordered empty set supports all types.
089      RegularImmutableSortedSet<E> result =
090          (RegularImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET;
091      return result;
092    } else {
093      return new RegularImmutableSortedSet<>(ImmutableList.of(), comparator);
094    }
095  }
096
097  /**
098   * Returns the empty immutable sorted set.
099   *
100   * <p><b>Performance note:</b> the instance returned is a singleton.
101   */
102  @SuppressWarnings("unchecked") // The natural-ordered empty set supports all types.
103  public static <E> ImmutableSortedSet<E> of() {
104    return (ImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET;
105  }
106
107  /** Returns an immutable sorted set containing a single element. */
108  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1) {
109    return new RegularImmutableSortedSet<>(ImmutableList.of(e1), Ordering.natural());
110  }
111
112  /**
113   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
114   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
115   * one specified is included.
116   *
117   * @throws NullPointerException if any element is null
118   */
119  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2) {
120    return construct(Ordering.natural(), 2, e1, e2);
121  }
122
123  /**
124   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
125   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
126   * one specified is included.
127   *
128   * @throws NullPointerException if any element is null
129   */
130  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2, E e3) {
131    return construct(Ordering.natural(), 3, e1, e2, e3);
132  }
133
134  /**
135   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
136   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
137   * one specified is included.
138   *
139   * @throws NullPointerException if any element is null
140   */
141  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4) {
142    return construct(Ordering.natural(), 4, e1, e2, e3, e4);
143  }
144
145  /**
146   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
147   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
148   * one specified is included.
149   *
150   * @throws NullPointerException if any element is null
151   */
152  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
153      E e1, E e2, E e3, E e4, E e5) {
154    return construct(Ordering.natural(), 5, e1, e2, e3, e4, e5);
155  }
156
157  /**
158   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
159   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
160   * one specified is included.
161   *
162   * @throws NullPointerException if any element is null
163   * @since 3.0 (source-compatible since 2.0)
164   */
165  @SuppressWarnings("unchecked")
166  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
167      E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
168    Comparable<?>[] contents = new Comparable<?>[6 + remaining.length];
169    contents[0] = e1;
170    contents[1] = e2;
171    contents[2] = e3;
172    contents[3] = e4;
173    contents[4] = e5;
174    contents[5] = e6;
175    System.arraycopy(remaining, 0, contents, 6, remaining.length);
176    return construct(Ordering.natural(), contents.length, (E[]) contents);
177  }
178
179  // TODO(kevinb): Consider factory methods that reject duplicates
180
181  /**
182   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
183   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
184   * one specified is included.
185   *
186   * @throws NullPointerException if any of {@code elements} is null
187   * @since 3.0
188   */
189  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(E[] elements) {
190    return construct(Ordering.natural(), elements.length, elements.clone());
191  }
192
193  /**
194   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
195   * When multiple elements are equivalent according to {@code compareTo()}, only the first one
196   * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator,
197   * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once.
198   *
199   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)}
200   * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s},
201   * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>}
202   * containing one element (the given set itself).
203   *
204   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
205   * safe to do so. The exact circumstances under which a copy will or will not be performed are
206   * undocumented and subject to change.
207   *
208   * <p>This method is not type-safe, as it may be called on elements that are not mutually
209   * comparable.
210   *
211   * @throws ClassCastException if the elements are not mutually comparable
212   * @throws NullPointerException if any of {@code elements} is null
213   */
214  public static <E> ImmutableSortedSet<E> copyOf(Iterable<? extends E> elements) {
215    // Hack around E not being a subtype of Comparable.
216    // Unsafe, see ImmutableSortedSetFauxverideShim.
217    @SuppressWarnings("unchecked")
218    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable<?>>natural();
219    return copyOf(naturalOrder, elements);
220  }
221
222  /**
223   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
224   * When multiple elements are equivalent according to {@code compareTo()}, only the first one
225   * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator,
226   * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once.
227   *
228   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)}
229   * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s},
230   * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>}
231   * containing one element (the given set itself).
232   *
233   * <p><b>Note:</b> Despite what the method name suggests, if {@code elements} is an {@code
234   * ImmutableSortedSet}, it may be returned instead of a copy.
235   *
236   * <p>This method is not type-safe, as it may be called on elements that are not mutually
237   * comparable.
238   *
239   * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent
240   * collection that is currently being modified by another thread.
241   *
242   * @throws ClassCastException if the elements are not mutually comparable
243   * @throws NullPointerException if any of {@code elements} is null
244   * @since 7.0 (source-compatible since 2.0)
245   */
246  public static <E> ImmutableSortedSet<E> copyOf(Collection<? extends E> elements) {
247    // Hack around E not being a subtype of Comparable.
248    // Unsafe, see ImmutableSortedSetFauxverideShim.
249    @SuppressWarnings("unchecked")
250    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable<?>>natural();
251    return copyOf(naturalOrder, elements);
252  }
253
254  /**
255   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
256   * When multiple elements are equivalent according to {@code compareTo()}, only the first one
257   * specified is included.
258   *
259   * <p>This method is not type-safe, as it may be called on elements that are not mutually
260   * comparable.
261   *
262   * @throws ClassCastException if the elements are not mutually comparable
263   * @throws NullPointerException if any of {@code elements} is null
264   */
265  public static <E> ImmutableSortedSet<E> copyOf(Iterator<? extends E> elements) {
266    // Hack around E not being a subtype of Comparable.
267    // Unsafe, see ImmutableSortedSetFauxverideShim.
268    @SuppressWarnings("unchecked")
269    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable<?>>natural();
270    return copyOf(naturalOrder, elements);
271  }
272
273  /**
274   * Returns an immutable sorted set containing the given elements sorted by the given {@code
275   * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the
276   * first one specified is included.
277   *
278   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
279   */
280  public static <E> ImmutableSortedSet<E> copyOf(
281      Comparator<? super E> comparator, Iterator<? extends E> elements) {
282    return new Builder<E>(comparator).addAll(elements).build();
283  }
284
285  /**
286   * Returns an immutable sorted set containing the given elements sorted by the given {@code
287   * Comparator}. When multiple elements are equivalent according to {@code compare()}, only the
288   * first one specified is included. This method iterates over {@code elements} at most once.
289   *
290   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
291   * safe to do so. The exact circumstances under which a copy will or will not be performed are
292   * undocumented and subject to change.
293   *
294   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
295   */
296  public static <E> ImmutableSortedSet<E> copyOf(
297      Comparator<? super E> comparator, Iterable<? extends E> elements) {
298    checkNotNull(comparator);
299    boolean hasSameComparator = SortedIterables.hasSameComparator(comparator, elements);
300
301    if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
302      @SuppressWarnings("unchecked")
303      ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
304      if (!original.isPartialView()) {
305        return original;
306      }
307    }
308    @SuppressWarnings("unchecked") // elements only contains E's; it's safe.
309    E[] array = (E[]) Iterables.toArray(elements);
310    return construct(comparator, array.length, array);
311  }
312
313  /**
314   * Returns an immutable sorted set containing the given elements sorted by the given {@code
315   * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the
316   * first one specified is included.
317   *
318   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
319   * safe to do so. The exact circumstances under which a copy will or will not be performed are
320   * undocumented and subject to change.
321   *
322   * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent
323   * collection that is currently being modified by another thread.
324   *
325   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
326   * @since 7.0 (source-compatible since 2.0)
327   */
328  public static <E> ImmutableSortedSet<E> copyOf(
329      Comparator<? super E> comparator, Collection<? extends E> elements) {
330    return copyOf(comparator, (Iterable<? extends E>) elements);
331  }
332
333  /**
334   * Returns an immutable sorted set containing the elements of a sorted set, sorted by the same
335   * {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which always uses the
336   * natural ordering of the elements.
337   *
338   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
339   * safe to do so. The exact circumstances under which a copy will or will not be performed are
340   * undocumented and subject to change.
341   *
342   * <p>This method is safe to use even when {@code sortedSet} is a synchronized or concurrent
343   * collection that is currently being modified by another thread.
344   *
345   * @throws NullPointerException if {@code sortedSet} or any of its elements is null
346   */
347  public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
348    Comparator<? super E> comparator = SortedIterables.comparator(sortedSet);
349    ImmutableList<E> list = ImmutableList.copyOf(sortedSet);
350    if (list.isEmpty()) {
351      return emptySet(comparator);
352    } else {
353      return new RegularImmutableSortedSet<>(list, comparator);
354    }
355  }
356
357  /**
358   * Constructs an {@code ImmutableSortedSet} from the first {@code n} elements of {@code contents}.
359   * If {@code k} is the size of the returned {@code ImmutableSortedSet}, then the sorted unique
360   * elements are in the first {@code k} positions of {@code contents}, and {@code contents[i] ==
361   * null} for {@code k <= i < n}.
362   *
363   * <p>This method takes ownership of {@code contents}; do not modify {@code contents} after this
364   * returns.
365   *
366   * @throws NullPointerException if any of the first {@code n} elements of {@code contents} is null
367   */
368  static <E> ImmutableSortedSet<E> construct(
369      Comparator<? super E> comparator, int n, E... contents) {
370    if (n == 0) {
371      return emptySet(comparator);
372    }
373    checkElementsNotNull(contents, n);
374    Arrays.sort(contents, 0, n, comparator);
375    int uniques = 1;
376    for (int i = 1; i < n; i++) {
377      E cur = contents[i];
378      E prev = contents[uniques - 1];
379      if (comparator.compare(cur, prev) != 0) {
380        contents[uniques++] = cur;
381      }
382    }
383    Arrays.fill(contents, uniques, n, null);
384    return new RegularImmutableSortedSet<>(
385        ImmutableList.<E>asImmutableList(contents, uniques), comparator);
386  }
387
388  /**
389   * Returns a builder that creates immutable sorted sets with an explicit comparator. If the
390   * comparator has a more general type than the set being generated, such as creating a {@code
391   * SortedSet<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} constructor
392   * instead.
393   *
394   * @throws NullPointerException if {@code comparator} is null
395   */
396  public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
397    return new Builder<>(comparator);
398  }
399
400  /**
401   * Returns a builder that creates immutable sorted sets whose elements are ordered by the reverse
402   * of their natural ordering.
403   */
404  public static <E extends Comparable<?>> Builder<E> reverseOrder() {
405    return new Builder<>(Collections.reverseOrder());
406  }
407
408  /**
409   * Returns a builder that creates immutable sorted sets whose elements are ordered by their
410   * natural ordering. The sorted sets use {@link Ordering#natural()} as the comparator. This method
411   * provides more type-safety than {@link #builder}, as it can be called only for classes that
412   * implement {@link Comparable}.
413   */
414  public static <E extends Comparable<?>> Builder<E> naturalOrder() {
415    return new Builder<>(Ordering.natural());
416  }
417
418  /**
419   * A builder for creating immutable sorted set instances, especially {@code public static final}
420   * sets ("constant sets"), with a given comparator. Example:
421   *
422   * <pre>{@code
423   * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
424   *     new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
425   *         .addAll(SINGLE_DIGIT_PRIMES)
426   *         .add(42)
427   *         .build();
428   * }</pre>
429   *
430   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
431   * multiple sets in series. Each set is a superset of the set created before it.
432   *
433   * @since 2.0
434   */
435  public static final class Builder<E> extends ImmutableSet.Builder<E> {
436    private final Comparator<? super E> comparator;
437    private E[] elements;
438    private int n;
439
440    /**
441     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
442     * ImmutableSortedSet#orderedBy}.
443     */
444    /*
445     * TODO(cpovirk): use Object[] instead of E[] in the mainline? (The backport is different and
446     * doesn't need this suppression, but we keep it to minimize diffs.) Generally be more clear
447     * about when we have an Object[] vs. a Comparable[] or other array type in internalArray? If we
448     * used Object[], we might be able to optimize toArray() to use clone() sometimes. (See
449     * cl/592273615 and cl/592273683.)
450     */
451    public Builder(Comparator<? super E> comparator) {
452      this(comparator, ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY);
453    }
454
455    /** Creates a new builder with an expected size. */
456    @SuppressWarnings("unchecked")
457    Builder(Comparator<? super E> comparator, int expectedSize) {
458      super(true); // don't construct guts of hash-based set builder
459      this.comparator = checkNotNull(comparator);
460      this.elements = (E[]) new Object[expectedSize];
461      this.n = 0;
462    }
463
464    @Override
465    void copy() {
466      elements = Arrays.copyOf(elements, elements.length);
467    }
468
469    private void sortAndDedup() {
470      if (n == 0) {
471        return;
472      }
473      Arrays.sort(elements, 0, n, comparator);
474      int unique = 1;
475      for (int i = 1; i < n; i++) {
476        int cmp = comparator.compare(elements[unique - 1], elements[i]);
477        if (cmp < 0) {
478          elements[unique++] = elements[i];
479        } else if (cmp > 0) {
480          throw new AssertionError(
481              "Comparator " + comparator + " compare method violates its contract");
482        }
483      }
484      Arrays.fill(elements, unique, n, null);
485      n = unique;
486    }
487
488    /**
489     * Adds {@code element} to the {@code ImmutableSortedSet}. If the {@code ImmutableSortedSet}
490     * already contains {@code element}, then {@code add} has no effect. (only the previously added
491     * element is retained).
492     *
493     * @param element the element to add
494     * @return this {@code Builder} object
495     * @throws NullPointerException if {@code element} is null
496     */
497    @CanIgnoreReturnValue
498    @Override
499    public Builder<E> add(E element) {
500      checkNotNull(element);
501      copyIfNecessary();
502      if (n == elements.length) {
503        sortAndDedup();
504        /**
505         * sortAndDedup may have made enough room for this element, but that's not necessarily good
506         * enough. Consider, for example, the case where we have a buffer of size (n+1), add n
507         * distinct elements, and add the last element over again many times over. We don't want a
508         * situation where we re-sort the entire buffer every time the last element is re-added.
509         *
510         * <p>The solution is to ensure there are O(n) spaces left over in the buffer after
511         * sortAndDedup -- that is, at least c*n for some constant c > 0. Ensuring the buffer size
512         * is at least expandedCapacity(n, n + 1) satisfies this property.
513         */
514        int newLength = ImmutableCollection.Builder.expandedCapacity(n, n + 1);
515        if (newLength > elements.length) {
516          elements = Arrays.copyOf(elements, newLength);
517        }
518      }
519      elements[n++] = element;
520      return this;
521    }
522
523    /**
524     * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
525     * elements (only the first duplicate element is added).
526     *
527     * @param elements the elements to add
528     * @return this {@code Builder} object
529     * @throws NullPointerException if {@code elements} contains a null element
530     */
531    @CanIgnoreReturnValue
532    @Override
533    public Builder<E> add(E... elements) {
534      checkElementsNotNull(elements);
535      for (E e : elements) {
536        add(e);
537      }
538      return this;
539    }
540
541    /**
542     * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
543     * elements (only the first duplicate element is added).
544     *
545     * @param elements the elements to add to the {@code ImmutableSortedSet}
546     * @return this {@code Builder} object
547     * @throws NullPointerException if {@code elements} contains a null element
548     */
549    @CanIgnoreReturnValue
550    @Override
551    public Builder<E> addAll(Iterable<? extends E> elements) {
552      super.addAll(elements);
553      return this;
554    }
555
556    /**
557     * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
558     * elements (only the first duplicate element is added).
559     *
560     * @param elements the elements to add to the {@code ImmutableSortedSet}
561     * @return this {@code Builder} object
562     * @throws NullPointerException if {@code elements} contains a null element
563     */
564    @CanIgnoreReturnValue
565    @Override
566    public Builder<E> addAll(Iterator<? extends E> elements) {
567      super.addAll(elements);
568      return this;
569    }
570
571    @CanIgnoreReturnValue
572    @Override
573    Builder<E> combine(ImmutableSet.Builder<E> builder) {
574      copyIfNecessary();
575      Builder<E> other = (Builder<E>) builder;
576      for (int i = 0; i < other.n; i++) {
577        add(other.elements[i]);
578      }
579      return this;
580    }
581
582    /**
583     * Returns a newly-created {@code ImmutableSortedSet} based on the contents of the {@code
584     * Builder} and its comparator.
585     */
586    @Override
587    public ImmutableSortedSet<E> build() {
588      sortAndDedup();
589      if (n == 0) {
590        return emptySet(comparator);
591      } else {
592        forceCopy = true;
593        return new RegularImmutableSortedSet<>(
594            ImmutableList.asImmutableList(elements, n), comparator);
595      }
596    }
597  }
598
599  int unsafeCompare(Object a, @CheckForNull Object b) {
600    return unsafeCompare(comparator, a, b);
601  }
602
603  static int unsafeCompare(Comparator<?> comparator, Object a, @CheckForNull Object b) {
604    // Pretend the comparator can compare anything. If it turns out it can't
605    // compare a and b, we should get a CCE or NPE on the subsequent line. Only methods
606    // that are spec'd to throw CCE and NPE should call this.
607    @SuppressWarnings({"unchecked", "nullness"})
608    Comparator<@Nullable Object> unsafeComparator = (Comparator<@Nullable Object>) comparator;
609    return unsafeComparator.compare(a, b);
610  }
611
612  final transient Comparator<? super E> comparator;
613
614  ImmutableSortedSet(Comparator<? super E> comparator) {
615    this.comparator = comparator;
616  }
617
618  /**
619   * Returns the comparator that orders the elements, which is {@link Ordering#natural()} when the
620   * natural ordering of the elements is used. Note that its behavior is not consistent with {@link
621   * SortedSet#comparator()}, which returns {@code null} to indicate natural ordering.
622   */
623  @Override
624  public Comparator<? super E> comparator() {
625    return comparator;
626  }
627
628  @Override // needed to unify the iterator() methods in Collection and SortedIterable
629  public abstract UnmodifiableIterator<E> iterator();
630
631  /**
632   * {@inheritDoc}
633   *
634   * <p>This method returns a serializable {@code ImmutableSortedSet}.
635   *
636   * <p>The {@link SortedSet#headSet} documentation states that a subset of a subset throws an
637   * {@link IllegalArgumentException} if passed a {@code toElement} greater than an earlier {@code
638   * toElement}. However, this method doesn't throw an exception in that situation, but instead
639   * keeps the original {@code toElement}.
640   */
641  @Override
642  public ImmutableSortedSet<E> headSet(E toElement) {
643    return headSet(toElement, false);
644  }
645
646  /** @since 12.0 */
647  @Override
648  public ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) {
649    return headSetImpl(checkNotNull(toElement), inclusive);
650  }
651
652  /**
653   * {@inheritDoc}
654   *
655   * <p>This method returns a serializable {@code ImmutableSortedSet}.
656   *
657   * <p>The {@link SortedSet#subSet} documentation states that a subset of a subset throws an {@link
658   * IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code
659   * fromElement}. However, this method doesn't throw an exception in that situation, but instead
660   * keeps the original {@code fromElement}. Similarly, this method keeps the original {@code
661   * toElement}, instead of throwing an exception, if passed a {@code toElement} greater than an
662   * earlier {@code toElement}.
663   */
664  @Override
665  public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
666    return subSet(fromElement, true, toElement, false);
667  }
668
669  /** @since 12.0 */
670  @GwtIncompatible // NavigableSet
671  @Override
672  public ImmutableSortedSet<E> subSet(
673      E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
674    checkNotNull(fromElement);
675    checkNotNull(toElement);
676    checkArgument(comparator.compare(fromElement, toElement) <= 0);
677    return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
678  }
679
680  /**
681   * {@inheritDoc}
682   *
683   * <p>This method returns a serializable {@code ImmutableSortedSet}.
684   *
685   * <p>The {@link SortedSet#tailSet} documentation states that a subset of a subset throws an
686   * {@link IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code
687   * fromElement}. However, this method doesn't throw an exception in that situation, but instead
688   * keeps the original {@code fromElement}.
689   */
690  @Override
691  public ImmutableSortedSet<E> tailSet(E fromElement) {
692    return tailSet(fromElement, true);
693  }
694
695  /** @since 12.0 */
696  @Override
697  public ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) {
698    return tailSetImpl(checkNotNull(fromElement), inclusive);
699  }
700
701  /*
702   * These methods perform most headSet, subSet, and tailSet logic, besides
703   * parameter validation.
704   */
705  abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive);
706
707  abstract ImmutableSortedSet<E> subSetImpl(
708      E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
709
710  abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive);
711
712  /** @since 12.0 */
713  @GwtIncompatible // NavigableSet
714  @Override
715  @CheckForNull
716  public E lower(E e) {
717    return Iterators.<@Nullable E>getNext(headSet(e, false).descendingIterator(), null);
718  }
719
720  /** @since 12.0 */
721  @Override
722  @CheckForNull
723  public E floor(E e) {
724    return Iterators.<@Nullable E>getNext(headSet(e, true).descendingIterator(), null);
725  }
726
727  /** @since 12.0 */
728  @Override
729  @CheckForNull
730  public E ceiling(E e) {
731    return Iterables.<@Nullable E>getFirst(tailSet(e, true), null);
732  }
733
734  /** @since 12.0 */
735  @GwtIncompatible // NavigableSet
736  @Override
737  @CheckForNull
738  public E higher(E e) {
739    return Iterables.<@Nullable E>getFirst(tailSet(e, false), null);
740  }
741
742  @Override
743  public E first() {
744    return iterator().next();
745  }
746
747  @Override
748  public E last() {
749    return descendingIterator().next();
750  }
751
752  /**
753   * Guaranteed to throw an exception and leave the set unmodified.
754   *
755   * @since 12.0
756   * @throws UnsupportedOperationException always
757   * @deprecated Unsupported operation.
758   */
759  @CanIgnoreReturnValue
760  @Deprecated
761  @GwtIncompatible // NavigableSet
762  @Override
763  @DoNotCall("Always throws UnsupportedOperationException")
764  @CheckForNull
765  public final E pollFirst() {
766    throw new UnsupportedOperationException();
767  }
768
769  /**
770   * Guaranteed to throw an exception and leave the set unmodified.
771   *
772   * @since 12.0
773   * @throws UnsupportedOperationException always
774   * @deprecated Unsupported operation.
775   */
776  @CanIgnoreReturnValue
777  @Deprecated
778  @GwtIncompatible // NavigableSet
779  @Override
780  @DoNotCall("Always throws UnsupportedOperationException")
781  @CheckForNull
782  public final E pollLast() {
783    throw new UnsupportedOperationException();
784  }
785
786  @GwtIncompatible // NavigableSet
787  @LazyInit
788  @CheckForNull
789  transient ImmutableSortedSet<E> descendingSet;
790
791  /** @since 12.0 */
792  @GwtIncompatible // NavigableSet
793  @Override
794  public ImmutableSortedSet<E> descendingSet() {
795    // racy single-check idiom
796    ImmutableSortedSet<E> result = descendingSet;
797    if (result == null) {
798      result = descendingSet = createDescendingSet();
799      result.descendingSet = this;
800    }
801    return result;
802  }
803
804  // Most classes should implement this as new DescendingImmutableSortedSet<E>(this),
805  // but we push down that implementation because ProGuard can't eliminate it even when it's always
806  // overridden.
807  @GwtIncompatible // NavigableSet
808  abstract ImmutableSortedSet<E> createDescendingSet();
809
810  @Override
811  public Spliterator<E> spliterator() {
812    return new Spliterators.AbstractSpliterator<E>(
813        size(), SPLITERATOR_CHARACTERISTICS | Spliterator.SIZED) {
814      final UnmodifiableIterator<E> iterator = iterator();
815
816      @Override
817      public boolean tryAdvance(Consumer<? super E> action) {
818        if (iterator.hasNext()) {
819          action.accept(iterator.next());
820          return true;
821        } else {
822          return false;
823        }
824      }
825
826      @Override
827      public Comparator<? super E> getComparator() {
828        return comparator;
829      }
830    };
831  }
832
833  /** @since 12.0 */
834  @GwtIncompatible // NavigableSet
835  @Override
836  public abstract UnmodifiableIterator<E> descendingIterator();
837
838  /** Returns the position of an element within the set, or -1 if not present. */
839  abstract int indexOf(@CheckForNull Object target);
840
841  /*
842   * This class is used to serialize all ImmutableSortedSet instances,
843   * regardless of implementation type. It captures their "logical contents"
844   * only. This is necessary to ensure that the existence of a particular
845   * implementation type is an implementation detail.
846   */
847  @J2ktIncompatible // serialization
848  private static class SerializedForm<E> implements Serializable {
849    final Comparator<? super E> comparator;
850    final Object[] elements;
851
852    public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
853      this.comparator = comparator;
854      this.elements = elements;
855    }
856
857    @SuppressWarnings("unchecked")
858    Object readResolve() {
859      return new Builder<E>(comparator).add((E[]) elements).build();
860    }
861
862    private static final long serialVersionUID = 0;
863  }
864
865  @J2ktIncompatible // serialization
866  private void readObject(ObjectInputStream unused) throws InvalidObjectException {
867    throw new InvalidObjectException("Use SerializedForm");
868  }
869
870  @Override
871  @J2ktIncompatible // serialization
872  Object writeReplace() {
873    return new SerializedForm<E>(comparator, toArray());
874  }
875
876  /**
877   * Not supported. Use {@link #toImmutableSortedSet} instead. This method exists only to hide
878   * {@link ImmutableSet#toImmutableSet} from consumers of {@code ImmutableSortedSet}.
879   *
880   * @throws UnsupportedOperationException always
881   * @deprecated Use {@link ImmutableSortedSet#toImmutableSortedSet}.
882   * @since 21.0
883   */
884  @DoNotCall("Use toImmutableSortedSet")
885  @Deprecated
886  public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() {
887    throw new UnsupportedOperationException();
888  }
889
890  /**
891   * Not supported. Use {@link #naturalOrder}, which offers better type-safety, instead. This method
892   * exists only to hide {@link ImmutableSet#builder} from consumers of {@code ImmutableSortedSet}.
893   *
894   * @throws UnsupportedOperationException always
895   * @deprecated Use {@link ImmutableSortedSet#naturalOrder}, which offers better type-safety.
896   */
897  @DoNotCall("Use naturalOrder")
898  @Deprecated
899  public static <E> ImmutableSortedSet.Builder<E> builder() {
900    throw new UnsupportedOperationException();
901  }
902
903  /**
904   * Not supported. This method exists only to hide {@link ImmutableSet#builderWithExpectedSize}
905   * from consumers of {@code ImmutableSortedSet}.
906   *
907   * @throws UnsupportedOperationException always
908   * @deprecated Not supported by ImmutableSortedSet.
909   */
910  @DoNotCall("Use naturalOrder (which does not accept an expected size)")
911  @Deprecated
912  public static <E> ImmutableSortedSet.Builder<E> builderWithExpectedSize(int expectedSize) {
913    throw new UnsupportedOperationException();
914  }
915
916  /**
917   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
918   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
919   * dummy version.
920   *
921   * @throws UnsupportedOperationException always
922   * @deprecated <b>Pass a parameter of type {@code Comparable} to use {@link
923   *     ImmutableSortedSet#of(Comparable)}.</b>
924   */
925  @DoNotCall("Pass a parameter of type Comparable")
926  @Deprecated
927  public static <E> ImmutableSortedSet<E> of(E e1) {
928    throw new UnsupportedOperationException();
929  }
930
931  /**
932   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
933   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
934   * dummy version.
935   *
936   * @throws UnsupportedOperationException always
937   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
938   *     ImmutableSortedSet#of(Comparable, Comparable)}.</b>
939   */
940  @DoNotCall("Pass parameters of type Comparable")
941  @Deprecated
942  public static <E> ImmutableSortedSet<E> of(E e1, E e2) {
943    throw new UnsupportedOperationException();
944  }
945
946  /**
947   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
948   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
949   * dummy version.
950   *
951   * @throws UnsupportedOperationException always
952   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
953   *     ImmutableSortedSet#of(Comparable, Comparable, Comparable)}.</b>
954   */
955  @DoNotCall("Pass parameters of type Comparable")
956  @Deprecated
957  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3) {
958    throw new UnsupportedOperationException();
959  }
960
961  /**
962   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
963   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
964   * dummy version.
965   *
966   * @throws UnsupportedOperationException always
967   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
968   *     ImmutableSortedSet#of(Comparable, Comparable, Comparable, Comparable)}. </b>
969   */
970  @DoNotCall("Pass parameters of type Comparable")
971  @Deprecated
972  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4) {
973    throw new UnsupportedOperationException();
974  }
975
976  /**
977   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
978   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
979   * dummy version.
980   *
981   * @throws UnsupportedOperationException always
982   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
983   *     ImmutableSortedSet#of( Comparable, Comparable, Comparable, Comparable, Comparable)}. </b>
984   */
985  @DoNotCall("Pass parameters of type Comparable")
986  @Deprecated
987  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4, E e5) {
988    throw new UnsupportedOperationException();
989  }
990
991  /**
992   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
993   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
994   * dummy version.
995   *
996   * @throws UnsupportedOperationException always
997   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
998   *     ImmutableSortedSet#of(Comparable, Comparable, Comparable, Comparable, Comparable,
999   *     Comparable, Comparable...)}. </b>
1000   */
1001  @DoNotCall("Pass parameters of type Comparable")
1002  @Deprecated
1003  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
1004    throw new UnsupportedOperationException();
1005  }
1006
1007  /**
1008   * Not supported. <b>You are attempting to create a set that may contain non-{@code Comparable}
1009   * elements.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
1010   * dummy version.
1011   *
1012   * @throws UnsupportedOperationException always
1013   * @deprecated <b>Pass parameters of type {@code Comparable} to use {@link
1014   *     ImmutableSortedSet#copyOf(Comparable[])}.</b>
1015   */
1016  @DoNotCall("Pass parameters of type Comparable")
1017  @Deprecated
1018  // The usage of "Z" here works around bugs in Javadoc (JDK-8318093) and JDiff.
1019  public static <Z> ImmutableSortedSet<Z> copyOf(Z[] elements) {
1020    throw new UnsupportedOperationException();
1021  }
1022
1023  private static final long serialVersionUID = 0xcafebabe;
1024}