1. Introduction

In Comparator series this is the 3rd article. We have already discussed Java Comparators(17 methods with examples) and Spring Comparators(5 methods with examples). In this article we are going to discuss the Comparators class in Google Guava library version 29.0-jre. If you are using maven you can use the below dependency in your pom file.

<dependency>
	<groupId>com.google.guava</groupId>
	<artifactId>guava</artifactId>
	<version>29.0-jre</version>
</dependency>

Let us dive in.

2. Content

Below are the methods that we will take a look at.

public static <T> boolean isInOrder(
				Iterable<? extends T> iterable, 
				Comparator<T> comparator)

public static <T> boolean isInStrictOrder(
				Iterable<? extends T> iterable, 
				Comparator<T> comparator)

public static <T, S extends T> Comparator<Iterable<S>>
				lexicographical(Comparator<T> comparator)

public static <T> Collector<T, ?, List<T>> least(
				int k, 
				Comparator<? super T> comparator)

public static <T> Collector<T, ?, List<T>> greatest(
				int k, 
				Comparator<? super T> comparator)

public static <T> Comparator<Optional<T>> emptiesFirst(
				Comparator<? super T> valueComparator)

public static <T> Comparator<Optional<T>> emptiesLast(
				Comparator<? super T> valueComparator)

3. public static <T> boolean isInOrder(
Iterable<? extends T> iterable,
Comparator<T> comparator)

isInOrder returns true if each element specified in Iterable is less than or equal to its next element. The ordering is specified in Comparator. 

Example : 

1, 2, 3, 3, 4 -> returns true

-1, -1, -1, -1 -> returns true

If the reverse Comparator is passed in then the reverse ordering is used. For example

4,3,3,2,1 -> returns true

-1, -1, -1, -1 -> returns true

Let us see a few examples of API usage.

Using Integer::compare as Comparator.

List<Integer> diffNumbers = Arrays.asList(1, 2, 3, 4);

boolean inOrderDiffNumbers 
	= Comparators.isInOrder(numbers, Integer::compare);

Assert.assertTrue(inOrderDiffNumbers);

List<Integer> sameNumbers = Arrays.asList(-1,-1,-1,-1);

boolean inOrderSameNumbers 
	= Comparators.isInOrder(numbers, Integer::compare);

Assert.assertTrue(inOrderSameNumbers);

Using Comparator.naturalOrder()

import static java.util.Comparator.naturalOrder;

List<Integer> numbers = Arrays.asList(1, 1, 2, 3, 4);

boolean inOrder 
	= Comparators.isInOrder(numbers, naturalOrder());

Assert.assertTrue(inOrder);

Using wrong order and asserting that result is false.

List<Integer> numbers = Arrays.asList(1, 2, 4, -1);

boolean inOrder = Comparators.isInOrder(numbers, Integer::compare);

Assert.assertFalse(inOrder);	

Using the reverse order

import static java.util.Comparator.reverseOrder;

List<Integer> numbers = Arrays.asList(4, 3, 3, 2, 1);

boolean inOrder 
	= Comparators.isInOrder(numbers, reverseOrder());

Assert.assertTrue(inOrder);

If all elements are the same then it doesn’t matter if you use Comparator.naturalOrder() or Comparator.reverseOrder(), the output will be true.

import static java.util.Comparator.naturalOrder;
import static java.util.Comparator.reverseOrder;

List<Integer> numbers = Arrays.asList(1, 1, 1, 1, 1);

boolean reverseOrder 
	= Comparators.isInOrder(numbers, reverseOrder());

boolean naturalOrder 
	= Comparators.isInOrder(numbers, naturalOrder());

Assert.assertTrue(reverseOrder == naturalOrder);

4. public static <T> boolean isInStrictOrder(
Iterable<? extends T> iterable,
Comparator<T> comparator)

isInStrictOrder returns true if each element specified in Iterable is strictly less than to its next element. The ordering is specified in Comparator. The difference between isInOrder and isInStrictOrder is that the elements in isInOrder equal elements in order are allowed whereas in isInStrictOrder it is not allowed. isInStrictOrder allows distinct values elements.

Example : 

1, 2, 3, 4 -> returns true

1, 2, 3, 3, 4 -> returns false

-1, -1, -1, -1-> returns true

If the reverse Comparator is passed in then the reverse ordering is used. For example

4, 3, 2, 1 -> returns true

4, 3, 3, 2, 1 -> returns false

-1, -1, -1, -1-> returns false

import static java.util.Comparator.naturalOrder;

List<Integer> numbers = Arrays.asList(1, 1, 2, 3, 4);

boolean isInStrictOrder 
	= Comparators.isInStrictOrder(numbers, naturalOrder());

Assert.assertFalse(isInStrictOrder);

import static java.util.Comparator.naturalOrder;

List<Integer> numbers = Arrays.asList(1, 12, 15, 19);

boolean isInStrictOrder 
	= Comparators.isInStrictOrder(numbers, naturalOrder());

Assert.assertTrue(isInStrictOrder);

5. public static <T, S extends T> Comparator<Iterable<S>>
lexicographical(Comparator<T> comparator)

As the method name lexicographical() would suggest, this method imposes the dictionary order. Unlike the previous methods this method returns Comparator. Look at the return type of the Comparator. It returns Comparator<Iterable<S>> which means that the input would be Collection of a Collection for example, List<List<Integer>>.

Let us take an example : 

Input : [[1, 2], [2], [1], [1, 1], []]

Expected Output : [[], [1], [1, 1], [1, 2], [2]]

While comparing two Lists, say for instance ListA and ListB, if Comparator reaches at the end of ListA and not ListB then a shorter list is considered to be less than a longer one.

Comparator<Iterable<Integer>> lexical 
	= Comparators.lexicographical(Integer::compare);

List<List<Integer>> numbers = Arrays.asList(
									Arrays.asList(1, 2),
									Arrays.asList(2),
									Arrays.asList(1), 
									Arrays.asList(1, 1),
									new ArrayList<>());

numbers.sort(lexical);

Input : [[1, 2], [2], [1], [1, 1], []]
Output : [[], [1], [1, 1], [1, 2], [2]]

We can also use the default method of Comparator interface too. Below example shows how to use the reversed() method from Comparator interface with guava Comparators.

Comparator<Iterable<Integer>> lexical = 
	Comparators.lexicographical(Integer::compare).reversed();

List<List<Integer>> numbers = Arrays.asList(
    Arrays.asList(1, 2),
    Arrays.asList(2),
    Arrays.asList(1), 
    Arrays.asList(1, 1),
    new ArrayList<>());

numbers.sort(lexical);
    	
Input : [[1, 2], [2], [1], [1, 1], []]
Output : [[2], [1, 2], [1, 1], [1], []]

6. public static <T> Collector<T, ?, List<T>> least(
int k,
Comparator<? super T> comparator)

The least() method returns a Collector that will return k smallest elements in order in an unmodifiable list. 

For example : 

Input : [45, 67,3, 78, 90]

Output : [78, 90]

You can implement same functionality using Stream’s sorted and limit method.

list.stream().sorted(comparator).limit(2);

The problem with the above approach is that the operation can be costly. Consider n as the total number of elements in List and k as total elements we want from List based on the provided Comparator.  The sorted method takes O(n log n) time whereas the data structure implemented in least() method takes O(n log k) time. How much of a difference is that? That depends on n and k. If k is significantly smaller than n then we would unnecessarily spend more in sorting more objects.

Assume n = 1 billion and assume k = 100. Log is log base 2.

O(n log n) would yield around 1B log 1B iterations which is
1B * 30 = 30B iterations

O(n log k) would yield around 1B log 1000 iterations which is
1B * 10 = 10B iterations

Remember the time complexity comparison is highly dependent on value k.

Let us see how to use least() API.

Collector<Integer, ?, List<Integer>> leastCollector 
	= Comparators.least(2, Integer::compare);

List<Integer> numbers = Arrays.asList(5, 67, 9, 23, 6, 7);

List<Integer> collect = numbers.stream().collect(leastCollector);

Input : [5, 67, 9, 23, 6, 7]

Output : [5, 6]

Least using string length Comparator

List<String> words = 
	Arrays.asList("The", "quick", "brown", "fox", 
				"jumps", "over", "lazy", "dog");

Collector<String, ?, List<String>> leastCollector 
	= Comparators.least(3, Comparator.comparingInt(String::length));

List<String> collect = words.stream().collect(leastCollector);

Input : [The, quick, brown, fox, jumps, over, lazy, dog]

Output : [fox, The, dog]

7. public static <T> Collector<T, ?, List<T>> greatest(
int k,
Comparator<? super T> comparator)

greatest() method does the opposite of least() method. It returns k largest elements in descending order in an unmodifiable list.

Collector<Integer, ?, List<Integer>> greatestCollector 
	= Comparators.greatest(2, Integer::compare);

List<Integer> numbers = Arrays.asList(5, 67, 9, 23, 6, 7);

List<Integer> collect = numbers.stream().collect(greatestCollector);
	
Input : [5, 67, 9, 23, 6, 7]

Output : [67, 23]

greatest() method using String.

Collector<String, ?, List<String>> greatestCollector 
	= Comparators.greatest(3, 
						  Comparator.comparingInt(String::length));

List<String> words = 
	Arrays.asList("The", "quick", "brown", "fox", 
				"jumps", "over", "lazy", "dog");

List<String> collect = words.stream().collect(greatestCollector);
	
Input : [The, quick, brown, fox, jumps, over, lazy, dog]

Output: [jumps, quick, brown]

8. public static <T> Comparator<Optional<T>>
emptiesFirst(Comparator<? super T> valueComparator)

emptiesFirst() method returns a Comparator<Optional<T>> which means if you want to sort a Collection filled with Optional values this is the comparator to use. 

I have written several articles on java.util.Optional here. I do not subscribe to the idea where we have Optional<Collection<T>> or Collection<Optional<T>>. Both of them are ugly representations of data. Read here on why Optional<Collection<T>> is bad and how to refactor it. Never wrap a Collection in Optional.

That being said, let us now discuss what emptiesFirst() method does. This method treats the empty Optional as less than other values. The Comparator of type T. The type T is wrapped in Optional. 

Let us see how to use this API. We will create a List<Optional<Integer>> and work through it.

List<Optional<Integer>> numbers = Arrays.asList(
											Optional.of(5), 
											Optional.of(67), 
											Optional.of(9),
											Optional.empty(), 
											Optional.of(23), 
											Optional.of(6), 
											Optional.empty(), 
											Optional.of(7), 
											Optional.empty());

Comparator<Optional<Integer>> emptiesFirst 
	= Comparators.emptiesFirst(Integer::compare);

numbers.sort(emptiesFirst);

Input : [
Optional[5], 
Optional[67], 
Optional[9], 
Optional.empty, 
Optional[23], 
Optional[6], 
Optional.empty, 
Optional[7], 
Optional.empty]

Output : [
Optional.empty, 
Optional.empty, 
Optional.empty, 
Optional[5], 
Optional[6], 
Optional[7], 
Optional[9], 
Optional[23], 
Optional[67]]

Let us reverse sort the List<Optional<Integer>> using the reversed() method of Comparator interface introduced in Java 8.

List<Optional<Integer>> numbers = Arrays.asList(
											Optional.of(5), 
											Optional.of(67), 
											Optional.of(9),
											Optional.empty(), 
											Optional.of(23), 
											Optional.of(6), 
											Optional.empty(), 
											Optional.of(7), 
											Optional.empty());

Comparator<Optional<Integer>> emptiesFirst 
	= Comparators.emptiesFirst(Integer::compare).reversed();

numbers.sort(emptiesFirst);
	
Input : [
Optional[5], 
Optional[67], 
Optional[9], 
Optional.empty, 
Optional[23], 
Optional[6], 
Optional.empty, 
Optional[7], 
Optional.empty]

Output : [
Optional[67], 
Optional[23], 
Optional[9], 
Optional[7], 
Optional[6], 
Optional[5], 
Optional.empty, 
Optional.empty, 
Optional.empty]

9. public static <T> Comparator<Optional<T>>
emptiesLast(Comparator<? super T> valueComparator)

emptiesLast() method does the opposite of what emptiesFirst() method does. The empty Optional values are treated as greater than non empty Optional values.

Let us see how to use this API. We will create a List<Optional<Integer>> and work through it.

List<Optional<String>> numbers = Arrays.asList(
											Optional.of("Jon"),
											Optional.of("Arya"), 
											Optional.of("Sansa"),
											Optional.empty(), 
											Optional.of("Robb"), 
											Optional.of("Bran"), 
											Optional.empty(), 
											Optional.of("Rickon"),
											Optional.empty());

Comparator<Optional<String>> emptiesLast 
	= Comparators.emptiesLast(String::compareTo);

numbers.sort(emptiesLast);

Input : [
Optional[Jon], 
Optional[Arya], 
Optional[Sansa], 
Optional.empty, 
Optional[Robb], 
Optional[Bran], 
Optional.empty, 
Optional[Rickon], 
Optional.empty]

Output : [
Optional[Arya], 
Optional[Bran], 
Optional[Jon], 
Optional[Rickon], 
Optional[Robb], 
Optional[Sansa], 
Optional.empty, 
Optional.empty, 
Optional.empty]

10. Conclusion

Google Guava’s Comparators class has a rich set of methods that can be used, especially the methods that return Collector. Be careful when implementing stream and using comparator in it. If the data elements are too large then it would take longer to sort those elements. That’s all in Guava’s Comparators class.

Code can be found on Github. Click here.