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.Beta;
023import com.google.common.annotations.GwtCompatible;
024import java.util.Comparator;
025import java.util.Iterator;
026import java.util.List;
027import java.util.Optional;
028import java.util.stream.Collector;
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 later), 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@Beta
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, S extends T> Comparator<Iterable<S>> lexicographical(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> boolean isInOrder(Iterable<? extends T> iterable, Comparator<T> comparator) {
074    checkNotNull(comparator);
075    Iterator<? extends T> it = iterable.iterator();
076    if (it.hasNext()) {
077      T prev = it.next();
078      while (it.hasNext()) {
079        T next = it.next();
080        if (comparator.compare(prev, next) > 0) {
081          return false;
082        }
083        prev = next;
084      }
085    }
086    return true;
087  }
088
089  /**
090   * Returns {@code true} if each element in {@code iterable} after the first is <i>strictly</i>
091   * greater than the element that preceded it, according to the specified comparator. Note that
092   * this is always true when the iterable has fewer than two elements.
093   */
094  public static <T> boolean isInStrictOrder(
095      Iterable<? extends T> iterable, Comparator<T> comparator) {
096    checkNotNull(comparator);
097    Iterator<? extends T> it = iterable.iterator();
098    if (it.hasNext()) {
099      T prev = it.next();
100      while (it.hasNext()) {
101        T next = it.next();
102        if (comparator.compare(prev, next) >= 0) {
103          return false;
104        }
105        prev = next;
106      }
107    }
108    return true;
109  }
110
111  /**
112   * Returns a {@code Collector} that returns the {@code k} smallest (relative to the specified
113   * {@code Comparator}) input elements, in ascending order, as an unmodifiable {@code List}. Ties
114   * are broken arbitrarily.
115   *
116   * <p>For example:
117   *
118   * <pre>{@code
119   * Stream.of("foo", "quux", "banana", "elephant")
120   *     .collect(least(2, comparingInt(String::length)))
121   * // returns {"foo", "quux"}
122   * }</pre>
123   *
124   * <p>This {@code Collector} uses O(k) memory and takes expected time O(n) (worst-case O(n log
125   * k)), as opposed to e.g. {@code Stream.sorted(comparator).limit(k)}, which currently takes O(n
126   * log n) time and O(n) space.
127   *
128   * @throws IllegalArgumentException if {@code k < 0}
129   * @since 22.0
130   */
131  public static <T> Collector<T, ?, List<T>> least(int k, Comparator<? super T> comparator) {
132    checkNonnegative(k, "k");
133    checkNotNull(comparator);
134    return Collector.of(
135        () -> TopKSelector.<T>least(k, comparator),
136        TopKSelector::offer,
137        TopKSelector::combine,
138        TopKSelector::topK,
139        Collector.Characteristics.UNORDERED);
140  }
141
142  /**
143   * Returns a {@code Collector} that returns the {@code k} greatest (relative to the specified
144   * {@code Comparator}) input elements, in descending order, as an unmodifiable {@code List}. Ties
145   * are broken arbitrarily.
146   *
147   * <p>For example:
148   *
149   * <pre>{@code
150   * Stream.of("foo", "quux", "banana", "elephant")
151   *     .collect(greatest(2, comparingInt(String::length)))
152   * // returns {"elephant", "banana"}
153   * }</pre>
154   *
155   * <p>This {@code Collector} uses O(k) memory and takes expected time O(n) (worst-case O(n log
156   * k)), as opposed to e.g. {@code Stream.sorted(comparator.reversed()).limit(k)}, which currently
157   * takes O(n log n) time and O(n) space.
158   *
159   * @throws IllegalArgumentException if {@code k < 0}
160   * @since 22.0
161   */
162  public static <T> Collector<T, ?, List<T>> greatest(int k, Comparator<? super T> comparator) {
163    return least(k, comparator.reversed());
164  }
165
166  /**
167   * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as less
168   * than all other values, and orders the rest using {@code valueComparator} on the contained
169   * value.
170   *
171   * @since 22.0
172   */
173  @Beta
174  public static <T> Comparator<Optional<T>> emptiesFirst(Comparator<T> valueComparator) {
175    checkNotNull(valueComparator);
176    return Comparator.comparing(o -> o.orElse(null), Comparator.nullsFirst(valueComparator));
177  }
178
179  /**
180   * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as greater
181   * than all other values, and orders the rest using {@code valueComparator} on the contained
182   * value.
183   *
184   * @since 22.0
185   */
186  @Beta
187  public static <T> Comparator<Optional<T>> emptiesLast(Comparator<T> valueComparator) {
188    checkNotNull(valueComparator);
189    return Comparator.comparing(o -> o.orElse(null), Comparator.nullsLast(valueComparator));
190  }
191}