Skip to content

Instantly share code, notes, and snippets.

@zsolt-donca
Last active August 8, 2016 12:58
Show Gist options
  • Save zsolt-donca/efd31828da91fd390819b19c28116d40 to your computer and use it in GitHub Desktop.
Save zsolt-donca/efd31828da91fd390819b19c28116d40 to your computer and use it in GitHub Desktop.
java.util.Stream for a binary tree; checking if it's sorted, min, max; first two values
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;
import java.util.stream.Stream;
class TreeTest {
static class Tree {
final int value;
final Tree left, right;
public Tree(int value, Tree left, Tree right) {
this.value = value;
this.left = left;
this.right = right;
}
Stream<Integer> toStream() {
return Stream.concat(left != null ? left.toStream() : Stream.empty(),
Stream.concat(Stream.of(value),
right != null ? right.toStream() : Stream.empty()));
}
}
// there are no tuples in JDK :(
static class SortedMinMax {
boolean sorted;
int min, max;
public SortedMinMax(boolean sorted, int min, int max) {
this.sorted = sorted;
this.min = min;
this.max = max;
}
}
public static Tree tree(int value, Tree left, Tree right) {
return new Tree(value, left, right);
}
public static Tree tree(int value) {
return new Tree(value, null, null);
}
public static void main(String[] args) {
Tree tree = tree(4, tree(2, tree(1), tree(3)), tree(5));
System.out.println("toStream: " + tree.toStream().collect(Collectors.toList())); // [1, 2, 3, 4, 5]
// SortedMinMax with the below reduce op is a Monoid
Optional<SortedMinMax> sortedMinMaxOption = tree.toStream().map(i -> new SortedMinMax(true, i, i))
.reduce((left, right) -> {
boolean sorted = left.sorted && right.sorted && left.max <= right.min;
int min = Math.min(left.min, right.min);
int max = Math.max(left.max, right.max);
return new SortedMinMax(sorted, min, max);
});
SortedMinMax sortedMinMax = sortedMinMaxOption.get(); // safe as long as the stream is not empty
System.out.println("Sorted: " + sortedMinMax.sorted); // true
System.out.println("Min: " + sortedMinMax.min); // 1
System.out.println("Max: " + sortedMinMax.max); // 5
List<Integer> firstTwo = tree.toStream().limit(2).collect(Collectors.toList());
System.out.println("First two: " + firstTwo); // [1, 2]
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment