001/*
002 * Copyright (C) 2016 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
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.CollectPreconditions.checkNonnegative;
021
022import com.google.common.annotations.GwtCompatible;
023import java.util.Comparator;
024import java.util.Iterator;
025import java.util.List;
026import java.util.Optional;
027import java.util.stream.Collector;
028import org.jspecify.annotations.Nullable;
029
030/**
031 * Provides static methods for working with {@link Comparator} instances. For many other helpful
032 * comparator utilities, see either {@code Comparator} itself (for Java 8+), or {@code
033 * com.google.common.collect.Ordering} (otherwise).
034 *
035 * <h3>Relationship to {@code Ordering}</h3>
036 *
037 * <p>In light of the significant enhancements to {@code Comparator} in Java 8, the overwhelming
038 * majority of usages of {@code Ordering} can be written using only built-in JDK APIs. This class is
039 * intended to "fill the gap" and provide those features of {@code Ordering} not already provided by
040 * the JDK.
041 *
042 * @since 21.0
043 * @author Louis Wasserman
044 */
045@GwtCompatible
046public final class Comparators {
047  private Comparators() {}
048
049  /**
050   * Returns a new comparator which sorts iterables by comparing corresponding elements pairwise
051   * until a nonzero result is found; imposes "dictionary order." If the end of one iterable is
052   * reached, but not the other, the shorter iterable is considered to be less than the longer one.
053   * For example, a lexicographical natural ordering over integers considers {@code [] < [1] < [1,
054   * 1] < [1, 2] < [2]}.
055   *
056   * <p>Note that {@code Collections.reverseOrder(lexicographical(comparator))} is not equivalent to
057   * {@code lexicographical(Collections.reverseOrder(comparator))} (consider how each would order
058   * {@code [1]} and {@code [1, 1]}).
059   */
060  // Note: 90% of the time we don't add type parameters or wildcards that serve only to "tweak" the
061  // desired return type. However, *nested* generics introduce a special class of problems that we
062  // think tip it over into being worthwhile.
063  public static <T extends @Nullable Object, S extends T> Comparator<Iterable<S>> lexicographical(
064      Comparator<T> comparator) {
065    return new LexicographicalOrdering<S>(checkNotNull(comparator));
066  }
067
068  /**
069   * Returns {@code true} if each element in {@code iterable} after the first is greater than or
070   * equal to the element that preceded it, according to the specified comparator. Note that this is
071   * always true when the iterable has fewer than two elements.
072   */
073  public static <T extends @Nullable Object> boolean isInOrder(
074      Iterable<? extends T> iterable, Comparator<T> comparator) {
075    checkNotNull(comparator);
076    Iterator<? extends T> it = iterable.iterator();
077    if (it.hasNext()) {
078      T prev = it.next();
079      while (it.hasNext()) {
080        T next = it.next();
081        if (comparator.compare(prev, next) > 0) {
082          return false;
083        }
084        prev = next;
085      }
086    }
087    return true;
088  }
089
090  /**
091   * Returns {@code true} if each element in {@code iterable} after the first is <i>strictly</i>
092   * greater than the element that preceded it, according to the specified comparator. Note that
093   * this is always true when the iterable has fewer than two elements.
094   */
095  public static <T extends @Nullable Object> boolean isInStrictOrder(
096      Iterable<? extends T> iterable, Comparator<T> comparator) {
097    checkNotNull(comparator);
098    Iterator<? extends T> it = iterable.iterator();
099    if (it.hasNext()) {
100      T prev = it.next();
101      while (it.hasNext()) {
102        T next = it.next();
103        if (comparator.compare(prev, next) >= 0) {
104          return false;
105        }
106        prev = next;
107      }
108    }
109    return true;
110  }
111
112  /**
113   * Returns a {@code Collector} that returns the {@code k} smallest (relative to the specified
114   * {@code Comparator}) input elements, in ascending order, as an unmodifiable {@code List}. Ties
115   * are broken arbitrarily.
116   *
117   * <p>For example:
118   *
119   * <pre>{@code
120   * Stream.of("foo", "quux", "banana", "elephant")
121   *     .collect(least(2, comparingInt(String::length)))
122   * // returns {"foo", "quux"}
123   * }</pre>
124   *
125   * <p>This {@code Collector} uses O(k) memory and takes expected time O(n) (worst-case O(n log
126   * k)), as opposed to e.g. {@code Stream.sorted(comparator).limit(k)}, which currently takes O(n
127   * log n) time and O(n) space.
128   *
129   * @throws IllegalArgumentException if {@code k < 0}
130   * @since 22.0
131   */
132  public static <T extends @Nullable Object> Collector<T, ?, List<T>> least(
133      int k, Comparator<? super T> comparator) {
134    checkNonnegative(k, "k");
135    checkNotNull(comparator);
136    return Collector.of(
137        () -> TopKSelector.<T>least(k, comparator),
138        TopKSelector::offer,
139        TopKSelector::combine,
140        TopKSelector::topK,
141        Collector.Characteristics.UNORDERED);
142  }
143
144  /**
145   * Returns a {@code Collector} that returns the {@code k} greatest (relative to the specified
146   * {@code Comparator}) input elements, in descending order, as an unmodifiable {@code List}. Ties
147   * are broken arbitrarily.
148   *
149   * <p>For example:
150   *
151   * <pre>{@code
152   * Stream.of("foo", "quux", "banana", "elephant")
153   *     .collect(greatest(2, comparingInt(String::length)))
154   * // returns {"elephant", "banana"}
155   * }</pre>
156   *
157   * <p>This {@code Collector} uses O(k) memory and takes expected time O(n) (worst-case O(n log
158   * k)), as opposed to e.g. {@code Stream.sorted(comparator.reversed()).limit(k)}, which currently
159   * takes O(n log n) time and O(n) space.
160   *
161   * @throws IllegalArgumentException if {@code k < 0}
162   * @since 22.0
163   */
164  public static <T extends @Nullable Object> Collector<T, ?, List<T>> greatest(
165      int k, Comparator<? super T> comparator) {
166    return least(k, comparator.reversed());
167  }
168
169  /**
170   * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as less
171   * than all other values, and orders the rest using {@code valueComparator} on the contained
172   * value.
173   *
174   * @since 22.0 (but only since 33.4.0 in the Android flavor)
175   */
176  public static <T> Comparator<Optional<T>> emptiesFirst(Comparator<? super T> valueComparator) {
177    checkNotNull(valueComparator);
178    return Comparator.<Optional<T>, @Nullable T>comparing(
179        o -> orElseNull(o), Comparator.nullsFirst(valueComparator));
180  }
181
182  /**
183   * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as greater
184   * than all other values, and orders the rest using {@code valueComparator} on the contained
185   * value.
186   *
187   * @since 22.0 (but only since 33.4.0 in the Android flavor)
188   */
189  public static <T> Comparator<Optional<T>> emptiesLast(Comparator<? super T> valueComparator) {
190    checkNotNull(valueComparator);
191    return Comparator.<Optional<T>, @Nullable T>comparing(
192        o -> orElseNull(o), Comparator.nullsLast(valueComparator));
193  }
194
195  // For discussion of why this exists, see the Android flavor.
196  private static <T> @Nullable T orElseNull(Optional<T> optional) {
197    return optional.orElse(null);
198  }
199
200  /**
201   * Returns the minimum of the two values. If the values compare as 0, the first is returned.
202   *
203   * <p>The recommended solution for finding the {@code minimum} of some values depends on the type
204   * of your data and the number of elements you have. Read more in the Guava User Guide article on
205   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
206   * Comparators}</a>.
207   *
208   * @param a first value to compare, returned if less than or equal to b.
209   * @param b second value to compare.
210   * @throws ClassCastException if the parameters are not <i>mutually comparable</i>.
211   * @since 30.0
212   */
213  public static <T extends Comparable<? super T>> T min(T a, T b) {
214    return (a.compareTo(b) <= 0) ? a : b;
215  }
216
217  /**
218   * Returns the minimum of the two values, according to the given comparator. If the values compare
219   * as equal, the first is returned.
220   *
221   * <p>The recommended solution for finding the {@code minimum} of some values depends on the type
222   * of your data and the number of elements you have. Read more in the Guava User Guide article on
223   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
224   * Comparators}</a>.
225   *
226   * @param a first value to compare, returned if less than or equal to b
227   * @param b second value to compare.
228   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given
229   *     comparator.
230   * @since 30.0
231   */
232  @ParametricNullness
233  public static <T extends @Nullable Object> T min(
234      @ParametricNullness T a, @ParametricNullness T b, Comparator<? super T> comparator) {
235    return (comparator.compare(a, b) <= 0) ? a : b;
236  }
237
238  /**
239   * Returns the maximum of the two values. If the values compare as 0, the first is returned.
240   *
241   * <p>The recommended solution for finding the {@code maximum} of some values depends on the type
242   * of your data and the number of elements you have. Read more in the Guava User Guide article on
243   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
244   * Comparators}</a>.
245   *
246   * @param a first value to compare, returned if greater than or equal to b.
247   * @param b second value to compare.
248   * @throws ClassCastException if the parameters are not <i>mutually comparable</i>.
249   * @since 30.0
250   */
251  public static <T extends Comparable<? super T>> T max(T a, T b) {
252    return (a.compareTo(b) >= 0) ? a : b;
253  }
254
255  /**
256   * Returns the maximum of the two values, according to the given comparator. If the values compare
257   * as equal, the first is returned.
258   *
259   * <p>The recommended solution for finding the {@code maximum} of some values depends on the type
260   * of your data and the number of elements you have. Read more in the Guava User Guide article on
261   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
262   * Comparators}</a>.
263   *
264   * @param a first value to compare, returned if greater than or equal to b.
265   * @param b second value to compare.
266   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given
267   *     comparator.
268   * @since 30.0
269   */
270  @ParametricNullness
271  public static <T extends @Nullable Object> T max(
272      @ParametricNullness T a, @ParametricNullness T b, Comparator<? super T> comparator) {
273    return (comparator.compare(a, b) >= 0) ? a : b;
274  }
275}