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