< Summary

Information
Class: MoreStructures.RecImmTrees.Visitor.FullyIterativeDepthFirstTraversal<T1, T2>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/RecImmTrees/Visitor/FullyIterativeDepthFirstTraversal.cs
Line coverage
100%
Covered lines: 37
Uncovered lines: 0
Coverable lines: 37
Total lines: 131
Line coverage: 100%
Branch coverage
100%
Covered branches: 18
Total branches: 18
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_Visit()100%1100%
Visit()100%4100%
ProcessStack(...)100%14100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/RecImmTrees/Visitor/FullyIterativeDepthFirstTraversal.cs

#LineLine coverage
 1namespace MoreStructures.RecImmTrees.Visitor;
 2
 3/// <inheritdoc cref="DepthFirstTraversal{TEdge, TNode}" path="//*[not(self::summary or self::remarks)]"/>
 4/// <summary>
 5/// A lazy, fully-iterative, depth-first <see cref="IVisitStrategy{TNode, TVisitContext}"/> implementation, i.e. a
 6/// traversing strategy which goes in depth as far as possible along each path of the tree, only backtracking when a
 7/// leaf is reached.
 8/// </summary>
 9/// <remarks>
 10///     <inheritdoc cref="DepthFirstTraversal{TEdge, TNode}" path="/remarks"/>
 11///     <para id="advantages">
 12///     ADVANTAGES AND DISADVANTAGES
 13///     <br/>
 14///     <inheritdoc cref="DocFragments" path="/remarks/para[@id='fully-iterative-advantages']"/>
 15///     </para>
 16/// </remarks>
 17public class FullyIterativeDepthFirstTraversal<TEdge, TNode>
 18    : DepthFirstTraversal<TEdge, TNode>
 19    where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode>
 20    where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
 21{
 8073222    private record struct StackFrame(TreeTraversalVisit<TEdge, TNode> Visit, bool ChildrenStacked);
 23
 24    /// <inheritdoc
 25    ///     cref="TreeTraversal{TEdge, TNode}.Visit(TNode)"
 26    ///     path="//*[not(self::summary or self::remarks)]"/>
 27    /// <summary>
 28    /// <b>Lazily and iteratively</b> visits the structure of the provided <paramref name= "node" />, returning the
 29    /// sequence of <see cref="IRecImmDictIndexedTreeNode{TEdge, TNode}"/> of the structure, in depth-first order.
 30    /// </summary>
 31    /// <remarks>
 32    ///     <inheritdoc cref="FullyIterativeDepthFirstTraversal{TEdge, TNode}" path="/remarks"/>
 33    ///     <para id = "algo" >
 34    ///     ALGORITHM
 35    ///     <br/>
 36    ///     The algorithm uses a <see cref="Stack{T}"/>:
 37    ///     <br/>
 38    ///     - At the beginning the stack contains only a frame with the root node, no parent node nor incoming edge and
 39    ///       with a <see cref="bool"/> indicating the children for this node haven't been added to the stack yet;
 40    ///       <br/>
 41    ///     - Then each frame at the top of the stack is popped out and processed, until the stack is empty.
 42    ///       <br/>
 43    ///     - If the node being processed has the "children stacked" flag not set, all children are stacked up. The
 44    ///       node itself is also stacked up, again, this time with the "children stacked" flag set.
 45    ///     - If the node being processed has the "children stacked" flag set, or is a leaf, it's yielded to the
 46    ///       output sequence, so that the client code implementing the visitor can lazily process the nodes.
 47    ///     </para>
 48    ///     <para id="complexity">
 49    ///     COMPLEXITY
 50    ///     <br/>
 51    ///     - Each of the n nodes and n - 1 edges of the tree is visited at most twice: the first time with the
 52    ///       "children stacked" flag unset and a second time with the flag set. Leafs are only visited once, since
 53    ///       they have no children and don't have to wait for their children to be visited.
 54    ///       <br/>
 55    ///     - <see cref="TreeTraversal{TEdge, TNode}.ChildrenSorter"/> can also increase time and space complexity,
 56    ///       especially if it perform an actual sorting of nodes. For example, if the sorter takes n * log(n) time
 57    ///       <br/>
 58    ///     - The <see cref="IEnumerable{T}"/> emitted by <see cref="TreeTraversal{TEdge, TNode}.ChildrenSorter"/> is
 59    ///       reversed to be pushed onto the stack in the right order, and that takes additional O(n - 1) total space,
 60    ///       since there are n - 1 edges, which are 1-to-1 with nodes in the tree.
 61    ///       <br/>
 62    ///     - Each frame processing of a node with the "children stacked" flag set takes constant time (e.g.to check
 63    ///       traversal order) and space (e.g. to extract parent node, incoming edge and node itself from the frame and
 64    ///       to build a <see cref="TreeTraversalVisit{TEdge, TNode}"/> object for the visit).
 65    ///       <br/>
 66    ///     - Time Complexity is O(n * Ts) in total, where Ts is the amortized Time Complexity of
 67    ///       <see cref="TreeTraversal{TEdge, TNode}.ChildrenSorter"/> per edge/node. Taking into account the visit of
 68    ///       each emitted node, Time Complexity is O(n * Ts * Tv), where Tv is the Time Complexity of the visitor per
 69    ///       node.
 70    ///       <br/>
 71    ///     - Space Complexity is O(n * Ss) in total, where Ss is the amortized Space Complexity of
 72    ///       <see cref="TreeTraversal{TEdge, TNode}.ChildrenSorter"/> per edge/node. Taking into account the visit of
 73    ///       each emitted node, Space Complexity is O(n * (Ss + Sv)), where Sv is the Space Complexity of the visitor
 74    ///       per node.
 75    ///     </para>
 76    /// </remarks>
 77    public override IEnumerable<TreeTraversalVisit<TEdge, TNode>> Visit(TNode node)
 1578    {
 1579        var stack = new Stack<StackFrame> { };
 1580        stack.Push(new(new(node, default, default, 0), false));
 2019681        while (stack.Count > 0)
 2018382        {
 2018383            if (ProcessStack(stack) is TreeTraversalVisit<TEdge, TNode> visit)
 1012684                yield return visit;
 2018185        }
 1386    }
 87
 88    private TreeTraversalVisit<TEdge, TNode>? ProcessStack(Stack<StackFrame> stack)
 2018389    {
 2018390        var (visit, childrenStacked) = stack.Pop();
 2018391        var (node, _, _, level) = visit;
 92
 2018393        if (node.IsLeaf())
 7294        {
 7295            return TraversalOrder switch
 7296            {
 7197                TreeTraversalOrder.ParentFirst or TreeTraversalOrder.ChildrenFirst => visit,
 198                _ => throw new NotSupportedException(
 199                    $"{nameof(TreeTraversalOrder)} {TraversalOrder} is not supported."),
 72100            };
 101        }
 102
 20111103        if (!childrenStacked)
 10056104        {
 10056105            switch (TraversalOrder)
 106            {
 107                case TreeTraversalOrder.ParentFirst:
 50296108                    foreach (var child in ChildrenSorter(visit).Reverse())
 10085109                        stack.Push(new(new(child.Value, node, child.Key, level + 1), false));
 10042110                    stack.Push(new(visit, true));
 111
 10042112                    break;
 113
 114                case TreeTraversalOrder.ChildrenFirst:
 13115                    stack.Push(new(visit, true));
 95116                    foreach (var child in ChildrenSorter(visit).Reverse())
 28117                        stack.Push(new(new(child.Value, node, child.Key, level + 1), false));
 118
 13119                    break;
 120
 121                default:
 1122                    throw new NotSupportedException(
 1123                        $"{nameof(TreeTraversalOrder)} {TraversalOrder} is not supported.");
 124            }
 125
 10055126            return null;
 127        }
 128
 10055129        return visit;
 20181130    }
 131}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_Visit()
Visit()
ProcessStack(System.Collections.Generic.Stack`1<MoreStructures.RecImmTrees.Visitor.FullyIterativeDepthFirstTraversal`2/StackFrame<TEdge,TNode>>)