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;
021
022import com.google.common.annotations.Beta;
023import com.google.common.annotations.GwtCompatible;
024
025import java.io.InvalidObjectException;
026import java.io.ObjectInputStream;
027import java.io.Serializable;
028import java.util.ArrayList;
029import java.util.Arrays;
030import java.util.Collection;
031import java.util.Collections;
032import java.util.Comparator;
033import java.util.Iterator;
034import java.util.List;
035import java.util.SortedSet;
036
037/**
038 * An immutable {@code SortedSet} that stores its elements in a sorted array.
039 * Some instances are ordered by an explicit comparator, while others follow the
040 * natural sort ordering of their elements. Either way, null elements are not
041 * supported.
042 *
043 * <p>Unlike {@link Collections#unmodifiableSortedSet}, which is a <i>view</i>
044 * of a separate collection that can still change, an instance of {@code
045 * ImmutableSortedSet} contains its own private data and will <i>never</i>
046 * change. This class is convenient for {@code public static final} sets
047 * ("constant sets") and also lets you easily make a "defensive copy" of a set
048 * provided to your class by a caller.
049 *
050 * <p>The sets returned by {@link #headSet}, {@link #tailSet}, and
051 * {@link #subSet} methods share the same array as the original set, preventing
052 * that array from being garbage collected. If this is a concern, the data may
053 * be copied into a correctly-sized array by calling {@link #copyOfSorted}.
054 *
055 * <p><b>Note on element equivalence:</b> The {@link #contains(Object)},
056 * {@link #containsAll(Collection)}, and {@link #equals(Object)}
057 * implementations must check whether a provided object is equivalent to an
058 * element in the collection. Unlike most collections, an
059 * {@code ImmutableSortedSet} doesn't use {@link Object#equals} to determine if
060 * two elements are equivalent. Instead, with an explicit comparator, the
061 * following relation determines whether elements {@code x} and {@code y} are
062 * equivalent: <pre>   {@code
063 *
064 *   {(x, y) | comparator.compare(x, y) == 0}}</pre>
065 *
066 * With natural ordering of elements, the following relation determines whether
067 * two elements are equivalent: <pre>   {@code
068 *
069 *   {(x, y) | x.compareTo(y) == 0}}</pre>
070 *
071 * <b>Warning:</b> Like most sets, an {@code ImmutableSortedSet} will not
072 * function correctly if an element is modified after being placed in the set.
073 * For this reason, and to avoid general confusion, it is strongly recommended
074 * to place only immutable objects into this collection.
075 *
076 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed as
077 * it has no public or protected constructors. Thus, instances of this type are
078 * guaranteed to be immutable.
079 *
080 * @see ImmutableSet
081 * @author Jared Levy
082 * @author Louis Wasserman
083 * @since 2 (imported from Google Collections Library)
084 */
085// TODO(benyu): benchmark and optimize all creation paths, which are a mess now
086@GwtCompatible(serializable = true, emulated = true)
087@SuppressWarnings("serial") // we're overriding default serialization
088public abstract class ImmutableSortedSet<E>
089    extends ImmutableSortedSetFauxverideShim<E> implements SortedSet<E> {
090
091  /*
092   * TODO(cpovirk): find a way to remove this @SuppressWarnings even for
093   * eclipse?
094   */
095  @SuppressWarnings("unchecked")
096  private static final Comparator<Comparable> NATURAL_ORDER =
097      Ordering.natural();
098
099  @SuppressWarnings("unchecked")
100  private static final ImmutableSortedSet<Comparable> NATURAL_EMPTY_SET =
101      new EmptyImmutableSortedSet<Comparable>(NATURAL_ORDER);
102
103  @SuppressWarnings("unchecked")
104  private static <E> ImmutableSortedSet<E> emptySet() {
105    return (ImmutableSortedSet<E>) NATURAL_EMPTY_SET;
106  }
107
108  static <E> ImmutableSortedSet<E> emptySet(
109      Comparator<? super E> comparator) {
110    if (NATURAL_ORDER.equals(comparator)) {
111      return emptySet();
112    } else {
113      return new EmptyImmutableSortedSet<E>(comparator);
114    }
115  }
116
117  /**
118   * Returns the empty immutable sorted set.
119   */
120  public static <E> ImmutableSortedSet<E> of() {
121    return emptySet();
122  }
123
124  /**
125   * Returns an immutable sorted set containing a single element.
126   */
127  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
128      E element) {
129    return new RegularImmutableSortedSet<E>(
130        ImmutableList.of(element), Ordering.natural());
131  }
132
133  /**
134   * Returns an immutable sorted set containing the given elements sorted by
135   * their natural ordering. When multiple elements are equivalent according to
136   * {@link Comparable#compareTo}, only the first one specified is included.
137   *
138   * @throws NullPointerException if any element is null
139   */
140  @SuppressWarnings("unchecked")
141  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
142      E e1, E e2) {
143    return copyOf(Ordering.natural(), Arrays.asList(e1, e2));
144  }
145
146  /**
147   * Returns an immutable sorted set containing the given elements sorted by
148   * their natural ordering. When multiple elements are equivalent according to
149   * {@link Comparable#compareTo}, only the first one specified is included.
150   *
151   * @throws NullPointerException if any element is null
152   */
153  @SuppressWarnings("unchecked")
154  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
155      E e1, E e2, E e3) {
156    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3));
157  }
158
159  /**
160   * Returns an immutable sorted set containing the given elements sorted by
161   * their natural ordering. When multiple elements are equivalent according to
162   * {@link Comparable#compareTo}, only the first one specified is included.
163   *
164   * @throws NullPointerException if any element is null
165   */
166  @SuppressWarnings("unchecked")
167  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
168      E e1, E e2, E e3, E e4) {
169    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4));
170  }
171
172  /**
173   * Returns an immutable sorted set containing the given elements sorted by
174   * their natural ordering. When multiple elements are equivalent according to
175   * {@link Comparable#compareTo}, only the first one specified is included.
176   *
177   * @throws NullPointerException if any element is null
178   */
179  @SuppressWarnings("unchecked")
180  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
181      E e1, E e2, E e3, E e4, E e5) {
182    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5));
183  }
184
185  /**
186   * Returns an immutable sorted set containing the given elements sorted by
187   * their natural ordering. When multiple elements are equivalent according to
188   * {@link Comparable#compareTo}, only the first one specified is included.
189   *
190   * @throws NullPointerException if any element is null
191   * @since 3 (source-compatible since release 2)
192   */
193  @SuppressWarnings("unchecked")
194  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
195      E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
196    int size = remaining.length + 6;
197    List<E> all = new ArrayList<E>(size);
198    Collections.addAll(all, e1, e2, e3, e4, e5, e6);
199    Collections.addAll(all, remaining);
200    return copyOf(Ordering.natural(), all);
201  }
202
203  // TODO(kevinb): Consider factory methods that reject duplicates
204
205  /**
206   * Returns an immutable sorted set containing the given elements sorted by
207   * their natural ordering. When multiple elements are equivalent according to
208   * {@link Comparable#compareTo}, only the first one specified is included.
209   *
210   * @throws NullPointerException if any of {@code elements} is null
211   * @deprecated use {@link #copyOf(Comparable[])}. <b>This method is scheduled
212   *     for deletion in October 2011.</b>
213   * @since 2 (changed from varargs in release 3)
214   */
215  @Deprecated
216  public
217  static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
218      E[] elements) {
219    return copyOf(elements);
220  }
221
222  /**
223   * Returns an immutable sorted set containing the given elements sorted by
224   * their natural ordering. When multiple elements are equivalent according to
225   * {@link Comparable#compareTo}, only the first one specified is included.
226   *
227   * @throws NullPointerException if any of {@code elements} is null
228   * @since 3
229   */
230  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(
231      E[] elements) {
232    return copyOf(Ordering.natural(), Arrays.asList(elements));
233  }
234
235  /**
236   * Returns an immutable sorted set containing the given elements sorted by
237   * their natural ordering. When multiple elements are equivalent according to
238   * {@code compareTo()}, only the first one specified is included. To create a
239   * copy of a {@code SortedSet} that preserves the comparator, call {@link
240   * #copyOfSorted} instead. This method iterates over {@code elements} at most
241   * once.
242
243   *
244   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
245   * ImmutableSortedSet.copyOf(s)} returns an {@code ImmutableSortedSet<String>}
246   * containing each of the strings in {@code s}, while {@code
247   * ImmutableSortedSet.of(s)} returns an {@code
248   * ImmutableSortedSet<Set<String>>} containing one element (the given set
249   * itself).
250   *
251   * <p>Despite the method name, this method attempts to avoid actually copying
252   * the data when it is safe to do so. The exact circumstances under which a
253   * copy will or will not be performed are undocumented and subject to change.
254   *
255   * <p>This method is not type-safe, as it may be called on elements that are
256   * not mutually comparable.
257   *
258   * @throws ClassCastException if the elements are not mutually comparable
259   * @throws NullPointerException if any of {@code elements} is null
260   */
261  public static <E> ImmutableSortedSet<E> copyOf(
262      Iterable<? extends E> elements) {
263    // Hack around K not being a subtype of Comparable.
264    // Unsafe, see ImmutableSortedSetFauxverideShim.
265    @SuppressWarnings("unchecked")
266    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
267    return copyOf(naturalOrder, elements);
268  }
269
270  /**
271   * Returns an immutable sorted set containing the given elements sorted by
272   * their natural ordering. When multiple elements are equivalent according to
273   * {@code compareTo()}, only the first one specified is included. To create a
274   * copy of a {@code SortedSet} that preserves the comparator, call
275   * {@link #copyOfSorted} instead. This method iterates over {@code elements}
276   * at most once.
277   *
278   * <p>Note that if {@code s} is a {@code Set<String>}, then
279   * {@code ImmutableSortedSet.copyOf(s)} returns an
280   * {@code ImmutableSortedSet<String>} containing each of the strings in
281   * {@code s}, while {@code ImmutableSortedSet.of(s)} returns an
282   * {@code ImmutableSortedSet<Set<String>>} containing one element (the given
283   * set itself).
284   *
285   * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
286   * is an {@code ImmutableSortedSet}, it may be returned instead of a copy.
287   *
288   * <p>This method is not type-safe, as it may be called on elements that are
289   * not mutually comparable.
290   *
291   * <p>This method is safe to use even when {@code elements} is a synchronized
292   * or concurrent collection that is currently being modified by another
293   * thread.
294   *
295   * @throws ClassCastException if the elements are not mutually comparable
296   * @throws NullPointerException if any of {@code elements} is null
297   * @since 7 (source-compatible since release 2)
298   */
299  public static <E> ImmutableSortedSet<E> copyOf(
300      Collection<? extends E> elements) {
301    // Hack around K not being a subtype of Comparable.
302    // Unsafe, see ImmutableSortedSetFauxverideShim.
303    @SuppressWarnings("unchecked")
304    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
305    return copyOf(naturalOrder, elements);
306  }
307
308  /**
309   * Returns an immutable sorted set containing the given elements sorted by
310   * their natural ordering. When multiple elements are equivalent according to
311   * {@code compareTo()}, only the first one specified is included.
312   *
313   * <p>This method is not type-safe, as it may be called on elements that are
314   * not mutually comparable.
315   *
316   * @throws ClassCastException if the elements are not mutually comparable
317   * @throws NullPointerException if any of {@code elements} is null
318   */
319  public static <E> ImmutableSortedSet<E> copyOf(
320      Iterator<? extends E> elements) {
321    // Hack around K not being a subtype of Comparable.
322    // Unsafe, see ImmutableSortedSetFauxverideShim.
323    @SuppressWarnings("unchecked")
324    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
325    return copyOfInternal(naturalOrder, elements);
326  }
327
328  /**
329   * Returns an immutable sorted set containing the given elements sorted by
330   * the given {@code Comparator}. When multiple elements are equivalent
331   * according to {@code compareTo()}, only the first one specified is
332   * included.
333   *
334   * @throws NullPointerException if {@code comparator} or any of
335   *     {@code elements} is null
336   */
337  public static <E> ImmutableSortedSet<E> copyOf(
338      Comparator<? super E> comparator, Iterator<? extends E> elements) {
339    checkNotNull(comparator);
340    return copyOfInternal(comparator, elements);
341  }
342
343  /**
344   * Returns an immutable sorted set containing the given elements sorted by
345   * the given {@code Comparator}. When multiple elements are equivalent
346   * according to {@code compare()}, only the first one specified is
347   * included. This method iterates over {@code elements} at most once.
348   *
349   * <p>Despite the method name, this method attempts to avoid actually copying
350   * the data when it is safe to do so. The exact circumstances under which a
351   * copy will or will not be performed are undocumented and subject to change.
352   *
353   * @throws NullPointerException if {@code comparator} or any of {@code
354   *         elements} is null
355   */
356  public static <E> ImmutableSortedSet<E> copyOf(
357      Comparator<? super E> comparator, Iterable<? extends E> elements) {
358    checkNotNull(comparator);
359    return copyOfInternal(comparator, elements, false);
360  }
361
362  /**
363   * Returns an immutable sorted set containing the given elements sorted by
364   * the given {@code Comparator}. When multiple elements are equivalent
365   * according to {@code compareTo()}, only the first one specified is
366   * included.
367   *
368   * <p>Despite the method name, this method attempts to avoid actually copying
369   * the data when it is safe to do so. The exact circumstances under which a
370   * copy will or will not be performed are undocumented and subject to change.
371   *
372   * <p>This method is safe to use even when {@code elements} is a synchronized
373   * or concurrent collection that is currently being modified by another
374   * thread.
375   *
376   * @throws NullPointerException if {@code comparator} or any of
377   *     {@code elements} is null
378   * @since 7 (source-compatible since release 2)
379   */
380  public static <E> ImmutableSortedSet<E> copyOf(
381      Comparator<? super E> comparator, Collection<? extends E> elements) {
382    checkNotNull(comparator);
383    return copyOfInternal(comparator, elements, false);
384  }
385
386  /**
387   * Returns an immutable sorted set containing the elements of a sorted set,
388   * sorted by the same {@code Comparator}. That behavior differs from {@link
389   * #copyOf(Iterable)}, which always uses the natural ordering of the
390   * elements.
391   *
392   * <p>Despite the method name, this method attempts to avoid actually copying
393   * the data when it is safe to do so. The exact circumstances under which a
394   * copy will or will not be performed are undocumented and subject to change.
395   *
396   * <p>This method is safe to use even when {@code elements} is a synchronized
397   * or concurrent collection that is currently being modified by another
398   * thread.
399   *
400   * @throws NullPointerException if {@code sortedSet} or any of its elements
401   *     is null
402   */
403  @SuppressWarnings("unchecked")
404  public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
405    Comparator<? super E> comparator = sortedSet.comparator();
406    if (comparator == null) {
407      comparator = (Comparator<? super E>) NATURAL_ORDER;
408    }
409    return copyOfInternal(comparator, sortedSet, true);
410  }
411
412  private static <E> ImmutableSortedSet<E> copyOfInternal(
413      Comparator<? super E> comparator, Iterable<? extends E> elements,
414      boolean fromSortedSet) {
415    boolean hasSameComparator
416        = fromSortedSet || hasSameComparator(elements, comparator);
417
418    if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
419      @SuppressWarnings("unchecked")
420      ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
421      if (original.isEmpty()) {
422        return original;
423      }
424      ImmutableList<E> elementsList = original.asList();
425      ImmutableList<E> copiedElementsList = ImmutableList.copyOf(elements);
426      if (elementsList == copiedElementsList) {
427        return original;
428      }
429      return new RegularImmutableSortedSet<E>(copiedElementsList, comparator);
430    }
431
432    ImmutableList<E> list =
433        immutableSortedUniqueCopy(comparator, Lists.newArrayList(elements));
434    if (list.isEmpty()) {
435      return emptySet(comparator);
436    }
437    return new RegularImmutableSortedSet<E>(list, comparator);
438  }
439
440  private static <E> ImmutableSortedSet<E> copyOfInternal(
441      Comparator<? super E> comparator, Iterator<? extends E> elements) {
442    if (!elements.hasNext()) {
443      return emptySet(comparator);
444    }
445    ImmutableList<E> list =
446        immutableSortedUniqueCopy(comparator, Lists.newArrayList(elements));
447    return new RegularImmutableSortedSet<E>(list, comparator);
448  }
449
450  /**
451   * The list will get modified. Sorts the list, eliminates duplicate elements,
452   * returns an immutable copy.
453   */
454  private static <E> ImmutableList<E> immutableSortedUniqueCopy(
455      Comparator<? super E> comparator, List<E> list) {
456    if (list.isEmpty()) {
457      return ImmutableList.of();
458    }
459    Collections.sort(list, comparator);
460    int size = 1;
461    for (int i = 1; i < list.size(); i++) {
462      E elem = list.get(i);
463      if (comparator.compare(elem, list.get(size - 1)) != 0) {
464        list.set(size++, elem);
465      }
466    }
467    return ImmutableList.copyOf(list.subList(0, size));
468  }
469
470  /**
471   * Returns {@code true} if {@code elements} is a {@code SortedSet} that uses
472   * {@code comparator} to order its elements. Note that equivalent comparators
473   * may still return {@code false}, if {@code equals} doesn't consider them
474   * equal. If one comparator is {@code null} and the other is
475   * {@link Ordering#natural()}, this method returns {@code true}.
476   */
477  static boolean hasSameComparator(
478      Iterable<?> elements, Comparator<?> comparator) {
479    if (elements instanceof SortedSet) {
480      SortedSet<?> sortedSet = (SortedSet<?>) elements;
481      Comparator<?> comparator2 = sortedSet.comparator();
482      return (comparator2 == null)
483          ? comparator == Ordering.natural()
484          : comparator.equals(comparator2);
485    }
486    return false;
487  }
488
489  /**
490   * Returns an immutable sorted set containing the elements in the given list
491   * in the same order. It is useful when the elements already have the desired
492   * order but constructing the appropriate comparator is difficult.
493   *
494   * @throws NullPointerException if any of the elements is null
495   * @throws IllegalArgumentException if {@code elements} contains any
496   *     duplicate values (according to {@link Object#equals})
497   * @since 3
498   * @deprecated If the provided elements are already in their natural order,
499   *     {@link #copyOf(Iterable)} will produce a set with the same elements in
500   *     the same order.  If the elements are arranged according to another
501   *     {@code Comparator}, use {@link #orderedBy(Comparator)}.  Otherwise, use
502   *     {@link ImmutableSet}, which maintains insertion order for inputs that
503   *     are ordered but not sorted. This method is scheduled for deletion in
504   *     Guava release 10.
505   */
506  @Beta
507  @Deprecated
508  public static <E> ImmutableSortedSet<E> withExplicitOrder(List<E> elements) {
509    return ExplicitOrderedImmutableSortedSet.create(elements);
510  }
511
512  /**
513   * Returns an immutable sorted set containing the provided elements in the
514   * same order. It is useful when the elements already have the desired order
515   * but constructing the appropriate comparator is difficult.
516   *
517   * @param firstElement the value which should appear first in the generated
518   *     set
519   * @param remainingElementsInOrder the rest of the values in the generated
520   *     set, in the order they should appear
521   * @throws NullPointerException if any of the elements is null
522   * @throws IllegalArgumentException if any duplicate values (according to
523   *     {@link Object#equals(Object)}) are present among the method arguments
524   * @since 3
525   * @deprecated If the provided elements are already in their natural order,
526   *     {@link #of()} will produce a set with the same elements in the same
527   *     order.  If the elements are arranged according to another {@code
528   *     Comparator}, use {@link #orderedBy(Comparator)}.  Otherwise, use {@link
529   *     ImmutableSet}, which maintains insertion order for inputs that are
530   *     ordered but not sorted. This method is scheduled for deletion in Guava
531   *     release 10.
532   */
533  @Beta
534  @Deprecated
535  public static <E> ImmutableSortedSet<E> withExplicitOrder(
536      E firstElement, E... remainingElementsInOrder) {
537    return withExplicitOrder(
538        Lists.asList(firstElement, remainingElementsInOrder));
539  }
540
541  /**
542   * Returns a builder that creates immutable sorted sets with an explicit
543   * comparator. If the comparator has a more general type than the set being
544   * generated, such as creating a {@code SortedSet<Integer>} with a
545   * {@code Comparator<Number>}, use the {@link Builder} constructor instead.
546   *
547   * @throws NullPointerException if {@code comparator} is null
548   */
549  public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
550    return new Builder<E>(comparator);
551  }
552
553  /**
554   * Returns a builder that creates immutable sorted sets whose elements are
555   * ordered by the reverse of their natural ordering.
556   *
557   * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
558   * than {@code Comparable<? super E>} as a workaround for javac <a
559   * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
560   * 6468354</a>.
561   */
562  public static <E extends Comparable<E>> Builder<E> reverseOrder() {
563    return new Builder<E>(Ordering.natural().reverse());
564  }
565
566  /**
567   * Returns a builder that creates immutable sorted sets whose elements are
568   * ordered by their natural ordering. The sorted sets use {@link
569   * Ordering#natural()} as the comparator. This method provides more
570   * type-safety than {@link #builder}, as it can be called only for classes
571   * that implement {@link Comparable}.
572   *
573   * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
574   * than {@code Comparable<? super E>} as a workaround for javac <a
575   * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
576   * 6468354</a>.
577   */
578  public static <E extends Comparable<E>> Builder<E> naturalOrder() {
579    return new Builder<E>(Ordering.natural());
580  }
581
582  /**
583   * A builder for creating immutable sorted set instances, especially {@code
584   * public static final} sets ("constant sets"), with a given comparator.
585   * Example: <pre>   {@code
586   *
587   *   public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
588   *       new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
589   *           .addAll(SINGLE_DIGIT_PRIMES)
590   *           .add(42)
591   *           .build();}</pre>
592   *
593   * Builder instances can be reused; it is safe to call {@link #build} multiple
594   * times to build multiple sets in series. Each set is a superset of the set
595   * created before it.
596   *
597   * @since 2 (imported from Google Collections Library)
598   */
599  public static final class Builder<E> extends ImmutableSet.Builder<E> {
600    private final Comparator<? super E> comparator;
601
602    /**
603     * Creates a new builder. The returned builder is equivalent to the builder
604     * generated by {@link ImmutableSortedSet#orderedBy}.
605     */
606    public Builder(Comparator<? super E> comparator) {
607      this.comparator = checkNotNull(comparator);
608    }
609
610    /**
611     * Adds {@code element} to the {@code ImmutableSortedSet}.  If the
612     * {@code ImmutableSortedSet} already contains {@code element}, then
613     * {@code add} has no effect. (only the previously added element
614     * is retained).
615     *
616     * @param element the element to add
617     * @return this {@code Builder} object
618     * @throws NullPointerException if {@code element} is null
619     */
620    @Override public Builder<E> add(E element) {
621      super.add(element);
622      return this;
623    }
624
625    /**
626     * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
627     * ignoring duplicate elements (only the first duplicate element is added).
628     *
629     * @param elements the elements to add
630     * @return this {@code Builder} object
631     * @throws NullPointerException if {@code elements} contains a null element
632     */
633    @Override public Builder<E> add(E... elements) {
634      super.add(elements);
635      return this;
636    }
637
638    /**
639     * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
640     * ignoring duplicate elements (only the first duplicate element is added).
641     *
642     * @param elements the elements to add to the {@code ImmutableSortedSet}
643     * @return this {@code Builder} object
644     * @throws NullPointerException if {@code elements} contains a null element
645     */
646    @Override public Builder<E> addAll(Iterable<? extends E> elements) {
647      super.addAll(elements);
648      return this;
649    }
650
651    /**
652     * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
653     * ignoring duplicate elements (only the first duplicate element is added).
654     *
655     * @param elements the elements to add to the {@code ImmutableSortedSet}
656     * @return this {@code Builder} object
657     * @throws NullPointerException if {@code elements} contains a null element
658     */
659    @Override public Builder<E> addAll(Iterator<? extends E> elements) {
660      super.addAll(elements);
661      return this;
662    }
663
664    /**
665     * Returns a newly-created {@code ImmutableSortedSet} based on the contents
666     * of the {@code Builder} and its comparator.
667     */
668    @Override public ImmutableSortedSet<E> build() {
669      return copyOfInternal(comparator, contents.iterator());
670    }
671  }
672
673  int unsafeCompare(Object a, Object b) {
674    return unsafeCompare(comparator, a, b);
675  }
676
677  static int unsafeCompare(
678      Comparator<?> comparator, Object a, Object b) {
679    // Pretend the comparator can compare anything. If it turns out it can't
680    // compare a and b, we should get a CCE on the subsequent line. Only methods
681    // that are spec'd to throw CCE should call this.
682    @SuppressWarnings("unchecked")
683    Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
684    return unsafeComparator.compare(a, b);
685  }
686
687  final transient Comparator<? super E> comparator;
688
689  ImmutableSortedSet(Comparator<? super E> comparator) {
690    this.comparator = comparator;
691  }
692
693  /**
694   * Returns the comparator that orders the elements, which is
695   * {@link Ordering#natural()} when the natural ordering of the
696   * elements is used. Note that its behavior is not consistent with
697   * {@link SortedSet#comparator()}, which returns {@code null} to indicate
698   * natural ordering.
699   */
700  @Override
701  public Comparator<? super E> comparator() {
702    return comparator;
703  }
704
705  /**
706   * {@inheritDoc}
707   *
708   * <p>This method returns a serializable {@code ImmutableSortedSet}.
709   *
710   * <p>The {@link SortedSet#headSet} documentation states that a subset of a
711   * subset throws an {@link IllegalArgumentException} if passed a
712   * {@code toElement} greater than an earlier {@code toElement}. However, this
713   * method doesn't throw an exception in that situation, but instead keeps the
714   * original {@code toElement}.
715   */
716  @Override
717  public ImmutableSortedSet<E> headSet(E toElement) {
718    return headSetImpl(checkNotNull(toElement));
719  }
720
721  /**
722   * {@inheritDoc}
723   *
724   * <p>This method returns a serializable {@code ImmutableSortedSet}.
725   *
726   * <p>The {@link SortedSet#subSet} documentation states that a subset of a
727   * subset throws an {@link IllegalArgumentException} if passed a
728   * {@code fromElement} smaller than an earlier {@code fromElement}. However,
729   * this method doesn't throw an exception in that situation, but instead keeps
730   * the original {@code fromElement}. Similarly, this method keeps the
731   * original {@code toElement}, instead of throwing an exception, if passed a
732   * {@code toElement} greater than an earlier {@code toElement}.
733   */
734  @Override
735  public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
736    checkNotNull(fromElement);
737    checkNotNull(toElement);
738    checkArgument(comparator.compare(fromElement, toElement) <= 0);
739    return subSetImpl(fromElement, toElement);
740  }
741
742  /**
743   * {@inheritDoc}
744   *
745   * <p>This method returns a serializable {@code ImmutableSortedSet}.
746   *
747   * <p>The {@link SortedSet#tailSet} documentation states that a subset of a
748   * subset throws an {@link IllegalArgumentException} if passed a
749   * {@code fromElement} smaller than an earlier {@code fromElement}. However,
750   * this method doesn't throw an exception in that situation, but instead keeps
751   * the original {@code fromElement}.
752   */
753  @Override
754  public ImmutableSortedSet<E> tailSet(E fromElement) {
755    return tailSetImpl(checkNotNull(fromElement));
756  }
757
758  /*
759   * These methods perform most headSet, subSet, and tailSet logic, besides
760   * parameter validation.
761   */
762  abstract ImmutableSortedSet<E> headSetImpl(E toElement);
763  abstract ImmutableSortedSet<E> subSetImpl(E fromElement, E toElement);
764  abstract ImmutableSortedSet<E> tailSetImpl(E fromElement);
765
766  /**
767   * Returns the position of an element within the set, or -1 if not present.
768   */
769  abstract int indexOf(Object target);
770
771  /*
772   * This class is used to serialize all ImmutableSortedSet instances,
773   * regardless of implementation type. It captures their "logical contents"
774   * only. This is necessary to ensure that the existence of a particular
775   * implementation type is an implementation detail.
776   */
777  private static class SerializedForm<E> implements Serializable {
778    final Comparator<? super E> comparator;
779    final Object[] elements;
780
781    public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
782      this.comparator = comparator;
783      this.elements = elements;
784    }
785
786    @SuppressWarnings("unchecked")
787    Object readResolve() {
788      return new Builder<E>(comparator).add((E[]) elements).build();
789    }
790
791    private static final long serialVersionUID = 0;
792  }
793
794  private void readObject(ObjectInputStream stream)
795      throws InvalidObjectException {
796    throw new InvalidObjectException("Use SerializedForm");
797  }
798
799  @Override Object writeReplace() {
800    return new SerializedForm<E>(comparator, toArray());
801  }
802}