< Summary

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

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
Visit()100%12100%
ProcessParentFirstTraversalQueue(...)100%2100%
ProcessChildrenFirstTraversalQueue(...)100%2100%

File(s)

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

#LineLine coverage
 1namespace MoreStructures.RecImmTrees.Visitor;
 2
 3/// <inheritdoc cref="BreadthFirstTraversal{TEdge, TNode}" path="//*[not(self::summary or self::remarks)]"/>
 4/// <summary>
 5/// A lazy, fully-iterative, breadth-first <see cref="IVisitStrategy{TNode, TVisitContext}"/> implementation, i.e. a
 6/// traversing strategy which visits all the nodes at the current depth, along any path of the tree, before going
 7/// deeper or shallower, exploring nodes with higher or lower depth.
 8/// </summary>
 9/// <remarks>
 10///     <inheritdoc cref="BreadthFirstTraversal{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 FullyIterativeBreadthFirstTraversal<TEdge, TNode>
 18    : BreadthFirstTraversal<TEdge, TNode>
 19    where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode>
 20    where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
 21{
 22
 23    /// <inheritdoc
 24    ///     cref="TreeTraversal{TEdge, TNode}.Visit(TNode)"
 25    ///     path="//*[not(self::summary or self::remarks)]"/>
 26    /// <summary>
 27    /// <b>Lazily and iteratively</b> visits the structure of the provided <paramref name= "node" />, returning the
 28    /// sequence of <see cref="IRecImmDictIndexedTreeNode{TEdge, TNode}"/> of the structure, in breadth-first order.
 29    /// </summary>
 30    /// <remarks>
 31    ///     <inheritdoc cref="FullyIterativeBreadthFirstTraversal{TEdge, TNode}" path="/remarks"/>
 32    ///     <para id="algo">
 33    ///     ALGORITHM
 34    ///     <br/>
 35    ///     The algorithm performs a double walk:
 36    ///     <br/>
 37    ///     - The first walk is of the nodes of the tree structure and always proceeds top-down, enqueuing each
 38    ///       encountered child for each node into a "traversal" <see cref="Queue{T}"/>, which is used to reproduce the
 39    ///       breadth-first order.
 40    ///       <br/>
 41    ///     - The first walk also enqueues each encountered node into a "visit" <see cref="Queue{T}"/>, if the
 42    ///       <see cref="TreeTraversal{TEdge, TNode}.TraversalOrder"/> is <see cref="TreeTraversalOrder.ParentFirst"/>,
 43    ///       or it pushes it onto a "visit" <see cref="Stack{T}"/>, if it is
 44    ///       <see cref="TreeTraversalOrder.ChildrenFirst"/>.
 45    ///       <br/>
 46    ///     - The second walk goes through the "visit" queue/stack, yielding to the output sequence, so that the
 47    ///       client code implementing the visitor can lazily process the nodes.
 48    ///     </para>
 49    ///     <para id="complexity">
 50    ///     COMPLEXITY
 51    ///     <br/>
 52    ///     Each of the walk goes through all the n nodes and n - 1 edges of the tree.
 53    ///     <br/>
 54    ///     Each walk uses a O(1) insertion and extraction data structure, which contains at most n elements of
 55    ///     constant size (reference to the node, reference to its parent, reference to its incoming edge).
 56    ///     <br/>
 57    ///     Time Complexity is O(n) for the first walk, when the visit queue/stack is populated and no actual node
 58    ///     visit is performed, and O(n) for the second walk, when the actual visit of all nodes is performed.
 59    ///     So O(n) in total.
 60    ///     <br/>
 61    ///     Space Complexity is O(2n) for the first walk, due to the traversal and visit queue/stack being allocated
 62    ///     and populated, and O(n) for the second walk, when the actual visit of all nodes is performed.
 63    ///     So O(n) in total.
 64    ///     </para>
 65    /// </remarks>
 66    public override IEnumerable<TreeTraversalVisit<TEdge, TNode>> Visit(TNode node)
 6667    {
 6668        switch (TraversalOrder)
 69        {
 70            case TreeTraversalOrder.ParentFirst:
 6071                {
 6072                    var traversalQueue = new Queue<TreeTraversalVisit<TEdge, TNode>>();
 6073                    traversalQueue.Enqueue(new(node, default, default, 0));
 74
 6075                    var visitQueue = new Queue<TreeTraversalVisit<TEdge, TNode>>();
 76
 1070577                    while (traversalQueue.Count > 0)
 1064578                        ProcessParentFirstTraversalQueue(traversalQueue, visitQueue);
 79
 1053280                    while (visitQueue.Count > 0)
 1049781                        yield return visitQueue.Dequeue();
 3582                }
 83
 3584                break;
 85
 86            case TreeTraversalOrder.ChildrenFirst:
 487                {
 488                    var traversalQueue = new Queue<TreeTraversalVisit<TEdge, TNode>>();
 489                    traversalQueue.Enqueue(new(node, default, default, 0));
 90
 491                    var visitStack = new Stack<TreeTraversalVisit<TEdge, TNode>>();
 92
 4593                    while (traversalQueue.Count > 0)
 4194                        ProcessChildrenFirstTraversalQueue(traversalQueue, visitStack);
 95
 4596                    while (visitStack.Count > 0)
 4197                        yield return visitStack.Pop();
 498                }
 99
 4100                break;
 101
 102            default:
 2103                throw new NotSupportedException($"{nameof(TraversalOrder)} {TraversalOrder} not supported.");
 104        }
 39105    }
 106
 107    private void ProcessParentFirstTraversalQueue(
 108        Queue<TreeTraversalVisit<TEdge, TNode>> traversalQueue, Queue<TreeTraversalVisit<TEdge, TNode>> visitQueue)
 10645109    {
 10645110        var visit = traversalQueue.Dequeue();
 10645111        var (node, _, _, level) = visit;
 112
 10645113        visitQueue.Enqueue(visit);
 53105114        foreach (var child in ChildrenSorter(visit))
 10585115            traversalQueue.Enqueue(new(child.Value, node, child.Key, level + 1));
 10645116    }
 117
 118    private void ProcessChildrenFirstTraversalQueue(
 119        Queue<TreeTraversalVisit<TEdge, TNode>> traversalQueue, Stack<TreeTraversalVisit<TEdge, TNode>> visitStack)
 41120    {
 41121        var visit = traversalQueue.Dequeue();
 41122        var (node, _, _, level) = visit;
 123
 41124        visitStack.Push(visit);
 197125        foreach (var child in ChildrenSorter(visit).Reverse())
 37126            traversalQueue.Enqueue(new(child.Value, node, child.Key, level + 1));
 41127    }
 128}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

Visit()
ProcessParentFirstTraversalQueue(System.Collections.Generic.Queue`1<MoreStructures.RecImmTrees.Visitor.TreeTraversalVisit`2<TEdge,TNode>>,System.Collections.Generic.Queue`1<MoreStructures.RecImmTrees.Visitor.TreeTraversalVisit`2<TEdge,TNode>>)
ProcessChildrenFirstTraversalQueue(System.Collections.Generic.Queue`1<MoreStructures.RecImmTrees.Visitor.TreeTraversalVisit`2<TEdge,TNode>>,System.Collections.Generic.Stack`1<MoreStructures.RecImmTrees.Visitor.TreeTraversalVisit`2<TEdge,TNode>>)