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.stream.Collector; 027import org.checkerframework.checker.nullness.qual.Nullable; 028 029/** 030 * Provides static methods for working with {@link Comparator} instances. For many other helpful 031 * comparator utilities, see either {@code Comparator} itself (for Java 8+), or {@code 032 * com.google.common.collect.Ordering} (otherwise). 033 * 034 * <h3>Relationship to {@code Ordering}</h3> 035 * 036 * <p>In light of the significant enhancements to {@code Comparator} in Java 8, the overwhelming 037 * majority of usages of {@code Ordering} can be written using only built-in JDK APIs. This class is 038 * intended to "fill the gap" and provide those features of {@code Ordering} not already provided by 039 * the JDK. 040 * 041 * @since 21.0 042 * @author Louis Wasserman 043 */ 044@GwtCompatible 045@ElementTypesAreNonnullByDefault 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({"AndroidJdkLibsChecker", "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({"AndroidJdkLibsChecker", "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 the minimum of the two values. If the values compare as 0, the first is returned. 175 * 176 * <p>The recommended solution for finding the {@code minimum} of some values depends on the type 177 * of your data and the number of elements you have. Read more in the Guava User Guide article on 178 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code 179 * Comparators}</a>. 180 * 181 * @param a first value to compare, returned if less than or equal to b. 182 * @param b second value to compare. 183 * @throws ClassCastException if the parameters are not <i>mutually comparable</i>. 184 * @since 30.0 185 */ 186 public static <T extends Comparable<? super T>> T min(T a, T b) { 187 return (a.compareTo(b) <= 0) ? a : b; 188 } 189 190 /** 191 * Returns the minimum of the two values, according to the given comparator. If the values compare 192 * as equal, the first is returned. 193 * 194 * <p>The recommended solution for finding the {@code minimum} of some values depends on the type 195 * of your data and the number of elements you have. Read more in the Guava User Guide article on 196 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code 197 * Comparators}</a>. 198 * 199 * @param a first value to compare, returned if less than or equal to b 200 * @param b second value to compare. 201 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given 202 * comparator. 203 * @since 30.0 204 */ 205 @ParametricNullness 206 public static <T extends @Nullable Object> T min( 207 @ParametricNullness T a, @ParametricNullness T b, Comparator<? super T> comparator) { 208 return (comparator.compare(a, b) <= 0) ? a : b; 209 } 210 211 /** 212 * Returns the maximum of the two values. If the values compare as 0, the first is returned. 213 * 214 * <p>The recommended solution for finding the {@code maximum} of some values depends on the type 215 * of your data and the number of elements you have. Read more in the Guava User Guide article on 216 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code 217 * Comparators}</a>. 218 * 219 * @param a first value to compare, returned if greater than or equal to b. 220 * @param b second value to compare. 221 * @throws ClassCastException if the parameters are not <i>mutually comparable</i>. 222 * @since 30.0 223 */ 224 public static <T extends Comparable<? super T>> T max(T a, T b) { 225 return (a.compareTo(b) >= 0) ? a : b; 226 } 227 228 /** 229 * Returns the maximum of the two values, according to the given comparator. If the values compare 230 * as equal, the first is returned. 231 * 232 * <p>The recommended solution for finding the {@code maximum} of some values depends on the type 233 * of your data and the number of elements you have. Read more in the Guava User Guide article on 234 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code 235 * Comparators}</a>. 236 * 237 * @param a first value to compare, returned if greater than or equal to b. 238 * @param b second value to compare. 239 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given 240 * comparator. 241 * @since 30.0 242 */ 243 @ParametricNullness 244 public static <T extends @Nullable Object> T max( 245 @ParametricNullness T a, @ParametricNullness T b, Comparator<? super T> comparator) { 246 return (comparator.compare(a, b) >= 0) ? a : b; 247 } 248}