1 /* 2 * Copyright (C) 2016 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import static com.google.common.base.Preconditions.checkNotNull; 20 import static com.google.common.collect.CollectPreconditions.checkNonnegative; 21 22 import com.google.common.annotations.GwtCompatible; 23 import java.util.Comparator; 24 import java.util.Iterator; 25 import java.util.List; 26 import java.util.Optional; 27 import java.util.stream.Collector; 28 import org.checkerframework.checker.nullness.qual.Nullable; 29 30 /** 31 * Provides static methods for working with {@link Comparator} instances. For many other helpful 32 * comparator utilities, see either {@code Comparator} itself (for Java 8 or later), or {@code 33 * com.google.common.collect.Ordering} (otherwise). 34 * 35 * <h3>Relationship to {@code Ordering}</h3> 36 * 37 * <p>In light of the significant enhancements to {@code Comparator} in Java 8, the overwhelming 38 * majority of usages of {@code Ordering} can be written using only built-in JDK APIs. This class is 39 * intended to "fill the gap" and provide those features of {@code Ordering} not already provided by 40 * the JDK. 41 * 42 * @since 21.0 43 * @author Louis Wasserman 44 */ 45 @GwtCompatible 46 @ElementTypesAreNonnullByDefault 47 public final class Comparators { Comparators()48 private Comparators() {} 49 50 /** 51 * Returns a new comparator which sorts iterables by comparing corresponding elements pairwise 52 * until a nonzero result is found; imposes "dictionary order." If the end of one iterable is 53 * reached, but not the other, the shorter iterable is considered to be less than the longer one. 54 * For example, a lexicographical natural ordering over integers considers {@code [] < [1] < [1, 55 * 1] < [1, 2] < [2]}. 56 * 57 * <p>Note that {@code Collections.reverseOrder(lexicographical(comparator))} is not equivalent to 58 * {@code lexicographical(Collections.reverseOrder(comparator))} (consider how each would order 59 * {@code [1]} and {@code [1, 1]}). 60 */ 61 // Note: 90% of the time we don't add type parameters or wildcards that serve only to "tweak" the 62 // desired return type. However, *nested* generics introduce a special class of problems that we 63 // think tip it over into being worthwhile. lexicographical( Comparator<T> comparator)64 public static <T extends @Nullable Object, S extends T> Comparator<Iterable<S>> lexicographical( 65 Comparator<T> comparator) { 66 return new LexicographicalOrdering<S>(checkNotNull(comparator)); 67 } 68 69 /** 70 * Returns {@code true} if each element in {@code iterable} after the first is greater than or 71 * equal to the element that preceded it, according to the specified comparator. Note that this is 72 * always true when the iterable has fewer than two elements. 73 */ isInOrder( Iterable<? extends T> iterable, Comparator<T> comparator)74 public static <T extends @Nullable Object> boolean isInOrder( 75 Iterable<? extends T> iterable, Comparator<T> comparator) { 76 checkNotNull(comparator); 77 Iterator<? extends T> it = iterable.iterator(); 78 if (it.hasNext()) { 79 T prev = it.next(); 80 while (it.hasNext()) { 81 T next = it.next(); 82 if (comparator.compare(prev, next) > 0) { 83 return false; 84 } 85 prev = next; 86 } 87 } 88 return true; 89 } 90 91 /** 92 * Returns {@code true} if each element in {@code iterable} after the first is <i>strictly</i> 93 * greater than the element that preceded it, according to the specified comparator. Note that 94 * this is always true when the iterable has fewer than two elements. 95 */ isInStrictOrder( Iterable<? extends T> iterable, Comparator<T> comparator)96 public static <T extends @Nullable Object> boolean isInStrictOrder( 97 Iterable<? extends T> iterable, Comparator<T> comparator) { 98 checkNotNull(comparator); 99 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 */ least( int k, Comparator<? super T> comparator)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 */ greatest( int k, Comparator<? super T> comparator)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 176 */ emptiesFirst(Comparator<? super T> valueComparator)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 -> o.orElse(null), 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 189 */ emptiesLast(Comparator<? super T> valueComparator)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 -> o.orElse(null), Comparator.nullsLast(valueComparator)); 194 } 195 196 /** 197 * Returns the minimum of the two values. If the values compare as 0, the first is returned. 198 * 199 * <p>The recommended solution for finding the {@code minimum} of some values depends on the type 200 * of your data and the number of elements you have. Read more in the Guava User Guide article on 201 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code 202 * Comparators}</a>. 203 * 204 * @param a first value to compare, returned if less than or equal to b. 205 * @param b second value to compare. 206 * @throws ClassCastException if the parameters are not <i>mutually comparable</i>. 207 * @since 30.0 208 */ min(T a, T b)209 public static <T extends Comparable<? super T>> T min(T a, T b) { 210 return (a.compareTo(b) <= 0) ? a : b; 211 } 212 213 /** 214 * Returns the minimum of the two values, according to the given comparator. If the values compare 215 * as equal, the first is returned. 216 * 217 * <p>The recommended solution for finding the {@code minimum} of some values depends on the type 218 * of your data and the number of elements you have. Read more in the Guava User Guide article on 219 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code 220 * Comparators}</a>. 221 * 222 * @param a first value to compare, returned if less than or equal to b 223 * @param b second value to compare. 224 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given 225 * comparator. 226 * @since 30.0 227 */ 228 @ParametricNullness min( @arametricNullness T a, @ParametricNullness T b, Comparator<T> comparator)229 public static <T extends @Nullable Object> T min( 230 @ParametricNullness T a, @ParametricNullness T b, Comparator<T> comparator) { 231 return (comparator.compare(a, b) <= 0) ? a : b; 232 } 233 234 /** 235 * Returns the maximum of the two values. If the values compare as 0, the first is returned. 236 * 237 * <p>The recommended solution for finding the {@code maximum} of some values depends on the type 238 * of your data and the number of elements you have. Read more in the Guava User Guide article on 239 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code 240 * Comparators}</a>. 241 * 242 * @param a first value to compare, returned if greater than or equal to b. 243 * @param b second value to compare. 244 * @throws ClassCastException if the parameters are not <i>mutually comparable</i>. 245 * @since 30.0 246 */ max(T a, T b)247 public static <T extends Comparable<? super T>> T max(T a, T b) { 248 return (a.compareTo(b) >= 0) ? a : b; 249 } 250 251 /** 252 * Returns the maximum of the two values, according to the given comparator. If the values compare 253 * as equal, the first is returned. 254 * 255 * <p>The recommended solution for finding the {@code maximum} of some values depends on the type 256 * of your data and the number of elements you have. Read more in the Guava User Guide article on 257 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code 258 * Comparators}</a>. 259 * 260 * @param a first value to compare, returned if greater than or equal to b. 261 * @param b second value to compare. 262 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given 263 * comparator. 264 * @since 30.0 265 */ 266 @ParametricNullness max( @arametricNullness T a, @ParametricNullness T b, Comparator<T> comparator)267 public static <T extends @Nullable Object> T max( 268 @ParametricNullness T a, @ParametricNullness T b, Comparator<T> comparator) { 269 return (comparator.compare(a, b) >= 0) ? a : b; 270 } 271 } 272