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