Дата публикации: 02.06.2014 15:31:41
As you know, we recently released Java 8, which main new feature is Lambda Expressions. In this article, I'd like to use Lambda and related functionality to implement the BeadSort algorithm. This algorithm was described in the previous article.
First of all, I created the following utility class:
private static class Utility { private final boolean reverse; private Utility(boolean reverse) { this.reverse = reverse; } private static int[] create(int value) { int[] array = new int[value]; while (0 < value--) { array[value] = 1; } return array; } private int[] join(int[] big, int[] small) { if (big.length < small.length) { int[] temp = big; big = small; small = temp; } int index = !this.reverse ? big.length - small.length : 0; for (int value : small) { big[index++] += value; } return big; } }
It contains two methods that will be used later through the method references. The create method constructs an array with the specified length and fills it with the number 1. For example, for the number 5 it creates the following array: [1,1,1,1,1]. The join method is intended to add all values of the shorter array to the corresponding values of the another one. Note, that it uses the reverse field to align arrays, when their lengths are different.
Then I rewrote the sort method on the new API:
public static int[] sort(int[] array, boolean reverse) { Objects.requireNonNull(array, "array"); if (array.length == 0) { return array; } int min = Arrays.stream(array).min().getAsInt(); Utility utility = new Utility(reverse); return Arrays .stream(Arrays .stream(array) .map(value -> value - min) .mapToObj(Utility::create) .reduce(utility::join) .map(Arrays::stream).get() .mapToObj(Utility::create) .reduce(new int[array.length], utility::join)) .map(value -> value + min) .toArray(); }
In the beginning this method calculates the minimum of the specified array by using the Stream API. Then, it creates the instance of the Utility class, defining the sort order. And after that the magic begins:
.stream(array)
convert the integer array to the integer stream;
.map(value -> value - min)
substract the minimal value from every integer value (normalize);
.mapToObj(Utility::create)
replace every integer value with the corresponding array via static method reference;
.reduce(utility::join)
join together every array via instance method reference;
.map(Arrays::stream).get()
convert the resulting array to the integer stream;
.mapToObj(Utility::create)
replace every integer value with a corresponding array via static method reference (second step);
.reduce(new int[array.length], utility::join))
join every array with the specified one via instance method reference;
.map(value -> value + min)
add the minimal value to every integer value (denormalize);
.toArray()
convert the integer stream to the integer array.
The following method can be used to reverse the order of the integer values in the specified array. It uses the known trick for the Comparator class:
private static int[] reverse(int[] array) { return Arrays .stream(array) .boxed() .sorted((o1, o2) -> -1) .mapToInt(Integer::intValue) .toArray(); }
This implementation of the BeadSort algorithm is not as cute and fast as the previous one. It is just an interesting theoretical exercise. The source file of the example is available.
PS. Do not forget to choose the right tool for a specific task!