< Summary

Information
Class: MoreStructures.CountTrees.CountTreeNode<T1, T2>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/CountTrees/CountTreeNode.cs
Line coverage
100%
Covered lines: 98
Uncovered lines: 0
Coverable lines: 98
Total lines: 163
Line coverage: 100%
Branch coverage
100%
Covered branches: 14
Total branches: 14
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_WrappedNode()100%1100%
.ctor(...)100%1100%
Compute()100%2100%
ProcessStack(...)100%8100%
get_Children()100%2100%
get_DescendantsCount()100%2100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/CountTrees/CountTreeNode.cs

#LineLine coverage
 1using MoreStructures.RecImmTrees;
 2using MoreStructures.Utilities;
 3
 4namespace MoreStructures.CountTrees;
 5
 6/// <summary>
 7/// An implementation of <see cref="IRecImmDictIndexedTreeNode{TEdge, TNode}"/>, wrapping another
 8/// implementation of <see cref="IRecImmDictIndexedTreeNode{TEdge, TNode}"/>, and counting the total
 9/// number of descendands the wrapped node has below (node itself excluded).
 10/// </summary>
 11/// <typeparam name="TEdge">
 12///     <inheritdoc cref="IRecImmDictIndexedTreeNode{TEdge, TNode}" path="/typeparam[@name='TEdge']"/>
 13/// </typeparam>
 14/// <typeparam name="TNode">
 15///     <inheritdoc cref="IRecImmDictIndexedTreeNode{TEdge, TNode}" path="/typeparam[@name='TNode']"/>
 16/// </typeparam>
 17/// <param name="WrappedNode">The node being wrapped, and whose descendants are going to be counted.</param>
 18/// <remarks>
 19///     <para id="records-semantics">
 20///     RECORDS SEMANTICS
 21///     <br/>
 22///     Due to records semantics, and the use of value readonly dictionaries, two
 23///     <see cref="CountTreeNode{TEdge, TNode}"/> instances wrapping the same underlying node, or two equivalent nodes,
 24///     will be equal.
 25///     </para>
 26///     <para id="iterativity">
 27///     ITERATIVITY
 28///     <br/>
 29///     <see cref="CountTreeNode{TEdge, TNode}"/> structure construction and properties calculation are done lazily.
 30///     <br/>
 31///     <inheritdoc cref="DocFragments" path="/remarks/para[@id='fully-iterative-advantages']"/>
 32///     </para>
 33///     <para id="caching">
 34///     CACHING
 35///     <br/>
 36///     Once <see cref="Children"/> and <see cref="DescendantsCount"/> properties are calculated, they are cached to
 37///     avoid multiple calculation. This is also one of the reasons why immutability of the wrapped tree is a
 38///     requirement to use <see cref="CountTreeNode{TEdge, TNode}"/>.
 39///     </para>
 40///     <para id="complexity">
 41///     COMPLEXITY
 42///     <br/>
 43///     Time Complexity = O(n) and Space Complexity = O(n) where n = number of nodes in <see cref="WrappedNode"/>
 44///     structure. Leafs are visited only once, intermediate nodes are visited (at most) twice.
 45///     </para>
 46/// </remarks>
 47/// <example>
 48/// <code>
 49/// var wrapped = new Node(1)
 50/// {
 51///     Children = new Dictionary&lt;Edge, Node&gt;
 52///     {
 53///         [new(1)] = new(2),
 54///         [new(2)] = new(3)
 55///         {
 56///             ...
 57///         },
 58///         [new(5)] = new(6),
 59///     }
 60/// };
 61///
 62/// var wrapping = new CountTreeNode&lt;Edge, Node&gt;(wrapped);
 63/// Assert.AreEqual(3, wrapping.Children.Count);
 64/// </code>
 65/// </example>
 6006666public sealed record CountTreeNode<TEdge, TNode>(TNode WrappedNode)
 3002667    : IRecImmDictIndexedTreeNode<CountTreeEdge<TEdge, TNode>, CountTreeNode<TEdge, TNode>>
 3002668    where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode>
 3002669    where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
 3002670{
 3002671    private IDictionary<CountTreeEdge<TEdge, TNode>, CountTreeNode<TEdge, TNode>>? _children;
 3002672    private int? _descendantsCount = null;
 3002673
 3002674    /// <summary>
 3002675    /// A private readonly object used for synchronization across multiple calls on the same instance.
 3002676    /// </summary>
 3002677    /// <remarks>
 3002678    /// A <see cref="LockValueObject"/> is used not to break value equality of this record.
 3002679    /// </remarks>
 3002680    private readonly LockValueObject _lockObject = new();
 3002681
 30018082    private record struct StackFrame(CountTreeNode<TEdge, TNode> Node, TNode WrappedNode, bool ChildrenProcessed);
 3002683
 3002684    private void Compute()
 785    {
 786        lock (_lockObject)
 787        {
 788            var stack = new Stack<StackFrame>();
 789            stack.Push(new(this, WrappedNode, false));
 3002690
 5003791            while (stack.Count > 0)
 5003092                ProcessStack(stack);
 793        }
 794    }
 3002695
 3002696    private static void ProcessStack(Stack<StackFrame> stack)
 5003097    {
 5003098        var (node, wrappedNode, childrenProcessed) = stack.Pop();
 3002699
 50030100        if (wrappedNode.IsLeaf())
 10012101        {
 10012102            var children = new Dictionary<CountTreeEdge<TEdge, TNode>, CountTreeNode<TEdge, TNode>> { };
 10012103            node._children = children.ToValueReadOnlyDictionary();
 10012104            node._descendantsCount = 0;
 10012105            return;
 30026106        }
 30026107
 40018108        if (!childrenProcessed)
 20009109        {
 20009110            stack.Push(new(node, wrappedNode, true));
 30026111
 20009112            var children = new Dictionary<CountTreeEdge<TEdge, TNode>, CountTreeNode<TEdge, TNode>> { };
 120055113            foreach (var (wrappedChildEdge, wrappedChildNode) in wrappedNode.Children)
 30014114            {
 30014115                var childEdge = new CountTreeEdge<TEdge, TNode>(wrappedChildEdge);
 30014116                var childNode = new CountTreeNode<TEdge, TNode>(wrappedChildNode);
 30014117                children[childEdge] = childNode;
 30026118
 30014119                stack.Push(new(childNode, wrappedChildNode, false));
 30014120            }
 30026121
 20009122            node._children = children.ToValueReadOnlyDictionary();
 20009123            return;
 30026124        }
 30026125
 30026126        // At this point _children has been initialized in previous ProcessStack execution for the same node
 30026127        // and _descendantsCount has been set for all the children of the node (due to the fact that the node has
 30026128        // been re-pushed to the stack just before all its children).
 50023129        node._descendantsCount = node._children!.Sum(c => c.Value._descendantsCount!.Value + 1);
 50030130    }
 30026131
 30026132    /// <inheritdoc path="//*[not(self::remarks)]"/>
 30026133    /// <remarks>
 30026134    /// <inheritdoc cref="CountTreeNode{TEdge, TNode}" path="/remarks/para[@id='info']"/>
 30026135    /// </remarks>
 30026136    public IDictionary<CountTreeEdge<TEdge, TNode>, CountTreeNode<TEdge, TNode>> Children
 30026137    {
 30026138        get
 7139        {
 7140            if (_children == null)
 1141                Compute();
 30026142
 7143            return _children!; // Initialized in Compute
 7144        }
 30026145    }
 30026146
 30026147    /// <summary>
 30026148    /// The number of descendands below this node (node itself excluded).
 30026149    /// </summary>
 30026150    /// <remarks>
 30026151    /// <inheritdoc cref="CountTreeNode{TEdge, TNode}" path="/remarks/para[@id='info']"/>
 30026152    /// </remarks>
 30026153    public int DescendantsCount
 30026154    {
 30026155        get
 8156        {
 8157            if (_descendantsCount == null)
 6158                Compute();
 30026159
 8160            return _descendantsCount!.Value; // Initialized in Compute
 8161        }
 30026162    }
 30026163}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_WrappedNode()
.ctor(TNode)
Compute()
ProcessStack(System.Collections.Generic.Stack`1<MoreStructures.CountTrees.CountTreeNode`2/StackFrame<TEdge,TNode>>)
get_Children()
get_DescendantsCount()