This article discusses implementing Java 8 Stream
s and the underlying Spliterator
implementation. The nontrivial implementations described here are Permutations
and Combinations
streams, both of which provide a stream of List<T>
instances representing the combinations of the argument Collection<T>
.
For example, the first Combinations
of 5
of a 52-card Deck
are:
[2-♧, 3-♧, 4-♧, 5-♧, 6-♧]
[2-♧, 3-♧, 4-♧, 5-♧, 7-♧]
[2-♧, 3-♧, 4-♧, 5-♧, 8-♧]
[2-♧, 3-♧, 4-♧, 5-♧, 9-♧]
[2-♧, 3-♧, 4-♧, 5-♧, 10-♧]
[2-♧, 3-♧, 4-♧, 5-♧, J-♧]
[2-♧, 3-♧, 4-♧, 5-♧, Q-♧]
[2-♧, 3-♧, 4-♧, 5-♧, K-♧]
[2-♧, 3-♧, 4-♧, 5-♧, A-♧]
[2-♧, 3-♧, 4-♧, 5-♧, 2-♢]
[2-♧, 3-♧, 4-♧, 5-♧, 3-♢]
...
Complete javadoc is provided.
Stream Implementation
The Permutations
stream is implemented in terms of Combinations
:
public static <T> Stream<List<T>> of(Predicate<List<T>> predicate,
Collection<T> collection) {
int size = collection.size();
return Combinations.of(size, size, predicate, collection);
}
and the Combinations
stream relies on a Spliterator
implementation provided through a Supplier
:
public static <T> Stream<List<T>> of(int size0, int sizeN,
Predicate<List<T>> predicate,
Collection<T> collection) {
SpliteratorSupplier<T> supplier =
new SpliteratorSupplier<T>()
.collection(collection)
.size0(size0).sizeN(sizeN)
.predicate(predicate);
return supplier.stream();
}
The supplier.stream()
method relies on StreamSupport
:
public Stream<List<T>> stream() {
return StreamSupport.<List<T>>stream(get(), false);
}
The Spliterator
implementation is the subject of the next section.
Spliterator Implementation
The abstract DispatchSpliterator
base class provides the implementation of Spliterator.tryAdvance(Consumer)
. The key logic is the current Spliterator
's tryAdvance(Consumer)
method is tried and if it returns false, the next Spliterator
1 is tried until there are no more Spliterator
s to be supplied.
private Iterator<Supplier<Spliterator<T>>> spliterators = null;
private Spliterator<T> spliterator = Spliterators.emptySpliterator();
...
protected abstract Iterator<Supplier<Spliterator<T>>> spliterators();
...
@Override
public Spliterator<T> trySplit() {
if (spliterators == null) {
spliterators = Spliterators.iterator(spliterators());
}
return spliterators.hasNext() ? spliterators.next().get() : null;
}
@Override
public boolean tryAdvance(Consumer<? super T> consumer) {
boolean accepted = false;
while (! accepted) {
if (spliterator == null) {
spliterator = trySplit();
}
if (spliterator != null) {
accepted = spliterator.tryAdvance(consumer);
if (! accepted) {
spliterator = null;
}
} else {
break;
}
}
return accepted;
}
Subclass implementors must supply an implementation of Iterator<Supplier<Spliterator<T>>> spliterators()
. In the Combinations
implementation, the key Spliterator
, ForPrefix
, iterates over every (sorted) prefix and either supplies more ForPrefix
Spliterator
s or a single ForCombination
Spliterator
:
private class ForPrefix extends DispatchSpliterator<List<T>> {
private final int size;
private final List<T> prefix;
private final List<T> remaining;
public ForPrefix(int size, List<T> prefix, List<T> remaining) {
super(binomial(remaining.size(), size),
SpliteratorSupplier.this.characteristics());
this.size = size;
this.prefix = requireNonNull(prefix);
this.remaining = requireNonNull(remaining);
}
@Override
protected Iterator<Supplier<Spliterator<List<T>>>> spliterators() {
List<Supplier<Spliterator<List<T>>>> list = new LinkedList<>();
if (prefix.size() < size) {
for (int i = 0, n = remaining.size(); i < n; i += 1) {
List<T> prefix = new LinkedList<>(this.prefix);
List<T> remaining = new LinkedList<>(this.remaining);
prefix.add(remaining.remove(i));
list.add(() -> new ForPrefix(size, prefix, remaining));
}
} else if (prefix.size() == size) {
list.add(() -> new ForCombination(prefix));
} else {
throw new IllegalStateException();
}
return list.iterator();
}
}
Size, supplied as a superclass constructor parameter, is calculated with the binomial()
method. For an individual combination, the size is 1
.
private class ForCombination extends DispatchSpliterator<List<T>> {
private final List<T> combination;
public ForCombination(List<T> combination) {
super(1, SpliteratorSupplier.this.characteristics());
this.combination = requireNonNull(combination);
}
@Override
protected Iterator<Supplier<Spliterator<List<T>>>> spliterators() {
Supplier<Spliterator<List<T>>> supplier =
() -> Collections.singleton(combination).spliterator();
return Collections.singleton(supplier).iterator();
}
}
Implementations should delay as much computation as possible until required in Spliterator.tryAdvance(Consumer)
allowing callers (including Stream
thorough StreamSupport
) to optimize and avoid computation.
The complete implementation provides a Start
Spliterator
returned by the SpliteratorSupplier
and a ForSize
spliterator to iterate over combination sizes.
private class Start extends DispatchSpliterator<List<T>> {
public Start() {
super(binomial(collection().size(), size0(), sizeN()),
SpliteratorSupplier.this.characteristics());
}
@Override
protected Iterator<Supplier<Spliterator<List<T>>>> spliterators() {
List<Supplier<Spliterator<List<T>>>> list = new LinkedList<>();
IntStream.rangeClosed(Math.min(size0(), sizeN()),
Math.max(size0(), sizeN()))
.filter(t -> ! (collection.size() < t))
.forEach(t -> list.add(() -> new ForSize(t)));
if (size0() > sizeN()) {
Collections.reverse(list);
}
return list.iterator();
}
...
}
private class ForSize extends DispatchSpliterator<List<T>> {
private final int size;
public ForSize(int size) {
super(binomial(collection().size(), size),
SpliteratorSupplier.this.characteristics());
this.size = size;
}
@Override
protected Iterator<Supplier<Spliterator<List<T>>>> spliterators() {
Supplier<Spliterator<List<T>>> supplier =
() -> new ForPrefix(size,
Collections.emptyList(),
new LinkedList<>(collection()));
return Collections.singleton(supplier).iterator();
}
...
}
Honoring the API Predicate Parameter
The API defines a Predicate
parameter which provides a way for callers to dynamically short-circuit all or part of the iteration. The ForPrefix
and ForCombination
tryAdvance(Consumer)
methods are overridden as follows:
private class ForPrefix extends DispatchSpliterator<List<T>> {
...
@Override
public boolean tryAdvance(Consumer<? super List<T>> consumer) {
Predicate<List<T>> predicate =
SpliteratorSupplier.this.predicate();
return ((prefix.isEmpty()
|| (predicate == null || predicate.test(prefix)))
&& super.tryAdvance(consumer));
}
...
}
private class ForCombination extends DispatchSpliterator<List<T>> {
...
public boolean tryAdvance(Consumer<? super List<T>> consumer) {
Predicate<List<T>> predicate =
SpliteratorSupplier.this.predicate();
return ((combination.isEmpty()
|| (predicate == null || predicate.test(combination)))
&& super.tryAdvance(consumer));
}
...
}
If a Predicate
is supplied and the current combination does not satisfy the Predicate
, that path is pruned immediately. A future blog post will discuss using this feature to quickly evaluate Poker hands.
[1] Obtained by calling the implementatioon of Spliterator.trySplit()
. ↩
Top comments (0)