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.ImmutableList.asImmutableList;
022import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
023import static java.lang.System.arraycopy;
024import static java.util.Arrays.sort;
025
026import com.google.common.annotations.GwtCompatible;
027import com.google.common.annotations.GwtIncompatible;
028import com.google.common.annotations.J2ktIncompatible;
029import com.google.errorprone.annotations.CanIgnoreReturnValue;
030import com.google.errorprone.annotations.DoNotCall;
031import com.google.errorprone.annotations.concurrent.LazyInit;
032import java.io.InvalidObjectException;
033import java.io.ObjectInputStream;
034import java.io.Serializable;
035import java.util.Arrays;
036import java.util.Collection;
037import java.util.Collections;
038import java.util.Comparator;
039import java.util.Iterator;
040import java.util.NavigableSet;
041import java.util.SortedSet;
042import java.util.Spliterator;
043import java.util.Spliterators;
044import java.util.function.Consumer;
045import java.util.stream.Collector;
046import org.jspecify.annotations.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
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<>(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   * {@snippet :
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   * }
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      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<>(asImmutableList(elements, n), comparator);
594      }
595    }
596  }
597
598  final int unsafeCompare(Object a, @Nullable Object b) {
599    return unsafeCompare(comparator, a, b);
600  }
601
602  static int unsafeCompare(Comparator<?> comparator, Object a, @Nullable Object b) {
603    // Pretend the comparator can compare anything. If it turns out it can't
604    // compare a and b, we should get a CCE or NPE on the subsequent line. Only methods
605    // that are spec'd to throw CCE and NPE should call this.
606    @SuppressWarnings({"unchecked", "nullness"})
607    Comparator<@Nullable Object> unsafeComparator = (Comparator<@Nullable Object>) comparator;
608    return unsafeComparator.compare(a, b);
609  }
610
611  final transient Comparator<? super E> comparator;
612
613  ImmutableSortedSet(Comparator<? super E> comparator) {
614    this.comparator = comparator;
615  }
616
617  /**
618   * Returns the comparator that orders the elements, which is {@link Ordering#natural()} when the
619   * natural ordering of the elements is used. Note that its behavior is not consistent with {@link
620   * SortedSet#comparator()}, which returns {@code null} to indicate natural ordering.
621   */
622  @Override
623  public final Comparator<? super E> comparator() {
624    return comparator;
625  }
626
627  @Override // needed to unify the iterator() methods in Collection and SortedIterable
628  public abstract UnmodifiableIterator<E> iterator();
629
630  /**
631   * {@inheritDoc}
632   *
633   * <p>This method returns a serializable {@code ImmutableSortedSet}.
634   *
635   * <p>The {@link SortedSet#headSet} documentation states that a subset of a subset throws an
636   * {@link IllegalArgumentException} if passed a {@code toElement} greater than an earlier {@code
637   * toElement}. However, this method doesn't throw an exception in that situation, but instead
638   * keeps the original {@code toElement}.
639   */
640  @Override
641  public ImmutableSortedSet<E> headSet(E toElement) {
642    return headSet(toElement, false);
643  }
644
645  /**
646   * @since 12.0
647   */
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  /**
671   * @since 12.0
672   */
673  @GwtIncompatible // NavigableSet
674  @Override
675  public ImmutableSortedSet<E> subSet(
676      E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
677    checkNotNull(fromElement);
678    checkNotNull(toElement);
679    checkArgument(comparator.compare(fromElement, toElement) <= 0);
680    return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
681  }
682
683  /**
684   * {@inheritDoc}
685   *
686   * <p>This method returns a serializable {@code ImmutableSortedSet}.
687   *
688   * <p>The {@link SortedSet#tailSet} documentation states that a subset of a subset throws an
689   * {@link IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code
690   * fromElement}. However, this method doesn't throw an exception in that situation, but instead
691   * keeps the original {@code fromElement}.
692   */
693  @Override
694  public ImmutableSortedSet<E> tailSet(E fromElement) {
695    return tailSet(fromElement, true);
696  }
697
698  /**
699   * @since 12.0
700   */
701  @Override
702  public ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) {
703    return tailSetImpl(checkNotNull(fromElement), inclusive);
704  }
705
706  /*
707   * These methods perform most headSet, subSet, and tailSet logic, besides
708   * parameter validation.
709   */
710  abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive);
711
712  abstract ImmutableSortedSet<E> subSetImpl(
713      E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
714
715  abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive);
716
717  /**
718   * @since 12.0
719   */
720  @GwtIncompatible // NavigableSet
721  @Override
722  public @Nullable E lower(E e) {
723    return Iterators.<@Nullable E>getNext(headSet(e, false).descendingIterator(), null);
724  }
725
726  /**
727   * @since 12.0
728   */
729  @Override
730  public @Nullable E floor(E e) {
731    return Iterators.<@Nullable E>getNext(headSet(e, true).descendingIterator(), null);
732  }
733
734  /**
735   * @since 12.0
736   */
737  @Override
738  public @Nullable E ceiling(E e) {
739    return Iterables.<@Nullable E>getFirst(tailSet(e, true), null);
740  }
741
742  /**
743   * @since 12.0
744   */
745  @GwtIncompatible // NavigableSet
746  @Override
747  public @Nullable E higher(E e) {
748    return Iterables.<@Nullable E>getFirst(tailSet(e, false), null);
749  }
750
751  @Override
752  public E first() {
753    return iterator().next();
754  }
755
756  @Override
757  public E last() {
758    return descendingIterator().next();
759  }
760
761  /**
762   * Guaranteed to throw an exception and leave the set unmodified.
763   *
764   * @since 12.0
765   * @throws UnsupportedOperationException always
766   * @deprecated Unsupported operation.
767   */
768  @CanIgnoreReturnValue
769  @Deprecated
770  @GwtIncompatible // NavigableSet
771  @Override
772  @DoNotCall("Always throws UnsupportedOperationException")
773  public final @Nullable E pollFirst() {
774    throw new UnsupportedOperationException();
775  }
776
777  /**
778   * Guaranteed to throw an exception and leave the set unmodified.
779   *
780   * @since 12.0
781   * @throws UnsupportedOperationException always
782   * @deprecated Unsupported operation.
783   */
784  @CanIgnoreReturnValue
785  @Deprecated
786  @GwtIncompatible // NavigableSet
787  @Override
788  @DoNotCall("Always throws UnsupportedOperationException")
789  public final @Nullable E pollLast() {
790    throw new UnsupportedOperationException();
791  }
792
793  @GwtIncompatible // NavigableSet
794  @LazyInit
795  transient @Nullable ImmutableSortedSet<E> descendingSet;
796
797  /**
798   * @since 12.0
799   */
800  @GwtIncompatible // NavigableSet
801  @Override
802  public ImmutableSortedSet<E> descendingSet() {
803    // racy single-check idiom
804    ImmutableSortedSet<E> result = descendingSet;
805    if (result == null) {
806      result = descendingSet = createDescendingSet();
807      result.descendingSet = this;
808    }
809    return result;
810  }
811
812  // Most classes should implement this as new DescendingImmutableSortedSet<E>(this),
813  // but we push down that implementation because ProGuard can't eliminate it even when it's always
814  // overridden.
815  @GwtIncompatible // NavigableSet
816  abstract ImmutableSortedSet<E> createDescendingSet();
817
818  @Override
819  public Spliterator<E> spliterator() {
820    return new Spliterators.AbstractSpliterator<E>(
821        size(), SPLITERATOR_CHARACTERISTICS | Spliterator.SIZED) {
822      final UnmodifiableIterator<E> iterator = iterator();
823
824      @Override
825      public boolean tryAdvance(Consumer<? super E> action) {
826        if (iterator.hasNext()) {
827          action.accept(iterator.next());
828          return true;
829        } else {
830          return false;
831        }
832      }
833
834      @Override
835      public Comparator<? super E> getComparator() {
836        return comparator;
837      }
838    };
839  }
840
841  /**
842   * @since 12.0
843   */
844  @GwtIncompatible // NavigableSet
845  @Override
846  public abstract UnmodifiableIterator<E> descendingIterator();
847
848  /** Returns the position of an element within the set, or -1 if not present. */
849  abstract int indexOf(@Nullable Object target);
850
851  /*
852   * This class is used to serialize all ImmutableSortedSet instances,
853   * regardless of implementation type. It captures their "logical contents"
854   * only. This is necessary to ensure that the existence of a particular
855   * implementation type is an implementation detail.
856   */
857  @J2ktIncompatible // serialization
858  private static final class SerializedForm<E> implements Serializable {
859    final Comparator<? super E> comparator;
860    final Object[] elements;
861
862    SerializedForm(Comparator<? super E> comparator, Object[] elements) {
863      this.comparator = comparator;
864      this.elements = elements;
865    }
866
867    @SuppressWarnings("unchecked")
868    Object readResolve() {
869      return new Builder<E>(comparator).add((E[]) elements).build();
870    }
871
872    @GwtIncompatible private static final long serialVersionUID = 0;
873  }
874
875  @J2ktIncompatible // serialization
876  private void readObject(ObjectInputStream unused) throws InvalidObjectException {
877    throw new InvalidObjectException("Use SerializedForm");
878  }
879
880  @Override
881  @J2ktIncompatible // serialization
882  Object writeReplace() {
883    return new SerializedForm<E>(comparator, toArray());
884  }
885
886  /**
887   * Not supported. Use {@link #toImmutableSortedSet} instead. This method exists only to hide
888   * {@link ImmutableSet#toImmutableSet} from consumers of {@code ImmutableSortedSet}.
889   *
890   * @throws UnsupportedOperationException always
891   * @deprecated Use {@link ImmutableSortedSet#toImmutableSortedSet}.
892   * @since 21.0
893   */
894  @DoNotCall("Use toImmutableSortedSet")
895  @Deprecated
896  public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() {
897    throw new UnsupportedOperationException();
898  }
899
900  /**
901   * Not supported. Use {@link #naturalOrder}, which offers better type-safety, instead. This method
902   * exists only to hide {@link ImmutableSet#builder} from consumers of {@code ImmutableSortedSet}.
903   *
904   * @throws UnsupportedOperationException always
905   * @deprecated Use {@link ImmutableSortedSet#naturalOrder}, which offers better type-safety.
906   */
907  @DoNotCall("Use naturalOrder")
908  @Deprecated
909  public static <E> ImmutableSortedSet.Builder<E> builder() {
910    throw new UnsupportedOperationException();
911  }
912
913  /**
914   * Not supported. This method exists only to hide {@link ImmutableSet#builderWithExpectedSize}
915   * from consumers of {@code ImmutableSortedSet}.
916   *
917   * @throws UnsupportedOperationException always
918   * @deprecated Not supported by ImmutableSortedSet.
919   */
920  @DoNotCall("Use naturalOrder (which does not accept an expected size)")
921  @Deprecated
922  public static <E> ImmutableSortedSet.Builder<E> builderWithExpectedSize(int expectedSize) {
923    throw new UnsupportedOperationException();
924  }
925
926  /**
927   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
928   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
929   * dummy version.
930   *
931   * @throws UnsupportedOperationException always
932   * @deprecated <b>Pass a parameter of type {@code Comparable} to use {@link
933   *     ImmutableSortedSet#of(Comparable)}.</b>
934   */
935  @DoNotCall("Pass a parameter of type Comparable")
936  @Deprecated
937  public static <E> ImmutableSortedSet<E> of(E e1) {
938    throw new UnsupportedOperationException();
939  }
940
941  /**
942   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
943   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
944   * dummy version.
945   *
946   * @throws UnsupportedOperationException always
947   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
948   *     ImmutableSortedSet#of(Comparable, Comparable)}.</b>
949   */
950  @DoNotCall("Pass parameters of type Comparable")
951  @Deprecated
952  public static <E> ImmutableSortedSet<E> of(E e1, E e2) {
953    throw new UnsupportedOperationException();
954  }
955
956  /**
957   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
958   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
959   * dummy version.
960   *
961   * @throws UnsupportedOperationException always
962   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
963   *     ImmutableSortedSet#of(Comparable, Comparable, Comparable)}.</b>
964   */
965  @DoNotCall("Pass parameters of type Comparable")
966  @Deprecated
967  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3) {
968    throw new UnsupportedOperationException();
969  }
970
971  /**
972   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
973   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
974   * dummy version.
975   *
976   * @throws UnsupportedOperationException always
977   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
978   *     ImmutableSortedSet#of(Comparable, Comparable, Comparable, Comparable)}. </b>
979   */
980  @DoNotCall("Pass parameters of type Comparable")
981  @Deprecated
982  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4) {
983    throw new UnsupportedOperationException();
984  }
985
986  /**
987   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
988   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
989   * dummy version.
990   *
991   * @throws UnsupportedOperationException always
992   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
993   *     ImmutableSortedSet#of(Comparable, Comparable, Comparable, Comparable, Comparable)}. </b>
994   */
995  @DoNotCall("Pass parameters of type Comparable")
996  @Deprecated
997  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4, E e5) {
998    throw new UnsupportedOperationException();
999  }
1000
1001  /**
1002   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
1003   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
1004   * dummy version.
1005   *
1006   * @throws UnsupportedOperationException always
1007   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
1008   *     ImmutableSortedSet#of(Comparable, Comparable, Comparable, Comparable, Comparable,
1009   *     Comparable, Comparable...)}. </b>
1010   */
1011  @DoNotCall("Pass parameters of type Comparable")
1012  @Deprecated
1013  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
1014    throw new UnsupportedOperationException();
1015  }
1016
1017  /**
1018   * Not supported. <b>You are attempting to create a set that may contain non-{@code Comparable}
1019   * elements.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
1020   * dummy version.
1021   *
1022   * @throws UnsupportedOperationException always
1023   * @deprecated <b>Pass parameters of type {@code Comparable} to use {@link
1024   *     ImmutableSortedSet#copyOf(Comparable[])}.</b>
1025   */
1026  @DoNotCall("Pass parameters of type Comparable")
1027  @Deprecated
1028  // The usage of "Z" here works around bugs in Javadoc (JDK-8318093) and JDiff.
1029  public static <Z> ImmutableSortedSet<Z> copyOf(Z[] elements) {
1030    throw new UnsupportedOperationException();
1031  }
1032
1033  @GwtIncompatible @J2ktIncompatible   private static final long serialVersionUID = 0xcafebabe;
1034}