ツリー構造の深度ストリームを作成

Question

私は親と子の参照を持つ他のツリーノードにリンクするツリーノードからなる基本的なツリー構造を持っています。葉ノードからルートノードへ、またはルートから葉へのストリームを返すメソッドを作成したいと思います。私はこれを既に実装していますが、最小限の量のオブジェクトが作成されるソリューションを探しています。好ましくはない。ここに私のコードは次のとおりです。これは正常に動作しますが、私の「問題」は、オブジェクトの多くは、各ストリームのコールのために作成されている

public class TreeNode<TNode> { 

     private TNode iValue; 

     private TreeNode<TNode> iParentNode = null; 

     private List<TreeNode<TNode>> iChildren = new ArrayList<>(); 

     public TreeNode(TNode value) { 
      this(value, null); 
     } 

     private TreeNode(TNode value, TreeNode<TNode> parentNode) { 
      iValue = value; 
      iParentNode = parentNode; 
     } 

     public Stream<TreeNode<TNode>> streamFromLeaf() { 
      return StreamSupport.stream(Spliterators.spliteratorUnknownSize(new LeafFirstIterator(this), Spliterator.SIZED), 
      false); 
     } 

     public Stream<TreeNode<TNode>> streamFromRoot() { 
      return StreamSupport.stream(Spliterators.spliteratorUnknownSize(new RootFirstIterator(this), Spliterator.SIZED), 
      false); 
     } 

     public TNode getValue() { 
      return iValue; 
     } 

     public TreeNode<TNode> getParent() { 
      return iParentNode; 
     } 

     public TreeNode<TNode> addChild(TNode childValue) { 
      TreeNode<TNode> childNode = new TreeNode<TNode>(childValue, iNodeNameFunction, this); 
      iChildren.add(childNode); 
      return childNode; 
     } 

     public boolean isLeaf() { 
      return iChildren.size() == 0; 
     } 

     public boolean isRoot() { 
      return iParentNode == null; 
     } 

     public List<TreeNode<TNode>> getChildren() { 
      return iChildren; 
     } 

     class LeafFirstIterator implements Iterator<TreeNode<TNode>> { 

      private TreeNode<TNode> iNextNode; 

      LeafFirstIterator(TreeNode<TNode> leafNode) { 
       iNextNode = leafNode; 
      } 

      @Override 
      public boolean hasNext() { 
       return iNextNode != null; 
      } 

      @Override 
      public TreeNode<TNode> next() { 
       TreeNode<TNode> current = iNextNode; 
       iNextNode = current.getParent(); 
       return current; 
      } 

     } 

     class RootFirstIterator implements Iterator<TreeNode<TNode>> { 

      private List<TreeNode<TNode>> iNodes = new ArrayList<>(); 

      private int iNextIndex; 

      RootFirstIterator(TreeNode<TNode> leafNode) { 
       TreeNode<TNode> currentNode = leafNode; 
       while (currentNode != null) { 
        iNodes.add(currentNode); 
        currentNode = currentNode.getParent(); 
       } 
       iNextIndex = iNodes.size() - 1; 
      } 

      @Override 
      public boolean hasNext() { 
       return iNextIndex >= 0; 
      } 

      @Override 
      public TreeNode<TNode> next() { 
       return iNodes.get(iNextIndex--); 
      } 

     } 
    } 

。

• StreamSupport.streamがSpliterators.spliteratorUnknownSizeが
• 私はSpliterator
に渡す私自身のイテレータの実装を作成IteratorSpliterator
• 新しいRootFirstIteratorはストリームがある

新しいのArrayListを作成し、作成する新しいReferencePipeline

を作成します私はできるだけオブジェクトの作成を避けたいです。ストリームなしでツリー構造を反復することは簡単な問題です。今はストリームのマップメソッドしか使用していません。コンシューマーを取り、深さを繰り返し、各ノードごとにコンシューマーを呼び出す方法があり、オブジェクトは作成されませんが、すべてのストリーム機能が失われます。これは次のようになります。

public void iterateUp(Consumer<TreeNode<TNode>> consumer) { 
    doIterateUp(this, consumer); 
} 

public static <T> void doIterateUp(TreeNode<T> node, Consumer<TreeNode<T>> consumer) { 
    if (node == null) 
     return; 
    consumer.accept(node); 
    doIterateUp(node.getParent(), consumer); 
} 

となり、ルートからの反復は簡単です。

これに関するご意見はありますか？私はこれについて間違った方法をとっていますか？ TreeNodeは代わりにインタフェース/クラスを実装または拡張する必要がありますか？不明な点があれば教えてください。

ありがとうございます！

Answer 1

ストリームを使用しないでください。代わりの名前を使用してください：visitor pattern。

ストリームは必ずしも正しいアプローチではなく、これはビジターパターンを使用する典型的なケースです。

絶対にストリームが必要な場合は、消費者にリスト内のノードを収集させてストリーミングするか、コンシューマをイテレータのnext()メソッド（適切な動作をさせるためにいくつかのコードを使用）に配線し、 StreamSupportをストリームに変換します。

Answer 2

私はあなたのパフォーマンスに関する懸念事項を共有しませんが、コードの簡素化の余地があり、副作用として懸念の一部を解決する可能性があります。

Iteratorインターフェイスが古くてよく知られているため、Iteratorの実装から始めるのはよくある間違いです。しかし、それを実装することは面倒であり、あなただけの直接Spliteratorを実装する場合は、SpliteratorでIteratorをラップする必要がないという事実は、唯一きちんと副作用である：私に

public Stream<TreeNode<TNode>> streamFromLeaf() { 
    return StreamSupport.stream(new LeafFirstSpliterator<>(this), false); 
} 
static class LeafFirstSpliterator<TNode> 
extends Spliterators.AbstractSpliterator<TreeNode<TNode>> { 
    private TreeNode<TNode> iNextNode; 
    LeafFirstSpliterator(TreeNode<TNode> leafNode) { 
     super(100, ORDERED|NONNULL); 
     iNextNode = leafNode; 
    } 
    public boolean tryAdvance(Consumer<? super TreeNode<TNode>> action) { 
     if(iNextNode==null) return false; 
     action.accept(iNextNode); 
     iNextNode=iNextNode.getParent(); 
     return true; 
    } 
} 

、Spliterator実装はあまり見えますクリーナーは、少なくともそれを恐れてはいけないし、より速いストリームトラバーサルを可能にするかもしれない。 forEachRemainingメソッドをオーバーライドすることも考えられますし、実装するのも簡単です。ルートからリーフまでの流れについては

は、一時的な記憶は避けられないようだが、それであれば、単にストレージのを使用して、まったく低レベルのコーディングで時間を無駄にしない内蔵のストリーミング機能：

public Stream<TreeNode<TNode>> streamFromRoot() { 
    ArrayDeque<TreeNode<TNode>> deque = new ArrayDeque<>(); 
    for(TreeNode<TNode> n = this; n != null; n = n.getParent()) 
     deque.addFirst(n); 
    return deque.stream(); 
}