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