/*
* Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package java.util;
import java.io.Serializable;
import java.util.function.Function;
import java.util.function.ToIntFunction;
import java.util.function.ToLongFunction;
import java.util.function.ToDoubleFunction;
import java.util.Comparators;
/**
* A comparison function, which imposes a total ordering on some
* collection of objects. Comparators can be passed to a sort method (such
* as {@link Collections#sort(List,Comparator) Collections.sort} or {@link
* Arrays#sort(Object[],Comparator) Arrays.sort}) to allow precise control
* over the sort order. Comparators can also be used to control the order of
* certain data structures (such as {@link SortedSet sorted sets} or {@link
* SortedMap sorted maps}), or to provide an ordering for collections of
* objects that don't have a {@link Comparable natural ordering}.
*
* The ordering imposed by a comparator {@code c} on a set of elements
* {@code S} is said to be consistent with equals if and only if
* {@code c.compare(e1, e2)==0} has the same boolean value as
* {@code e1.equals(e2)} for every {@code e1} and {@code e2} in
* {@code S}.
*
* Caution should be exercised when using a comparator capable of imposing an
* ordering inconsistent with equals to order a sorted set (or sorted map).
* Suppose a sorted set (or sorted map) with an explicit comparator {@code c}
* is used with elements (or keys) drawn from a set {@code S}. If the
* ordering imposed by {@code c} on {@code S} is inconsistent with equals,
* the sorted set (or sorted map) will behave "strangely." In particular the
* sorted set (or sorted map) will violate the general contract for set (or
* map), which is defined in terms of {@code equals}.
*
* For example, suppose one adds two elements {@code a} and {@code b} such that
* {@code (a.equals(b) && c.compare(a, b) != 0)}
* to an empty {@code TreeSet} with comparator {@code c}.
* The second {@code add} operation will return
* true (and the size of the tree set will increase) because {@code a} and
* {@code b} are not equivalent from the tree set's perspective, even though
* this is contrary to the specification of the
* {@link Set#add Set.add} method.
*
* Note: It is generally a good idea for comparators to also implement
* {@code java.io.Serializable}, as they may be used as ordering methods in
* serializable data structures (like {@link TreeSet}, {@link TreeMap}). In
* order for the data structure to serialize successfully, the comparator (if
* provided) must implement {@code Serializable}.
*
* For the mathematically inclined, the relation that defines the
* imposed ordering that a given comparator {@code c} imposes on a
* given set of objects {@code S} is:
* {(x, y) such that c.compare(x, y) <= 0}.
* The quotient for this total order is:
* {(x, y) such that c.compare(x, y) == 0}.
*
*
* It follows immediately from the contract for {@code compare} that the
* quotient is an equivalence relation on {@code S}, and that the
* imposed ordering is a total order on {@code S}. When we say that
* the ordering imposed by {@code c} on {@code S} is consistent with
* equals, we mean that the quotient for the ordering is the equivalence
* relation defined by the objects' {@link Object#equals(Object)
* equals(Object)} method(s):
* {(x, y) such that x.equals(y)}.
*
* Unlike {@code Comparable}, a comparator may optionally permit
* comparison of null arguments, while maintaining the requirements for
* an equivalence relation.
*
*
This interface is a member of the
*
* Java Collections Framework.
*
* @param the type of objects that may be compared by this comparator
*
* @author Josh Bloch
* @author Neal Gafter
* @see Comparable
* @see java.io.Serializable
* @since 1.2
*/
@FunctionalInterface
public interface Comparator {
/**
* Compares its two arguments for order. Returns a negative integer,
* zero, or a positive integer as the first argument is less than, equal
* to, or greater than the second.
*
* The implementor must ensure that {@code sgn(compare(x, y)) ==
* -sgn(compare(y, x))} for all {@code x} and {@code y}. (This
* implies that {@code compare(x, y)} must throw an exception if and only
* if {@code compare(y, x)} throws an exception.)
*
* The implementor must also ensure that the relation is transitive:
* {@code ((compare(x, y)>0) && (compare(y, z)>0))} implies
* {@code compare(x, z)>0}.
*
* Finally, the implementor must ensure that {@code compare(x, y)==0}
* implies that {@code sgn(compare(x, z))==sgn(compare(y, z))} for all
* {@code z}.
*
* It is generally the case, but not strictly required that
* {@code (compare(x, y)==0) == (x.equals(y))}. Generally speaking,
* any comparator that violates this condition should clearly indicate
* this fact. The recommended language is "Note: this comparator
* imposes orderings that are inconsistent with equals."
*
* In the foregoing description, the notation
* {@code sgn(}expression{@code )} designates the mathematical
* signum function, which is defined to return one of {@code -1},
* {@code 0}, or {@code 1} according to whether the value of
* expression is negative, zero, or positive, respectively.
*
* @param o1 the first object to be compared.
* @param o2 the second object to be compared.
* @return a negative integer, zero, or a positive integer as the
* first argument is less than, equal to, or greater than the
* second.
* @throws NullPointerException if an argument is null and this
* comparator does not permit null arguments
* @throws ClassCastException if the arguments' types prevent them from
* being compared by this comparator.
*/
int compare(T o1, T o2);
/**
* Indicates whether some other object is "equal to" this
* comparator. This method must obey the general contract of
* {@link Object#equals(Object)}. Additionally, this method can return
* {@code true} only if the specified object is also a comparator
* and it imposes the same ordering as this comparator. Thus,
* {@code comp1.equals(comp2)} implies that {@code sgn(comp1.compare(o1,
* o2))==sgn(comp2.compare(o1, o2))} for every object reference
* {@code o1} and {@code o2}.
*
* Note that it is always safe not to override
* {@code Object.equals(Object)}. However, overriding this method may,
* in some cases, improve performance by allowing programs to determine
* that two distinct comparators impose the same order.
*
* @param obj the reference object with which to compare.
* @return {@code true} only if the specified object is also
* a comparator and it imposes the same ordering as this
* comparator.
* @see Object#equals(Object)
* @see Object#hashCode()
*/
boolean equals(Object obj);
/**
* Returns a comparator that imposes the reverse ordering of this
* comparator.
*
* @return a comparator that imposes the reverse ordering of this
* comparator.
* @since 1.8
*/
default Comparator reversed() {
return Collections.reverseOrder(this);
}
/**
* Returns a lexicographic-order comparator with another comparator.
* If this {@code Comparator} considers two elements equal, i.e.
* {@code compare(a, b) == 0}, {@code other} is used to determine the order.
*
* The returned comparator is serializable if the specified comparator
* is also serializable.
*
* @apiNote
* For example, to sort a collection of {@code String} based on the length
* and then case-insensitive natural ordering, the comparator can be
* composed using following code,
*
*
{@code
* Comparator cmp = Comparator.comparingInt(String::length)
* .thenComparing(String.CASE_INSENSITIVE_ORDER);
* }
*
* @param other the other comparator to be used when this comparator
* compares two objects that are equal.
* @return a lexicographic-order comparator composed of this and then the
* other comparator
* @throws NullPointerException if the argument is null.
* @since 1.8
*/
default Comparator thenComparing(Comparator other) {
Objects.requireNonNull(other);
return (Comparator & Serializable) (c1, c2) -> {
int res = compare(c1, c2);
return (res != 0) ? res : other.compare(c1, c2);
};
}
/**
* Returns a lexicographic-order comparator with a function that
* extracts a key to be compared with the given {@code Comparator}.
*
* @implSpec This default implementation behaves as if {@code
* thenComparing(comparing(keyExtractor, cmp))}.
*
* @param the type of the sort key
* @param keyExtractor the function used to extract the sort key
* @param keyComparator the {@code Comparator} used to compare the sort key
* @return a lexicographic-order comparator composed of this comparator
* and then comparing on the key extracted by the keyExtractor function
* @throws NullPointerException if either argument is null.
* @see #comparing(Function, Comparator)
* @see #thenComparing(Comparator)
* @since 1.8
*/
default Comparator thenComparing(
Function keyExtractor,
Comparator keyComparator)
{
return thenComparing(comparing(keyExtractor, keyComparator));
}
/**
* Returns a lexicographic-order comparator with a function that
* extracts a {@code Comparable} sort key.
*
* @implSpec This default implementation behaves as if {@code
* thenComparing(comparing(keyExtractor))}.
*
* @param the type of the {@link Comparable} sort key
* @param keyExtractor the function used to extract the {@link
* Comparable} sort key
* @return a lexicographic-order comparator composed of this and then the
* {@link Comparable} sort key.
* @throws NullPointerException if the argument is null.
* @see #comparing(Function)
* @see #thenComparing(Comparator)
* @since 1.8
*/
default > Comparator thenComparing(
Function keyExtractor)
{
return thenComparing(comparing(keyExtractor));
}
/**
* Returns a lexicographic-order comparator with a function that
* extracts an {@code int} sort key.
*
* @implSpec This default implementation behaves as if {@code
* thenComparing(comparingInt(keyExtractor))}.
*
* @param keyExtractor the function used to extract the integer sort key
* @return a lexicographic-order comparator composed of this and then the
* {@code int} sort key
* @throws NullPointerException if the argument is null.
* @see #comparingInt(ToIntFunction)
* @see #thenComparing(Comparator)
* @since 1.8
*/
default Comparator thenComparingInt(ToIntFunction keyExtractor) {
return thenComparing(comparingInt(keyExtractor));
}
/**
* Returns a lexicographic-order comparator with a function that
* extracts a {@code long} sort key.
*
* @implSpec This default implementation behaves as if {@code
* thenComparing(comparingLong(keyExtractor))}.
*
* @param keyExtractor the function used to extract the long sort key
* @return a lexicographic-order comparator composed of this and then the
* {@code long} sort key
* @throws NullPointerException if the argument is null.
* @see #comparingLong(ToLongFunction)
* @see #thenComparing(Comparator)
* @since 1.8
*/
default Comparator thenComparingLong(ToLongFunction keyExtractor) {
return thenComparing(comparingLong(keyExtractor));
}
/**
* Returns a lexicographic-order comparator with a function that
* extracts a {@code double} sort key.
*
* @implSpec This default implementation behaves as if {@code
* thenComparing(comparingDouble(keyExtractor))}.
*
* @param keyExtractor the function used to extract the double sort key
* @return a lexicographic-order comparator composed of this and then the
* {@code double} sort key
* @throws NullPointerException if the argument is null.
* @see #comparingDouble(ToDoubleFunction)
* @see #thenComparing(Comparator)
* @since 1.8
*/
default Comparator thenComparingDouble(ToDoubleFunction keyExtractor) {
return thenComparing(comparingDouble(keyExtractor));
}
/**
* Returns a comparator that imposes the reverse of the natural
* ordering.
*
* The returned comparator is serializable and throws {@link
* NullPointerException} when comparing {@code null}.
*
* @param the {@link Comparable} type of element to be compared
* @return a comparator that imposes the reverse of the natural
* ordering on {@code Comparable} objects.
* @see Comparable
* @since 1.8
*/
public static > Comparator reverseOrder() {
return Collections.reverseOrder();
}
/**
* Returns a comparator that compares {@link Comparable} objects in natural
* order.
*
* The returned comparator is serializable and throws {@link
* NullPointerException} when comparing {@code null}.
*
* @param the {@link Comparable} type of element to be compared
* @return a comparator that imposes the natural ordering on {@code
* Comparable} objects.
* @see Comparable
* @since 1.8
*/
@SuppressWarnings("unchecked")
public static > Comparator naturalOrder() {
return (Comparator) Comparators.NaturalOrderComparator.INSTANCE;
}
/**
* Returns a null-friendly comparator that considers {@code null} to be
* less than non-null. When both are {@code null}, they are considered
* equal. If both are non-null, the specified {@code Comparator} is used
* to determine the order. If the specified comparator is {@code null},
* then the returned comparator considers all non-null values to be equal.
*
* The returned comparator is serializable if the specified comparator
* is serializable.
*
* @param the type of the elements to be compared
* @param comparator a {@code Comparator} for comparing non-null values
* @return a comparator that considers {@code null} to be less than
* non-null, and compares non-null objects with the supplied
* {@code Comparator}.
* @since 1.8
*/
public static Comparator nullsFirst(Comparator comparator) {
return new Comparators.NullComparator<>(true, comparator);
}
/**
* Returns a null-friendly comparator that considers {@code null} to be
* greater than non-null. When both are {@code null}, they are considered
* equal. If both are non-null, the specified {@code Comparator} is used
* to determine the order. If the specified comparator is {@code null},
* then the returned comparator considers all non-null values to be equal.
*
* The returned comparator is serializable if the specified comparator
* is serializable.
*
* @param the type of the elements to be compared
* @param comparator a {@code Comparator} for comparing non-null values
* @return a comparator that considers {@code null} to be greater than
* non-null, and compares non-null objects with the supplied
* {@code Comparator}.
* @since 1.8
*/
public static Comparator nullsLast(Comparator comparator) {
return new Comparators.NullComparator<>(false, comparator);
}
/**
* Accepts a function that extracts a sort key from a type {@code T}, and
* returns a {@code Comparator} that compares by that sort key using
* the specified {@link Comparator}.
*
* The returned comparator is serializable if the specified function
* and comparator are both serializable.
*
* @apiNote
* For example, to obtain a {@code Comparator} that compares {@code
* Person} objects by their last name ignoring case differences,
*
*
{@code
* Comparator cmp = Comparator.comparing(
* Person::getLastName,
* String.CASE_INSENSITIVE_ORDER);
* }
*
* @param the type of element to be compared
* @param the type of the sort key
* @param keyExtractor the function used to extract the sort key
* @param keyComparator the {@code Comparator} used to compare the sort key
* @return a comparator that compares by an extracted key using the
* specified {@code Comparator}
* @throws NullPointerException if either argument is null
* @since 1.8
*/
public static Comparator comparing(
Function keyExtractor,
Comparator keyComparator)
{
Objects.requireNonNull(keyExtractor);
Objects.requireNonNull(keyComparator);
return (Comparator & Serializable)
(c1, c2) -> keyComparator.compare(keyExtractor.apply(c1),
keyExtractor.apply(c2));
}
/**
* Accepts a function that extracts a {@link java.lang.Comparable
* Comparable} sort key from a type {@code T}, and returns a {@code
* Comparator} that compares by that sort key.
*
* The returned comparator is serializable if the specified function
* is also serializable.
*
* @apiNote
* For example, to obtain a {@code Comparator} that compares {@code
* Person} objects by their last name,
*
*
{@code
* Comparator byLastName = Comparator.comparing(Person::getLastName);
* }
*
* @param the type of element to be compared
* @param the type of the {@code Comparable} sort key
* @param keyExtractor the function used to extract the {@link
* Comparable} sort key
* @return a comparator that compares by an extracted key
* @throws NullPointerException if the argument is null
* @since 1.8
*/
public static > Comparator comparing(
Function keyExtractor)
{
Objects.requireNonNull(keyExtractor);
return (Comparator & Serializable)
(c1, c2) -> keyExtractor.apply(c1).compareTo(keyExtractor.apply(c2));
}
/**
* Accepts a function that extracts an {@code int} sort key from a type
* {@code T}, and returns a {@code Comparator} that compares by that
* sort key.
*
* The returned comparator is serializable if the specified function
* is also serializable.
*
* @param the type of element to be compared
* @param keyExtractor the function used to extract the integer sort key
* @return a comparator that compares by an extracted key
* @see #comparing(Function)
* @throws NullPointerException if the argument is null
* @since 1.8
*/
public static Comparator comparingInt(ToIntFunction keyExtractor) {
Objects.requireNonNull(keyExtractor);
return (Comparator & Serializable)
(c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
}
/**
* Accepts a function that extracts a {@code long} sort key from a type
* {@code T}, and returns a {@code Comparator} that compares by that
* sort key.
*
* The returned comparator is serializable if the specified function is
* also serializable.
*
* @param the type of element to be compared
* @param keyExtractor the function used to extract the long sort key
* @return a comparator that compares by an extracted key
* @see #comparing(Function)
* @throws NullPointerException if the argument is null
* @since 1.8
*/
public static Comparator comparingLong(ToLongFunction keyExtractor) {
Objects.requireNonNull(keyExtractor);
return (Comparator & Serializable)
(c1, c2) -> Long.compare(keyExtractor.applyAsLong(c1), keyExtractor.applyAsLong(c2));
}
/**
* Accepts a function that extracts a {@code double} sort key from a type
* {@code T}, and returns a {@code Comparator} that compares by that
* sort key.
*
* The returned comparator is serializable if the specified function
* is also serializable.
*
* @param the type of element to be compared
* @param keyExtractor the function used to extract the double sort key
* @return a comparator that compares by an extracted key
* @see #comparing(Function)
* @throws NullPointerException if the argument is null
* @since 1.8
*/
public static Comparator comparingDouble(ToDoubleFunction keyExtractor) {
Objects.requireNonNull(keyExtractor);
return (Comparator & Serializable)
(c1, c2) -> Double.compare(keyExtractor.applyAsDouble(c1), keyExtractor.applyAsDouble(c2));
}
/**
* Returns a comparator that compares {@link CharSequence} objects,
* paying special attention to the decimal digit characters.
* For example, the following array was sorted using such comparator:
* {@code { "abc5", "abc10", "abc15", "xyz5", "xyz10"}}.
*
* The returned comparator does the following to compare two char
* sequences: first, the common prefix of the sequences is skipped;
* then, if the sequences are different at the point lying inside or
* at the boundary of a subsequence consisting solely of decimal digits,
* then the corresponding numerical values are compared; otherwise,
* the char sequences are compared literally.
*
*
In the case the numeric values of two compared char sequences
* are equal, but their string representations have different number
* of leading zeroes, the comparator treats the number with more
* leading zeros as greater.
* E.g. {@code "abc 1" < "abc 01" < "abc 001"}.
*
* @implSpec The returned comparator uses
* {@link java.lang.Character#compare(char,char)} to compare pairs of
* characters of its arguments. The comparator uses
* {@link java.lang.Character#isDigit(char)} to test if the character
* represents a decimal digit. The comparator uses
* {@link java.lang.Character#digit(char, int)} with the second
* argument set to {@code 10} to determine the decimal numeric value
* of the character.
*
* @param the type of elements to be compared
* @return a comparator that is to compare character sequences
*
* @since 10
*/
@SuppressWarnings("unchecked")
public static Comparator comparingNumerically() {
return (Comparator)Comparators.NumericComparator.INSTANCE_LEADING_ZEROS_LAST_NATURAL;
}
/**
* Returns a comparator that compares {@link CharSequence} objects,
* paying special attention to the decimal digit characters.
* For example, the following array was sorted using such comparator:
* {@code { "abc5", "abc10", "abc15", "xyz5", "xyz10"}}.
*
* The returned comparator does the following to compare two char
* sequences: first, the common prefix of the sequences is skipped;
* then, if the sequences are different at the point lying inside or
* at the boundary of a subsequence, consisting of decimal digits, the
* at the boundary of a subsequence consisting solely of decimal digits,
* then the corresponding numerical values are compared; otherwise,
* the char sequences are compared literally.
*
*
In the case the numeric values of two compared char sequences
* are equal, but their string representations have different number
* of leading zeroes, the comparator treats the number with more
* leading zeros as smaller.
* E.g. {@code "abc 001" < "abc 01" < "abc 1"}.
*
* @implSpec The returned comparator uses
* {@link java.lang.Character#compare(char,char)} to compare pairs of
* characters of its arguments. The comparator uses
* {@link java.lang.Character#isDigit(char)} to test if the character
* represents a decimal digit. The comparator uses
* {@link java.lang.Character#digit(char, int)} with the second
* argument set to {@code 10} to determine the decimal numeric value
* of the character.
*
* @param the type of elements to be compared
* @return a comparator that is to compare character sequences
*
* @since 10
*/
@SuppressWarnings("unchecked")
public static Comparator comparingNumericallyLeadingZerosFirst() {
return (Comparator)Comparators.NumericComparator.INSTANCE_LEADING_ZEROS_FIRST_NATURAL;
}
}