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