    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.
    582       *
    583       * @param iterable the iterable whose maximum element is to be determined
    584       * @throws NoSuchElementException if {@code iterable} is empty
    585       * @throws ClassCastException if the parameters are not <i>mutually
    586       *     comparable</i> under this ordering.
    587       */
    588      public <E extends T> E max(Iterable<E> iterable) {
    589        Iterator<E> iterator = iterable.iterator();
    590
    591        // let this throw NoSuchElementException as necessary
    592        E maxSoFar = iterator.next();
    593
    594        while (iterator.hasNext()) {
    595          maxSoFar = max(maxSoFar, iterator.next());
    596        }
    597
    598        return maxSoFar;
    599      }
    600
    601      /**
    602       * Returns the greatest of the specified values according to this ordering. If
    603       * there are multiple greatest values, the first of those is returned.
    604       *
    605       * @param a value to compare, returned if greater than or equal to the rest.
    606       * @param b value to compare
    607       * @param c value to compare
    608       * @param rest values to compare
    609       * @throws ClassCastException if the parameters are not <i>mutually
    610       *     comparable</i> under this ordering.
    611       */
    612      public <E extends T> E max(
    613          @Nullable E a, @Nullable E b, @Nullable E c, E... rest) {
    614        E maxSoFar = max(max(a, b), c);
    615
    616        for (E r : rest) {
    617          maxSoFar = max(maxSoFar, r);
    618        }
    619
    620        return maxSoFar;
    621      }
    622
    623      /**
    624       * Returns the greater of the two values according to this ordering. If the
    625       * values compare as 0, the first is returned.
    626       *
    627       * <p><b>Implementation note:</b> this method is invoked by the default
    628       * implementations of the other {@code max} overloads, so overriding it will
    629       * affect their behavior.
    630       *
    631       * @param a value to compare, returned if greater than or equal to b.
    632       * @param b value to compare.
    633       * @throws ClassCastException if the parameters are not <i>mutually
    634       *     comparable</i> under this ordering.
    635       */
    636      public <E extends T> E max(@Nullable E a, @Nullable E b) {
    637        return compare(a, b) >= 0 ? a : b;
    638      }
    639
    640      /**
    641       * Returns the least of the specified values according to this ordering. If
    642       * there are multiple least values, the first of those is returned.
    643       *
    644       * @param iterable the iterable whose minimum element is to be determined
    645       * @throws NoSuchElementException if {@code iterable} is empty
    646       * @throws ClassCastException if the parameters are not <i>mutually
    647       *     comparable</i> under this ordering.
    648       */
    649      public <E extends T> E min(Iterable<E> iterable) {
    650        Iterator<E> iterator = iterable.iterator();
    651
    652        // let this throw NoSuchElementException as necessary
    653        E minSoFar = iterator.next();
    654
    655        while (iterator.hasNext()) {
    656          minSoFar = min(minSoFar, iterator.next());
    657        }
    658
    659        return minSoFar;
    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.
    665       *
    666       * @param a value to compare, returned if less than or equal to the rest.
    667       * @param b value to compare
    668       * @param c value to compare
    669       * @param rest values to compare
    670       * @throws ClassCastException if the parameters are not <i>mutually
    671       *     comparable</i> under this ordering.
    672       */
    673      public <E extends T> E min(
    674          @Nullable E a, @Nullable E b, @Nullable E c, E... rest) {
    675        E minSoFar = min(min(a, b), c);
    676
    677        for (E r : rest) {
    678          minSoFar = min(minSoFar, r);
    679        }
    680
    681        return minSoFar;
    682      }
    683
    684      /**
    685       * Returns the lesser of the two values according to this ordering. If the
    686       * values compare as 0, the first is returned.
    687       *
    688       * <p><b>Implementation note:</b> this method is invoked by the default
    689       * implementations of the other {@code min} overloads, so overriding it will
    690       * affect their behavior.
    691       *
    692       * @param a value to compare, returned if less than or equal to b.
    693       * @param b value to compare.
    694       * @throws ClassCastException if the parameters are not <i>mutually
    695       *     comparable</i> under this ordering.
    696       */
    697      public <E extends T> E min(@Nullable E a, @Nullable E b) {
    698        return compare(a, b) <= 0 ? a : b;
    699      }
    700
    701      // Never make these public
    702      static final int LEFT_IS_GREATER = 1;
    703      static final int RIGHT_IS_GREATER = -1;
    704    }