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