1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2008 The Guava Authors 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkArgument; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkNotNull; 210888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.collect.ObjectArrays.checkElementsNotNull; 22090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 23090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.GwtCompatible; 247dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.annotations.GwtIncompatible; 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.InvalidObjectException; 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectInputStream; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.Serializable; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Arrays; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collections; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Comparator; 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.NavigableSet; 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.SortedSet; 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * An immutable {@code SortedSet} that stores its elements in a sorted array. 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Some instances are ordered by an explicit comparator, while others follow the 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * natural sort ordering of their elements. Either way, null elements are not 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * supported. 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Unlike {@link Collections#unmodifiableSortedSet}, which is a <i>view</i> 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * of a separate collection that can still change, an instance of {@code 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSortedSet} contains its own private data and will <i>never</i> 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * change. This class is convenient for {@code public static final} sets 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ("constant sets") and also lets you easily make a "defensive copy" of a set 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * provided to your class by a caller. 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The sets returned by the {@link #headSet}, {@link #tailSet}, and 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #subSet} methods share the same array as the original set, preventing 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * that array from being garbage collected. If this is a concern, the data may 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * be copied into a correctly-sized array by calling {@link #copyOfSorted}. 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note on element equivalence:</b> The {@link #contains(Object)}, 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #containsAll(Collection)}, and {@link #equals(Object)} 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementations must check whether a provided object is equivalent to an 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * element in the collection. Unlike most collections, an 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code ImmutableSortedSet} doesn't use {@link Object#equals} to determine if 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * two elements are equivalent. Instead, with an explicit comparator, the 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * following relation determines whether elements {@code x} and {@code y} are 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * equivalent: <pre> {@code 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {(x, y) | comparator.compare(x, y) == 0}}</pre> 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>With natural ordering of elements, the following relation determines whether 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * two elements are equivalent: <pre> {@code 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {(x, y) | x.compareTo(y) == 0}}</pre> 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <b>Warning:</b> Like most sets, an {@code ImmutableSortedSet} will not 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * function correctly if an element is modified after being placed in the set. 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * For this reason, and to avoid general confusion, it is strongly recommended 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to place only immutable objects into this collection. 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * it has no public or protected constructors. Thus, instances of this type are 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * guaranteed to be immutable. 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 827dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>See the Guava User Guide article on <a href= 837dd252788645e940eada959bdde927426e2531c9Paul Duffin * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained"> 847dd252788645e940eada959bdde927426e2531c9Paul Duffin * immutable collections</a>. 857dd252788645e940eada959bdde927426e2531c9Paul Duffin * 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @see ImmutableSet 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Jared Levy 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 897dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 2.0 (imported from Google Collections Library; implements {@code NavigableSet} since 12.0) 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert// TODO(benyu): benchmark and optimize all creation paths, which are a mess now 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(serializable = true, emulated = true) 930888a09821a98ac0680fad765217302858e70fa4Paul Duffin@SuppressWarnings("serial") // we're overriding default serialization 940888a09821a98ac0680fad765217302858e70fa4Paul Duffinpublic abstract class ImmutableSortedSet<E> extends ImmutableSortedSetFauxverideShim<E> 953ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin implements NavigableSet<E>, SortedIterable<E> { 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 970888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final Comparator<Comparable> NATURAL_ORDER = 980888a09821a98ac0680fad765217302858e70fa4Paul Duffin Ordering.natural(); 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1000888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final ImmutableSortedSet<Comparable> NATURAL_EMPTY_SET = 1010888a09821a98ac0680fad765217302858e70fa4Paul Duffin new EmptyImmutableSortedSet<Comparable>(NATURAL_ORDER); 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static <E> ImmutableSortedSet<E> emptySet() { 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (ImmutableSortedSet<E>) NATURAL_EMPTY_SET; 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1080888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <E> ImmutableSortedSet<E> emptySet( 1090888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<? super E> comparator) { 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (NATURAL_ORDER.equals(comparator)) { 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return emptySet(); 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new EmptyImmutableSortedSet<E>(comparator); 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the empty immutable sorted set. 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> ImmutableSortedSet<E> of() { 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return emptySet(); 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set containing a single element. 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1270888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin E element) { 1290888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new RegularImmutableSortedSet<E>( 1300888a09821a98ac0680fad765217302858e70fa4Paul Duffin ImmutableList.of(element), Ordering.natural()); 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set containing the given elements sorted by 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering. When multiple elements are equivalent according to 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Comparable#compareTo}, only the first one specified is included. 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any element is null 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 1410888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 1420888a09821a98ac0680fad765217302858e70fa4Paul Duffin E e1, E e2) { 1430888a09821a98ac0680fad765217302858e70fa4Paul Duffin return construct(Ordering.natural(), 2, e1, e2); 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set containing the given elements sorted by 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering. When multiple elements are equivalent according to 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Comparable#compareTo}, only the first one specified is included. 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any element is null 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 1540888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 1550888a09821a98ac0680fad765217302858e70fa4Paul Duffin E e1, E e2, E e3) { 1560888a09821a98ac0680fad765217302858e70fa4Paul Duffin return construct(Ordering.natural(), 3, e1, e2, e3); 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set containing the given elements sorted by 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering. When multiple elements are equivalent according to 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Comparable#compareTo}, only the first one specified is included. 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any element is null 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 1670888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 1680888a09821a98ac0680fad765217302858e70fa4Paul Duffin E e1, E e2, E e3, E e4) { 1690888a09821a98ac0680fad765217302858e70fa4Paul Duffin return construct(Ordering.natural(), 4, e1, e2, e3, e4); 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set containing the given elements sorted by 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering. When multiple elements are equivalent according to 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Comparable#compareTo}, only the first one specified is included. 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any element is null 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 1800888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 1810888a09821a98ac0680fad765217302858e70fa4Paul Duffin E e1, E e2, E e3, E e4, E e5) { 1820888a09821a98ac0680fad765217302858e70fa4Paul Duffin return construct(Ordering.natural(), 5, e1, e2, e3, e4, e5); 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1847dd252788645e940eada959bdde927426e2531c9Paul Duffin 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set containing the given elements sorted by 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering. When multiple elements are equivalent according to 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Comparable#compareTo}, only the first one specified is included. 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any element is null 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 3.0 (source-compatible since 2.0) 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1940888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 1950888a09821a98ac0680fad765217302858e70fa4Paul Duffin E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) { 1960888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparable[] contents = new Comparable[6 + remaining.length]; 1970888a09821a98ac0680fad765217302858e70fa4Paul Duffin contents[0] = e1; 1980888a09821a98ac0680fad765217302858e70fa4Paul Duffin contents[1] = e2; 1990888a09821a98ac0680fad765217302858e70fa4Paul Duffin contents[2] = e3; 2000888a09821a98ac0680fad765217302858e70fa4Paul Duffin contents[3] = e4; 2010888a09821a98ac0680fad765217302858e70fa4Paul Duffin contents[4] = e5; 2020888a09821a98ac0680fad765217302858e70fa4Paul Duffin contents[5] = e6; 2030888a09821a98ac0680fad765217302858e70fa4Paul Duffin System.arraycopy(remaining, 0, contents, 6, remaining.length); 2040888a09821a98ac0680fad765217302858e70fa4Paul Duffin return construct(Ordering.natural(), contents.length, (E[]) contents); 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): Consider factory methods that reject duplicates 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted set containing the given elements sorted by 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * their natural ordering. When multiple elements are equivalent according to 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Comparable#compareTo}, only the first one specified is included. 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any of {@code elements} is null 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 3.0 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 2170888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf( 2180888a09821a98ac0680fad765217302858e70fa4Paul Duffin E[] elements) { 2190888a09821a98ac0680fad765217302858e70fa4Paul Duffin return construct(Ordering.natural(), elements.length, elements.clone()); 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted set containing the given elements sorted by 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * their natural ordering. When multiple elements are equivalent according to 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code compareTo()}, only the first one specified is included. To create a 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * copy of a {@code SortedSet} that preserves the comparator, call {@link 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * #copyOfSorted} instead. This method iterates over {@code elements} at most 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * once. 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Note that if {@code s} is a {@code Set<String>}, then {@code 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ImmutableSortedSet.copyOf(s)} returns an {@code ImmutableSortedSet<String>} 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * containing each of the strings in {@code s}, while {@code 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ImmutableSortedSet.of(s)} returns an {@code 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ImmutableSortedSet<Set<String>>} containing one element (the given set 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * itself). 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Despite the method name, this method attempts to avoid actually copying 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the data when it is safe to do so. The exact circumstances under which a 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * copy will or will not be performed are undocumented and subject to change. 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method is not type-safe, as it may be called on elements that are 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * not mutually comparable. 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ClassCastException if the elements are not mutually comparable 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any of {@code elements} is null 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2480888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ImmutableSortedSet<E> copyOf( 2490888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterable<? extends E> elements) { 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Hack around E not being a subtype of Comparable. 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Unsafe, see ImmutableSortedSetFauxverideShim. 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 2530888a09821a98ac0680fad765217302858e70fa4Paul Duffin Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyOf(naturalOrder, elements); 255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set containing the given elements sorted by 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering. When multiple elements are equivalent according to 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code compareTo()}, only the first one specified is included. To create a 261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * copy of a {@code SortedSet} that preserves the comparator, call 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #copyOfSorted} instead. This method iterates over {@code elements} 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * at most once. 264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Note that if {@code s} is a {@code Set<String>}, then 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code ImmutableSortedSet.copyOf(s)} returns an 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code ImmutableSortedSet<String>} containing each of the strings in 268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code s}, while {@code ImmutableSortedSet.of(s)} returns an 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code ImmutableSortedSet<Set<String>>} containing one element (the given 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * set itself). 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> Despite what the method name suggests, if {@code elements} 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * is an {@code ImmutableSortedSet}, it may be returned instead of a copy. 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method is not type-safe, as it may be called on elements that are 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * not mutually comparable. 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method is safe to use even when {@code elements} is a synchronized 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * or concurrent collection that is currently being modified by another 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * thread. 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws ClassCastException if the elements are not mutually comparable 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any of {@code elements} is null 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 7.0 (source-compatible since 2.0) 285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 2860888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ImmutableSortedSet<E> copyOf( 2870888a09821a98ac0680fad765217302858e70fa4Paul Duffin Collection<? extends E> elements) { 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Hack around E not being a subtype of Comparable. 289090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Unsafe, see ImmutableSortedSetFauxverideShim. 290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 2910888a09821a98ac0680fad765217302858e70fa4Paul Duffin Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyOf(naturalOrder, elements); 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set containing the given elements sorted by 297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering. When multiple elements are equivalent according to 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code compareTo()}, only the first one specified is included. 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 300090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method is not type-safe, as it may be called on elements that are 301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * not mutually comparable. 302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws ClassCastException if the elements are not mutually comparable 304090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any of {@code elements} is null 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3060888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ImmutableSortedSet<E> copyOf( 3070888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<? extends E> elements) { 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Hack around E not being a subtype of Comparable. 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Unsafe, see ImmutableSortedSetFauxverideShim. 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 3110888a09821a98ac0680fad765217302858e70fa4Paul Duffin Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 3127dd252788645e940eada959bdde927426e2531c9Paul Duffin return copyOf(naturalOrder, elements); 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set containing the given elements sorted by 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the given {@code Comparator}. When multiple elements are equivalent 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * according to {@code compareTo()}, only the first one specified is 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * included. 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code comparator} or any of 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code elements} is null 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3240888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ImmutableSortedSet<E> copyOf( 3250888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<? super E> comparator, Iterator<? extends E> elements) { 3260888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new Builder<E>(comparator).addAll(elements).build(); 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted set containing the given elements sorted by 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the given {@code Comparator}. When multiple elements are equivalent 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * according to {@code compare()}, only the first one specified is 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * included. This method iterates over {@code elements} at most once. 334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Despite the method name, this method attempts to avoid actually copying 3361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the data when it is safe to do so. The exact circumstances under which a 3371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * copy will or will not be performed are undocumented and subject to change. 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code comparator} or any of {@code 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements} is null 341090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3420888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ImmutableSortedSet<E> copyOf( 3430888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<? super E> comparator, Iterable<? extends E> elements) { 344090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(comparator); 3450888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean hasSameComparator = 3460888a09821a98ac0680fad765217302858e70fa4Paul Duffin SortedIterables.hasSameComparator(comparator, elements); 3477dd252788645e940eada959bdde927426e2531c9Paul Duffin 3487dd252788645e940eada959bdde927426e2531c9Paul Duffin if (hasSameComparator && (elements instanceof ImmutableSortedSet)) { 3497dd252788645e940eada959bdde927426e2531c9Paul Duffin @SuppressWarnings("unchecked") 3507dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements; 3517dd252788645e940eada959bdde927426e2531c9Paul Duffin if (!original.isPartialView()) { 3527dd252788645e940eada959bdde927426e2531c9Paul Duffin return original; 3537dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3547dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3550888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") // elements only contains E's; it's safe. 3567dd252788645e940eada959bdde927426e2531c9Paul Duffin E[] array = (E[]) Iterables.toArray(elements); 3577dd252788645e940eada959bdde927426e2531c9Paul Duffin return construct(comparator, array.length, array); 358090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 359090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 360090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set containing the given elements sorted by 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the given {@code Comparator}. When multiple elements are equivalent 363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * according to {@code compareTo()}, only the first one specified is 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * included. 365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 3661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Despite the method name, this method attempts to avoid actually copying 3671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the data when it is safe to do so. The exact circumstances under which a 3681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * copy will or will not be performed are undocumented and subject to change. 3691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method is safe to use even when {@code elements} is a synchronized 3711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * or concurrent collection that is currently being modified by another 3721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * thread. 3731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code comparator} or any of 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code elements} is null 3761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 7.0 (source-compatible since 2.0) 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3780888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ImmutableSortedSet<E> copyOf( 3790888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<? super E> comparator, Collection<? extends E> elements) { 3807dd252788645e940eada959bdde927426e2531c9Paul Duffin return copyOf(comparator, (Iterable<? extends E>) elements); 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set containing the elements of a sorted set, 3851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * sorted by the same {@code Comparator}. That behavior differs from {@link 3861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * #copyOf(Iterable)}, which always uses the natural ordering of the 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements. 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 3891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Despite the method name, this method attempts to avoid actually copying 3901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the data when it is safe to do so. The exact circumstances under which a 3911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * copy will or will not be performed are undocumented and subject to change. 392090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 3931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method is safe to use even when {@code sortedSet} is a synchronized 3941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * or concurrent collection that is currently being modified by another 3951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * thread. 3961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code sortedSet} or any of its elements 3981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is null 399090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 400090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) { 4017dd252788645e940eada959bdde927426e2531c9Paul Duffin Comparator<? super E> comparator = SortedIterables.comparator(sortedSet); 4020888a09821a98ac0680fad765217302858e70fa4Paul Duffin ImmutableList<E> list = ImmutableList.copyOf(sortedSet); 4030888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (list.isEmpty()) { 4047dd252788645e940eada959bdde927426e2531c9Paul Duffin return emptySet(comparator); 4057dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 4060888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new RegularImmutableSortedSet<E>(list, comparator); 407090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 408090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 409090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4107dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 4110888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Constructs an {@code ImmutableSortedSet} from the first {@code n} elements of 4120888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code contents}. If {@code k} is the size of the returned {@code ImmutableSortedSet}, then 4130888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the sorted unique elements are in the first {@code k} positions of {@code contents}, and 4140888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code contents[i] == null} for {@code k <= i < n}. 4150888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4160888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>If {@code k == contents.length}, then {@code contents} may no longer be safe for 4170888a09821a98ac0680fad765217302858e70fa4Paul Duffin * modification. 4187dd252788645e940eada959bdde927426e2531c9Paul Duffin * 4197dd252788645e940eada959bdde927426e2531c9Paul Duffin * @throws NullPointerException if any of the first {@code n} elements of {@code contents} is 4207dd252788645e940eada959bdde927426e2531c9Paul Duffin * null 4217dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 4220888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <E> ImmutableSortedSet<E> construct( 4230888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<? super E> comparator, int n, E... contents) { 4247dd252788645e940eada959bdde927426e2531c9Paul Duffin if (n == 0) { 4250888a09821a98ac0680fad765217302858e70fa4Paul Duffin return emptySet(comparator); 4267dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4270888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkElementsNotNull(contents, n); 4287dd252788645e940eada959bdde927426e2531c9Paul Duffin Arrays.sort(contents, 0, n, comparator); 4297dd252788645e940eada959bdde927426e2531c9Paul Duffin int uniques = 1; 4307dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 1; i < n; i++) { 4317dd252788645e940eada959bdde927426e2531c9Paul Duffin E cur = contents[i]; 4327dd252788645e940eada959bdde927426e2531c9Paul Duffin E prev = contents[uniques - 1]; 4337dd252788645e940eada959bdde927426e2531c9Paul Duffin if (comparator.compare(cur, prev) != 0) { 4347dd252788645e940eada959bdde927426e2531c9Paul Duffin contents[uniques++] = cur; 435090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 436090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 4377dd252788645e940eada959bdde927426e2531c9Paul Duffin Arrays.fill(contents, uniques, n, null); 4380888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new RegularImmutableSortedSet<E>( 4390888a09821a98ac0680fad765217302858e70fa4Paul Duffin ImmutableList.<E>asImmutableList(contents, uniques), comparator); 440090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 441090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 442090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 443090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a builder that creates immutable sorted sets with an explicit 444090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparator. If the comparator has a more general type than the set being 445090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * generated, such as creating a {@code SortedSet<Integer>} with a 446090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code Comparator<Number>}, use the {@link Builder} constructor instead. 447090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 448090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code comparator} is null 449090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 450090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> Builder<E> orderedBy(Comparator<E> comparator) { 451090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<E>(comparator); 452090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 453090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 454090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 455090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a builder that creates immutable sorted sets whose elements are 456090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ordered by the reverse of their natural ordering. 457090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 4587dd252788645e940eada959bdde927426e2531c9Paul Duffin public static <E extends Comparable<?>> Builder<E> reverseOrder() { 459090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<E>(Ordering.natural().reverse()); 460090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 461090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 462090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 463090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a builder that creates immutable sorted sets whose elements are 464090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ordered by their natural ordering. The sorted sets use {@link 465090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Ordering#natural()} as the comparator. This method provides more 466090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * type-safety than {@link #builder}, as it can be called only for classes 467090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * that implement {@link Comparable}. 468090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 4697dd252788645e940eada959bdde927426e2531c9Paul Duffin public static <E extends Comparable<?>> Builder<E> naturalOrder() { 470090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<E>(Ordering.natural()); 471090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 472090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 473090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 4741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A builder for creating immutable sorted set instances, especially {@code 4751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * public static final} sets ("constant sets"), with a given comparator. 4761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Example: <pre> {@code 4771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS = 4791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR) 480090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * .addAll(SINGLE_DIGIT_PRIMES) 481090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * .add(42) 482090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * .build();}</pre> 483090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4840888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Builder instances can be reused; it is safe to call {@link #build} multiple 4851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * times to build multiple sets in series. Each set is a superset of the set 4861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * created before it. 4871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 489090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 490090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static final class Builder<E> extends ImmutableSet.Builder<E> { 491090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final Comparator<? super E> comparator; 492090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 493090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 494090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a new builder. The returned builder is equivalent to the builder 495090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * generated by {@link ImmutableSortedSet#orderedBy}. 496090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 497090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Builder(Comparator<? super E> comparator) { 498090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.comparator = checkNotNull(comparator); 499090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 500090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 501090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 502090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds {@code element} to the {@code ImmutableSortedSet}. If the 503090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code ImmutableSortedSet} already contains {@code element}, then 504090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code add} has no effect. (only the previously added element 505090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * is retained). 506090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 507090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param element the element to add 508090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return this {@code Builder} object 509090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code element} is null 510090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 5110888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Builder<E> add(E element) { 512090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super.add(element); 513090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this; 514090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 515090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 516090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 517090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, 518090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ignoring duplicate elements (only the first duplicate element is added). 519090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 520090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements to add 521090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return this {@code Builder} object 522090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code elements} contains a null element 523090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 5240888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Builder<E> add(E... elements) { 525090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super.add(elements); 526090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this; 527090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 528090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 529090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 530090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, 531090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ignoring duplicate elements (only the first duplicate element is added). 532090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 533090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements to add to the {@code ImmutableSortedSet} 534090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return this {@code Builder} object 535090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code elements} contains a null element 536090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 5370888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Builder<E> addAll(Iterable<? extends E> elements) { 538090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super.addAll(elements); 539090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this; 540090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 541090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 542090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 543090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, 544090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ignoring duplicate elements (only the first duplicate element is added). 545090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 546090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements to add to the {@code ImmutableSortedSet} 547090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return this {@code Builder} object 548090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code elements} contains a null element 549090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 5500888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Builder<E> addAll(Iterator<? extends E> elements) { 551090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super.addAll(elements); 552090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this; 553090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 554090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 555090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 556090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a newly-created {@code ImmutableSortedSet} based on the contents 557090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * of the {@code Builder} and its comparator. 558090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 5590888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public ImmutableSortedSet<E> build() { 5600888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") // we're careful to put only E's in here 5617dd252788645e940eada959bdde927426e2531c9Paul Duffin E[] contentsArray = (E[]) contents; 5627dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableSortedSet<E> result = construct(comparator, size, contentsArray); 5637dd252788645e940eada959bdde927426e2531c9Paul Duffin this.size = result.size(); // we eliminated duplicates in-place in contentsArray 5647dd252788645e940eada959bdde927426e2531c9Paul Duffin return result; 565090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 566090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 567090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 568090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int unsafeCompare(Object a, Object b) { 569090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return unsafeCompare(comparator, a, b); 570090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 571090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5720888a09821a98ac0680fad765217302858e70fa4Paul Duffin static int unsafeCompare( 5730888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<?> comparator, Object a, Object b) { 574090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Pretend the comparator can compare anything. If it turns out it can't 575090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // compare a and b, we should get a CCE on the subsequent line. Only methods 576090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // that are spec'd to throw CCE should call this. 577090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 578090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Comparator<Object> unsafeComparator = (Comparator<Object>) comparator; 579090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return unsafeComparator.compare(a, b); 580090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 581090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 582090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final transient Comparator<? super E> comparator; 583090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 584090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ImmutableSortedSet(Comparator<? super E> comparator) { 585090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.comparator = comparator; 586090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 587090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 588090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 589090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the comparator that orders the elements, which is 590090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Ordering#natural()} when the natural ordering of the 591090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements is used. Note that its behavior is not consistent with 592090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link SortedSet#comparator()}, which returns {@code null} to indicate 593090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * natural ordering. 594090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 5950888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 596090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Comparator<? super E> comparator() { 597090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return comparator; 598090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 599090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6000888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override // needed to unify the iterator() methods in Collection and SortedIterable 6011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public abstract UnmodifiableIterator<E> iterator(); 6021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 603090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 604090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 605090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 606090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method returns a serializable {@code ImmutableSortedSet}. 607090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 608090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The {@link SortedSet#headSet} documentation states that a subset of a 609090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * subset throws an {@link IllegalArgumentException} if passed a 610090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code toElement} greater than an earlier {@code toElement}. However, this 611090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * method doesn't throw an exception in that situation, but instead keeps the 612090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * original {@code toElement}. 613090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6140888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 615090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ImmutableSortedSet<E> headSet(E toElement) { 6161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return headSet(toElement, false); 6171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6197dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 6207dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 6217dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 6227dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 6233ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 6247dd252788645e940eada959bdde927426e2531c9Paul Duffin public ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) { 6251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return headSetImpl(checkNotNull(toElement), inclusive); 626090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 627090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 628090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 629090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 630090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 631090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method returns a serializable {@code ImmutableSortedSet}. 632090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 633090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The {@link SortedSet#subSet} documentation states that a subset of a 634090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * subset throws an {@link IllegalArgumentException} if passed a 635090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code fromElement} smaller than an earlier {@code fromElement}. However, 636090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * this method doesn't throw an exception in that situation, but instead keeps 637090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the original {@code fromElement}. Similarly, this method keeps the 638090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * original {@code toElement}, instead of throwing an exception, if passed a 639090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code toElement} greater than an earlier {@code toElement}. 640090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6410888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 642090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ImmutableSortedSet<E> subSet(E fromElement, E toElement) { 6431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return subSet(fromElement, true, toElement, false); 6441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6467dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 6477dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 6487dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 6497dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 6503ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 6510888a09821a98ac0680fad765217302858e70fa4Paul Duffin public ImmutableSortedSet<E> subSet( 6520888a09821a98ac0680fad765217302858e70fa4Paul Duffin E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 653090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(fromElement); 654090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(toElement); 655090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(comparator.compare(fromElement, toElement) <= 0); 6561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return subSetImpl(fromElement, fromInclusive, toElement, toInclusive); 657090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 658090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 659090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 660090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 661090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 662090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method returns a serializable {@code ImmutableSortedSet}. 663090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 664090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The {@link SortedSet#tailSet} documentation states that a subset of a 665090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * subset throws an {@link IllegalArgumentException} if passed a 666090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code fromElement} smaller than an earlier {@code fromElement}. However, 667090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * this method doesn't throw an exception in that situation, but instead keeps 668090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the original {@code fromElement}. 669090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6700888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 671090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ImmutableSortedSet<E> tailSet(E fromElement) { 6721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return tailSet(fromElement, true); 6731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6757dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 6767dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 6777dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 6787dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 6793ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 6807dd252788645e940eada959bdde927426e2531c9Paul Duffin public ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) { 6811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return tailSetImpl(checkNotNull(fromElement), inclusive); 682090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 683090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 684090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 685090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * These methods perform most headSet, subSet, and tailSet logic, besides 686090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * parameter validation. 687090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive); 689090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6900888a09821a98ac0680fad765217302858e70fa4Paul Duffin abstract ImmutableSortedSet<E> subSetImpl( 6910888a09821a98ac0680fad765217302858e70fa4Paul Duffin E fromElement, boolean fromInclusive, E toElement, boolean toInclusive); 6921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive); 6940888a09821a98ac0680fad765217302858e70fa4Paul Duffin 695bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor /** 6967dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 6977dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 6987dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 6993ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 7007dd252788645e940eada959bdde927426e2531c9Paul Duffin public E lower(E e) { 7017dd252788645e940eada959bdde927426e2531c9Paul Duffin return Iterators.getNext(headSet(e, false).descendingIterator(), null); 7027dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7037dd252788645e940eada959bdde927426e2531c9Paul Duffin 7047dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 7057dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 7067dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 7077dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 7083ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 7097dd252788645e940eada959bdde927426e2531c9Paul Duffin public E floor(E e) { 7107dd252788645e940eada959bdde927426e2531c9Paul Duffin return Iterators.getNext(headSet(e, true).descendingIterator(), null); 7117dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7127dd252788645e940eada959bdde927426e2531c9Paul Duffin 7137dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 7147dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 7157dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 7167dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 7173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 7187dd252788645e940eada959bdde927426e2531c9Paul Duffin public E ceiling(E e) { 7197dd252788645e940eada959bdde927426e2531c9Paul Duffin return Iterables.getFirst(tailSet(e, true), null); 7207dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7217dd252788645e940eada959bdde927426e2531c9Paul Duffin 7227dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 7237dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 7247dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 7257dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 7263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 7277dd252788645e940eada959bdde927426e2531c9Paul Duffin public E higher(E e) { 7287dd252788645e940eada959bdde927426e2531c9Paul Duffin return Iterables.getFirst(tailSet(e, false), null); 7297dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7307dd252788645e940eada959bdde927426e2531c9Paul Duffin 7310888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 7327dd252788645e940eada959bdde927426e2531c9Paul Duffin public E first() { 7337dd252788645e940eada959bdde927426e2531c9Paul Duffin return iterator().next(); 7347dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7357dd252788645e940eada959bdde927426e2531c9Paul Duffin 7360888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 7377dd252788645e940eada959bdde927426e2531c9Paul Duffin public E last() { 7387dd252788645e940eada959bdde927426e2531c9Paul Duffin return descendingIterator().next(); 7397dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7407dd252788645e940eada959bdde927426e2531c9Paul Duffin 7417dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 7427dd252788645e940eada959bdde927426e2531c9Paul Duffin * Guaranteed to throw an exception and leave the set unmodified. 7437dd252788645e940eada959bdde927426e2531c9Paul Duffin * 7447dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 7457dd252788645e940eada959bdde927426e2531c9Paul Duffin * @throws UnsupportedOperationException always 7467dd252788645e940eada959bdde927426e2531c9Paul Duffin * @deprecated Unsupported operation. 7477dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 7487dd252788645e940eada959bdde927426e2531c9Paul Duffin @Deprecated 7497dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 7503ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 7517dd252788645e940eada959bdde927426e2531c9Paul Duffin public final E pollFirst() { 7527dd252788645e940eada959bdde927426e2531c9Paul Duffin throw new UnsupportedOperationException(); 7537dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7547dd252788645e940eada959bdde927426e2531c9Paul Duffin 7557dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 7567dd252788645e940eada959bdde927426e2531c9Paul Duffin * Guaranteed to throw an exception and leave the set unmodified. 7577dd252788645e940eada959bdde927426e2531c9Paul Duffin * 7587dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 7597dd252788645e940eada959bdde927426e2531c9Paul Duffin * @throws UnsupportedOperationException always 7607dd252788645e940eada959bdde927426e2531c9Paul Duffin * @deprecated Unsupported operation. 7617dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 7627dd252788645e940eada959bdde927426e2531c9Paul Duffin @Deprecated 7637dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 7643ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 7657dd252788645e940eada959bdde927426e2531c9Paul Duffin public final E pollLast() { 7667dd252788645e940eada959bdde927426e2531c9Paul Duffin throw new UnsupportedOperationException(); 7677dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7687dd252788645e940eada959bdde927426e2531c9Paul Duffin 7697dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 7707dd252788645e940eada959bdde927426e2531c9Paul Duffin transient ImmutableSortedSet<E> descendingSet; 7717dd252788645e940eada959bdde927426e2531c9Paul Duffin 7727dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 7737dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 7747dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 7757dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 7763ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 7777dd252788645e940eada959bdde927426e2531c9Paul Duffin public ImmutableSortedSet<E> descendingSet() { 7787dd252788645e940eada959bdde927426e2531c9Paul Duffin // racy single-check idiom 7797dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableSortedSet<E> result = descendingSet; 7807dd252788645e940eada959bdde927426e2531c9Paul Duffin if (result == null) { 7817dd252788645e940eada959bdde927426e2531c9Paul Duffin result = descendingSet = createDescendingSet(); 7827dd252788645e940eada959bdde927426e2531c9Paul Duffin result.descendingSet = this; 7837dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7847dd252788645e940eada959bdde927426e2531c9Paul Duffin return result; 7857dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7867dd252788645e940eada959bdde927426e2531c9Paul Duffin 7877dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 7887dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableSortedSet<E> createDescendingSet() { 7897dd252788645e940eada959bdde927426e2531c9Paul Duffin return new DescendingImmutableSortedSet<E>(this); 7907dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7917dd252788645e940eada959bdde927426e2531c9Paul Duffin 7927dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 7937dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 7947dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 7957dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("NavigableSet") 7963ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 7977dd252788645e940eada959bdde927426e2531c9Paul Duffin public abstract UnmodifiableIterator<E> descendingIterator(); 7987dd252788645e940eada959bdde927426e2531c9Paul Duffin 7997dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 800bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Returns the position of an element within the set, or -1 if not present. 801bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor */ 8021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert abstract int indexOf(@Nullable Object target); 803bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 804090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 805090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This class is used to serialize all ImmutableSortedSet instances, 806090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * regardless of implementation type. It captures their "logical contents" 807090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * only. This is necessary to ensure that the existence of a particular 808090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementation type is an implementation detail. 809090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 810090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static class SerializedForm<E> implements Serializable { 811090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Comparator<? super E> comparator; 812090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Object[] elements; 813090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 814090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public SerializedForm(Comparator<? super E> comparator, Object[] elements) { 815090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.comparator = comparator; 816090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.elements = elements; 817090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 818090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 819090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 820090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Object readResolve() { 821090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<E>(comparator).add((E[]) elements).build(); 822090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 823090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 824090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 825090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 826090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8270888a09821a98ac0680fad765217302858e70fa4Paul Duffin private void readObject(ObjectInputStream stream) 8280888a09821a98ac0680fad765217302858e70fa4Paul Duffin throws InvalidObjectException { 829090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new InvalidObjectException("Use SerializedForm"); 830090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 831090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8320888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override Object writeReplace() { 833090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SerializedForm<E>(comparator, toArray()); 834090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 835090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 8360888a09821a98ac0680fad765217302858e70fa4Paul Duffin 837