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