Google Guava Comparators

Introduction

Google Guava library has a class called Comparators, which provides static methods for working with Java Comparator instances. The method offered are marked as @Beta, meaning that they can be changed in a backward incompatible manner or even totally removed in the future. But I found these methods interesting and useful and hence writing about them in this post. Let us dive deep into the Google Guava Comparators class.

Using or Importing Google Guava

For Maven projects, you can import Google Guava from Maven as:

<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.1.1-jre</version>
</dependency>

For Gradle, add Google Guava as,

implementation 'com.google.guava:guava:30.1.1-jre'

Note: You can replace 30.1.1-jre with the latest version (or your preferred version) of Google Guava. However, if you are using an older version than 30.1.1-jre, some of the methods discussed here may not be available.

Comparators - lexicographical

The Comparators#lexicographical method in Google Guava Comparators class takes a comparator as input and returns a new comparator. The returned comparator sorts Iterables by comparing the corresponding elements (pair-wise) until it gets a non-zero result.

Example: Let us consider a list of list (2D array) as shown below:

[
    [2, 1],
    [3, 8],
    [3, 7]
    [1, 100]
]

If we were to sort these using the comparator returned by Comparators#lexicographical, then we will get,

[
    [1, 100],
    [2, 1],
    [3, 7],
    [3, 8]
]

It doesn’t sort the individual rows. It sorts the 2D array (Iterables) by comparing elements pair-wise (1 < 2 < 3 and 7 < 8).

Note: If it reaches the end of one Iterable and not the other, the shorter Iterable is less than the longer one.

Let us look at an example.

List<List<Integer>> listOfList = new ArrayList<>(List.of(
        List.of(5),
        List.of(3, 4),
        List.of(4, 6, 1),
        List.of(1, 2, 3),
        List.of(2, 10, 20),
        List.of(3)
));

I’ve created a list of list (list of Iterables) using the List.of() method added in Java 9 (Refer to Convenience Factory Method for Collections post for more details). I’ve copied it into an ArrayList as we have to sort it (hence the list must be mutable).

Comparator<Iterable<Integer>> comparator = Comparators.lexicographical(Comparator.<Integer>naturalOrder());

In the above code, we call the Comparators.lexicographical method passing a naturalOrder comparator for Integer type. It returns a Comparator for Iterable<Integer>. Let us now sort the list using this comparator.

listOfList.sort(comparator);
System.out.println(listOfList);

Note that the sort method accepts a Comparator<? super E> - meaning that we can pass a comparator of a type which is a super class of the element type of the list. That is why we are able to pass a Comparator<Iterable<Integer>> as Iterable<Integer> is a List<Integer>.

The result is:

[[1, 2, 3], [2, 10, 20], [3], [3, 4], [4, 6, 1], [5]]

Note that the shorter Iterable ([3]) comes before the longer one ([3, 4]). And it doesn’t sort the individual rows ([4, 6, 1]).

Comparators - isInOrder and isInStrictOrder

isInOrder

The isInOrder method takes an Iterable and a Comparator as arguments. It returns true if each element in the Iterable after the first is greater than or equal to the previous element according to the passed Comparator. Note that this is always true when the iterable has fewer than two elements.

List<Integer> list = List.of(1, 6, 10, 17, 17, 80, 100);
Comparator<Integer> cmp = Comparator.naturalOrder();
System.out.println(Comparators.isInOrder(list, cmp)); //true

In the above code we have an Iterable of integers (list of integers) and it is sorted and hence the call to isInOrder returns true. Note that there are two instances of 17 - it returns a true because it checks if each element is greater than or equal to the previous element.

On the other hand, we have a list which is not sorted and hence the below call returns false.

List<Integer> list = List.of(1, 6, 10, 7, 17, 80, 100);
System.out.println(Comparators.isInOrder(list, cmp)); //false

When we have fewer than two elements, it returns true.

List<Integer> list = List.of(1);
System.out.println(Comparators.isInOrder(list, cmp)); //true

isInStrictOrder

The isInStrictOrder is similar to isInOrder but it returns true only if each element is strictly greater than the previous element.

List<Integer> list = List.of(1, 6, 10, 17, 18, 80, 100);
System.out.println(Comparators.isInStrictOrder(list, cmp)); //true

The above code has Iterable of integers, which is sorted and there are no duplicate elements and hence it returns true.

But if we use the same input for which isInOrder() returned true here, we would get a false because there were two values of 17. (Remember that isInStrictOrder checks if each element is strictly greater than the previous element).

List<Integer> list = List.of(1, 6, 10, 17, 17, 80, 100);
System.out.println(Comparators.isInStrictOrder(list, cmp)); //false

//not sorted list - returns false
List<Integer> list = List.of(1, 6, 10, 7, 17, 80, 100);
System.out.println(Comparators.isInStrictOrder(list, cmp)); //false

When we have fewer than two elements, it returns true.

List<Integer> list = List.of(1);
System.out.println(Comparators.isInStrictOrder(list, cmp)); //true

Comparators - least and greatest

least

The Comparators#least method takes an integer (k) and a Comparator and returns a Java Collector and the collector will return the k smallest elements in the input. The smallest among the input elements (or the ordering of the elements) is relative to the passed Comparator. Thus, you can imagine sorting the input element by the passed Comparator and picking the least k elements from it.

List<Integer> list = List.of(6, 10, 1, 4, 11, 2);
Comparator<Integer> naturalOrderCmp = Comparator.naturalOrder();
List<Integer> least2 = list.stream()
        .collect(Comparators.least(2, naturalOrderCmp));
System.out.println(least2); //[1, 2]

In the above code, we have a list of integers and we will be using a simple naturalOrder comparator. We create a stream out of the list and pass the comparator returned by the least() method to the collect method of the Stream. This will give the first k elements when the input list is sorted as per the naturalOrder comparator.

Similarly, let us pick the least 4 elements from the list.

List<Integer> least4 = list.stream()
        .collect(Comparators.least(4, naturalOrderCmp));
System.out.println(least4); //[1, 2, 4, 6]

Let us use Comparator.reverseOrder() comparator so that the ordering we get is descending. Let us pick the least 4 elements in that.

Comparator<Integer> reverseOrderCmp = Comparator.reverseOrder();

List<Integer> least4 = list.stream()
        .collect(Comparators.least(4, reverseOrderCmp));
System.out.println(least4); //[11, 10, 6, 4]

The reverse sorted output will be [11, 10, 6, 4, 2, 1] and from this you can see how the least 4 elements were chosen.

Performance

As per the documentation, this Collector uses O(k) memory and will take a O(n) time (worst-case O(n log k)), as opposed to e.g. Stream.sorted(comparator).limit(k), which currently takes O(n log n) time and O(n) space.

greatest

This is similar to the least method, but it will return a collector which will return the k greatest elements from the input (ordered as per the passed comparator).

Note: Implementation wise, it calls reversed() on the passed comparator and calls the least() method seen earlier.

Let us use the same list as before and the natural ordering comparator and call the greatest() method to get the top 2 greatest elements.

List<Integer> greatest2 = list.stream()
        .collect(Comparators.greatest(2, naturalOrderCmp));
System.out.println(greatest2); //[11, 10]

Since it calls reversed() on the passed comparator, it effectively becomes a reverse ordering comparator. Hence, the sorted order would be [11, 10, 6, 4, 2, 1]. And hence the top 2 greatest elements are 11 and 10.

Similarly, for getting the top 4 elements, we have,

List<Integer> greatest4 = list.stream()
        .collect(Comparators.greatest(4, naturalOrderCmp));
System.out.println(greatest4); //[11, 10, 6, 4]

Finally, using the reverse ordering comparator, getting the top 4 greatest elements is shown below.

List<Integer> greatest4 = list.stream()
        .collect(Comparators.greatest(4, reverseOrderCmp));
System.out.println(greatest4); //[1, 2, 4, 6]

As an observation,

The output of least() with a natural ordering comparator is same as the output of greatest() with a reverse ordering comparator.
Similarly, the output of least() with a reverse ordering comparator is same as the output of greatest() with a natural ordering comparator.

Performance

The runtime performance numbers are similar to the least() method.

Using least and greatest on strings and compare by string length

As another example, let us use the least() and the greatest() methods on strings.

least

Let us create a stream of strings and use a comparator that orders by the string length, i.e., from shortest to the longest string.

//sorted order is [pear, orange, banana]
System.out.println(
        Stream.of("orange", "pear", "banana")
                .collect(Comparators.least(2, Comparator.comparingInt(String::length))));
                
//[pear, orange]

In the above code, we get the top 2 elements as per the comparator passed. The result is [pear, orange]. From the sorted output I’ve shown above, you can see that it doesn’t re-order ‘orange’ and ‘banana’. Both have the same length and hence it maintains the relative order as in the input stream (in-place sort).

Now, let us chain a comparator to order by the string’s natural ordering when there is a tie on the length.

//sorted order is [pear, banana, orange]
System.out.println(
        Stream.of("orange", "pear", "banana")
                .collect(Comparators.least(2, Comparator.comparingInt(String::length)
                        .thenComparing(Comparator.naturalOrder()))));
                        
//[pear, banana]

As shown above, since there is a tie on the first comparator (ordering by length) between ‘orange’ and ‘banana’, the second comparator will order by the string’s natural order. So, ‘banana’ comes before ‘orange’ and hence the output is [pear, banana].

greatest

Let us apply the same two scenarios seen before to greatest().

//reverse sorted order is [orange, banana, pear]
System.out.println(
        Stream.of("orange", "pear", "banana")
                .collect(Comparators.greatest(2, Comparator.comparingInt(String::length))));
//[orange, banana]

If you can recall, the greatest() method reverses the comparator (by calling reversed() on it) and uses the least() method. So, this will effectively order the strings from longest to the shortest by length. Hence, the sorted output will be [orange, banana, pear] and hence the greatest 2 elements are [orange, banana]. (Note: It doesn’t re-order ‘orange’ and ‘banana’ and it keeps the original relative ordering as seen before).

Now, let us add the tie breaking comparator to order by the natural order.

//reverse sorted order is: [orange, banana, pear]
//so naturalOrder becomes like reverseOrder and orange is at top already
System.out.println(
        Stream.of("orange", "pear", "banana")
                .collect(Comparators.greatest(2, Comparator.comparingInt(String::length)
                        .thenComparing(Comparator.naturalOrder()))));
//[orange, banana]

Now, the ordering is still [orange, banana, pear]. If you are wondering how, this is the interesting part. Since it calls reversed on the passed comparator chain, it will apply to each comparator in the chain. Thus, both get reversed or inverted. So, the comparator logic/chain would look like:

Sort by the string length (longest first).
And then for ties, sort by the string’s natural ordering in reverse.

Hence, ‘orange’ still remains before ‘banana’ and hence the output doesn’t change from the previous case.

Comparators - emptiesFirst and emptiesLast

The emptiesFirst method takes a comparator and returns a comparator of Optional values which will treat empty Optionals as less than the other values. Similarly, emptiesLast returns a comparator which considers empty Optionals as greater than the other values. It will use the passed comparator to order the non-empty Optionals.

Implementation wise, it just converts empty optionals to null and uses nullsFirst and nullsLast in the Java’s Comparator.

Let us use the below shown list of optionals.

List<Optional<Integer>> optionals = List.of(
        Optional.of(1),
        Optional.empty(),
        Optional.of(20),
        Optional.of(2),
        Optional.empty(),
        Optional.of(6)
);
Comparator<Integer> naturalOrderCmp = Comparator.naturalOrder();
Comparator<Integer> reverseOrderCmp = Comparator.reverseOrder();

System.out.println(optionals.stream()
        .sorted(Comparators.emptiesFirst(naturalOrderCmp))
        .collect(Collectors.toList()));
        
System.out.println(optionals.stream()
        .sorted(Comparators.emptiesFirst(reverseOrderCmp))
        .collect(Collectors.toList()));

We are using the emptiesFirst with natural and reverse ordering comparators. The output is:

[Optional.empty, Optional.empty, Optional[1], Optional[2], Optional[6], Optional[20]]
[Optional.empty, Optional.empty, Optional[20], Optional[6], Optional[2], Optional[1]]

As you can see, the empty optionals are placed first and the rest of the values are sorted either in ascending (natural ordering) or descending (reverse ordering).

Similarly, when using the emptiesLast, it will place the empty optionals at the end. The other values will be sorted as before.

System.out.println(optionals.stream()
        .sorted(Comparators.emptiesLast(naturalOrderCmp))
        .collect(Collectors.toList()));

System.out.println(optionals.stream()
        .sorted(Comparators.emptiesLast(reverseOrderCmp))
        .collect(Collectors.toList()));

Output:

[Optional[1], Optional[2], Optional[6], Optional[20], Optional.empty, Optional.empty]
[Optional[20], Optional[6], Optional[2], Optional[1], Optional.empty, Optional.empty]

Conclusion

In this post, we learnt about the Google Guava Comparators class in detail. For more details on the comparators, check out the below posts:

Introduction#

Using or Importing Google Guava#

Comparators - lexicographical#

Comparators - isInOrder and isInStrictOrder#

isInOrder#

isInStrictOrder#

Comparators - least and greatest#

least#

Performance#

greatest#

Performance#

Using least and greatest on strings and compare by string length#

least#

greatest#

Comparators - emptiesFirst and emptiesLast#

Conclusion#

Introduction

Using or Importing Google Guava

Comparators - lexicographical

Comparators - isInOrder and isInStrictOrder

isInOrder

isInStrictOrder

Comparators - least and greatest

least

Performance

greatest

Performance

Using least and greatest on strings and compare by string length

least

greatest

Comparators - emptiesFirst and emptiesLast

Conclusion