diff options
Diffstat (limited to 'guava/src/com/google/common/collect/Ordering.java')
| -rw-r--r-- | guava/src/com/google/common/collect/Ordering.java | 718 |
1 files changed, 280 insertions, 438 deletions
diff --git a/guava/src/com/google/common/collect/Ordering.java b/guava/src/com/google/common/collect/Ordering.java index 9ee9c48..1f0c6e3 100644 --- a/guava/src/com/google/common/collect/Ordering.java +++ b/guava/src/com/google/common/collect/Ordering.java @@ -19,13 +19,12 @@ package com.google.common.collect; import static com.google.common.base.Preconditions.checkArgument; import static com.google.common.base.Preconditions.checkNotNull; +import com.google.common.annotations.Beta; import com.google.common.annotations.GwtCompatible; import com.google.common.annotations.VisibleForTesting; import com.google.common.base.Function; -import java.util.ArrayList; import java.util.Arrays; -import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.HashSet; @@ -35,15 +34,13 @@ import java.util.Map; import java.util.NoSuchElementException; import java.util.SortedMap; import java.util.SortedSet; -import java.util.TreeSet; import java.util.concurrent.atomic.AtomicInteger; import javax.annotation.Nullable; /** - * A comparator, with additional methods to support common operations. This is - * an "enriched" version of {@code Comparator}, in the same sense that {@link - * FluentIterable} is an enriched {@link Iterable}). For example: <pre> {@code + * A comparator with added methods to support common functions. For example: + * <pre> {@code * * if (Ordering.from(comparator).reverse().isOrdered(list)) { ... }}</pre> * @@ -62,17 +59,13 @@ import javax.annotation.Nullable; * are. For example, if {@code ordering} and {@code function} can themselves be * serialized, then {@code ordering.onResultOf(function)} can as well. * - * <p>See the Guava User Guide article on <a href= - * "http://code.google.com/p/guava-libraries/wiki/OrderingExplained"> - * {@code Ordering}</a>. - * * @author Jesse Wilson * @author Kevin Bourrillion * @since 2.0 (imported from Google Collections Library) */ @GwtCompatible public abstract class Ordering<T> implements Comparator<T> { - // Natural order + // Static factories /** * Returns a serializable ordering that uses the natural order of the values. @@ -89,17 +82,13 @@ public abstract class Ordering<T> implements Comparator<T> { return (Ordering<C>) NaturalOrdering.INSTANCE; } - // Static factories - /** - * Returns an ordering based on an <i>existing</i> comparator instance. Note - * that there's no need to create a <i>new</i> comparator just to pass it in - * here; simply subclass {@code Ordering} and implement its {@code compareTo} - * method directly instead. + * Returns an ordering for a pre-existing {@code comparator}. Note + * that if the comparator is not pre-existing, and you don't require + * serialization, you can subclass {@code Ordering} and implement its + * {@link #compare(Object, Object) compare} method instead. * * @param comparator the comparator that defines the order - * @return comparator itself if it is already an {@code Ordering}; otherwise - * an ordering that wraps that comparator */ @GwtCompatible(serializable = true) public static <T> Ordering<T> from(Comparator<T> comparator) { @@ -173,48 +162,23 @@ public abstract class Ordering<T> implements Comparator<T> { return explicit(Lists.asList(leastValue, remainingValuesInOrder)); } - // Ordering<Object> singletons - /** - * Returns an ordering which treats all values as equal, indicating "no - * ordering." Passing this ordering to any <i>stable</i> sort algorithm - * results in no change to the order of elements. Note especially that {@link - * #sortedCopy} and {@link #immutableSortedCopy} are stable, and in the - * returned instance these are implemented by simply copying the source list. - * - * <p>Example: <pre> {@code - * - * Ordering.allEqual().nullsLast().sortedCopy( - * asList(t, null, e, s, null, t, null))}</pre> - * - * Assuming {@code t}, {@code e} and {@code s} are non-null, this returns - * {@code [t, e, s, t, null, null, null]} regardlesss of the true comparison - * order of those three values (which might not even implement {@link - * Comparable} at all). - * - * <p><b>Warning:</b> by definition, this comparator is not <i>consistent with - * equals</i> (as defined {@linkplain Comparator here}). Avoid its use in - * APIs, such as {@link TreeSet#TreeSet(Comparator)}, where such consistency - * is expected. - * - * <p>The returned comparator is serializable. + * Exception thrown by a {@link Ordering#explicit(List)} or {@link + * Ordering#explicit(Object, Object[])} comparator when comparing a value + * outside the set of values it can compare. Extending {@link + * ClassCastException} may seem odd, but it is required. */ - @GwtCompatible(serializable = true) - @SuppressWarnings("unchecked") - public static Ordering<Object> allEqual() { - return AllEqualOrdering.INSTANCE; - } + // TODO(kevinb): make this public, document it right + @VisibleForTesting + static class IncomparableValueException extends ClassCastException { + final Object value; - /** - * Returns an ordering that compares objects by the natural ordering of their - * string representations as returned by {@code toString()}. It does not - * support null values. - * - * <p>The comparator is serializable. - */ - @GwtCompatible(serializable = true) - public static Ordering<Object> usingToString() { - return UsingToStringOrdering.INSTANCE; + IncomparableValueException(Object value) { + super("Cannot compare value: " + value); + this.value = value; + } + + private static final long serialVersionUID = 0; } /** @@ -256,10 +220,6 @@ public abstract class Ordering<T> implements Comparator<T> { @Override public int compare(Object left, Object right) { if (left == right) { return 0; - } else if (left == null) { - return -1; - } else if (right == null) { - return 1; } int leftCode = identityHashCode(left); int rightCode = identityHashCode(right); @@ -292,62 +252,46 @@ public abstract class Ordering<T> implements Comparator<T> { } } - // Constructor - /** - * Constructs a new instance of this class (only invokable by the subclass - * constructor, typically implicit). - */ - protected Ordering() {} - - // Instance-based factories (and any static equivalents) - - /** - * Returns the reverse of this ordering; the {@code Ordering} equivalent to - * {@link Collections#reverseOrder(Comparator)}. + * Returns an ordering that compares objects by the natural ordering of their + * string representations as returned by {@code toString()}. It does not + * support null values. + * + * <p>The comparator is serializable. */ - // type parameter <S> lets us avoid the extra <String> in statements like: - // Ordering<String> o = Ordering.<String>natural().reverse(); @GwtCompatible(serializable = true) - public <S extends T> Ordering<S> reverse() { - return new ReverseOrdering<S>(this); + public static Ordering<Object> usingToString() { + return UsingToStringOrdering.INSTANCE; } /** - * Returns an ordering that treats {@code null} as less than all other values - * and uses {@code this} to compare non-null values. + * Returns an ordering which tries each given comparator in order until a + * non-zero result is found, returning that result, and returning zero only if + * all comparators return zero. The returned ordering is based on the state of + * the {@code comparators} iterable at the time it was provided to this + * method. + * + * <p>The returned ordering is equivalent to that produced using {@code + * Ordering.from(comp1).compound(comp2).compound(comp3) . . .}. + * + * <p><b>Warning:</b> Supplying an argument with undefined iteration order, + * such as a {@link HashSet}, will produce non-deterministic results. + * + * @param comparators the comparators to try in order */ - // type parameter <S> lets us avoid the extra <String> in statements like: - // Ordering<String> o = Ordering.<String>natural().nullsFirst(); @GwtCompatible(serializable = true) - public <S extends T> Ordering<S> nullsFirst() { - return new NullsFirstOrdering<S>(this); + public static <T> Ordering<T> compound( + Iterable<? extends Comparator<? super T>> comparators) { + return new CompoundOrdering<T>(comparators); } /** - * Returns an ordering that treats {@code null} as greater than all other - * values and uses this ordering to compare non-null values. + * Constructs a new instance of this class (only invokable by the subclass + * constructor, typically implicit). */ - // type parameter <S> lets us avoid the extra <String> in statements like: - // Ordering<String> o = Ordering.<String>natural().nullsLast(); - @GwtCompatible(serializable = true) - public <S extends T> Ordering<S> nullsLast() { - return new NullsLastOrdering<S>(this); - } + protected Ordering() {} - /** - * Returns a new ordering on {@code F} which orders elements by first applying - * a function to them, then comparing those results using {@code this}. For - * example, to compare objects by their string forms, in a case-insensitive - * manner, use: <pre> {@code - * - * Ordering.from(String.CASE_INSENSITIVE_ORDER) - * .onResultOf(Functions.toStringFunction())}</pre> - */ - @GwtCompatible(serializable = true) - public <F> Ordering<F> onResultOf(Function<F, ? extends T> function) { - return new ByFunctionOrdering<F, T>(function, this); - } + // Non-static factories /** * Returns an ordering which first uses the ordering {@code this}, but which @@ -367,24 +311,28 @@ public abstract class Ordering<T> implements Comparator<T> { } /** - * Returns an ordering which tries each given comparator in order until a - * non-zero result is found, returning that result, and returning zero only if - * all comparators return zero. The returned ordering is based on the state of - * the {@code comparators} iterable at the time it was provided to this - * method. - * - * <p>The returned ordering is equivalent to that produced using {@code - * Ordering.from(comp1).compound(comp2).compound(comp3) . . .}. - * - * <p><b>Warning:</b> Supplying an argument with undefined iteration order, - * such as a {@link HashSet}, will produce non-deterministic results. + * Returns the reverse of this ordering; the {@code Ordering} equivalent to + * {@link Collections#reverseOrder(Comparator)}. + */ + // type parameter <S> lets us avoid the extra <String> in statements like: + // Ordering<String> o = Ordering.<String>natural().reverse(); + @GwtCompatible(serializable = true) + public <S extends T> Ordering<S> reverse() { + return new ReverseOrdering<S>(this); + } + + /** + * Returns a new ordering on {@code F} which orders elements by first applying + * a function to them, then comparing those results using {@code this}. For + * example, to compare objects by their string forms, in a case-insensitive + * manner, use: <pre> {@code * - * @param comparators the comparators to try in order + * Ordering.from(String.CASE_INSENSITIVE_ORDER) + * .onResultOf(Functions.toStringFunction())}</pre> */ @GwtCompatible(serializable = true) - public static <T> Ordering<T> compound( - Iterable<? extends Comparator<? super T>> comparators) { - return new CompoundOrdering<T>(comparators); + public <F> Ordering<F> onResultOf(Function<F, ? extends T> function) { + return new ByFunctionOrdering<F, T>(function, this); } /** @@ -416,162 +364,32 @@ public abstract class Ordering<T> implements Comparator<T> { return new LexicographicalOrdering<S>(this); } - // Regular instance methods - - // Override to add @Nullable - @Override public abstract int compare(@Nullable T left, @Nullable T right); - - /** - * Returns the least of the specified values according to this ordering. If - * there are multiple least values, the first of those is returned. The - * iterator will be left exhausted: its {@code hasNext()} method will return - * {@code false}. - * - * @param iterator the iterator whose minimum element is to be determined - * @throws NoSuchElementException if {@code iterator} is empty - * @throws ClassCastException if the parameters are not <i>mutually - * comparable</i> under this ordering. - * - * @since 11.0 - */ - public <E extends T> E min(Iterator<E> iterator) { - // let this throw NoSuchElementException as necessary - E minSoFar = iterator.next(); - - while (iterator.hasNext()) { - minSoFar = min(minSoFar, iterator.next()); - } - - return minSoFar; - } - - /** - * Returns the least of the specified values according to this ordering. If - * there are multiple least values, the first of those is returned. - * - * @param iterable the iterable whose minimum element is to be determined - * @throws NoSuchElementException if {@code iterable} is empty - * @throws ClassCastException if the parameters are not <i>mutually - * comparable</i> under this ordering. - */ - public <E extends T> E min(Iterable<E> iterable) { - return min(iterable.iterator()); - } - - /** - * Returns the lesser of the two values according to this ordering. If the - * values compare as 0, the first is returned. - * - * <p><b>Implementation note:</b> this method is invoked by the default - * implementations of the other {@code min} overloads, so overriding it will - * affect their behavior. - * - * @param a value to compare, returned if less than or equal to b. - * @param b value to compare. - * @throws ClassCastException if the parameters are not <i>mutually - * comparable</i> under this ordering. - */ - public <E extends T> E min(@Nullable E a, @Nullable E b) { - return (compare(a, b) <= 0) ? a : b; - } - - /** - * Returns the least of the specified values according to this ordering. If - * there are multiple least values, the first of those is returned. - * - * @param a value to compare, returned if less than or equal to the rest. - * @param b value to compare - * @param c value to compare - * @param rest values to compare - * @throws ClassCastException if the parameters are not <i>mutually - * comparable</i> under this ordering. - */ - public <E extends T> E min( - @Nullable E a, @Nullable E b, @Nullable E c, E... rest) { - E minSoFar = min(min(a, b), c); - - for (E r : rest) { - minSoFar = min(minSoFar, r); - } - - return minSoFar; - } - /** - * Returns the greatest of the specified values according to this ordering. If - * there are multiple greatest values, the first of those is returned. The - * iterator will be left exhausted: its {@code hasNext()} method will return - * {@code false}. - * - * @param iterator the iterator whose maximum element is to be determined - * @throws NoSuchElementException if {@code iterator} is empty - * @throws ClassCastException if the parameters are not <i>mutually - * comparable</i> under this ordering. - * - * @since 11.0 - */ - public <E extends T> E max(Iterator<E> iterator) { - // let this throw NoSuchElementException as necessary - E maxSoFar = iterator.next(); - - while (iterator.hasNext()) { - maxSoFar = max(maxSoFar, iterator.next()); - } - - return maxSoFar; - } - - /** - * Returns the greatest of the specified values according to this ordering. If - * there are multiple greatest values, the first of those is returned. - * - * @param iterable the iterable whose maximum element is to be determined - * @throws NoSuchElementException if {@code iterable} is empty - * @throws ClassCastException if the parameters are not <i>mutually - * comparable</i> under this ordering. + * Returns an ordering that treats {@code null} as less than all other values + * and uses {@code this} to compare non-null values. */ - public <E extends T> E max(Iterable<E> iterable) { - return max(iterable.iterator()); + // type parameter <S> lets us avoid the extra <String> in statements like: + // Ordering<String> o = Ordering.<String>natural().nullsFirst(); + @GwtCompatible(serializable = true) + public <S extends T> Ordering<S> nullsFirst() { + return new NullsFirstOrdering<S>(this); } /** - * Returns the greater of the two values according to this ordering. If the - * values compare as 0, the first is returned. - * - * <p><b>Implementation note:</b> this method is invoked by the default - * implementations of the other {@code max} overloads, so overriding it will - * affect their behavior. - * - * @param a value to compare, returned if greater than or equal to b. - * @param b value to compare. - * @throws ClassCastException if the parameters are not <i>mutually - * comparable</i> under this ordering. + * Returns an ordering that treats {@code null} as greater than all other + * values and uses this ordering to compare non-null values. */ - public <E extends T> E max(@Nullable E a, @Nullable E b) { - return (compare(a, b) >= 0) ? a : b; + // type parameter <S> lets us avoid the extra <String> in statements like: + // Ordering<String> o = Ordering.<String>natural().nullsLast(); + @GwtCompatible(serializable = true) + public <S extends T> Ordering<S> nullsLast() { + return new NullsLastOrdering<S>(this); } - /** - * Returns the greatest of the specified values according to this ordering. If - * there are multiple greatest values, the first of those is returned. - * - * @param a value to compare, returned if greater than or equal to the rest. - * @param b value to compare - * @param c value to compare - * @param rest values to compare - * @throws ClassCastException if the parameters are not <i>mutually - * comparable</i> under this ordering. - */ - public <E extends T> E max( - @Nullable E a, @Nullable E b, @Nullable E c, E... rest) { - E maxSoFar = max(max(a, b), c); - - for (E r : rest) { - maxSoFar = max(maxSoFar, r); - } + // Regular instance methods - return maxSoFar; - } + // Override to add @Nullable + @Override public abstract int compare(@Nullable T left, @Nullable T right); /** * Returns the {@code k} least elements of the given iterable according to @@ -587,130 +405,64 @@ public abstract class Ordering<T> implements Comparator<T> { * @throws IllegalArgumentException if {@code k} is negative * @since 8.0 */ + @Beta public <E extends T> List<E> leastOf(Iterable<E> iterable, int k) { - if (iterable instanceof Collection) { - Collection<E> collection = (Collection<E>) iterable; - if (collection.size() <= 2L * k) { - // In this case, just dumping the collection to an array and sorting is - // faster than using the implementation for Iterator, which is - // specialized for k much smaller than n. - - @SuppressWarnings("unchecked") // c only contains E's and doesn't escape - E[] array = (E[]) collection.toArray(); - Arrays.sort(array, this); - if (array.length > k) { - array = ObjectArrays.arraysCopyOf(array, k); - } - return Collections.unmodifiableList(Arrays.asList(array)); - } + checkArgument(k >= 0, "%d is negative", k); + + // values is not an E[], but we use it as such for readability. Hack. + @SuppressWarnings("unchecked") + E[] values = (E[]) Iterables.toArray(iterable); + + // TODO(nshupe): also sort whole list if k is *near* values.length? + // TODO(kevinb): benchmark this impl against hand-coded heap + E[] resultArray; + if (values.length <= k) { + Arrays.sort(values, this); + resultArray = values; + } else { + quicksortLeastK(values, 0, values.length - 1, k); + + // this is not an E[], but we use it as such for readability. Hack. + @SuppressWarnings("unchecked") + E[] tmp = (E[]) new Object[k]; + resultArray = tmp; + System.arraycopy(values, 0, resultArray, 0, k); } - return leastOf(iterable.iterator(), k); + + return Collections.unmodifiableList(Arrays.asList(resultArray)); } /** - * Returns the {@code k} least elements from the given iterator according to - * this ordering, in order from least to greatest. If there are fewer than + * Returns the {@code k} greatest elements of the given iterable according to + * this ordering, in order from greatest to least. If there are fewer than * {@code k} elements present, all will be included. * * <p>The implementation does not necessarily use a <i>stable</i> sorting * algorithm; when multiple elements are equivalent, it is undefined which * will come first. * - * @return an immutable {@code RandomAccess} list of the {@code k} least - * elements in ascending order + * @return an immutable {@code RandomAccess} list of the {@code k} greatest + * elements in <i>descending order</i> * @throws IllegalArgumentException if {@code k} is negative - * @since 14.0 + * @since 8.0 */ - public <E extends T> List<E> leastOf(Iterator<E> elements, int k) { - checkNotNull(elements); - checkArgument(k >= 0, "k (%s) must be nonnegative", k); - - if (k == 0 || !elements.hasNext()) { - return ImmutableList.of(); - } else if (k >= Integer.MAX_VALUE / 2) { - // k is really large; just do a straightforward sorted-copy-and-sublist - ArrayList<E> list = Lists.newArrayList(elements); - Collections.sort(list, this); - if (list.size() > k) { - list.subList(k, list.size()).clear(); - } - list.trimToSize(); - return Collections.unmodifiableList(list); - } - - /* - * Our goal is an O(n) algorithm using only one pass and O(k) additional - * memory. - * - * We use the following algorithm: maintain a buffer of size 2*k. Every time - * the buffer gets full, find the median and partition around it, keeping - * only the lowest k elements. This requires n/k find-median-and-partition - * steps, each of which take O(k) time with a traditional quickselect. - * - * After sorting the output, the whole algorithm is O(n + k log k). It - * degrades gracefully for worst-case input (descending order), performs - * competitively or wins outright for randomly ordered input, and doesn't - * require the whole collection to fit into memory. - */ - int bufferCap = k * 2; - @SuppressWarnings("unchecked") // we'll only put E's in - E[] buffer = (E[]) new Object[bufferCap]; - E threshold = elements.next(); - buffer[0] = threshold; - int bufferSize = 1; - // threshold is the kth smallest element seen so far. Once bufferSize >= k, - // anything larger than threshold can be ignored immediately. - - while (bufferSize < k && elements.hasNext()) { - E e = elements.next(); - buffer[bufferSize++] = e; - threshold = max(threshold, e); - } - - while (elements.hasNext()) { - E e = elements.next(); - if (compare(e, threshold) >= 0) { - continue; - } - - buffer[bufferSize++] = e; - if (bufferSize == bufferCap) { - // We apply the quickselect algorithm to partition about the median, - // and then ignore the last k elements. - int left = 0; - int right = bufferCap - 1; - - int minThresholdPosition = 0; - // The leftmost position at which the greatest of the k lower elements - // -- the new value of threshold -- might be found. - - while (left < right) { - int pivotIndex = (left + right + 1) >>> 1; - int pivotNewIndex = partition(buffer, left, right, pivotIndex); - if (pivotNewIndex > k) { - right = pivotNewIndex - 1; - } else if (pivotNewIndex < k) { - left = Math.max(pivotNewIndex, left + 1); - minThresholdPosition = pivotNewIndex; - } else { - break; - } - } - bufferSize = k; + @Beta + public <E extends T> List<E> greatestOf(Iterable<E> iterable, int k) { + // TODO(kevinb): see if delegation is hurting performance noticeably + // TODO(kevinb): if we change this implementation, add full unit tests. + return reverse().leastOf(iterable, k); + } - threshold = buffer[minThresholdPosition]; - for (int i = minThresholdPosition + 1; i < bufferSize; i++) { - threshold = max(threshold, buffer[i]); - } + private <E extends T> void quicksortLeastK( + E[] values, int left, int right, int k) { + if (right > left) { + int pivotIndex = (left + right) >>> 1; // left + ((right - left) / 2) + int pivotNewIndex = partition(values, left, right, pivotIndex); + quicksortLeastK(values, left, pivotNewIndex - 1, k); + if (pivotNewIndex < k) { + quicksortLeastK(values, pivotNewIndex + 1, right, k); } } - - Arrays.sort(buffer, 0, bufferSize, this); - - bufferSize = Math.min(bufferSize, k); - return Collections.unmodifiableList( - Arrays.asList(ObjectArrays.arraysCopyOf(buffer, bufferSize))); - // We can't use ImmutableList; we have to be null-friendly! } private <E extends T> int partition( @@ -732,41 +484,15 @@ public abstract class Ordering<T> implements Comparator<T> { } /** - * Returns the {@code k} greatest elements of the given iterable according to - * this ordering, in order from greatest to least. If there are fewer than - * {@code k} elements present, all will be included. - * - * <p>The implementation does not necessarily use a <i>stable</i> sorting - * algorithm; when multiple elements are equivalent, it is undefined which - * will come first. - * - * @return an immutable {@code RandomAccess} list of the {@code k} greatest - * elements in <i>descending order</i> - * @throws IllegalArgumentException if {@code k} is negative - * @since 8.0 - */ - public <E extends T> List<E> greatestOf(Iterable<E> iterable, int k) { - // TODO(kevinb): see if delegation is hurting performance noticeably - // TODO(kevinb): if we change this implementation, add full unit tests. - return reverse().leastOf(iterable, k); - } - - /** - * Returns the {@code k} greatest elements from the given iterator according to - * this ordering, in order from greatest to least. If there are fewer than - * {@code k} elements present, all will be included. - * - * <p>The implementation does not necessarily use a <i>stable</i> sorting - * algorithm; when multiple elements are equivalent, it is undefined which - * will come first. + * {@link Collections#binarySearch(List, Object, Comparator) Searches} + * {@code sortedList} for {@code key} using the binary search algorithm. The + * list must be sorted using this ordering. * - * @return an immutable {@code RandomAccess} list of the {@code k} greatest - * elements in <i>descending order</i> - * @throws IllegalArgumentException if {@code k} is negative - * @since 14.0 + * @param sortedList the list to be searched + * @param key the key to be searched for */ - public <E extends T> List<E> greatestOf(Iterator<E> iterator, int k) { - return reverse().leastOf(iterator, k); + public int binarySearch(List<? extends T> sortedList, @Nullable T key) { + return Collections.binarySearch(sortedList, key, this); } /** @@ -783,10 +509,9 @@ public abstract class Ordering<T> implements Comparator<T> { * @return a new list containing the given elements in sorted order */ public <E extends T> List<E> sortedCopy(Iterable<E> iterable) { - @SuppressWarnings("unchecked") // does not escape, and contains only E's - E[] array = (E[]) Iterables.toArray(iterable); - Arrays.sort(array, this); - return Lists.newArrayList(Arrays.asList(array)); + List<E> list = Lists.newArrayList(iterable); + Collections.sort(list, this); + return list; } /** @@ -806,13 +531,7 @@ public abstract class Ordering<T> implements Comparator<T> { */ public <E extends T> ImmutableList<E> immutableSortedCopy( Iterable<E> iterable) { - @SuppressWarnings("unchecked") // we'll only ever have E's in here - E[] elements = (E[]) Iterables.toArray(iterable); - for (E e : elements) { - checkNotNull(e); - } - Arrays.sort(elements, this); - return ImmutableList.asImmutableList(elements); + return ImmutableList.copyOf(sortedCopy(iterable)); } /** @@ -858,34 +577,157 @@ public abstract class Ordering<T> implements Comparator<T> { } /** - * {@link Collections#binarySearch(List, Object, Comparator) Searches} - * {@code sortedList} for {@code key} using the binary search algorithm. The - * list must be sorted using this ordering. + * Returns the greatest of the specified values according to this ordering. If + * there are multiple greatest values, the first of those is returned. The + * iterator will be left exhausted: its {@code hasNext()} method will return + * {@code false}. * - * @param sortedList the list to be searched - * @param key the key to be searched for + * @param iterator the iterator whose maximum element is to be determined + * @throws NoSuchElementException if {@code iterator} is empty + * @throws ClassCastException if the parameters are not <i>mutually + * comparable</i> under this ordering. + * + * @since 11.0 */ - public int binarySearch(List<? extends T> sortedList, @Nullable T key) { - return Collections.binarySearch(sortedList, key, this); + @Beta + public <E extends T> E max(Iterator<E> iterator) { + // let this throw NoSuchElementException as necessary + E maxSoFar = iterator.next(); + + while (iterator.hasNext()) { + maxSoFar = max(maxSoFar, iterator.next()); + } + + return maxSoFar; } /** - * Exception thrown by a {@link Ordering#explicit(List)} or {@link - * Ordering#explicit(Object, Object[])} comparator when comparing a value - * outside the set of values it can compare. Extending {@link - * ClassCastException} may seem odd, but it is required. + * Returns the greatest of the specified values according to this ordering. If + * there are multiple greatest values, the first of those is returned. + * + * @param iterable the iterable whose maximum element is to be determined + * @throws NoSuchElementException if {@code iterable} is empty + * @throws ClassCastException if the parameters are not <i>mutually + * comparable</i> under this ordering. */ - // TODO(kevinb): make this public, document it right - @VisibleForTesting - static class IncomparableValueException extends ClassCastException { - final Object value; + public <E extends T> E max(Iterable<E> iterable) { + return max(iterable.iterator()); + } - IncomparableValueException(Object value) { - super("Cannot compare value: " + value); - this.value = value; + /** + * Returns the greatest of the specified values according to this ordering. If + * there are multiple greatest values, the first of those is returned. + * + * @param a value to compare, returned if greater than or equal to the rest. + * @param b value to compare + * @param c value to compare + * @param rest values to compare + * @throws ClassCastException if the parameters are not <i>mutually + * comparable</i> under this ordering. + */ + public <E extends T> E max( + @Nullable E a, @Nullable E b, @Nullable E c, E... rest) { + E maxSoFar = max(max(a, b), c); + + for (E r : rest) { + maxSoFar = max(maxSoFar, r); } - private static final long serialVersionUID = 0; + return maxSoFar; + } + + /** + * Returns the greater of the two values according to this ordering. If the + * values compare as 0, the first is returned. + * + * <p><b>Implementation note:</b> this method is invoked by the default + * implementations of the other {@code max} overloads, so overriding it will + * affect their behavior. + * + * @param a value to compare, returned if greater than or equal to b. + * @param b value to compare. + * @throws ClassCastException if the parameters are not <i>mutually + * comparable</i> under this ordering. + */ + public <E extends T> E max(@Nullable E a, @Nullable E b) { + return compare(a, b) >= 0 ? a : b; + } + + /** + * Returns the least of the specified values according to this ordering. If + * there are multiple least values, the first of those is returned. The + * iterator will be left exhausted: its {@code hasNext()} method will return + * {@code false}. + * + * @param iterator the iterator whose minimum element is to be determined + * @throws NoSuchElementException if {@code iterator} is empty + * @throws ClassCastException if the parameters are not <i>mutually + * comparable</i> under this ordering. + * + * @since 11.0 + */ + @Beta + public <E extends T> E min(Iterator<E> iterator) { + // let this throw NoSuchElementException as necessary + E minSoFar = iterator.next(); + + while (iterator.hasNext()) { + minSoFar = min(minSoFar, iterator.next()); + } + + return minSoFar; + } + + /** + * Returns the least of the specified values according to this ordering. If + * there are multiple least values, the first of those is returned. + * + * @param iterable the iterable whose minimum element is to be determined + * @throws NoSuchElementException if {@code iterable} is empty + * @throws ClassCastException if the parameters are not <i>mutually + * comparable</i> under this ordering. + */ + public <E extends T> E min(Iterable<E> iterable) { + return min(iterable.iterator()); + } + + /** + * Returns the least of the specified values according to this ordering. If + * there are multiple least values, the first of those is returned. + * + * @param a value to compare, returned if less than or equal to the rest. + * @param b value to compare + * @param c value to compare + * @param rest values to compare + * @throws ClassCastException if the parameters are not <i>mutually + * comparable</i> under this ordering. + */ + public <E extends T> E min( + @Nullable E a, @Nullable E b, @Nullable E c, E... rest) { + E minSoFar = min(min(a, b), c); + + for (E r : rest) { + minSoFar = min(minSoFar, r); + } + + return minSoFar; + } + + /** + * Returns the lesser of the two values according to this ordering. If the + * values compare as 0, the first is returned. + * + * <p><b>Implementation note:</b> this method is invoked by the default + * implementations of the other {@code min} overloads, so overriding it will + * affect their behavior. + * + * @param a value to compare, returned if less than or equal to b. + * @param b value to compare. + * @throws ClassCastException if the parameters are not <i>mutually + * comparable</i> under this ordering. + */ + public <E extends T> E min(@Nullable E a, @Nullable E b) { + return compare(a, b) <= 0 ? a : b; } // Never make these public |