free html hit counter

Introduction

The goal of this library is to provide useful Java 8 streams and to assist you in building new streams that allow efficient parallel processing.

The utilities offered by Streamplify include:

  • combinatorics streams: permutations, combinations, Cartesian products, powers sets, derangements, partial permutations.

  • classes that help you implement your own efficient parallel streams.

The source code is available on GitHub.

Getting Started

You need Java 8 or newer in order to use streamplify-root.

streamplify-root is available in Maven Central and JCenter.

Maven
<dependency>
    <groupId>org.beryx</groupId>
    <artifactId>streamplify-root</artifactId>
    <version>1.1.1</version>
</dependency>
Gradle
compile 'org.beryx:streamplify-root:1.1.1'

User Guide

The JavaDoc is available here.

Utilities

Indexed Spliterators

Spliterators play an essential role in enabling parallel operations on streams. They cover the elements of a source, which can be, for example, an array, a Collection, an I/O channel, or a generator function.

In order to allow parallel operations, a spliterator must be able to partition its source. This operation is performed by the trySplit() method. If the spliterator can be partitioned, this method returns a new spliterator, which covers some portion of the elements, while the caller spliterator will no longer cover this portion.

Java’s Spliterators class provides static methods for creating instances of Spliterator from any Iterator. The trySplit method of the spliterators produced by these methods works as follows: it creates a new spliterator that covers a batch of elements obtained by repeatedly calling the iterator’s next method. If the iterator’s next method is expensive, the spliterator will have a high splitting cost, which leads to poor parallel performance. Such situations may arise if retrieving the next element involves extensive computations or long I/O operations.

In this case, if your source allows indexed-based access to its elements, you can use the indexed spliterators offered by Streamplify in order to ensure that your stream can be efficiently parallelized. The trySplit method of the indexed spliterators is very efficient: it just divides the index range in two subranges of about the same size.

Two spliterators for indexed stream sources are currently available: LongIndexedSpliterator and BigIntegerIndexedSpliterator. The second one is needed for huge sources, with a number of elements that does not fit in a long.

Look at the source code of some classes that extend LongIndexedSpliterator: LongCombinations.java, LongPermutations.java or LongCartesianProduct.java. Fibonacci.java, Jacobsthal.java.

Look at the source code of some classes that extend BigIntegerIndexedSpliterator: BigIntegerCombinations.java, BigIntegerPermutations.java or BigIntegerCartesianProduct.java.

Before using an indexed spliterator, you must set its value supplier, which, depending on the type of your spliterator, is an instance of either Splittable.LongIndexed or Splittable.BigIntegerIndexed.

The apply(long index) method of a value supplier should return the element with the given index in the stream. Using an index to retrieve the corresponding element of a stream is sometimes computationally expensive, but in many cases a more efficient alternative exists: obtaining the requested element based on the value of the element that precedes it in the stream. This is the case for most combinatorics classes provided by Streamplify. Therefore, these classes use stateful value suppliers, which keep track of the last requested index and its associated element. If the value of the preceding element is available, these value suppliers use it to obtain the requested element. Otherwise, for example right after a call to trySplit, the more computationally expensive method of obtaining the requested element based on its index will be used.

When an indexed spliterator splits itself as a result to a trySplit call, the newly created indexed spliterator must also get a value supplier. This is provided by the value supplier of the current spliterator, which calls its own split method. If the value supplier is stateless, the return value of split may be the value supplier itself. Otherwise, a new value supplier should be created.

Look at the source code of some value supplier classes: CombinationSupplier.java, PermutationSupplier.java or CartesianProductSupplier.java.

Streamable

Objects implementing the Streamable interface provide data in form of sequential or parallel Streams.

Important methods:

  • Stream<T> stream();
    Returns a sequential stream.

  • Stream<T> parallelStream();
    Returns a possibly parallel stream.

  • long count();
    BigInteger bigCount();
    These methods return the number of elements in the data source as long or BigInteger.

  • <Z extends Streamable<T,?>> Z skip(long n);
    <Z extends Streamable<T,?>> Z skip(BigInteger n);
    These methods configure the streamable to provide streams that skip the first n elements in the data source. The number of elements to be skipped can be provided as a long or as a BigInteger.

  • <Z extends Streamable<T,?>> Z shuffle();
    <Z extends Streamable<T,?>> Z shuffle(Random random);
    These methods configure the streamable to provide streams that shuffle the elements in the data source. If the random argument is missing, a new Random instance will be created and used.

    Shuffling a potentially huge stream is not a trivial task. Streamplify takes a pragmatic approach and uses a shuffling algorithm that is fast, memory efficient and decently scatters the elements, although not in a uniformly distributed manner. This means that shuffle() is adequate for most practical purposes, but not for hardcore scientific research.

StreamableProxy

Some streams can have a huge number of elements. For example, the number of permutations of n objects is n!, which means that even a permutation stream for 21 objects has a number of elements that no longer fits in a long. For efficiency reasons, you may want to dynamically decide whether to provide a Streamable implementation based on LongIndexedSpliterator or on BigIntegerIndexedSpliterator, depending on the number of elements in your stream. This is possible by using a StreamableProxy, which forwards its method calls to a delegate.

A concrete class that extends StreamableProxy must implement the following method:
Streamable<T, ?> getDelegate();

See the implementation of getDelegate() in Combinations.java, Permutations.java or CartesianProduct.java.

Combinatorics

Combinations

To generate streams of combinations of n elements taken k at a time, Streamplify offers the Combinations class, which is a StreamableProxy that delegates to either LongCombinations or BigIntegerCombinations, depending on the values of n and k.

The code below uses the Combinations class to solve the following problem:
Each morning, you must eat 3 different fruits. You can choose from: apple, banana, mango, orange, peach. Print all your options.

Print all combinations of 3 fruits chosen from: apple, banana, mango, orange, peach
final String[] FRUITS = {"apple", "banana", "mango", "orange", "peach"};
System.out.println(new Combinations(5, 3)
        .stream()
        .map(combination -> Arrays.stream(combination)
                .mapToObj(i -> FRUITS[i])
                .collect(Collectors.joining(", ")))
        .collect(Collectors.joining("\n")));
Output
apple, banana, mango
apple, banana, orange
apple, banana, peach
apple, mango, orange
apple, mango, peach
apple, orange, peach
banana, mango, orange
banana, mango, peach
banana, orange, peach
mango, orange, peach
See Diet.java for a more elaborate version of the above example.
See Arrangements.java for an example of combining combinations and permutations.

Permutations

To generate streams of permutations of n elements, Streamplify offers the Permutations class, which is a StreamableProxy that delegates to either LongPermutations or BigIntegerPermutations, depending on the value of n.

To illustrate the use of permutations, let’s solve the N-Queens problem for a board with size 10 x 10.

Solve the N-Queens problem with size 10
System.out.println(new Permutations(10)
        .parallelStream()
        .filter(perm -> {
            for(int i = 0; i < perm.length - 1; i++) {
                for(int j = i + 1; j < perm.length; j++) {
                    if(Math.abs(perm[j] - perm[i]) == j - i) return false;
                }
            }
            return true;
        })
        .map(perm -> IntStream.range(0, perm.length)
                .mapToObj(i -> "(" + (i + 1) + "," + (perm[i] + 1) + ")")
                .collect(Collectors.joining(", ")))
        .collect(Collectors.joining("\n")));
Output (fragment)
(1,1), (2,3), (3,6), (4,8), (5,10), (6,5), (7,9), (8,2), (9,4), (10,7)
(1,1), (2,3), (3,6), (4,9), (5,7), (6,10), (7,4), (8,2), (9,5), (10,8)
(1,1), (2,3), (3,6), (4,9), (5,7), (6,10), (7,4), (8,2), (9,8), (10,5)
(1,1), (2,3), (3,9), (4,7), (5,10), (6,4), (7,2), (8,5), (9,8), (10,6)
(1,1), (2,4), (3,6), (4,9), (5,3), (6,10), (7,8), (8,2), (9,5), (10,7)
(1,1), (2,4), (3,7), (4,10), (5,2), (6,9), (7,5), (8,3), (9,8), (10,6)
(1,1), (2,4), (3,7), (4,10), (5,3), (6,9), (7,2), (8,5), (9,8), (10,6)
(1,1), (2,4), (3,7), (4,10), (5,6), (6,9), (7,2), (8,5), (9,3), (10,8)
...
See NQueens.java for a more elaborate version of the above example.
See CardDeck.java and TSP.java for more examples using permutations, and Arrangements.java for an example of combining combinations and permutations.

Cartesian Product

To generate streams of Cartesian product elements, Streamplify offers the CartesianProduct class, which is a StreamableProxy that delegates to either LongCartesianProduct or BigIntegerCartesianProduct, depending on the cardinalities of the involved sets.

The code below uses the CartesianProduct class to solve the following problem:
On a flight, you get a snack consisting of a fruit, a candy and a beverage. The fruit is either an apple or a banana. The candy is either Twix or Mars. Available beverages are: water, tea and coffee. Print all possible ways to choose your snack.

Print all possible ways to choose a snack
final String[] FRUITS = {"apple", "banana"};
final String[] CANDIES = {"Twix", "Mars"};
final String[] DRINKS = {"water", "tea", "coffee"};

System.out.println(
  new CartesianProduct(FRUITS.length, CANDIES.length, DRINKS.length)
        .stream()
        .map(snack -> FRUITS[snack[0]]
                      + ", " + CANDIES[snack[1]]
                      + ", " + DRINKS[snack[2]])
        .collect(Collectors.joining("\n")));
Output
apple, Twix, water
apple, Twix, tea
apple, Twix, coffee
apple, Mars, water
apple, Mars, tea
apple, Mars, coffee
banana, Twix, water
banana, Twix, tea
banana, Twix, coffee
banana, Mars, water
banana, Mars, tea
banana, Mars, coffee
See RandomPoetry.java for another example involving CartesianProduct.

Derangements

To generate streams of derangements of n elements, Streamplify offers the Derangements class, which is a StreamableProxy that delegates to either LongDerangements or BigIntegerDerangements, depending on the value of n.

The code below uses the Derangements class to solve the following problem:
List all possible permutations of the word ABCD such that none of the letters remain in its original position.

Print all derangements of the word ABCD
final String WORD = "ABCD";
System.out.println(new Derangements(4)
        .stream()
        .map(combination -> Arrays.stream(combination)
                .mapToObj(i -> Character.toString(WORD.charAt(i)))
                .collect(Collectors.joining("")))
        .collect(Collectors.joining("\n")));
Output
BCDA
BDAC
BADC
CADB
CDBA
CDAB
DABC
DCAB
DCBA
See Hats.java for a different version of the above example.

PowerSet

To generate streams of PowerSet of n elements, Streamplify offers the PowerSet class, which is a StreamableProxy that delegates to either LongPowerSet or BigIntegerPowerSet, depending on the value of n.

The code below uses the PowerSet class to solve the following problem:
Print possible ways in which group of 4 friends can for a trip.

Print all possible groups of 4 friends Alice, Bob, Chloe, David.
final String[] friends = new String[]{"Alice", "Bob", "Chloe", "David"};
        new PowerSet(4).stream().forEach(set -> {
            for (int setElementIndex : set) {
                System.out.print(friends[setElementIndex] + " ");
            }
            System.out.println();
        });
Output
Alice
Bob
Alice Bob
Chloe
Alice Chloe
Bob Chloe
Alice Bob Chloe
David
Alice David
Bob David
Alice Bob David
Chloe David
Alice Chloe David
Bob Chloe David
Alice Bob Chloe David

Partial Permutations

To generate streams of partial permutations of n elements, Streamplify offers the PartialPermutations class, which is a StreamableProxy that delegates to either LongPartialPermutations or BigIntegerPartialPermutations, depending on the value of n.

The code below uses the PartialPermutations class to solve the following problem:
List all possible permutations of the letters ABC such that any letter(s) can be replaced by "_"

Print all partial permutations of the letters ABC
final String WORD = "ABC";
final String BLANK = "_";
System.out.println(new PartialPermutations(WORD.length())
        .stream()
        .map(combination -> Arrays.stream(combination)
                .mapToObj(i -> i == PartialPermutationSupplier.HOLE ? BLANK : Character.toString(WORD.charAt(i)))
                .collect(Collectors.joining("")))
        .collect(Collectors.joining("\n")));
Output
___
__A
_A_
A__
__B
_B_
B__
__C
_C_
C__
_AB
_BA
A_B
AB_
B_A
BA_
_AC
_CA
A_C
AC_
C_A
CA_
_BC
_CB
B_C
BC_
C_B
CB_
ABC
ACB
BAC
BCA
CAB
CBA
See Vacation.java for a different version of the above example.

Release Notes

1.1.0

Thanks to all the contributors to this release: brightcoder, polmauri and John Hadfield.

1.0.0