流的优点之一是您可以避免访问某些操作的整个结构,例如anyMatch或filter findFirst。但是,如果您有自己的数据结构,根据您将其转换为流的方式,您最终可能会访问所有数据。将自定义树数据类型转换为流的正确方法是什么?考虑以下示例:
interface Tree{
void forEach(Consumer<Integer> c);
}
final class EmptyTree implements Tree{
public void forEach(Consumer<Integer> c){}
}
interface NonEmptyTree extends Tree{}
record Leave(int label) implements NonEmptyTree{
public void forEach(Consumer<Integer> c){
System.out.println("In forEachLeave "+label);
c.accept(label);
}
}
record Node(NonEmptyTree left, NonEmptyTree right) implements NonEmptyTree{
public void forEach(Consumer<Integer> c){
left.forEach(c); right.forEach(c);
}
}
把一棵树变成溪流的两种主要方法是
var sb=Stream.<Integer>builder();
myTree.forEach(sb);
sb.build()
或
Stream.of(myTree).mapMulti(Tree::forEach)
但是,它们都调用for每一个,因此它们都将访问所有树(并在本例中调用所有标签的打印)。
您如何在Tree类型中实现. stream()方法,以便在不需要时它甚至不会访问整个树?(例如,因为.anyMatch)
好的,我对它进行了排序。我很确定我正在做的事情对于不可变树来说是相当标准的(父字段只有在可变树中才有意义)
这是我的结果,供未来在不可变树上做流的程序员参考。类TreeIterator
interface Tree<E> extends Iterable<E>{
Tree<E> and(Tree<E> other);
default Tree<E> left(){ return empty(); }
default Tree<E> right(){ return empty(); }
default E label(Supplier<E> orElse){ return orElse.get(); }
@SuppressWarnings("unchecked")
static <E> Tree<E> empty(){ return (Tree<E>)EmptyTree.empty; }
static <E> Tree<E> leaf(E label){ return new Leaf<E>(label); }
default Stream<E> stream(){ return StreamSupport.stream(spliterator(), false); }
}
final class EmptyTree<E> implements Tree<E>{
public Tree<E> and(Tree<E> other){ return other; }
private EmptyTree(){} //Singleton pattern: only one EmptyTree can exists
static final Tree<?> empty = new EmptyTree<>();
public Iterator<E> iterator(){ return List.<E>of().iterator(); }
public String toString(){ return "<EMPTY>"; }
}
interface NonEmptyTree<E> extends Tree<E>{
Leaf<E> itAdvance(ArrayList<NonEmptyTree<E>> stack);
default Tree<E> and(Tree<E> other){
if (!(other instanceof NonEmptyTree<E> net)){ return this; }
return new Node<E>(this, net);
}
}
record Leaf<E>(E label) implements NonEmptyTree<E>{
public E label(Supplier<E> orElse){ return label; }
public Leaf<E> itAdvance(ArrayList<NonEmptyTree<E>> stack){ return this; }
public Iterator<E> iterator(){ return List.<E>of(label).iterator(); }
public String toString(){ return label+""; }
}
record Node<E>(NonEmptyTree<E> left, NonEmptyTree<E> right) implements NonEmptyTree<E>{
public Node{ assert left!=null && right!=null; }//null is not a valid tree
public Leaf<E> itAdvance(ArrayList<NonEmptyTree<E>> stack){
stack.add(right);
return left.itAdvance(stack);
}
public Iterator<E> iterator(){ return new TreeIterator<E>(this); }
public String toString(){ return "("+left+", "+right+")"; }
}
class TreeIterator<E> implements Iterator<E>{
private final ArrayList<NonEmptyTree<E>> stack = new ArrayList<>(32);
public boolean hasNext(){ return !stack.isEmpty(); }
public TreeIterator(Node<E> n){ stack.add(n); }
public E next(){
if(stack.isEmpty()){ throw new NoSuchElementException(); }
var last=stack.remove(stack.size()-1);
return last.itAdvance(stack).label();
}
}
查看记录定义离开(int label)实现了NonCountyTree
,我有两个问题:
我推荐一个像这样的简单实现:https://www.baeldung.com/java-binary-tree
谈到流,您有两种选择:
请记住,外面有许多不同的树,例如红黑树、正树、AVL树、B树…