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