1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 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 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkArgument; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.Beta; 23090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.GwtCompatible; 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.VisibleForTesting; 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Function; 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Arrays; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collections; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Comparator; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.HashSet; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.List; 33bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport java.util.Map; 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.NoSuchElementException; 35bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport java.util.SortedMap; 36bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport java.util.SortedSet; 37bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport java.util.concurrent.atomic.AtomicInteger; 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * A comparator with added methods to support common functions. For example: 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <pre> {@code 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * if (Ordering.from(comparator).reverse().isOrdered(list)) { ... }}</pre> 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * The {@link #from(Comparator)} method returns the equivalent {@code Ordering} 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * instance for a pre-existing comparator. You can also skip the comparator step 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * and extend {@code Ordering} directly: <pre> {@code 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Ordering<String> byLengthOrdering = new Ordering<String>() { 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * public int compare(String left, String right) { 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * return Ints.compare(left.length(), right.length()); 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * } 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * };}</pre> 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Except as noted, the orderings returned by the factory methods of this 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * class are serializable if and only if the provided instances that back them 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * are. For example, if {@code ordering} and {@code function} can themselves be 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * serialized, then {@code ordering.onResultOf(function)} can as well. 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Jesse Wilson 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Kevin Bourrillion 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@GwtCompatible 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic abstract class Ordering<T> implements Comparator<T> { 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Static factories 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a serializable ordering that uses the natural order of the values. 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * The ordering throws a {@link NullPointerException} when passed a null 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * parameter. 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The type specification is {@code <C extends Comparable>}, instead of 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the technically correct {@code <C extends Comparable<? super C>>}, to 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * support legacy types from before Java 5. 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") // TODO(kevinb): right way to explain this?? 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <C extends Comparable> Ordering<C> natural() { 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (Ordering<C>) NaturalOrdering.INSTANCE; 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an ordering for a pre-existing {@code comparator}. Note 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * that if the comparator is not pre-existing, and you don't require 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * serialization, you can subclass {@code Ordering} and implement its 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #compare(Object, Object) compare} method instead. 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param comparator the comparator that defines the order 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <T> Ordering<T> from(Comparator<T> comparator) { 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (comparator instanceof Ordering) 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ? (Ordering<T>) comparator 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson : new ComparatorOrdering<T>(comparator); 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Simply returns its argument. 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @deprecated no need to use this 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Deprecated public static <T> Ordering<T> from(Ordering<T> ordering) { 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return checkNotNull(ordering); 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an ordering that compares objects according to the order in 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * which they appear in the given list. Only objects present in the list 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * (according to {@link Object#equals}) may be compared. This comparator 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * imposes a "partial ordering" over the type {@code T}. Subsequent changes 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to the {@code valuesInOrder} list will have no effect on the returned 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparator. Null values in the list are not supported. 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned comparator throws an {@link ClassCastException} when it 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * receives an input parameter that isn't among the provided values. 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The generated comparator is serializable if all the provided values are 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * serializable. 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param valuesInOrder the values that the returned comparator will be able 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to compare, in the order the comparator should induce 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return the comparator described above 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any of the provided values is null 128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code valuesInOrder} contains any 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * duplicate values (according to {@link Object#equals}) 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <T> Ordering<T> explicit(List<T> valuesInOrder) { 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ExplicitOrdering<T>(valuesInOrder); 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an ordering that compares objects according to the order in 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * which they are given to this method. Only objects present in the argument 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * list (according to {@link Object#equals}) may be compared. This comparator 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * imposes a "partial ordering" over the type {@code T}. Null values in the 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * argument list are not supported. 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned comparator throws a {@link ClassCastException} when it 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * receives an input parameter that isn't among the provided values. 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The generated comparator is serializable if all the provided values are 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * serializable. 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param leastValue the value which the returned comparator should consider 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the "least" of all values 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param remainingValuesInOrder the rest of the values that the returned 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparator will be able to compare, in the order the comparator should 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * follow 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return the comparator described above 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any of the provided values is null 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if any duplicate values (according to 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Object#equals(Object)}) are present among the method arguments 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <T> Ordering<T> explicit( 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson T leastValue, T... remainingValuesInOrder) { 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return explicit(Lists.asList(leastValue, remainingValuesInOrder)); 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Exception thrown by a {@link Ordering#explicit(List)} or {@link 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Ordering#explicit(Object, Object[])} comparator when comparing a value 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * outside the set of values it can compare. Extending {@link 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ClassCastException} may seem odd, but it is required. 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): make this public, document it right 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @VisibleForTesting 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson static class IncomparableValueException extends ClassCastException { 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Object value; 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson IncomparableValueException(Object value) { 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super("Cannot compare value: " + value); 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.value = value; 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 185bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Returns an arbitrary ordering over all objects, for which {@code compare(a, 186bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * b) == 0} implies {@code a == b} (identity equality). There is no meaning 187bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * whatsoever to the order imposed, but it is constant for the life of the VM. 188bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 189bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <p>Because the ordering is identity-based, it is not "consistent with 190bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * {@link Object#equals(Object)}" as defined by {@link Comparator}. Use 191bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * caution when building a {@link SortedSet} or {@link SortedMap} from it, as 192bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * the resulting collection will not behave exactly according to spec. 193bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 194bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <p>This ordering is not serializable, as its implementation relies on 195bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * {@link System#identityHashCode(Object)}, so its behavior cannot be 196bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * preserved across serialization. 197bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 199bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor */ 200bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor public static Ordering<Object> arbitrary() { 201bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return ArbitraryOrderingHolder.ARBITRARY_ORDERING; 202bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 203bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 204bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor private static class ArbitraryOrderingHolder { 205bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor static final Ordering<Object> ARBITRARY_ORDERING = new ArbitraryOrdering(); 206bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 207bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 208bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @VisibleForTesting static class ArbitraryOrdering extends Ordering<Object> { 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("deprecation") // TODO(kevinb): ? 210bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor private Map<Object, Integer> uids = 211bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Platform.tryWeakKeys(new MapMaker()).makeComputingMap( 212bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor new Function<Object, Integer>() { 213bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor final AtomicInteger counter = new AtomicInteger(0); 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 215bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor public Integer apply(Object from) { 216bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return counter.getAndIncrement(); 217bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 218bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor }); 219bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int compare(Object left, Object right) { 221bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (left == right) { 222bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return 0; 223bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 224bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int leftCode = identityHashCode(left); 225bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int rightCode = identityHashCode(right); 226bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (leftCode != rightCode) { 227bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return leftCode < rightCode ? -1 : 1; 228bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 229bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 230bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // identityHashCode collision (rare, but not as rare as you'd think) 231bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int result = uids.get(left).compareTo(uids.get(right)); 232bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (result == 0) { 233bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor throw new AssertionError(); // extremely, extremely unlikely. 234bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 235bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return result; 236bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 237bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 238bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public String toString() { 239bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return "Ordering.arbitrary()"; 240bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 241bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 242bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor /* 243bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * We need to be able to mock identityHashCode() calls for tests, because it 244bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * can take 1-10 seconds to find colliding objects. Mocking frameworks that 245bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * can do magic to mock static method calls still can't do so for a system 246bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * class, so we need the indirection. In production, Hotspot should still 247bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * recognize that the call is 1-morphic and should still be willing to 248bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * inline it if necessary. 249bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor */ 250bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int identityHashCode(Object object) { 251bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return System.identityHashCode(object); 252bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 253bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 254bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 255bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor /** 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an ordering that compares objects by the natural ordering of their 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * string representations as returned by {@code toString()}. It does not 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * support null values. 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The comparator is serializable. 261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static Ordering<Object> usingToString() { 264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return UsingToStringOrdering.INSTANCE; 265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an ordering which tries each given comparator in order until a 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * non-zero result is found, returning that result, and returning zero only if 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * all comparators return zero. The returned ordering is based on the state of 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the {@code comparators} iterable at the time it was provided to this 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * method. 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned ordering is equivalent to that produced using {@code 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Ordering.from(comp1).compound(comp2).compound(comp3) . . .}. 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Warning:</b> Supplying an argument with undefined iteration order, 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * such as a {@link HashSet}, will produce non-deterministic results. 279090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param comparators the comparators to try in order 281090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <T> Ordering<T> compound( 284090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterable<? extends Comparator<? super T>> comparators) { 285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new CompoundOrdering<T>(comparators); 286090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 287090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 288090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 289090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs a new instance of this class (only invokable by the subclass 290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * constructor, typically implicit). 291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson protected Ordering() {} 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Non-static factories 295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an ordering which first uses the ordering {@code this}, but which 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * in the event of a "tie", then delegates to {@code secondaryComparator}. 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * For example, to sort a bug list first by status and second by priority, you 300090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * might use {@code byStatus.compound(byPriority)}. For a compound ordering 301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * with three or more components, simply chain multiple calls to this method. 302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>An ordering produced by this method, or a chain of calls to this method, 304090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * is equivalent to one created using {@link Ordering#compound(Iterable)} on 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the same component comparators. 306090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 308090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public <U extends T> Ordering<U> compound( 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Comparator<? super U> secondaryComparator) { 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new CompoundOrdering<U>(this, checkNotNull(secondaryComparator)); 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the reverse of this ordering; the {@code Ordering} equivalent to 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Collections#reverseOrder(Comparator)}. 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // type parameter <S> lets us avoid the extra <String> in statements like: 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Ordering<String> o = Ordering.<String>natural().reverse(); 319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 320090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public <S extends T> Ordering<S> reverse() { 321090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ReverseOrdering<S>(this); 322090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 323090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 325090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a new ordering on {@code F} which orders elements by first applying 326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * a function to them, then comparing those results using {@code this}. For 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * example, to compare objects by their string forms, in a case-insensitive 328090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * manner, use: <pre> {@code 329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Ordering.from(String.CASE_INSENSITIVE_ORDER) 331090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * .onResultOf(Functions.toStringFunction())}</pre> 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public <F> Ordering<F> onResultOf(Function<F, ? extends T> function) { 335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ByFunctionOrdering<F, T>(function, this); 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 339bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Returns a new ordering which sorts iterables by comparing corresponding 340bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * elements pairwise until a nonzero result is found; imposes "dictionary 341bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * order". If the end of one iterable is reached, but not the other, the 342bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * shorter iterable is considered to be less than the longer one. For example, 343bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * a lexicographical natural ordering over integers considers {@code 344bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * [] < [1] < [1, 1] < [1, 2] < [2]}. 345bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 346bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <p>Note that {@code ordering.lexicographical().reverse()} is not 347bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * equivalent to {@code ordering.reverse().lexicographical()} (consider how 348bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * each would order {@code [1]} and {@code [1, 1]}). 349bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 351bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor */ 352bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @GwtCompatible(serializable = true) 353bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // type parameter <S> lets us avoid the extra <String> in statements like: 354bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // Ordering<Iterable<String>> o = 355bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // Ordering.<String>natural().lexicographical(); 356bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor public <S extends T> Ordering<Iterable<S>> lexicographical() { 357bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor /* 358bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Note that technically the returned ordering should be capable of 359bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * handling not just {@code Iterable<S>} instances, but also any {@code 360bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Iterable<? extends S>}. However, the need for this comes up so rarely 361bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * that it doesn't justify making everyone else deal with the very ugly 362bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * wildcard. 363bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor */ 364bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return new LexicographicalOrdering<S>(this); 365bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 366bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 367bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor /** 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an ordering that treats {@code null} as less than all other values 369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and uses {@code this} to compare non-null values. 370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // type parameter <S> lets us avoid the extra <String> in statements like: 372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Ordering<String> o = Ordering.<String>natural().nullsFirst(); 373090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public <S extends T> Ordering<S> nullsFirst() { 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new NullsFirstOrdering<S>(this); 376090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an ordering that treats {@code null} as greater than all other 380090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * values and uses this ordering to compare non-null values. 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // type parameter <S> lets us avoid the extra <String> in statements like: 383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Ordering<String> o = Ordering.<String>natural().nullsLast(); 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 385090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public <S extends T> Ordering<S> nullsLast() { 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new NullsLastOrdering<S>(this); 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Regular instance methods 3901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Override to add @Nullable 3921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public abstract int compare(@Nullable T left, @Nullable T right); 3931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the {@code k} least elements of the given iterable according to 3961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this ordering, in order from least to greatest. If there are fewer than 3971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code k} elements present, all will be included. 3981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The implementation does not necessarily use a <i>stable</i> sorting 4001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * algorithm; when multiple elements are equivalent, it is undefined which 4011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * will come first. 4021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return an immutable {@code RandomAccess} list of the {@code k} least 4041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements in ascending order 4051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code k} is negative 4061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 8.0 4071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Beta 4091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E extends T> List<E> leastOf(Iterable<E> iterable, int k) { 4101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(k >= 0, "%d is negative", k); 4111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // values is not an E[], but we use it as such for readability. Hack. 4131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 4141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E[] values = (E[]) Iterables.toArray(iterable); 4151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(nshupe): also sort whole list if k is *near* values.length? 4171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): benchmark this impl against hand-coded heap 4181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E[] resultArray; 4191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (values.length <= k) { 4201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Arrays.sort(values, this); 4211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert resultArray = values; 4221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 4231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert quicksortLeastK(values, 0, values.length - 1, k); 4241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // this is not an E[], but we use it as such for readability. Hack. 4261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 4271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E[] tmp = (E[]) new Object[k]; 4281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert resultArray = tmp; 4291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert System.arraycopy(values, 0, resultArray, 0, k); 4301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Collections.unmodifiableList(Arrays.asList(resultArray)); 4331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the {@code k} greatest elements of the given iterable according to 4371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this ordering, in order from greatest to least. If there are fewer than 4381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code k} elements present, all will be included. 4391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The implementation does not necessarily use a <i>stable</i> sorting 4411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * algorithm; when multiple elements are equivalent, it is undefined which 4421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * will come first. 4431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return an immutable {@code RandomAccess} list of the {@code k} greatest 4451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements in <i>descending order</i> 4461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code k} is negative 4471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 8.0 4481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Beta 4501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E extends T> List<E> greatestOf(Iterable<E> iterable, int k) { 4511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): see if delegation is hurting performance noticeably 4521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): if we change this implementation, add full unit tests. 4531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return reverse().leastOf(iterable, k); 4541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private <E extends T> void quicksortLeastK( 4571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E[] values, int left, int right, int k) { 4581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (right > left) { 4591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int pivotIndex = (left + right) >>> 1; // left + ((right - left) / 2) 4601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int pivotNewIndex = partition(values, left, right, pivotIndex); 4611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert quicksortLeastK(values, left, pivotNewIndex - 1, k); 4621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (pivotNewIndex < k) { 4631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert quicksortLeastK(values, pivotNewIndex + 1, right, k); 4641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private <E extends T> int partition( 4691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E[] values, int left, int right, int pivotIndex) { 4701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E pivotValue = values[pivotIndex]; 4711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert values[pivotIndex] = values[right]; 4731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert values[right] = pivotValue; 4741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int storeIndex = left; 4761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = left; i < right; i++) { 4771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (compare(values[i], pivotValue) < 0) { 4781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ObjectArrays.swap(values, storeIndex, i); 4791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert storeIndex++; 4801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ObjectArrays.swap(values, right, storeIndex); 4831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return storeIndex; 4841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 486090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 487090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Collections#binarySearch(List, Object, Comparator) Searches} 488090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code sortedList} for {@code key} using the binary search algorithm. The 489090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * list must be sorted using this ordering. 490090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 491090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param sortedList the list to be searched 492090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param key the key to be searched for 493090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 4941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int binarySearch(List<? extends T> sortedList, @Nullable T key) { 495090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Collections.binarySearch(sortedList, key, this); 496090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 497090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 498090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 499090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a copy of the given iterable sorted by this ordering. The input is 500090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * not modified. The returned list is modifiable, serializable, and has random 501090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * access. 502090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 5031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard 5041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements that are duplicates according to the comparator. The sort 5051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * performed is <i>stable</i>, meaning that such elements will appear in the 5061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * resulting list in the same order they appeared in the input. 507090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 508090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param iterable the elements to be copied and sorted 509090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new list containing the given elements in sorted order 510090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 511090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public <E extends T> List<E> sortedCopy(Iterable<E> iterable) { 512090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson List<E> list = Lists.newArrayList(iterable); 513090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collections.sort(list, this); 514090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return list; 515090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 516090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 517090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 5181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an <i>immutable</i> copy of the given iterable sorted by this 5191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ordering. The input is not modified. 5201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 5211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard 5221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements that are duplicates according to the comparator. The sort 5231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * performed is <i>stable</i>, meaning that such elements will appear in the 5241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * resulting list in the same order they appeared in the input. 5251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 5261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param iterable the elements to be copied and sorted 5271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return a new immutable list containing the given elements in sorted order 5281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code iterable} or any of its elements is 5291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * null 5301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 3.0 5311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E extends T> ImmutableList<E> immutableSortedCopy( 5331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterable<E> iterable) { 5341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ImmutableList.copyOf(sortedCopy(iterable)); 5351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 538090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns {@code true} if each element in {@code iterable} after the first is 539090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * greater than or equal to the element that preceded it, according to this 540090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ordering. Note that this is always true when the iterable has fewer than 541090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * two elements. 542090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 543090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean isOrdered(Iterable<? extends T> iterable) { 544090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<? extends T> it = iterable.iterator(); 545090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (it.hasNext()) { 546090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson T prev = it.next(); 547090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (it.hasNext()) { 548090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson T next = it.next(); 549090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (compare(prev, next) > 0) { 550090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 551090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 552090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson prev = next; 553090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 554090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 555090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 556090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 557090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 558090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 559090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns {@code true} if each element in {@code iterable} after the first is 560090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <i>strictly</i> greater than the element that preceded it, according to 561090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * this ordering. Note that this is always true when the iterable has fewer 562090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * than two elements. 563090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 564090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean isStrictlyOrdered(Iterable<? extends T> iterable) { 565090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<? extends T> it = iterable.iterator(); 566090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (it.hasNext()) { 567090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson T prev = it.next(); 568090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (it.hasNext()) { 569090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson T next = it.next(); 570090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (compare(prev, next) >= 0) { 571090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 572090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 573090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson prev = next; 574090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 575090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 576090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 577090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 578090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 579090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 5801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the greatest of the specified values according to this ordering. If 5811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * there are multiple greatest values, the first of those is returned. The 5821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * iterator will be left exhausted: its {@code hasNext()} method will return 5831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code false}. 584090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 5851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param iterator the iterator whose maximum element is to be determined 5861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NoSuchElementException if {@code iterator} is empty 587090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws ClassCastException if the parameters are not <i>mutually 588090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparable</i> under this ordering. 5891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 5901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 591090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 5921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Beta 5931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E extends T> E max(Iterator<E> iterator) { 594090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // let this throw NoSuchElementException as necessary 595090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E maxSoFar = iterator.next(); 596090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 597090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (iterator.hasNext()) { 598090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson maxSoFar = max(maxSoFar, iterator.next()); 599090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 600090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 601090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return maxSoFar; 602090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 603090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 604090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 6051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the greatest of the specified values according to this ordering. If 6061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * there are multiple greatest values, the first of those is returned. 6071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 6081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param iterable the iterable whose maximum element is to be determined 6091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NoSuchElementException if {@code iterable} is empty 6101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ClassCastException if the parameters are not <i>mutually 6111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * comparable</i> under this ordering. 6121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 6131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E extends T> E max(Iterable<E> iterable) { 6141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return max(iterable.iterator()); 6151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 6181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the greatest of the specified values according to this ordering. If 6191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * there are multiple greatest values, the first of those is returned. 620090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 621090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param a value to compare, returned if greater than or equal to the rest. 622090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param b value to compare 623090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param c value to compare 624090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param rest values to compare 625090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws ClassCastException if the parameters are not <i>mutually 626090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparable</i> under this ordering. 627090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E extends T> E max( 6291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable E a, @Nullable E b, @Nullable E c, E... rest) { 630090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E maxSoFar = max(max(a, b), c); 631090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 632090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (E r : rest) { 633090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson maxSoFar = max(maxSoFar, r); 634090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 635090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 636090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return maxSoFar; 637090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 638090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 639090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 6401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the greater of the two values according to this ordering. If the 641090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * values compare as 0, the first is returned. 642090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 643090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Implementation note:</b> this method is invoked by the default 644090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementations of the other {@code max} overloads, so overriding it will 645090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * affect their behavior. 646090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 647090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param a value to compare, returned if greater than or equal to b. 648090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param b value to compare. 649090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws ClassCastException if the parameters are not <i>mutually 650090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparable</i> under this ordering. 651090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E extends T> E max(@Nullable E a, @Nullable E b) { 653090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return compare(a, b) >= 0 ? a : b; 654090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 655090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 656090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 6571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the least of the specified values according to this ordering. If 6581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * there are multiple least values, the first of those is returned. The 6591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * iterator will be left exhausted: its {@code hasNext()} method will return 6601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code false}. 661090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 6621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param iterator the iterator whose minimum element is to be determined 6631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NoSuchElementException if {@code iterator} is empty 664090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws ClassCastException if the parameters are not <i>mutually 665090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparable</i> under this ordering. 6661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 6671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 668090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Beta 6701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E extends T> E min(Iterator<E> iterator) { 671090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // let this throw NoSuchElementException as necessary 672090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E minSoFar = iterator.next(); 673090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 674090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (iterator.hasNext()) { 675090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson minSoFar = min(minSoFar, iterator.next()); 676090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 677090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 678090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return minSoFar; 679090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 680090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 681090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 6821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the least of the specified values according to this ordering. If 6831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * there are multiple least values, the first of those is returned. 6841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 6851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param iterable the iterable whose minimum element is to be determined 6861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NoSuchElementException if {@code iterable} is empty 6871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ClassCastException if the parameters are not <i>mutually 6881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * comparable</i> under this ordering. 6891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 6901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E extends T> E min(Iterable<E> iterable) { 6911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return min(iterable.iterator()); 6921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 6951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the least of the specified values according to this ordering. If 6961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * there are multiple least values, the first of those is returned. 697090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 698090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param a value to compare, returned if less than or equal to the rest. 699090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param b value to compare 700090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param c value to compare 701090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param rest values to compare 702090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws ClassCastException if the parameters are not <i>mutually 703090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparable</i> under this ordering. 704090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 7051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E extends T> E min( 7061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable E a, @Nullable E b, @Nullable E c, E... rest) { 707090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E minSoFar = min(min(a, b), c); 708090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 709090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (E r : rest) { 710090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson minSoFar = min(minSoFar, r); 711090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 712090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 713090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return minSoFar; 714090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 715090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 716090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 7171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the lesser of the two values according to this ordering. If the 718090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * values compare as 0, the first is returned. 719090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 720090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Implementation note:</b> this method is invoked by the default 721090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementations of the other {@code min} overloads, so overriding it will 722090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * affect their behavior. 723090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 724090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param a value to compare, returned if less than or equal to b. 725090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param b value to compare. 726090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws ClassCastException if the parameters are not <i>mutually 727090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparable</i> under this ordering. 728090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 7291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E extends T> E min(@Nullable E a, @Nullable E b) { 730090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return compare(a, b) <= 0 ? a : b; 731090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 732090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 733090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Never make these public 734090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson static final int LEFT_IS_GREATER = 1; 735090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson static final int RIGHT_IS_GREATER = -1; 736090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 737