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.checkerframework.checker.nullness.qual.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 046@ElementTypesAreNonnullByDefault 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 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 -> 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 */ 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 */ 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 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 */ 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 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}