In the
first part of my tutorial , I explained anything related to Strings in Guava. In this part of my tutorial, I will explain the Ordering class which combines the power of Comparators with Collections' functionality and which adds other interesting features (such as compound comparators). This class is really useful if you need to order your Iterable, find the maximum/minimum element in your Iterable, find the index of an arbitrary element. It implements Comparator interface for backward compatibility.
I will use a basic Employee class during my examples. Employee is a mutable class with three attributes: id, name and years of service..
01 | class Employee implements Comparable < Employee > { |
04 | private int yearsOfService; |
06 | public Employee(int id, String name, int yearsOfService){ |
09 | this.yearsOfService = yearsOfService; |
14 | public void setId(int id) { |
17 | public String getName() { |
20 | public void setName(String name) { |
23 | public int getYearsOfService() { |
24 | return yearsOfService; |
26 | public void setYearsOfService(int yearsOfService) { |
27 | this.yearsOfService = yearsOfService; |
30 | public int compareTo(Employee employee) { |
31 | return this.getName().compareTo(employee.getName()); |
35 | public String toString() { |
36 | String toString = "id="+id |
37 | +"-name="+name+"-years of service="+yearsOfService; |
As I implemented Comparable in the Employee class, I have to add compareTo(). In this method I only compare the name of the employees. I'll create three employees and add them to an ArrayList.
01 | Employee sezinKarli = new Employee(4, "Sezin Karli", 4); |
02 | Employee darthVader = new Employee(3, "Darth Vader", 5); |
03 | Employee hanSolo = new Employee(2, "Han Solo", 10); |
04 | List < Employee > employeeList = |
05 | Lists.newArrayList(sezinKarli, hanSolo, darthVader); |
06 | System.out.println("employee list: "+employeeList); |
There are many ways to create an Ordering. You can create one using the good old Comparator, using a predefined list of objects that explicitly imposes the ordering strategy, using the toString() method of the objects in hand and using the compareTo() method of the objects. You'll need to implement Comparable in your object if you want to take the compareTo() road. Lets create two comparators. One for comparing the years of service and another for employee id.
01 | Comparator < Employee > yearsComparator = |
02 | new Comparator < Employee >(){ |
04 | public int compare(Employee employee1, Employee employee2) { |
06 | employee1.getYearsOfService() - employee2.getYearsOfService()); |
10 | Comparator < Employee > idComparator = |
11 | new Comparator < Employee >(){ |
13 | public int compare(Employee employee1, Employee employee2) { |
14 | return (employee1.getId() - employee2.getId()); |
20 | Ordering < Employee > orderUsingYearsComparator = |
21 | Ordering.from(yearsComparator); |
23 | List < Employee > sortedCopy = |
25 | orderUsingYearsComparator.sortedCopy(employeeList); |
27 | "sorted copy based on years of service comparator: "+sortedCopy); |
The example above is not different from calling Collections.sort() with the comparator in hand but notice that we don't sort Collections but Iterables.
With explicit(), we create an Ordering where we impose an order explicitly.
I want to order en enum type (colors) and I want red, blue, green as order. I created the enum type as instance variable.
1 | static enum Colors{RED, GREEN, BLUE, YELLOW}; |
Not lets see the Ordering part.
01 | Ordering < Colors > explicitOrdering = |
02 | Ordering.explicit(Colors.RED, Colors.BLUE, Colors.GREEN); |
04 | List < Colors > colorList = |
05 | Lists.newArrayList(Colors.BLUE, Colors.RED, |
06 | Colors.BLUE, Colors.GREEN, Colors.RED); |
08 | List < Colors > sortedCopy8 = |
09 | explicitOrdering.sortedCopy(colorList); |
10 | System.out.println("ordered color list: "+sortedCopy8); |
Notice that explicit() works only with the given objects. You can't sort you iterable if you didnt specify the order in explicit(). If you try to to that you'll get IncomparableValueException.
Let me show you how to create an Ordering using toString() method of the object in hand.
01 | Ordering < Object > usingToString = Ordering.usingToString(); |
04 | List < Employee > sortedCopy3 = |
05 | usingToString.sortedCopy(employeeList); |
06 | System.out.println("sorted usingToString: "+sortedCopy3); |
Lets create an Ordering with natural ordering (using compareTo() of the objects)
01 | Ordering < Employee > natural = Ordering.natural(); |
02 | List < Employee > sortedCopy4 = natural.sortedCopy(employeeList); |
03 | System.out.println("sorted with natural: "+sortedCopy4); |
We can do binary search on the sorted list for an element. Notice that the Ordering that calls the binary search method and Ordering that sorted the Iterable in hand must be the same. binarySearch() was available in Collections class just like min() and max() we'll see in next examples.
1 | int binarySearch = natural.binarySearch(sortedCopy4, sezinKarli); |
2 | System.out.println("My index in the list: "+binarySearch); |
I will add elements of employee list, 2 null elements to a new list so we can explore new methods related to the handling of null elements.
1 | List < Employee > employeeListWithNulls = |
2 | new ArrayList < Employee > (employeeList); |
3 | employeeListWithNulls.add(null); |
4 | employeeListWithNulls.add(null); |
2 methods can be used for changing the handling of null elements. nullsFirst(), (nullsLast()) returns an Ordering which puts null elements to the beginning (end) of every non-null value.
03 | List < Employee > sortedCopy5 = |
04 | natural.nullsFirst().sortedCopy(employeeListWithNulls); |
05 | System.out.println("nulls first: "+sortedCopy5); |
I'd like to find the employee with the highest (lowest) time of service. I can do a sort based on years of service but that'll be slower then doing a single sweep for finding the element with max (min) year of service.
01 | Employee employeeWithMaxYearsOfService = |
02 | orderUsingYearsComparator.max(employeeList); |
03 | System.out.println(employeeWithMaxYearsOfService); |
07 | Employee employeeWithMinYearsOfService = |
08 | orderUsingYearsComparator.min(employeeList); |
09 | System.out.println(employeeWithMinYearsOfService); |
22 | orderUsingYearsComparator.max(sezinKarli, darthVader); |
23 | System.out.println(max); |
31 | orderUsingYearsComparator.max(sezinKarli, darthVader, hanSolo); |
33 | "Are the max results the same?: " |
34 | +max2.equals(employeeWithMaxYearsOfService)); |
In each ordering we defined an increasing order. We can reverse the Ordering calling reverse() and obtaining a new Ordering. Lets build a new ordering that'll use the idComparator.
01 | Ordering < Employee > reverseIdOrdering = |
02 | Ordering.from(idComparator).reverse(); |
06 | List < Employee > employeeWithReverseIdOrder = |
08 | reverseIdOrdering.sortedCopy(employeeList); |
10 | "employeeWithReverseIdOrder:"+ employeeWithReverseIdOrder); |
A useful ability of Orderings is the fact that you can combine multiple Comparators with it. Call compound() for this. If the result of comparator1 is 0 then the second one will be called and this will continue until a non-zero value (a larger/smaller relationship) is obtained from the comparator. If all comparators return 0 then the elements are treated as equal (we get 0 from the combined comparator).
01 | List < Employee > newEmployeeList = |
02 | Lists.newArrayList(new Employee(1, "Mr Pink", 8), |
03 | new Employee(2, "Mr Brown", 8), new Employee(3, "Mr Green", 3), |
04 | new Employee(4, "Mr Yellow", 5)); |
10 | Ordering < Employee > combinedComparatorOrdering = |
11 | orderUsingYearsComparator.compound(idComparator); |
12 | List < Employee > sortedCopy7 = |
13 | combinedComparatorOrdering.sortedCopy(newEmployeeList); |
15 | System.out.println("Combined comparators: "+sortedCopy7); |
As you can see the years of service increase (3 then 5 then two 8). When years of service comparator see that the result is a draw the second comparator is called. As you can see Mr Pink and Mr Brown have the same years of service so their id are inspected and the order between them is calculated. As the id of Mr Pink is less than Mr Brown's he's before Mr Brown.
This is all for compound comparators.
There are two slightly different methods for checking if the iterable in hand is ordered. isOrdered() checks if each element is less than/equal to the subsequent element. isStrictlyOrdered() checks if each element is strictly less than the subsequent element.
01 | List < Integer > integers = Lists.newArrayList(1, 2, 3, 4); |
07 | boolean ordered = Ordering.natural().isOrdered(integers); |
08 | System.out.println("isOrdered: "+ordered); |
09 | boolean strictlyOrdered = |
10 | Ordering.natural().isStrictlyOrdered(integers); |
11 | System.out.println("isStrictlyOrdered: "+strictlyOrdered); |
15 | List < Integer > newIntegers = |
16 | Lists.newArrayList(1, 2, 3, 3, 4); |
21 | ordered = Ordering.natural().isOrdered(newIntegers); |
22 | System.out.println("isOrdered: "+ordered); |
24 | Ordering.natural().isStrictlyOrdered(newIntegers); |
25 | System.out.println("isStrictlyOrdered: "+strictlyOrdered); |
Using functions as Ordering is quite interesting, but I will explain functional programming capabilities later so lets skip it for the moment.
Posts
unique visitors seen
VERY interesting! Two suggestions:
ReplyDelete1) Please add a syntax highlighter to the code, it is difficult to read as it is presented.
2) Can you talk a bit about performance? For example, String's built-in split is surprisingly slow if one is not using regular expression.
Again, great introduction!
I'll add a syntax highlighter as soon as possible. It's quite difficult to read when lots of code are involved.
ReplyDeleteI'll see what I can do about performance tests.