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
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021
022 import com.google.common.annotations.Beta;
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.annotations.VisibleForTesting;
025 import com.google.common.base.Function;
026
027 import java.util.Arrays;
028 import java.util.Collections;
029 import java.util.Comparator;
030 import java.util.HashSet;
031 import java.util.Iterator;
032 import java.util.List;
033 import java.util.Map;
034 import java.util.NoSuchElementException;
035 import java.util.SortedMap;
036 import java.util.SortedSet;
037 import java.util.concurrent.atomic.AtomicInteger;
038
039 import javax.annotation.Nullable;
040
041 /**
042 * A comparator with added methods to support common functions. For example:
043 * <pre> {@code
044 *
045 * if (Ordering.from(comparator).reverse().isOrdered(list)) { ... }}</pre>
046 *
047 * The {@link #from(Comparator)} method returns the equivalent {@code Ordering}
048 * instance for a pre-existing comparator. You can also skip the comparator step
049 * and extend {@code Ordering} directly: <pre> {@code
050 *
051 * Ordering<String> byLengthOrdering = new Ordering<String>() {
052 * public int compare(String left, String right) {
053 * return Ints.compare(left.length(), right.length());
054 * }
055 * };}</pre>
056 *
057 * Except as noted, the orderings returned by the factory methods of this
058 * class are serializable if and only if the provided instances that back them
059 * are. For example, if {@code ordering} and {@code function} can themselves be
060 * serialized, then {@code ordering.onResultOf(function)} can as well.
061 *
062 * <p>See the Guava User Guide article on <a href=
063 * "http://code.google.com/p/guava-libraries/wiki/OrderingExplained">
064 * {@code Ordering}</a>.
065 *
066 * @author Jesse Wilson
067 * @author Kevin Bourrillion
068 * @since 2.0 (imported from Google Collections Library)
069 */
070 @GwtCompatible
071 public abstract class Ordering<T> implements Comparator<T> {
072 // Static factories
073
074 /**
075 * Returns a serializable ordering that uses the natural order of the values.
076 * The ordering throws a {@link NullPointerException} when passed a null
077 * parameter.
078 *
079 * <p>The type specification is {@code <C extends Comparable>}, instead of
080 * the technically correct {@code <C extends Comparable<? super C>>}, to
081 * support legacy types from before Java 5.
082 */
083 @GwtCompatible(serializable = true)
084 @SuppressWarnings("unchecked") // TODO(kevinb): right way to explain this??
085 public static <C extends Comparable> Ordering<C> natural() {
086 return (Ordering<C>) NaturalOrdering.INSTANCE;
087 }
088
089 /**
090 * Returns an ordering based on an <i>existing</i> comparator instance. Note
091 * that there's no need to create a <i>new</i> comparator just to pass it in
092 * here; simply subclass {@code Ordering} and implement its {@code compareTo}
093 * method directly instead.
094 *
095 * @param comparator the comparator that defines the order
096 * @return comparator itself if it is already an {@code Ordering}; otherwise
097 * an ordering that wraps that comparator
098 */
099 @GwtCompatible(serializable = true)
100 public static <T> Ordering<T> from(Comparator<T> comparator) {
101 return (comparator instanceof Ordering)
102 ? (Ordering<T>) comparator
103 : new ComparatorOrdering<T>(comparator);
104 }
105
106 /**
107 * Simply returns its argument.
108 *
109 * @deprecated no need to use this
110 */
111 @GwtCompatible(serializable = true)
112 @Deprecated public static <T> Ordering<T> from(Ordering<T> ordering) {
113 return checkNotNull(ordering);
114 }
115
116 /**
117 * Returns an ordering that compares objects according to the order in
118 * which they appear in the given list. Only objects present in the list
119 * (according to {@link Object#equals}) may be compared. This comparator
120 * imposes a "partial ordering" over the type {@code T}. Subsequent changes
121 * to the {@code valuesInOrder} list will have no effect on the returned
122 * comparator. Null values in the list are not supported.
123 *
124 * <p>The returned comparator throws an {@link ClassCastException} when it
125 * receives an input parameter that isn't among the provided values.
126 *
127 * <p>The generated comparator is serializable if all the provided values are
128 * serializable.
129 *
130 * @param valuesInOrder the values that the returned comparator will be able
131 * to compare, in the order the comparator should induce
132 * @return the comparator described above
133 * @throws NullPointerException if any of the provided values is null
134 * @throws IllegalArgumentException if {@code valuesInOrder} contains any
135 * duplicate values (according to {@link Object#equals})
136 */
137 @GwtCompatible(serializable = true)
138 public static <T> Ordering<T> explicit(List<T> valuesInOrder) {
139 return new ExplicitOrdering<T>(valuesInOrder);
140 }
141
142 /**
143 * Returns an ordering that compares objects according to the order in
144 * which they are given to this method. Only objects present in the argument
145 * list (according to {@link Object#equals}) may be compared. This comparator
146 * imposes a "partial ordering" over the type {@code T}. Null values in the
147 * argument list are not supported.
148 *
149 * <p>The returned comparator throws a {@link ClassCastException} when it
150 * receives an input parameter that isn't among the provided values.
151 *
152 * <p>The generated comparator is serializable if all the provided values are
153 * serializable.
154 *
155 * @param leastValue the value which the returned comparator should consider
156 * the "least" of all values
157 * @param remainingValuesInOrder the rest of the values that the returned
158 * comparator will be able to compare, in the order the comparator should
159 * follow
160 * @return the comparator described above
161 * @throws NullPointerException if any of the provided values is null
162 * @throws IllegalArgumentException if any duplicate values (according to
163 * {@link Object#equals(Object)}) are present among the method arguments
164 */
165 @GwtCompatible(serializable = true)
166 public static <T> Ordering<T> explicit(
167 T leastValue, T... remainingValuesInOrder) {
168 return explicit(Lists.asList(leastValue, remainingValuesInOrder));
169 }
170
171 /**
172 * Exception thrown by a {@link Ordering#explicit(List)} or {@link
173 * Ordering#explicit(Object, Object[])} comparator when comparing a value
174 * outside the set of values it can compare. Extending {@link
175 * ClassCastException} may seem odd, but it is required.
176 */
177 // TODO(kevinb): make this public, document it right
178 @VisibleForTesting
179 static class IncomparableValueException extends ClassCastException {
180 final Object value;
181
182 IncomparableValueException(Object value) {
183 super("Cannot compare value: " + value);
184 this.value = value;
185 }
186
187 private static final long serialVersionUID = 0;
188 }
189
190 /**
191 * Returns an arbitrary ordering over all objects, for which {@code compare(a,
192 * b) == 0} implies {@code a == b} (identity equality). There is no meaning
193 * whatsoever to the order imposed, but it is constant for the life of the VM.
194 *
195 * <p>Because the ordering is identity-based, it is not "consistent with
196 * {@link Object#equals(Object)}" as defined by {@link Comparator}. Use
197 * caution when building a {@link SortedSet} or {@link SortedMap} from it, as
198 * the resulting collection will not behave exactly according to spec.
199 *
200 * <p>This ordering is not serializable, as its implementation relies on
201 * {@link System#identityHashCode(Object)}, so its behavior cannot be
202 * preserved across serialization.
203 *
204 * @since 2.0
205 */
206 public static Ordering<Object> arbitrary() {
207 return ArbitraryOrderingHolder.ARBITRARY_ORDERING;
208 }
209
210 private static class ArbitraryOrderingHolder {
211 static final Ordering<Object> ARBITRARY_ORDERING = new ArbitraryOrdering();
212 }
213
214 @VisibleForTesting static class ArbitraryOrdering extends Ordering<Object> {
215 @SuppressWarnings("deprecation") // TODO(kevinb): ?
216 private Map<Object, Integer> uids =
217 Platform.tryWeakKeys(new MapMaker()).makeComputingMap(
218 new Function<Object, Integer>() {
219 final AtomicInteger counter = new AtomicInteger(0);
220 @Override
221 public Integer apply(Object from) {
222 return counter.getAndIncrement();
223 }
224 });
225
226 @Override public int compare(Object left, Object right) {
227 if (left == right) {
228 return 0;
229 }
230 int leftCode = identityHashCode(left);
231 int rightCode = identityHashCode(right);
232 if (leftCode != rightCode) {
233 return leftCode < rightCode ? -1 : 1;
234 }
235
236 // identityHashCode collision (rare, but not as rare as you'd think)
237 int result = uids.get(left).compareTo(uids.get(right));
238 if (result == 0) {
239 throw new AssertionError(); // extremely, extremely unlikely.
240 }
241 return result;
242 }
243
244 @Override public String toString() {
245 return "Ordering.arbitrary()";
246 }
247
248 /*
249 * We need to be able to mock identityHashCode() calls for tests, because it
250 * can take 1-10 seconds to find colliding objects. Mocking frameworks that
251 * can do magic to mock static method calls still can't do so for a system
252 * class, so we need the indirection. In production, Hotspot should still
253 * recognize that the call is 1-morphic and should still be willing to
254 * inline it if necessary.
255 */
256 int identityHashCode(Object object) {
257 return System.identityHashCode(object);
258 }
259 }
260
261 /**
262 * Returns an ordering that compares objects by the natural ordering of their
263 * string representations as returned by {@code toString()}. It does not
264 * support null values.
265 *
266 * <p>The comparator is serializable.
267 */
268 @GwtCompatible(serializable = true)
269 public static Ordering<Object> usingToString() {
270 return UsingToStringOrdering.INSTANCE;
271 }
272
273 /**
274 * Returns an ordering which tries each given comparator in order until a
275 * non-zero result is found, returning that result, and returning zero only if
276 * all comparators return zero. The returned ordering is based on the state of
277 * the {@code comparators} iterable at the time it was provided to this
278 * method.
279 *
280 * <p>The returned ordering is equivalent to that produced using {@code
281 * Ordering.from(comp1).compound(comp2).compound(comp3) . . .}.
282 *
283 * <p><b>Warning:</b> Supplying an argument with undefined iteration order,
284 * such as a {@link HashSet}, will produce non-deterministic results.
285 *
286 * @param comparators the comparators to try in order
287 */
288 @GwtCompatible(serializable = true)
289 public static <T> Ordering<T> compound(
290 Iterable<? extends Comparator<? super T>> comparators) {
291 return new CompoundOrdering<T>(comparators);
292 }
293
294 /**
295 * Constructs a new instance of this class (only invokable by the subclass
296 * constructor, typically implicit).
297 */
298 protected Ordering() {}
299
300 // Non-static factories
301
302 /**
303 * Returns an ordering which first uses the ordering {@code this}, but which
304 * in the event of a "tie", then delegates to {@code secondaryComparator}.
305 * For example, to sort a bug list first by status and second by priority, you
306 * might use {@code byStatus.compound(byPriority)}. For a compound ordering
307 * with three or more components, simply chain multiple calls to this method.
308 *
309 * <p>An ordering produced by this method, or a chain of calls to this method,
310 * is equivalent to one created using {@link Ordering#compound(Iterable)} on
311 * the same component comparators.
312 */
313 @GwtCompatible(serializable = true)
314 public <U extends T> Ordering<U> compound(
315 Comparator<? super U> secondaryComparator) {
316 return new CompoundOrdering<U>(this, checkNotNull(secondaryComparator));
317 }
318
319 /**
320 * Returns the reverse of this ordering; the {@code Ordering} equivalent to
321 * {@link Collections#reverseOrder(Comparator)}.
322 */
323 // type parameter <S> lets us avoid the extra <String> in statements like:
324 // Ordering<String> o = Ordering.<String>natural().reverse();
325 @GwtCompatible(serializable = true)
326 public <S extends T> Ordering<S> reverse() {
327 return new ReverseOrdering<S>(this);
328 }
329
330 /**
331 * Returns a new ordering on {@code F} which orders elements by first applying
332 * a function to them, then comparing those results using {@code this}. For
333 * example, to compare objects by their string forms, in a case-insensitive
334 * manner, use: <pre> {@code
335 *
336 * Ordering.from(String.CASE_INSENSITIVE_ORDER)
337 * .onResultOf(Functions.toStringFunction())}</pre>
338 */
339 @GwtCompatible(serializable = true)
340 public <F> Ordering<F> onResultOf(Function<F, ? extends T> function) {
341 return new ByFunctionOrdering<F, T>(function, this);
342 }
343
344 /**
345 * Returns a new ordering which sorts iterables by comparing corresponding
346 * elements pairwise until a nonzero result is found; imposes "dictionary
347 * order". If the end of one iterable is reached, but not the other, the
348 * shorter iterable is considered to be less than the longer one. For example,
349 * a lexicographical natural ordering over integers considers {@code
350 * [] < [1] < [1, 1] < [1, 2] < [2]}.
351 *
352 * <p>Note that {@code ordering.lexicographical().reverse()} is not
353 * equivalent to {@code ordering.reverse().lexicographical()} (consider how
354 * each would order {@code [1]} and {@code [1, 1]}).
355 *
356 * @since 2.0
357 */
358 @GwtCompatible(serializable = true)
359 // type parameter <S> lets us avoid the extra <String> in statements like:
360 // Ordering<Iterable<String>> o =
361 // Ordering.<String>natural().lexicographical();
362 public <S extends T> Ordering<Iterable<S>> lexicographical() {
363 /*
364 * Note that technically the returned ordering should be capable of
365 * handling not just {@code Iterable<S>} instances, but also any {@code
366 * Iterable<? extends S>}. However, the need for this comes up so rarely
367 * that it doesn't justify making everyone else deal with the very ugly
368 * wildcard.
369 */
370 return new LexicographicalOrdering<S>(this);
371 }
372
373 /**
374 * Returns an ordering that treats {@code null} as less than all other values
375 * and uses {@code this} to compare non-null values.
376 */
377 // type parameter <S> lets us avoid the extra <String> in statements like:
378 // Ordering<String> o = Ordering.<String>natural().nullsFirst();
379 @GwtCompatible(serializable = true)
380 public <S extends T> Ordering<S> nullsFirst() {
381 return new NullsFirstOrdering<S>(this);
382 }
383
384 /**
385 * Returns an ordering that treats {@code null} as greater than all other
386 * values and uses this ordering to compare non-null values.
387 */
388 // type parameter <S> lets us avoid the extra <String> in statements like:
389 // Ordering<String> o = Ordering.<String>natural().nullsLast();
390 @GwtCompatible(serializable = true)
391 public <S extends T> Ordering<S> nullsLast() {
392 return new NullsLastOrdering<S>(this);
393 }
394
395 // Regular instance methods
396
397 // Override to add @Nullable
398 @Override public abstract int compare(@Nullable T left, @Nullable T right);
399
400 /**
401 * Returns the {@code k} least elements of the given iterable according to
402 * this ordering, in order from least to greatest. If there are fewer than
403 * {@code k} elements present, all will be included.
404 *
405 * <p>The implementation does not necessarily use a <i>stable</i> sorting
406 * algorithm; when multiple elements are equivalent, it is undefined which
407 * will come first.
408 *
409 * @return an immutable {@code RandomAccess} list of the {@code k} least
410 * elements in ascending order
411 * @throws IllegalArgumentException if {@code k} is negative
412 * @since 8.0
413 */
414 @Beta
415 public <E extends T> List<E> leastOf(Iterable<E> iterable, int k) {
416 checkArgument(k >= 0, "%d is negative", k);
417
418 // values is not an E[], but we use it as such for readability. Hack.
419 @SuppressWarnings("unchecked")
420 E[] values = (E[]) Iterables.toArray(iterable);
421
422 // TODO(nshupe): also sort whole list if k is *near* values.length?
423 // TODO(kevinb): benchmark this impl against hand-coded heap
424 E[] resultArray;
425 if (values.length <= k) {
426 Arrays.sort(values, this);
427 resultArray = values;
428 } else {
429 quicksortLeastK(values, 0, values.length - 1, k);
430
431 // this is not an E[], but we use it as such for readability. Hack.
432 @SuppressWarnings("unchecked")
433 E[] tmp = (E[]) new Object[k];
434 resultArray = tmp;
435 System.arraycopy(values, 0, resultArray, 0, k);
436 }
437
438 return Collections.unmodifiableList(Arrays.asList(resultArray));
439 }
440
441 /**
442 * Returns the {@code k} greatest elements of the given iterable according to
443 * this ordering, in order from greatest to least. If there are fewer than
444 * {@code k} elements present, all will be included.
445 *
446 * <p>The implementation does not necessarily use a <i>stable</i> sorting
447 * algorithm; when multiple elements are equivalent, it is undefined which
448 * will come first.
449 *
450 * @return an immutable {@code RandomAccess} list of the {@code k} greatest
451 * elements in <i>descending order</i>
452 * @throws IllegalArgumentException if {@code k} is negative
453 * @since 8.0
454 */
455 @Beta
456 public <E extends T> List<E> greatestOf(Iterable<E> iterable, int k) {
457 // TODO(kevinb): see if delegation is hurting performance noticeably
458 // TODO(kevinb): if we change this implementation, add full unit tests.
459 return reverse().leastOf(iterable, k);
460 }
461
462 private <E extends T> void quicksortLeastK(
463 E[] values, int left, int right, int k) {
464 if (right > left) {
465 int pivotIndex = (left + right) >>> 1; // left + ((right - left) / 2)
466 int pivotNewIndex = partition(values, left, right, pivotIndex);
467 quicksortLeastK(values, left, pivotNewIndex - 1, k);
468 if (pivotNewIndex < k) {
469 quicksortLeastK(values, pivotNewIndex + 1, right, k);
470 }
471 }
472 }
473
474 private <E extends T> int partition(
475 E[] values, int left, int right, int pivotIndex) {
476 E pivotValue = values[pivotIndex];
477
478 values[pivotIndex] = values[right];
479 values[right] = pivotValue;
480
481 int storeIndex = left;
482 for (int i = left; i < right; i++) {
483 if (compare(values[i], pivotValue) < 0) {
484 ObjectArrays.swap(values, storeIndex, i);
485 storeIndex++;
486 }
487 }
488 ObjectArrays.swap(values, right, storeIndex);
489 return storeIndex;
490 }
491
492 /**
493 * {@link Collections#binarySearch(List, Object, Comparator) Searches}
494 * {@code sortedList} for {@code key} using the binary search algorithm. The
495 * list must be sorted using this ordering.
496 *
497 * @param sortedList the list to be searched
498 * @param key the key to be searched for
499 */
500 public int binarySearch(List<? extends T> sortedList, @Nullable T key) {
501 return Collections.binarySearch(sortedList, key, this);
502 }
503
504 /**
505 * Returns a copy of the given iterable sorted by this ordering. The input is
506 * not modified. The returned list is modifiable, serializable, and has random
507 * access.
508 *
509 * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard
510 * elements that are duplicates according to the comparator. The sort
511 * performed is <i>stable</i>, meaning that such elements will appear in the
512 * resulting list in the same order they appeared in the input.
513 *
514 * @param iterable the elements to be copied and sorted
515 * @return a new list containing the given elements in sorted order
516 */
517 public <E extends T> List<E> sortedCopy(Iterable<E> iterable) {
518 List<E> list = Lists.newArrayList(iterable);
519 Collections.sort(list, this);
520 return list;
521 }
522
523 /**
524 * Returns an <i>immutable</i> copy of the given iterable sorted by this
525 * ordering. The input is not modified.
526 *
527 * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard
528 * elements that are duplicates according to the comparator. The sort
529 * performed is <i>stable</i>, meaning that such elements will appear in the
530 * resulting list in the same order they appeared in the input.
531 *
532 * @param iterable the elements to be copied and sorted
533 * @return a new immutable list containing the given elements in sorted order
534 * @throws NullPointerException if {@code iterable} or any of its elements is
535 * null
536 * @since 3.0
537 */
538 public <E extends T> ImmutableList<E> immutableSortedCopy(
539 Iterable<E> iterable) {
540 return ImmutableList.copyOf(sortedCopy(iterable));
541 }
542
543 /**
544 * Returns {@code true} if each element in {@code iterable} after the first is
545 * greater than or equal to the element that preceded it, according to this
546 * ordering. Note that this is always true when the iterable has fewer than
547 * two elements.
548 */
549 public boolean isOrdered(Iterable<? extends T> iterable) {
550 Iterator<? extends T> it = iterable.iterator();
551 if (it.hasNext()) {
552 T prev = it.next();
553 while (it.hasNext()) {
554 T next = it.next();
555 if (compare(prev, next) > 0) {
556 return false;
557 }
558 prev = next;
559 }
560 }
561 return true;
562 }
563
564 /**
565 * Returns {@code true} if each element in {@code iterable} after the first is
566 * <i>strictly</i> greater than the element that preceded it, according to
567 * this ordering. Note that this is always true when the iterable has fewer
568 * than two elements.
569 */
570 public boolean isStrictlyOrdered(Iterable<? extends T> iterable) {
571 Iterator<? extends T> it = iterable.iterator();
572 if (it.hasNext()) {
573 T prev = it.next();
574 while (it.hasNext()) {
575 T next = it.next();
576 if (compare(prev, next) >= 0) {
577 return false;
578 }
579 prev = next;
580 }
581 }
582 return true;
583 }
584
585 /**
586 * Returns the greatest of the specified values according to this ordering. If
587 * there are multiple greatest values, the first of those is returned. The
588 * iterator will be left exhausted: its {@code hasNext()} method will return
589 * {@code false}.
590 *
591 * @param iterator the iterator whose maximum element is to be determined
592 * @throws NoSuchElementException if {@code iterator} is empty
593 * @throws ClassCastException if the parameters are not <i>mutually
594 * comparable</i> under this ordering.
595 *
596 * @since 11.0
597 */
598 @Beta
599 public <E extends T> E max(Iterator<E> iterator) {
600 // let this throw NoSuchElementException as necessary
601 E maxSoFar = iterator.next();
602
603 while (iterator.hasNext()) {
604 maxSoFar = max(maxSoFar, iterator.next());
605 }
606
607 return maxSoFar;
608 }
609
610 /**
611 * Returns the greatest of the specified values according to this ordering. If
612 * there are multiple greatest values, the first of those is returned.
613 *
614 * @param iterable the iterable whose maximum element is to be determined
615 * @throws NoSuchElementException if {@code iterable} is empty
616 * @throws ClassCastException if the parameters are not <i>mutually
617 * comparable</i> under this ordering.
618 */
619 public <E extends T> E max(Iterable<E> iterable) {
620 return max(iterable.iterator());
621 }
622
623 /**
624 * Returns the greatest of the specified values according to this ordering. If
625 * there are multiple greatest values, the first of those is returned.
626 *
627 * @param a value to compare, returned if greater than or equal to the rest.
628 * @param b value to compare
629 * @param c value to compare
630 * @param rest values to compare
631 * @throws ClassCastException if the parameters are not <i>mutually
632 * comparable</i> under this ordering.
633 */
634 public <E extends T> E max(
635 @Nullable E a, @Nullable E b, @Nullable E c, E... rest) {
636 E maxSoFar = max(max(a, b), c);
637
638 for (E r : rest) {
639 maxSoFar = max(maxSoFar, r);
640 }
641
642 return maxSoFar;
643 }
644
645 /**
646 * Returns the greater of the two values according to this ordering. If the
647 * values compare as 0, the first is returned.
648 *
649 * <p><b>Implementation note:</b> this method is invoked by the default
650 * implementations of the other {@code max} overloads, so overriding it will
651 * affect their behavior.
652 *
653 * @param a value to compare, returned if greater than or equal to b.
654 * @param b value to compare.
655 * @throws ClassCastException if the parameters are not <i>mutually
656 * comparable</i> under this ordering.
657 */
658 public <E extends T> E max(@Nullable E a, @Nullable E b) {
659 return compare(a, b) >= 0 ? a : b;
660 }
661
662 /**
663 * Returns the least of the specified values according to this ordering. If
664 * there are multiple least values, the first of those is returned. The
665 * iterator will be left exhausted: its {@code hasNext()} method will return
666 * {@code false}.
667 *
668 * @param iterator the iterator whose minimum element is to be determined
669 * @throws NoSuchElementException if {@code iterator} is empty
670 * @throws ClassCastException if the parameters are not <i>mutually
671 * comparable</i> under this ordering.
672 *
673 * @since 11.0
674 */
675 @Beta
676 public <E extends T> E min(Iterator<E> iterator) {
677 // let this throw NoSuchElementException as necessary
678 E minSoFar = iterator.next();
679
680 while (iterator.hasNext()) {
681 minSoFar = min(minSoFar, iterator.next());
682 }
683
684 return minSoFar;
685 }
686
687 /**
688 * Returns the least of the specified values according to this ordering. If
689 * there are multiple least values, the first of those is returned.
690 *
691 * @param iterable the iterable whose minimum element is to be determined
692 * @throws NoSuchElementException if {@code iterable} is empty
693 * @throws ClassCastException if the parameters are not <i>mutually
694 * comparable</i> under this ordering.
695 */
696 public <E extends T> E min(Iterable<E> iterable) {
697 return min(iterable.iterator());
698 }
699
700 /**
701 * Returns the least of the specified values according to this ordering. If
702 * there are multiple least values, the first of those is returned.
703 *
704 * @param a value to compare, returned if less than or equal to the rest.
705 * @param b value to compare
706 * @param c value to compare
707 * @param rest values to compare
708 * @throws ClassCastException if the parameters are not <i>mutually
709 * comparable</i> under this ordering.
710 */
711 public <E extends T> E min(
712 @Nullable E a, @Nullable E b, @Nullable E c, E... rest) {
713 E minSoFar = min(min(a, b), c);
714
715 for (E r : rest) {
716 minSoFar = min(minSoFar, r);
717 }
718
719 return minSoFar;
720 }
721
722 /**
723 * Returns the lesser of the two values according to this ordering. If the
724 * values compare as 0, the first is returned.
725 *
726 * <p><b>Implementation note:</b> this method is invoked by the default
727 * implementations of the other {@code min} overloads, so overriding it will
728 * affect their behavior.
729 *
730 * @param a value to compare, returned if less than or equal to b.
731 * @param b value to compare.
732 * @throws ClassCastException if the parameters are not <i>mutually
733 * comparable</i> under this ordering.
734 */
735 public <E extends T> E min(@Nullable E a, @Nullable E b) {
736 return compare(a, b) <= 0 ? a : b;
737 }
738
739 // Never make these public
740 static final int LEFT_IS_GREATER = 1;
741 static final int RIGHT_IS_GREATER = -1;
742 }