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