001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.CollectPreconditions.checkNonnegative;
021import static java.util.Arrays.asList;
022import static java.util.Arrays.sort;
023import static java.util.Collections.emptyList;
024import static java.util.Collections.sort;
025import static java.util.Collections.unmodifiableList;
026
027import com.google.common.annotations.GwtCompatible;
028import com.google.common.annotations.J2ktIncompatible;
029import com.google.common.annotations.VisibleForTesting;
030import com.google.common.base.Function;
031import java.util.ArrayList;
032import java.util.Arrays;
033import java.util.Collection;
034import java.util.Collections;
035import java.util.Comparator;
036import java.util.HashSet;
037import java.util.Iterator;
038import java.util.List;
039import java.util.Map.Entry;
040import java.util.NoSuchElementException;
041import java.util.SortedMap;
042import java.util.SortedSet;
043import java.util.TreeSet;
044import java.util.concurrent.ConcurrentMap;
045import java.util.concurrent.atomic.AtomicInteger;
046import javax.annotation.CheckForNull;
047import org.checkerframework.checker.nullness.qual.NonNull;
048import org.checkerframework.checker.nullness.qual.Nullable;
049
050/**
051 * A comparator, with additional methods to support common operations. This is an "enriched" version
052 * of {@code Comparator} for pre-Java-8 users, in the same sense that {@link FluentIterable} is an
053 * enriched {@link Iterable} for pre-Java-8 users.
054 *
055 * <h3>Three types of methods</h3>
056 *
057 * Like other fluent types, there are three types of methods present: methods for <i>acquiring</i>,
058 * <i>chaining</i>, and <i>using</i>.
059 *
060 * <h4>Acquiring</h4>
061 *
062 * <p>The common ways to get an instance of {@code Ordering} are:
063 *
064 * <ul>
065 *   <li>Subclass it and implement {@link #compare} instead of implementing {@link Comparator}
066 *       directly
067 *   <li>Pass a <i>pre-existing</i> {@link Comparator} instance to {@link #from(Comparator)}
068 *   <li>Use the natural ordering, {@link Ordering#natural}
069 * </ul>
070 *
071 * <h4>Chaining</h4>
072 *
073 * <p>Then you can use the <i>chaining</i> methods to get an altered version of that {@code
074 * Ordering}, including:
075 *
076 * <ul>
077 *   <li>{@link #reverse}
078 *   <li>{@link #compound(Comparator)}
079 *   <li>{@link #onResultOf(Function)}
080 *   <li>{@link #nullsFirst} / {@link #nullsLast}
081 * </ul>
082 *
083 * <h4>Using</h4>
084 *
085 * <p>Finally, use the resulting {@code Ordering} anywhere a {@link Comparator} is required, or use
086 * any of its special operations, such as:
087 *
088 * <ul>
089 *   <li>{@link #immutableSortedCopy}
090 *   <li>{@link #isOrdered} / {@link #isStrictlyOrdered}
091 *   <li>{@link #min} / {@link #max}
092 * </ul>
093 *
094 * <h3>Understanding complex orderings</h3>
095 *
096 * <p>Complex chained orderings like the following example can be challenging to understand.
097 *
098 * <pre>{@code
099 * Ordering<Foo> ordering =
100 *     Ordering.natural()
101 *         .nullsFirst()
102 *         .onResultOf(getBarFunction)
103 *         .nullsLast();
104 * }</pre>
105 *
106 * Note that each chaining method returns a new ordering instance which is backed by the previous
107 * instance, but has the chance to act on values <i>before</i> handing off to that backing instance.
108 * As a result, it usually helps to read chained ordering expressions <i>backwards</i>. For example,
109 * when {@code compare} is called on the above ordering:
110 *
111 * <ol>
112 *   <li>First, if only one {@code Foo} is null, that null value is treated as <i>greater</i>
113 *   <li>Next, non-null {@code Foo} values are passed to {@code getBarFunction} (we will be
114 *       comparing {@code Bar} values from now on)
115 *   <li>Next, if only one {@code Bar} is null, that null value is treated as <i>lesser</i>
116 *   <li>Finally, natural ordering is used (i.e. the result of {@code Bar.compareTo(Bar)} is
117 *       returned)
118 * </ol>
119 *
120 * <p>Alas, {@link #reverse} is a little different. As you read backwards through a chain and
121 * encounter a call to {@code reverse}, continue working backwards until a result is determined, and
122 * then reverse that result.
123 *
124 * <h3>Additional notes</h3>
125 *
126 * <p>Except as noted, the orderings returned by the factory methods of this class are serializable
127 * if and only if the provided instances that back them are. For example, if {@code ordering} and
128 * {@code function} can themselves be serialized, then {@code ordering.onResultOf(function)} can as
129 * well.
130 *
131 * <h3>Java 8+ users</h3>
132 *
133 * <p>If you are using Java 8+, this class is now obsolete. Most of its functionality is now
134 * provided by {@link java.util.stream.Stream Stream} and by {@link Comparator} itself, and the rest
135 * can now be found as static methods in our new {@link Comparators} class. See each method below
136 * for further instructions. Whenever possible, you should change any references of type {@code
137 * Ordering} to be of type {@code Comparator} instead. However, at this time we have no plan to
138 * <i>deprecate</i> this class.
139 *
140 * <p>Many replacements involve adopting {@code Stream}, and these changes can sometimes make your
141 * code verbose. Whenever following this advice, you should check whether {@code Stream} could be
142 * adopted more comprehensively in your code; the end result may be quite a bit simpler.
143 *
144 * <h3>See also</h3>
145 *
146 * <p>See the Guava User Guide article on <a href=
147 * "https://github.com/google/guava/wiki/OrderingExplained">{@code Ordering}</a>.
148 *
149 * @author Jesse Wilson
150 * @author Kevin Bourrillion
151 * @since 2.0
152 */
153@GwtCompatible
154public abstract class Ordering<T extends @Nullable Object> implements Comparator<T> {
155  // Natural order
156
157  /**
158   * Returns a serializable ordering that uses the natural order of the values. The ordering throws
159   * a {@link NullPointerException} when passed a null parameter.
160   *
161   * <p>The type specification is {@code <C extends Comparable>}, instead of the technically correct
162   * {@code <C extends Comparable<? super C>>}, to support legacy types from before Java 5.
163   *
164   * <p><b>Java 8+ users:</b> use {@link Comparator#naturalOrder} instead.
165   */
166  @GwtCompatible(serializable = true)
167  @SuppressWarnings({"unchecked", "rawtypes"})
168  // TODO(kevinb): right way to explain this??
169  // plus https://github.com/google/guava/issues/989
170  public static <C extends Comparable> Ordering<C> natural() {
171    return (Ordering<C>) NaturalOrdering.INSTANCE;
172  }
173
174  // Static factories
175
176  /**
177   * Returns an ordering based on an <i>existing</i> comparator instance. Note that it is
178   * unnecessary to create a <i>new</i> anonymous inner class implementing {@code Comparator} just
179   * to pass it in here. Instead, simply subclass {@code Ordering} and implement its {@code compare}
180   * method directly.
181   *
182   * <p>The returned object is serializable if {@code comparator} is serializable.
183   *
184   * <p><b>Java 8+ users:</b> this class is now obsolete as explained in the class documentation, so
185   * there is no need to use this method.
186   *
187   * @param comparator the comparator that defines the order
188   * @return comparator itself if it is already an {@code Ordering}; otherwise an ordering that
189   *     wraps that comparator
190   */
191  @GwtCompatible(serializable = true)
192  public static <T extends @Nullable Object> Ordering<T> from(Comparator<T> comparator) {
193    return (comparator instanceof Ordering)
194        ? (Ordering<T>) comparator
195        : new ComparatorOrdering<T>(comparator);
196  }
197
198  /**
199   * Simply returns its argument.
200   *
201   * @deprecated no need to use this
202   */
203  @GwtCompatible(serializable = true)
204  @Deprecated
205  public static <T extends @Nullable Object> Ordering<T> from(Ordering<T> ordering) {
206    return checkNotNull(ordering);
207  }
208
209  /**
210   * Returns an ordering that compares objects according to the order in which they appear in the
211   * given list. Only objects present in the list (according to {@link Object#equals}) may be
212   * compared. This comparator imposes a "partial ordering" over the type {@code T}. Subsequent
213   * changes to the {@code valuesInOrder} list will have no effect on the returned comparator. Null
214   * values in the list are not supported.
215   *
216   * <p>The returned comparator throws a {@link ClassCastException} when it receives an input
217   * parameter that isn't among the provided values.
218   *
219   * <p>The generated comparator is serializable if all the provided values are serializable.
220   *
221   * @param valuesInOrder the values that the returned comparator will be able to compare, in the
222   *     order the comparator should induce
223   * @return the comparator described above
224   * @throws NullPointerException if any of the provided values is null
225   * @throws IllegalArgumentException if {@code valuesInOrder} contains any duplicate values
226   *     (according to {@link Object#equals})
227   */
228  // TODO(kevinb): provide replacement
229  @GwtCompatible(serializable = true)
230  public static <T> Ordering<T> explicit(List<T> valuesInOrder) {
231    return new ExplicitOrdering<>(valuesInOrder);
232  }
233
234  /**
235   * Returns an ordering that compares objects according to the order in which they are given to
236   * this method. Only objects present in the argument list (according to {@link Object#equals}) may
237   * be compared. This comparator imposes a "partial ordering" over the type {@code T}. Null values
238   * in the argument list are not supported.
239   *
240   * <p>The returned comparator throws a {@link ClassCastException} when it receives an input
241   * parameter that isn't among the provided values.
242   *
243   * <p>The generated comparator is serializable if all the provided values are serializable.
244   *
245   * @param leastValue the value which the returned comparator should consider the "least" of all
246   *     values
247   * @param remainingValuesInOrder the rest of the values that the returned comparator will be able
248   *     to compare, in the order the comparator should follow
249   * @return the comparator described above
250   * @throws NullPointerException if any of the provided values is null
251   * @throws IllegalArgumentException if any duplicate values (according to {@link
252   *     Object#equals(Object)}) are present among the method arguments
253   */
254  // TODO(kevinb): provide replacement
255  @GwtCompatible(serializable = true)
256  public static <T> Ordering<T> explicit(T leastValue, T... remainingValuesInOrder) {
257    return explicit(Lists.asList(leastValue, remainingValuesInOrder));
258  }
259
260  // Ordering<Object> singletons
261
262  /**
263   * Returns an ordering which treats all values as equal, indicating "no ordering." Passing this
264   * ordering to any <i>stable</i> sort algorithm results in no change to the order of elements.
265   * Note especially that {@link #sortedCopy} and {@link #immutableSortedCopy} are stable, and in
266   * the returned instance these are implemented by simply copying the source list.
267   *
268   * <p>Example:
269   *
270   * <pre>{@code
271   * Ordering.allEqual().nullsLast().sortedCopy(
272   *     asList(t, null, e, s, null, t, null))
273   * }</pre>
274   *
275   * <p>Assuming {@code t}, {@code e} and {@code s} are non-null, this returns {@code [t, e, s, t,
276   * null, null, null]} regardless of the true comparison order of those three values (which might
277   * not even implement {@link Comparable} at all).
278   *
279   * <p><b>Warning:</b> by definition, this comparator is not <i>consistent with equals</i> (as
280   * defined {@linkplain Comparator here}). Avoid its use in APIs, such as {@link
281   * TreeSet#TreeSet(Comparator)}, where such consistency is expected.
282   *
283   * <p>The returned comparator is serializable.
284   *
285   * <p><b>Java 8+ users:</b> Use the lambda expression {@code (a, b) -> 0} instead (in certain
286   * cases you may need to cast that to {@code Comparator<YourType>}).
287   *
288   * @since 13.0
289   */
290  @GwtCompatible(serializable = true)
291  public static Ordering<@Nullable Object> allEqual() {
292    return AllEqualOrdering.INSTANCE;
293  }
294
295  /**
296   * Returns an ordering that compares objects by the natural ordering of their string
297   * representations as returned by {@code toString()}. It does not support null values.
298   *
299   * <p>The comparator is serializable.
300   *
301   * <p><b>Java 8+ users:</b> Use {@code Comparator.comparing(Object::toString)} instead.
302   */
303  @GwtCompatible(serializable = true)
304  public static Ordering<Object> usingToString() {
305    return UsingToStringOrdering.INSTANCE;
306  }
307
308  /**
309   * Returns an arbitrary ordering over all objects, for which {@code compare(a, b) == 0} implies
310   * {@code a == b} (identity equality). There is no meaning whatsoever to the order imposed, but it
311   * is constant for the life of the VM.
312   *
313   * <p>Because the ordering is identity-based, it is not "consistent with {@link
314   * Object#equals(Object)}" as defined by {@link Comparator}. Use caution when building a {@link
315   * SortedSet} or {@link SortedMap} from it, as the resulting collection will not behave exactly
316   * according to spec.
317   *
318   * <p>This ordering is not serializable, as its implementation relies on {@link
319   * System#identityHashCode(Object)}, so its behavior cannot be preserved across serialization.
320   *
321   * @since 2.0
322   */
323  // TODO(kevinb): copy to Comparators, etc.
324  @J2ktIncompatible // MapMaker
325  public static Ordering<@Nullable Object> arbitrary() {
326    return ArbitraryOrderingHolder.ARBITRARY_ORDERING;
327  }
328
329  @J2ktIncompatible // MapMaker
330  private static class ArbitraryOrderingHolder {
331    static final Ordering<@Nullable Object> ARBITRARY_ORDERING = new ArbitraryOrdering();
332  }
333
334  @J2ktIncompatible // MapMaker
335  @VisibleForTesting
336  static class ArbitraryOrdering extends Ordering<@Nullable Object> {
337
338    private final AtomicInteger counter = new AtomicInteger(0);
339    private final ConcurrentMap<Object, Integer> uids =
340        Platform.tryWeakKeys(new MapMaker()).makeMap();
341
342    private Integer getUid(Object obj) {
343      Integer uid = uids.get(obj);
344      if (uid == null) {
345        // One or more integer values could be skipped in the event of a race
346        // to generate a UID for the same object from multiple threads, but
347        // that shouldn't be a problem.
348        uid = counter.getAndIncrement();
349        Integer alreadySet = uids.putIfAbsent(obj, uid);
350        if (alreadySet != null) {
351          uid = alreadySet;
352        }
353      }
354      return uid;
355    }
356
357    @Override
358    public int compare(@CheckForNull Object left, @CheckForNull Object right) {
359      if (left == right) {
360        return 0;
361      } else if (left == null) {
362        return -1;
363      } else if (right == null) {
364        return 1;
365      }
366      int leftCode = identityHashCode(left);
367      int rightCode = identityHashCode(right);
368      if (leftCode != rightCode) {
369        return leftCode < rightCode ? -1 : 1;
370      }
371
372      // identityHashCode collision (rare, but not as rare as you'd think)
373      int result = getUid(left).compareTo(getUid(right));
374      if (result == 0) {
375        throw new AssertionError(); // extremely, extremely unlikely.
376      }
377      return result;
378    }
379
380    @Override
381    public String toString() {
382      return "Ordering.arbitrary()";
383    }
384
385    /*
386     * We need to be able to mock identityHashCode() calls for tests, because it
387     * can take 1-10 seconds to find colliding objects. Mocking frameworks that
388     * can do magic to mock static method calls still can't do so for a system
389     * class, so we need the indirection. In production, Hotspot should still
390     * recognize that the call is 1-morphic and should still be willing to
391     * inline it if necessary.
392     */
393    int identityHashCode(Object object) {
394      return System.identityHashCode(object);
395    }
396  }
397
398  // Constructor
399
400  /**
401   * Constructs a new instance of this class (only invokable by the subclass constructor, typically
402   * implicit).
403   */
404  protected Ordering() {}
405
406  // Instance-based factories (and any static equivalents)
407
408  /**
409   * Returns the reverse of this ordering; the {@code Ordering} equivalent to {@link
410   * Collections#reverseOrder(Comparator)}.
411   *
412   * <p><b>Java 8+ users:</b> Use {@code thisComparator.reversed()} instead.
413   */
414  // type parameter <S> lets us avoid the extra <String> in statements like:
415  // Ordering<String> o = Ordering.<String>natural().reverse();
416  @GwtCompatible(serializable = true)
417  public <S extends T> Ordering<S> reverse() {
418    return new ReverseOrdering<>(this);
419  }
420
421  /**
422   * Returns an ordering that treats {@code null} as less than all other values and uses {@code
423   * this} to compare non-null values.
424   *
425   * <p>The returned object is serializable if this object is serializable.
426   *
427   * <p><b>Java 8+ users:</b> Use {@code Comparator.nullsFirst(thisComparator)} instead.
428   */
429  // type parameter <S> lets us avoid the extra <String> in statements like:
430  // Ordering<String> o = Ordering.<String>natural().nullsFirst();
431  @GwtCompatible(serializable = true)
432  public <S extends T> Ordering<@Nullable S> nullsFirst() {
433    return new NullsFirstOrdering<S>(this);
434  }
435
436  /**
437   * Returns an ordering that treats {@code null} as greater than all other values and uses this
438   * ordering to compare non-null values.
439   *
440   * <p>The returned object is serializable if this object is serializable.
441   *
442   * <p><b>Java 8+ users:</b> Use {@code Comparator.nullsLast(thisComparator)} instead.
443   */
444  // type parameter <S> lets us avoid the extra <String> in statements like:
445  // Ordering<String> o = Ordering.<String>natural().nullsLast();
446  @GwtCompatible(serializable = true)
447  public <S extends T> Ordering<@Nullable S> nullsLast() {
448    return new NullsLastOrdering<S>(this);
449  }
450
451  /**
452   * Returns a new ordering on {@code F} which orders elements by first applying a function to them,
453   * then comparing those results using {@code this}. For example, to compare objects by their
454   * string forms, in a case-insensitive manner, use:
455   *
456   * <pre>{@code
457   * Ordering.from(String.CASE_INSENSITIVE_ORDER)
458   *     .onResultOf(Functions.toStringFunction())
459   * }</pre>
460   *
461   * <p><b>Java 8+ users:</b> Use {@code Comparator.comparing(function, thisComparator)} instead
462   * (you can omit the comparator if it is the natural order).
463   */
464  @GwtCompatible(serializable = true)
465  public <F extends @Nullable Object> Ordering<F> onResultOf(Function<F, ? extends T> function) {
466    return new ByFunctionOrdering<>(function, this);
467  }
468
469  <T2 extends T> Ordering<Entry<T2, ?>> onKeys() {
470    return onResultOf(Maps.<T2>keyFunction());
471  }
472
473  /**
474   * Returns an ordering which first uses the ordering {@code this}, but which in the event of a
475   * "tie", then delegates to {@code secondaryComparator}. For example, to sort a bug list first by
476   * status and second by priority, you might use {@code byStatus.compound(byPriority)}. For a
477   * compound ordering with three or more components, simply chain multiple calls to this method.
478   *
479   * <p>An ordering produced by this method, or a chain of calls to this method, is equivalent to
480   * one created using {@link Ordering#compound(Iterable)} on the same component comparators.
481   *
482   * <p>The returned object is serializable if this object and {@code secondaryComparator} are both
483   * serializable.
484   *
485   * <p><b>Java 8+ users:</b> Use {@code thisComparator.thenComparing(secondaryComparator)} instead.
486   * Depending on what {@code secondaryComparator} is, one of the other overloads of {@code
487   * thenComparing} may be even more useful.
488   */
489  @GwtCompatible(serializable = true)
490  public <U extends T> Ordering<U> compound(Comparator<? super U> secondaryComparator) {
491    return new CompoundOrdering<>(this, checkNotNull(secondaryComparator));
492  }
493
494  /**
495   * Returns an ordering which tries each given comparator in order until a non-zero result is
496   * found, returning that result, and returning zero only if all comparators return zero. The
497   * returned ordering is based on the state of the {@code comparators} iterable at the time it was
498   * provided to this method.
499   *
500   * <p>The returned ordering is equivalent to that produced using {@code
501   * Ordering.from(comp1).compound(comp2).compound(comp3) . . .}.
502   *
503   * <p>The returned object is serializable if each of the {@code comparators} is serializable.
504   *
505   * <p><b>Warning:</b> Supplying an argument with undefined iteration order, such as a {@link
506   * HashSet}, will produce non-deterministic results.
507   *
508   * <p><b>Java 8+ users:</b> Use a chain of calls to {@link Comparator#thenComparing(Comparator)},
509   * or {@code comparatorCollection.stream().reduce(Comparator::thenComparing).get()} (if the
510   * collection might be empty, also provide a default comparator as the {@code identity} parameter
511   * to {@code reduce}).
512   *
513   * @param comparators the comparators to try in order
514   */
515  @GwtCompatible(serializable = true)
516  public static <T extends @Nullable Object> Ordering<T> compound(
517      Iterable<? extends Comparator<? super T>> comparators) {
518    return new CompoundOrdering<>(comparators);
519  }
520
521  /**
522   * Returns a new ordering which sorts iterables by comparing corresponding elements pairwise until
523   * a nonzero result is found; imposes "dictionary order". If the end of one iterable is reached,
524   * but not the other, the shorter iterable is considered to be less than the longer one. For
525   * example, a lexicographical natural ordering over integers considers {@code [] < [1] < [1, 1] <
526   * [1, 2] < [2]}.
527   *
528   * <p>Note that {@code ordering.lexicographical().reverse()} is not equivalent to {@code
529   * ordering.reverse().lexicographical()} (consider how each would order {@code [1]} and {@code [1,
530   * 1]}).
531   *
532   * <p><b>Java 8+ users:</b> Use {@link Comparators#lexicographical(Comparator)} instead.
533   *
534   * @since 2.0
535   */
536  @GwtCompatible(serializable = true)
537  // type parameter <S> lets us avoid the extra <String> in statements like:
538  // Ordering<Iterable<String>> o =
539  //     Ordering.<String>natural().lexicographical();
540  public <S extends T> Ordering<Iterable<S>> lexicographical() {
541    /*
542     * Note that technically the returned ordering should be capable of
543     * handling not just {@code Iterable<S>} instances, but also any {@code
544     * Iterable<? extends S>}. However, the need for this comes up so rarely
545     * that it doesn't justify making everyone else deal with the very ugly
546     * wildcard.
547     */
548    return new LexicographicalOrdering<S>(this);
549  }
550
551  // Regular instance methods
552
553  @Override
554  public abstract int compare(@ParametricNullness T left, @ParametricNullness T right);
555
556  /**
557   * Returns the least of the specified values according to this ordering. If there are multiple
558   * least values, the first of those is returned. The iterator will be left exhausted: its {@code
559   * hasNext()} method will return {@code false}.
560   *
561   * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterator).min(thisComparator).get()} instead
562   * (but note that it does not guarantee which tied minimum element is returned).
563   *
564   * @param iterator the iterator whose minimum element is to be determined
565   * @throws NoSuchElementException if {@code iterator} is empty
566   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this
567   *     ordering.
568   * @since 11.0
569   */
570  @ParametricNullness
571  public <E extends T> E min(Iterator<E> iterator) {
572    // let this throw NoSuchElementException as necessary
573    E minSoFar = iterator.next();
574
575    while (iterator.hasNext()) {
576      minSoFar = this.<E>min(minSoFar, iterator.next());
577    }
578
579    return minSoFar;
580  }
581
582  /**
583   * Returns the least of the specified values according to this ordering. If there are multiple
584   * least values, the first of those is returned.
585   *
586   * <p><b>Java 8+ users:</b> If {@code iterable} is a {@link Collection}, use {@code
587   * Collections.min(collection, thisComparator)} instead. Otherwise, use {@code
588   * Streams.stream(iterable).min(thisComparator).get()} instead. Note that these alternatives do
589   * not guarantee which tied minimum element is returned.
590   *
591   * @param iterable the iterable whose minimum element is to be determined
592   * @throws NoSuchElementException if {@code iterable} is empty
593   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this
594   *     ordering.
595   */
596  @ParametricNullness
597  public <E extends T> E min(Iterable<E> iterable) {
598    return min(iterable.iterator());
599  }
600
601  /**
602   * Returns the lesser of the two values according to this ordering. If the values compare as 0,
603   * the first is returned.
604   *
605   * <p><b>Implementation note:</b> this method is invoked by the default implementations of the
606   * other {@code min} overloads, so overriding it will affect their behavior.
607   *
608   * <p><b>Note:</b> Consider using {@code Comparators.min(a, b, thisComparator)} instead. If {@code
609   * thisComparator} is {@link Ordering#natural}, then use {@code Comparators.min(a, b)}.
610   *
611   * @param a value to compare, returned if less than or equal to b.
612   * @param b value to compare.
613   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this
614   *     ordering.
615   */
616  @ParametricNullness
617  public <E extends T> E min(@ParametricNullness E a, @ParametricNullness E b) {
618    return (compare(a, b) <= 0) ? a : b;
619  }
620
621  /**
622   * Returns the least of the specified values according to this ordering. If there are multiple
623   * least values, the first of those is returned.
624   *
625   * <p><b>Java 8+ users:</b> Use {@code Collections.min(Arrays.asList(a, b, c...), thisComparator)}
626   * instead (but note that it does not guarantee which tied minimum element is returned).
627   *
628   * @param a value to compare, returned if less than or equal to the rest.
629   * @param b value to compare
630   * @param c value to compare
631   * @param rest values to compare
632   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this
633   *     ordering.
634   */
635  @ParametricNullness
636  public <E extends T> E min(
637      @ParametricNullness E a, @ParametricNullness E b, @ParametricNullness E c, E... rest) {
638    E minSoFar = min(min(a, b), c);
639
640    for (E r : rest) {
641      minSoFar = min(minSoFar, r);
642    }
643
644    return minSoFar;
645  }
646
647  /**
648   * Returns the greatest of the specified values according to this ordering. If there are multiple
649   * greatest values, the first of those is returned. The iterator will be left exhausted: its
650   * {@code hasNext()} method will return {@code false}.
651   *
652   * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterator).max(thisComparator).get()} instead
653   * (but note that it does not guarantee which tied maximum element is returned).
654   *
655   * @param iterator the iterator whose maximum element is to be determined
656   * @throws NoSuchElementException if {@code iterator} is empty
657   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this
658   *     ordering.
659   * @since 11.0
660   */
661  @ParametricNullness
662  public <E extends T> E max(Iterator<E> iterator) {
663    // let this throw NoSuchElementException as necessary
664    E maxSoFar = iterator.next();
665
666    while (iterator.hasNext()) {
667      maxSoFar = this.<E>max(maxSoFar, iterator.next());
668    }
669
670    return maxSoFar;
671  }
672
673  /**
674   * Returns the greatest of the specified values according to this ordering. If there are multiple
675   * greatest values, the first of those is returned.
676   *
677   * <p><b>Java 8+ users:</b> If {@code iterable} is a {@link Collection}, use {@code
678   * Collections.max(collection, thisComparator)} instead. Otherwise, use {@code
679   * Streams.stream(iterable).max(thisComparator).get()} instead. Note that these alternatives do
680   * not guarantee which tied maximum element is returned.
681   *
682   * @param iterable the iterable whose maximum element is to be determined
683   * @throws NoSuchElementException if {@code iterable} is empty
684   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this
685   *     ordering.
686   */
687  @ParametricNullness
688  public <E extends T> E max(Iterable<E> iterable) {
689    return max(iterable.iterator());
690  }
691
692  /**
693   * Returns the greater of the two values according to this ordering. If the values compare as 0,
694   * the first is returned.
695   *
696   * <p><b>Implementation note:</b> this method is invoked by the default implementations of the
697   * other {@code max} overloads, so overriding it will affect their behavior.
698   *
699   * <p><b>Note:</b> Consider using {@code Comparators.max(a, b, thisComparator)} instead. If {@code
700   * thisComparator} is {@link Ordering#natural}, then use {@code Comparators.max(a, b)}.
701   *
702   * @param a value to compare, returned if greater than or equal to b.
703   * @param b value to compare.
704   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this
705   *     ordering.
706   */
707  @ParametricNullness
708  public <E extends T> E max(@ParametricNullness E a, @ParametricNullness E b) {
709    return (compare(a, b) >= 0) ? a : b;
710  }
711
712  /**
713   * Returns the greatest of the specified values according to this ordering. If there are multiple
714   * greatest values, the first of those is returned.
715   *
716   * <p><b>Java 8+ users:</b> Use {@code Collections.max(Arrays.asList(a, b, c...), thisComparator)}
717   * instead (but note that it does not guarantee which tied maximum element is returned).
718   *
719   * @param a value to compare, returned if greater than or equal to the rest.
720   * @param b value to compare
721   * @param c value to compare
722   * @param rest values to compare
723   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this
724   *     ordering.
725   */
726  @ParametricNullness
727  public <E extends T> E max(
728      @ParametricNullness E a, @ParametricNullness E b, @ParametricNullness E c, E... rest) {
729    E maxSoFar = max(max(a, b), c);
730
731    for (E r : rest) {
732      maxSoFar = max(maxSoFar, r);
733    }
734
735    return maxSoFar;
736  }
737
738  /**
739   * Returns the {@code k} least elements of the given iterable according to this ordering, in order
740   * from least to greatest. If there are fewer than {@code k} elements present, all will be
741   * included.
742   *
743   * <p>The implementation does not necessarily use a <i>stable</i> sorting algorithm; when multiple
744   * elements are equivalent, it is undefined which will come first.
745   *
746   * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterable).collect(Comparators.least(k,
747   * thisComparator))} instead.
748   *
749   * @return an immutable {@code RandomAccess} list of the {@code k} least elements in ascending
750   *     order
751   * @throws IllegalArgumentException if {@code k} is negative
752   * @since 8.0
753   */
754  public <E extends T> List<E> leastOf(Iterable<E> iterable, int k) {
755    if (iterable instanceof Collection) {
756      Collection<E> collection = (Collection<E>) iterable;
757      if (collection.size() <= 2L * k) {
758        // In this case, just dumping the collection to an array and sorting is
759        // faster than using the implementation for Iterator, which is
760        // specialized for k much smaller than n.
761
762        @SuppressWarnings("unchecked") // c only contains E's and doesn't escape
763        E[] array = (E[]) collection.toArray();
764        sort(array, this);
765        if (array.length > k) {
766          array = Arrays.copyOf(array, k);
767        }
768        return unmodifiableList(asList(array));
769      }
770    }
771    return leastOf(iterable.iterator(), k);
772  }
773
774  /**
775   * Returns the {@code k} least elements from the given iterator according to this ordering, in
776   * order from least to greatest. If there are fewer than {@code k} elements present, all will be
777   * included.
778   *
779   * <p>The implementation does not necessarily use a <i>stable</i> sorting algorithm; when multiple
780   * elements are equivalent, it is undefined which will come first.
781   *
782   * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterator).collect(Comparators.least(k,
783   * thisComparator))} instead.
784   *
785   * @return an immutable {@code RandomAccess} list of the {@code k} least elements in ascending
786   *     order
787   * @throws IllegalArgumentException if {@code k} is negative
788   * @since 14.0
789   */
790  public <E extends T> List<E> leastOf(Iterator<E> iterator, int k) {
791    checkNotNull(iterator);
792    checkNonnegative(k, "k");
793
794    if (k == 0 || !iterator.hasNext()) {
795      return emptyList();
796    } else if (k >= Integer.MAX_VALUE / 2) {
797      // k is really large; just do a straightforward sorted-copy-and-sublist
798      ArrayList<E> list = Lists.newArrayList(iterator);
799      sort(list, this);
800      if (list.size() > k) {
801        list.subList(k, list.size()).clear();
802      }
803      list.trimToSize();
804      return unmodifiableList(list);
805    } else {
806      TopKSelector<E> selector = TopKSelector.least(k, this);
807      selector.offerAll(iterator);
808      return selector.topK();
809    }
810  }
811
812  /**
813   * Returns the {@code k} greatest elements of the given iterable according to this ordering, in
814   * order from greatest to least. If there are fewer than {@code k} elements present, all will be
815   * included.
816   *
817   * <p>The implementation does not necessarily use a <i>stable</i> sorting algorithm; when multiple
818   * elements are equivalent, it is undefined which will come first.
819   *
820   * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterable).collect(Comparators.greatest(k,
821   * thisComparator))} instead.
822   *
823   * @return an immutable {@code RandomAccess} list of the {@code k} greatest elements in
824   *     <i>descending order</i>
825   * @throws IllegalArgumentException if {@code k} is negative
826   * @since 8.0
827   */
828  public <E extends T> List<E> greatestOf(Iterable<E> iterable, int k) {
829    // TODO(kevinb): see if delegation is hurting performance noticeably
830    // TODO(kevinb): if we change this implementation, add full unit tests.
831    return this.<E>reverse().leastOf(iterable, k);
832  }
833
834  /**
835   * Returns the {@code k} greatest elements from the given iterator according to this ordering, in
836   * order from greatest to least. If there are fewer than {@code k} elements present, all will be
837   * included.
838   *
839   * <p>The implementation does not necessarily use a <i>stable</i> sorting algorithm; when multiple
840   * elements are equivalent, it is undefined which will come first.
841   *
842   * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterator).collect(Comparators.greatest(k,
843   * thisComparator))} instead.
844   *
845   * @return an immutable {@code RandomAccess} list of the {@code k} greatest elements in
846   *     <i>descending order</i>
847   * @throws IllegalArgumentException if {@code k} is negative
848   * @since 14.0
849   */
850  public <E extends T> List<E> greatestOf(Iterator<E> iterator, int k) {
851    return this.<E>reverse().leastOf(iterator, k);
852  }
853
854  /**
855   * Returns a <b>mutable</b> list containing {@code elements} sorted by this ordering; use this
856   * only when the resulting list may need further modification, or may contain {@code null}. The
857   * input is not modified. The returned list is serializable and has random access.
858   *
859   * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard elements that are
860   * duplicates according to the comparator. The sort performed is <i>stable</i>, meaning that such
861   * elements will appear in the returned list in the same order they appeared in {@code elements}.
862   *
863   * <p><b>Performance note:</b> According to our
864   * benchmarking
865   * on Open JDK 7, {@link #immutableSortedCopy} generally performs better (in both time and space)
866   * than this method, and this method in turn generally performs better than copying the list and
867   * calling {@link Collections#sort(List)}.
868   */
869  // TODO(kevinb): rerun benchmarks including new options
870  public <E extends T> List<E> sortedCopy(Iterable<E> elements) {
871    @SuppressWarnings("unchecked") // does not escape, and contains only E's
872    E[] array = (E[]) Iterables.toArray(elements);
873    sort(array, this);
874    return Lists.newArrayList(asList(array));
875  }
876
877  /**
878   * Returns an <b>immutable</b> list containing {@code elements} sorted by this ordering. The input
879   * is not modified.
880   *
881   * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard elements that are
882   * duplicates according to the comparator. The sort performed is <i>stable</i>, meaning that such
883   * elements will appear in the returned list in the same order they appeared in {@code elements}.
884   *
885   * <p><b>Performance note:</b> According to our
886   * benchmarking
887   * on Open JDK 7, this method is the most efficient way to make a sorted copy of a collection.
888   *
889   * @throws NullPointerException if any element of {@code elements} is {@code null}
890   * @since 3.0
891   */
892  // TODO(kevinb): rerun benchmarks including new options
893  public <E extends @NonNull T> ImmutableList<E> immutableSortedCopy(Iterable<E> elements) {
894    return ImmutableList.sortedCopyOf(this, elements);
895  }
896
897  /**
898   * Returns {@code true} if each element in {@code iterable} after the first is greater than or
899   * equal to the element that preceded it, according to this ordering. Note that this is always
900   * true when the iterable has fewer than two elements.
901   *
902   * <p><b>Java 8+ users:</b> Use the equivalent {@link Comparators#isInOrder(Iterable, Comparator)}
903   * instead, since the rest of {@code Ordering} is mostly obsolete (as explained in the class
904   * documentation).
905   */
906  public boolean isOrdered(Iterable<? extends T> iterable) {
907    Iterator<? extends T> it = iterable.iterator();
908    if (it.hasNext()) {
909      T prev = it.next();
910      while (it.hasNext()) {
911        T next = it.next();
912        if (compare(prev, next) > 0) {
913          return false;
914        }
915        prev = next;
916      }
917    }
918    return true;
919  }
920
921  /**
922   * Returns {@code true} if each element in {@code iterable} after the first is <i>strictly</i>
923   * greater than the element that preceded it, according to this ordering. Note that this is always
924   * true when the iterable has fewer than two elements.
925   *
926   * <p><b>Java 8+ users:</b> Use the equivalent {@link Comparators#isInStrictOrder(Iterable,
927   * Comparator)} instead, since the rest of {@code Ordering} is mostly obsolete (as explained in
928   * the class documentation).
929   */
930  public boolean isStrictlyOrdered(Iterable<? extends T> iterable) {
931    Iterator<? extends T> it = iterable.iterator();
932    if (it.hasNext()) {
933      T prev = it.next();
934      while (it.hasNext()) {
935        T next = it.next();
936        if (compare(prev, next) >= 0) {
937          return false;
938        }
939        prev = next;
940      }
941    }
942    return true;
943  }
944
945  /**
946   * {@link Collections#binarySearch(List, Object, Comparator) Searches} {@code sortedList} for
947   * {@code key} using the binary search algorithm. The list must be sorted using this ordering.
948   *
949   * @param sortedList the list to be searched
950   * @param key the key to be searched for
951   * @deprecated Use {@link Collections#binarySearch(List, Object, Comparator)} directly.
952   */
953  @Deprecated
954  public int binarySearch(
955      List<? extends T> sortedList, @ParametricNullness T key) {
956    return Collections.binarySearch(sortedList, key, this);
957  }
958
959  /**
960   * Exception thrown by a {@link Ordering#explicit(List)} or {@link Ordering#explicit(Object,
961   * Object[])} comparator when comparing a value outside the set of values it can compare.
962   * Extending {@link ClassCastException} may seem odd, but it is required.
963   */
964  static class IncomparableValueException extends ClassCastException {
965    final Object value;
966
967    IncomparableValueException(Object value) {
968      super("Cannot compare value: " + value);
969      this.value = value;
970    }
971
972    private static final long serialVersionUID = 0;
973  }
974
975  // Never make these public
976  static final int LEFT_IS_GREATER = 1;
977  static final int RIGHT_IS_GREATER = -1;
978}