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 33.2.0 (available since 22.0 in guava-jre) 131 */ 132 @SuppressWarnings("Java7ApiChecker") 133 @IgnoreJRERequirement // Users will use this only if they're already using streams. 134 public static <T extends @Nullable Object> Collector<T, ?, List<T>> least( 135 int k, Comparator<? super T> comparator) { 136 checkNonnegative(k, "k"); 137 checkNotNull(comparator); 138 return Collector.of( 139 () -> TopKSelector.<T>least(k, comparator), 140 TopKSelector::offer, 141 TopKSelector::combine, 142 TopKSelector::topK, 143 Collector.Characteristics.UNORDERED); 144 } 145 146 /** 147 * Returns a {@code Collector} that returns the {@code k} greatest (relative to the specified 148 * {@code Comparator}) input elements, in descending order, as an unmodifiable {@code List}. Ties 149 * are broken arbitrarily. 150 * 151 * <p>For example: 152 * 153 * <pre>{@code 154 * Stream.of("foo", "quux", "banana", "elephant") 155 * .collect(greatest(2, comparingInt(String::length))) 156 * // returns {"elephant", "banana"} 157 * }</pre> 158 * 159 * <p>This {@code Collector} uses O(k) memory and takes expected time O(n) (worst-case O(n log 160 * k)), as opposed to e.g. {@code Stream.sorted(comparator.reversed()).limit(k)}, which currently 161 * takes O(n log n) time and O(n) space. 162 * 163 * @throws IllegalArgumentException if {@code k < 0} 164 * @since 33.2.0 (available since 22.0 in guava-jre) 165 */ 166 @SuppressWarnings("Java7ApiChecker") 167 @IgnoreJRERequirement // Users will use this only if they're already using streams. 168 public static <T extends @Nullable Object> Collector<T, ?, List<T>> greatest( 169 int k, Comparator<? super T> comparator) { 170 return least(k, comparator.reversed()); 171 } 172 173 /** 174 * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as less 175 * than all other values, and orders the rest using {@code valueComparator} on the contained 176 * value. 177 * 178 * @since 33.4.0 (but since 22.0 in the JRE flavor) 179 */ 180 @SuppressWarnings("Java7ApiChecker") 181 @IgnoreJRERequirement // Users will use this only if they're already using Optional. 182 public static <T> Comparator<Optional<T>> emptiesFirst(Comparator<? super T> valueComparator) { 183 checkNotNull(valueComparator); 184 return Comparator.<Optional<T>, @Nullable T>comparing( 185 o -> orElseNull(o), Comparator.nullsFirst(valueComparator)); 186 } 187 188 /** 189 * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as greater 190 * than all other values, and orders the rest using {@code valueComparator} on the contained 191 * value. 192 * 193 * @since 33.4.0 (but since 22.0 in the JRE flavor) 194 */ 195 @SuppressWarnings("Java7ApiChecker") 196 @IgnoreJRERequirement // Users will use this only if they're already using Optional. 197 public static <T> Comparator<Optional<T>> emptiesLast(Comparator<? super T> valueComparator) { 198 checkNotNull(valueComparator); 199 return Comparator.<Optional<T>, @Nullable T>comparing( 200 o -> orElseNull(o), Comparator.nullsLast(valueComparator)); 201 } 202 203 @SuppressWarnings("Java7ApiChecker") 204 @IgnoreJRERequirement // helper for emptiesFirst+emptiesLast 205 /* 206 * If we make these calls inline inside the lambda inside emptiesFirst()/emptiesLast(), we get an 207 * Animal Sniffer error, despite the @IgnoreJRERequirement annotation there. For details, see 208 * ImmutableSortedMultiset. 209 */ 210 private static <T> @Nullable T orElseNull(Optional<T> optional) { 211 return optional.orElse(null); 212 } 213 214 /** 215 * Returns the minimum of the two values. If the values compare as 0, 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>. 225 * @since 30.0 226 */ 227 public static <T extends Comparable<? super T>> T min(T a, T b) { 228 return (a.compareTo(b) <= 0) ? a : b; 229 } 230 231 /** 232 * Returns the minimum of the two values, according to the given comparator. If the values compare 233 * as equal, the first is returned. 234 * 235 * <p>The recommended solution for finding the {@code minimum} of some values depends on the type 236 * of your data and the number of elements you have. Read more in the Guava User Guide article on 237 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code 238 * Comparators}</a>. 239 * 240 * @param a first value to compare, returned if less than or equal to b 241 * @param b second value to compare. 242 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given 243 * comparator. 244 * @since 30.0 245 */ 246 @ParametricNullness 247 public static <T extends @Nullable Object> T min( 248 @ParametricNullness T a, @ParametricNullness T b, Comparator<? super T> comparator) { 249 return (comparator.compare(a, b) <= 0) ? a : b; 250 } 251 252 /** 253 * Returns the maximum of the two values. If the values compare as 0, 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>. 263 * @since 30.0 264 */ 265 public static <T extends Comparable<? super T>> T max(T a, T b) { 266 return (a.compareTo(b) >= 0) ? a : b; 267 } 268 269 /** 270 * Returns the maximum of the two values, according to the given comparator. If the values compare 271 * as equal, the first is returned. 272 * 273 * <p>The recommended solution for finding the {@code maximum} of some values depends on the type 274 * of your data and the number of elements you have. Read more in the Guava User Guide article on 275 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code 276 * Comparators}</a>. 277 * 278 * @param a first value to compare, returned if greater than or equal to b. 279 * @param b second value to compare. 280 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given 281 * comparator. 282 * @since 30.0 283 */ 284 @ParametricNullness 285 public static <T extends @Nullable Object> T max( 286 @ParametricNullness T a, @ParametricNullness T b, Comparator<? super T> comparator) { 287 return (comparator.compare(a, b) >= 0) ? a : b; 288 } 289}