Source code

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