Class CountTreeNode<TEdge, TNode>

An implementation of IRecImmDictIndexedTreeNode<TEdge, TNode>, wrapping another implementation of IRecImmDictIndexedTreeNode<TEdge, TNode>, and counting the total number of descendands the wrapped node has below (node itself excluded).

Inheritance
System.Object
CountTreeNode<TEdge, TNode>
Implements
System.IEquatable<CountTreeNode<TEdge, TNode>>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.CountTrees
Assembly: MoreStructures.dll
Syntax
public sealed class CountTreeNode<TEdge, TNode> : IRecImmDictIndexedTreeNode<CountTreeEdge<TEdge, TNode>, CountTreeNode<TEdge, TNode>>, IEquatable<CountTreeNode<TEdge, TNode>> where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode> where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
Type Parameters
Name Description
TEdge

TNode

Remarks

RECORDS SEMANTICS
Due to records semantics, and the use of value readonly dictionaries, two CountTreeNode<TEdge, TNode> instances wrapping the same underlying node, or two equivalent nodes, will be equal.

ITERATIVITY
CountTreeNode<TEdge, TNode> structure construction and properties calculation are done lazily.

CACHING
Once Children and DescendantsCount properties are calculated, they are cached to avoid multiple calculation. This is also one of the reasons why immutability of the wrapped tree is a requirement to use CountTreeNode<TEdge, TNode>.

COMPLEXITY
Time Complexity = O(n) and Space Complexity = O(n) where n = number of nodes in WrappedNode structure. Leafs are visited only once, intermediate nodes are visited (at most) twice.

Examples
var wrapped = new Node(1) 
{ 
    Children = new Dictionary<Edge, Node> 
    {
        [new(1)] = new(2),
        [new(2)] = new(3)
        {
            ...
        },
        [new(5)] = new(6),
    } 
};

var wrapping = new CountTreeNode<Edge, Node>(wrapped);
Assert.AreEqual(3, wrapping.Children.Count);

Constructors

| Improve this Doc View Source

CountTreeNode(TNode)

An implementation of IRecImmDictIndexedTreeNode<TEdge, TNode>, wrapping another implementation of IRecImmDictIndexedTreeNode<TEdge, TNode>, and counting the total number of descendands the wrapped node has below (node itself excluded).

Declaration
public CountTreeNode(TNode WrappedNode)
Parameters
Type Name Description
TNode WrappedNode

The node being wrapped, and whose descendants are going to be counted.
Remarks

RECORDS SEMANTICS
Due to records semantics, and the use of value readonly dictionaries, two CountTreeNode<TEdge, TNode> instances wrapping the same underlying node, or two equivalent nodes, will be equal.

ITERATIVITY
CountTreeNode<TEdge, TNode> structure construction and properties calculation are done lazily.

CACHING
Once Children and DescendantsCount properties are calculated, they are cached to avoid multiple calculation. This is also one of the reasons why immutability of the wrapped tree is a requirement to use CountTreeNode<TEdge, TNode>.

COMPLEXITY
Time Complexity = O(n) and Space Complexity = O(n) where n = number of nodes in WrappedNode structure. Leafs are visited only once, intermediate nodes are visited (at most) twice.

Examples
var wrapped = new Node(1) 
{ 
    Children = new Dictionary<Edge, Node> 
    {
        [new(1)] = new(2),
        [new(2)] = new(3)
        {
            ...
        },
        [new(5)] = new(6),
    } 
};

var wrapping = new CountTreeNode<Edge, Node>(wrapped);
Assert.AreEqual(3, wrapping.Children.Count);

Properties

| Improve this Doc View Source

Children

Declaration
public IDictionary<CountTreeEdge<TEdge, TNode>, CountTreeNode<TEdge, TNode>> Children { get; }
Property Value
Type Description
IDictionary<CountTreeEdge<TEdge, TNode>, CountTreeNode<TEdge, TNode>>
Remarks

| Improve this Doc View Source

DescendantsCount

The number of descendands below this node (node itself excluded).

Declaration
public int DescendantsCount { get; }
Property Value
Type Description
System.Int32
Remarks

| Improve this Doc View Source

WrappedNode

Declaration
public TNode WrappedNode { get; set; }
Property Value
Type Description
TNode

Implements

System.IEquatable<T>

Extension Methods