Sorting and lambda functions¶
Java class library offers e.g the class functions Arrays.sort
for sorting plain arrays and
Collections.sort
for sorting lists (e.g. also ArrayList
). These functions sort Java’s
basic number and string types into “natural” ascending order. If the sorted objects do not readily
support values comparison, or we wish to use some other sorting order (e.g. descending), we may
give these sorting functions a custom comparison function as a second parameter. Java lists
(including ArrayList
) also have a member function sort
that always requires a comparison
function as a parameter (even when sorting Java’s basic number or string types).
A comparison function for values of some type T
has the form int compare(T a, T b)
: the
function takes two compared items of type T
as parameters and returns an int
that describes
the result of comparing them. A negative return value means that the first item is smaller, zero
that they are equal, and a positive that the second item is smaller.
It is often most convenient to define a custom comparison function as a so-called lambda function
directly inside the sorting function call. A lambda function is a simplified anonymous function
definition that consists of a parameter list, an arrow “->
”, and the function body. Parameter
types can be omitted from the parameter list, the parameter list does not need to be enclosed
in parentheses if there is only one parameter, and the function body can be given either as a
usual code block or alternatively as a single expression that computes the function’s return
value (without performing an explicit return
operation). Java lambda function syntax is almost
identical with JavaScript lambda functions. We give below three simple lambda functions that
perform essentially the same operations. Each of them takes two parameters a
and b
, which
are assumed to be numbers (so they can be compared with < and >), and compares a
and b
according to descending sorting order. The example illustrates on one hand how the parameter types
are optional and on the other hand how a simple function body can be given as an expression
instead of a code block. Note that the middle lambda function is actually a little bit more
restricted than the other two because it explicitly defines the parameter types as double
.
A lambda function without parameter types behaves as if the parameters were defined using the
inferred parameter type var
.
(a, b) -> a < b ? 1 : (a > b ? -1 : 0)
(double a, double b) -> a < b ? 1 : (a > b ? -1 : 0)
(a, b) -> {
if(a < b) {
return 1;
}
if(a > b) {
return -1;
}
return 0;
}
The example below demonstrates Java’s sorting and lambda functions. The program sorts its command line parameters in a few different ways.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Sorting {
public static void main(String[] argArr) {
// Duplicate the command line parameters also into an ArrayList so we
// can test sorting both arrays and lists.
// List.of creates a list from values or an array given to it.
ArrayList<String> argList = new ArrayList<>(List.of(argArr));
System.out.println("Original order:");
System.out.println(" array: " + Arrays.toString(argArr));
System.out.println(" list: " + argList);
// The first sort without separate comparison function: ascending order.
Arrays.sort(argArr);
Collections.sort(argList);
System.out.println("Default sorting (= increasing alphabetical) order:");
System.out.println(" array: " + Arrays.toString(argArr));
System.out.println(" list: " + argList);
// The second sort: descending case-insensitive alphabetical order.
// We define the comparison function as a lambda function directly inside
// the sorting function's parameter list. The function body is given as an
// expression (which here calls String member function compareToIgnoreCase).
// Both comparison functions below work identically. The first just gives
// the String parameter types explicitly whereas the second omits them.
Arrays.sort(argArr, (String a, String b) -> b.compareToIgnoreCase(a));
Collections.sort(argList, (a, b) -> b.compareToIgnoreCase(a));
System.out.println("Decreasing case-insensitive alphabetical order:");
System.out.println(" array: " + Arrays.toString(argArr));
System.out.println(" list: " + argList);
// The third sort: primarily length-based order and secondarily (to break ties
// between equal lengths) in ascending case-insensitive alphabetical order.
// Both lambda functions produce the same result, but the body of the first has
// been defined as a normal code block whereas the second body is an expression.
Arrays.sort(argArr, (a, b) -> {
if(a.length() != b.length()) {
return a.length() - b.length();
}
return a.compareToIgnoreCase(b);
});
argList.sort((a, b) -> (a.length() != b.length()) ? a.length() - b.length()
: a.compareToIgnoreCase(b));
System.out.println("Ordered by length, secondarily in alphabetical order:");
System.out.println(" array: " + Arrays.toString(argArr));
System.out.println(" list: " + argList);
}
}
Running this example program as java Sorting One two Three seven ten
outputs:
Original order:
array: [One, two, Three, seven, ten]
list: [One, two, Three, seven, ten]
Default sorting (= increasing alphabetical) order:
array: [One, Three, seven, ten, two]
list: [One, Three, seven, ten, two]
Decreasing case-insensitive alphabetical order:
array: [two, Three, ten, seven, One]
list: [two, Three, ten, seven, One]
Ordered by length, secondarily in alphabetical order:
array: [One, ten, two, seven, Three]
list: [One, ten, two, seven, Three]
The preceding example did not take advantage of the fact that lambda functions can refer to variables that are visible at the code point where the lambda function is defined. This differs from C++ that requires a lambda function definition to explicitly state which external variables, if any, the lambda function uses.
If a comparison lambda function would have the form (a, b) -> x.f(a, b)
, where x
is a
class or an object, orthe form (a, b) -> a.f(b)
, one does not need to define a lambda function.
In such cases we can directly pass the function f
as such to the sorting function. This is
possible by using Java’s function reference operator ::
. When f
is a member of the class
C
, it can be referenced in on of the three following ways:
If
f
is a class function, the function reference is always of formC::f
and can be used instead of a lambda function of form(a, b) -> C.f(a, b)
.If
f
is a non-static member function, the function reference syntax depends on whether a correspinding lambda function would have the form(a, b) -> o.f(a, b)
, whereo
is an object of some classC
, or the form(a, b) -> a.f(b)
.The case
(a, b) -> o.f(a, b)
corresponds to function referenceo::f
.The case
(a, b) -> a.f(b)
corresponds to function referenceC::f
(that is, same as with a class function). But note that heref
is a non-static member function that is called via the first parametera
, and only the second parameterb
is passed to the funkctionf
.
It is important to note how Java interprets function references in different manner based on whether the reference is done via a class or an object.
The example code below performs the same sorts as the previous example but now using function references instead of lambda functions. The program output is identical.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class FuncRefs {
// An inner helper class whose member function cmp compares strings in
// case-insensitive manner. The sorting order depends on the value given
// as the constructor parameter reversed.
private class StrCmp {
// Do we compare according to a reversed (descending) order?
private boolean reversed;
StrCmp(boolean reversed) {
this.reversed = reversed;
}
int cmp(String a, String b) {
if(!reversed) {
return a.compareToIgnoreCase(b);
}
return b.compareToIgnoreCase(a);
}
}
// A member function that compares strings primarily based on lengths and
// secondarily on case-insensitive ascending alphabetical order.
private int lenCmp(String a, String b) {
if(a.length() != b.length()) {
return a.length() - b.length();
}
return a.compareToIgnoreCase(b);
}
// Like above, but now as a class function.
private static int staticLenCmp(String a, String b) {
if(a.length() != b.length()) {
return a.length() - b.length();
}
return a.compareToIgnoreCase(b);
}
private void execute(String[] argArr) {
ArrayList<String> argList = new ArrayList<>(List.of(argArr));
System.out.println("Original order:");
System.out.println(" array: " + Arrays.toString(argArr));
System.out.println(" list: " + argList);
// Sorting to default ascending order would not require separate comparison
// function. But we as an example provide a function reference to the member
// function compareTo of the String class that does default comparison. It is
// a non-static member function and hence the comparisons done during sorting
// are of form a.compareTo(b). The correct rererence is thus String::compareTo.
Arrays.sort(argArr, String::compareTo);
Collections.sort(argList, String::compareTo);
System.out.println("Default sorting (= increasing alphabetical) order:");
System.out.println(" array: " + Arrays.toString(argArr));
System.out.println(" list: " + argList);
// Create a StrCmp object that compares according to descending order.
StrCmp descStrCmp = new StrCmp(true);
// Sort both argArr and argList into descending case-insensitive order by
// using the cmp member function of the object descStrcmp. Here the comparisons
// done during sorting are of form descStrCmp.cmp(a, b), so we use a function
// reference of form descStrCmp::cmp.
Arrays.sort(argArr, descStrCmp::cmp);
Collections.sort(argList, descStrCmp::cmp);
System.out.println("Decreasing case-insensitive alphabetical order:");
System.out.println(" array: " + Arrays.toString(argArr));
System.out.println(" list: " + argList);
// Sort both argArr and argList primarily into ascending order primarily based
// on length and secondarily on case-insensitive alphabetical order. The first
// sort uses the non-static member function lenCmp that does the comparisons
// as this.lenCmp(a, b), so the function reference is of form this::lenCmp.
// The second sort uses the class function staticLenCmp and the function
// reference this is of form FuncRefs::staticLenCmp.
Arrays.sort(argArr, this::lenCmp);
argList.sort(FuncRefs::staticLenCmp);
System.out.println("Ordered by length, secondarily in alphabetical order:");
System.out.println(" array: " + Arrays.toString(argArr));
System.out.println(" list: " + argList);
}
// This example uses non-static member functions StrCmp and lenCmp. To make these
// available, we create a FuncRefs object dynamically and execute the actual program
// logic by calling the above defined member function "execute".
public static void main(String[] argArr) {
new FuncRefs().execute(argArr);
}
}
We will later discuss how to define a Java function that accepts a lambda function or a function reference as a parameter.