< Summary

Information
Class: MoreStructures.SuffixTrees.SuffixTreeNode
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/SuffixTrees/SuffixTreeNode.cs
Line coverage
100%
Covered lines: 129
Uncovered lines: 0
Coverable lines: 129
Total lines: 164
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
.ctor(...)100%8100%
get_Children()100%1100%
get_Start()100%1100%
get_Item(...)100%1100%
ToString()100%1100%
HaveEquivalentChildren(...)100%6100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/SuffixTrees/SuffixTreeNode.cs

#LineLine coverage
 1using MoreStructures.RecImmTrees;
 2using MoreStructures.RecImmTrees.Conversions;
 3using MoreStructures.SuffixStructures;
 4using MoreStructures.Utilities;
 5
 6namespace MoreStructures.SuffixTrees;
 7
 8/// <summary>
 9/// An immutable node of an immutable Suffix Tree, recursively pointing to its children nodes via
 10/// <see cref="SuffixTreeEdge"/> instances, associated with selector strings.
 11/// </summary>
 12/// <param name="Children">The collection of children for the node, indexed by string edges.</param>
 13/// <param name="Start">
 14/// <inheritdoc cref="ISuffixStructureNode{TEdge, TNode}.Start" path="/summary"/>
 15/// </param>
 16/// <remarks>
 17///     <para id="advantages">
 18///     ADVANTAGES AND DISADVANTAGES
 19///     <br/>
 20///     Suffix Trees are more space-efficient than Suffix Tries due to the reduced number of
 21///     <see cref="SuffixTreeEdge"/> and their <see cref="SuffixTreeNode"/>, compare to the corresponding
 22///     <see cref="SuffixTries.SuffixTrieEdge"/> and their <see cref="SuffixTries.SuffixTrieNode"/>, due to entire
 23///     paths of single chains of chars in Suffix Tries being coalesced into a single selector string, which is stored
 24///     on the edge with path label compression, i.e. using two fixed sized numbers (<see cref="SuffixTreeEdge.Start"/>
 25///     and <see cref="SuffixTreeEdge.Length"/>) instead of a variable-length string of characters.
 26///     <br/>
 27///     Furthermore, suffix trees, unlike suffix tries, can be constructed in linear time, for example via the
 28///     <see cref="Builders.UkkonenSuffixTreeBuilder"/>.
 29///     </para>
 30///     <para id="immutability">
 31///     IMMUTABILITY
 32///     <br/>
 33///     Immutability is guaranteed by using <see cref="ValueReadOnlyCollection{T}"/>.
 34///     </para>
 35/// </remarks>
 2161336public abstract record SuffixTreeNode(IDictionary<SuffixTreeEdge, SuffixTreeNode> Children, int? Start)
 2161337    : ISuffixStructureNode<SuffixTreeEdge, SuffixTreeNode>
 2161338{
 2161339    /// <summary>
 2161340    /// Builds an intermediate node, i.e. a node with children and their corresponding incoming edges.
 2161341    /// </summary>
 2161342    public record Intermediate(IDictionary<SuffixTreeEdge, SuffixTreeNode> Children)
 1055843        : SuffixTreeNode(Children, null)
 2161344    {
 2161345        /// <inheritdoc/>
 2161346        public override bool IsEquivalentTo(SuffixTreeNode other, params TextWithTerminator[] texts) =>
 16547            other is Intermediate(var otherChildren) &&
 16548            SuffixTreeNode.HaveEquivalentChildren(texts.GenerateFullText().fullText, Children, otherChildren);
 2161349    }
 2161350
 2161351    /// <summary>
 2161352    /// Builds a leaf, i.e. a node with no children and the start index of the suffix in the text.
 2161353    /// </summary>
 1187554    public record Leaf(int LeafStart)
 1105055        : SuffixTreeNode(new Dictionary<SuffixTreeEdge, SuffixTreeNode> { }, LeafStart)
 2161356    {
 2161357        /// <inheritdoc/>
 2161358        public override bool IsEquivalentTo(SuffixTreeNode other, params TextWithTerminator[] texts) =>
 38659            other is Leaf(var otherLeafStart) &&
 38660            LeafStart == otherLeafStart;
 2161361    }
 2161362
 2161363    /// <inheritdoc/>
 4365964    public IDictionary<SuffixTreeEdge, SuffixTreeNode> Children { get; }
 2161665        = (Children.Any() == (Start == null)) && Start.GetValueOrDefault(0) >= 0
 2161666        ? Children.ToValueReadOnlyDictionary()
 2161667        : throw new ArgumentException($"Leafs needs to specificy a non-negative {nameof(Start)}.", nameof(Children));
 2161368
 2161369    /// <inheritdoc/>
 2253970    public int? Start { get; } = Start;
 2161371
 2161372    /// <summary>
 2161373    /// Indexes into the children of this node, by edge.
 2161374    /// </summary>
 775    public SuffixTreeNode this[SuffixTreeEdge edge] => Children[edge];
 2161376
 177    private static readonly IStringifier<SuffixTreeEdge, SuffixTreeNode> Stringifier =
 178        new FullyIterativeStringifier<SuffixTreeEdge, SuffixTreeNode>(
 14179            r => r.IsLeaf() ? $"R from {r.Start}" : "R",
 94280            (e, n) => $"{e} -> {(n.IsLeaf() ? $"L from {n.Start}" : "I")}")
 181            {
 182                StopIndentingLevel = 10,
 183            };
 2161384
 2161385    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 2161386    /// <summary>
 2161387    ///     <inheritdoc/>
 2161388    ///     <br/>
 2161389    ///     Uses a <see cref="IStringifier{TEdge, TNode}"/> to generate the string which show the node and its
 2161390    ///     underlying structure.
 2161391    /// </summary>
 2161392    /// <remarks>
 2161393    /// Sealed to prevent compiler from superceding <see cref="ToString()"/> in derived record.
 2161394    /// </remarks>
 14195    public override sealed string ToString() => Stringifier.Stringify(this);
 2161396
 2161397    /// <summary>
 2161398    /// Determines whether this <see cref="SuffixTreeNode"/> structure is equivalent to the provided
 2161399    /// <paramref name="other"/> structure, w.r.t. the provided <paramref name="texts"/>.
 21613100    /// </summary>
 21613101    /// <param name="other">The other tree, to compare this tree against.</param>
 21613102    /// <param name="texts">The text, based on which to evaluate the tree equivalence.</param>
 21613103    /// <returns>True if the two trees are equivalent for the provided text, false otherwise.</returns>
 21613104    /// <remarks>
 21613105    ///     <para id="definition">
 21613106    ///     DEFINITION
 21613107    ///     <br/>
 21613108    ///     The definition of <see cref="SuffixTreeNode"/> structures equivalence depends on (a list of)
 21613109    ///     <see cref="TextWithTerminator"/>: two trees can be equivalent for some texts, and not equivalent
 21613110    ///     for others. This is because of the <b>Edge Compression</b> technique used by
 21613111    ///     <see cref="SuffixTreeEdge"/>, to store edges in O(1) space, instead of O(n).
 21613112    ///     <br/>
 21613113    ///     Moreover, equivalence is based on the equivalence of edges and of the specific type of node.
 21613114    ///     <br/>
 21613115    ///     - Two <see cref="SuffixTreeEdge"/> E1 and E2 are equivalent w.r.t. a <see cref="TextWithTerminator"/> T,
 21613116    ///       if the string identified by each edge is the same: <c>T[E1] == T[E2]</c>.
 21613117    ///       <br/>
 21613118    ///     - Two <see cref="Leaf"/> L1 and L2 are equivalent if their <see cref="Leaf.LeafStart"/> is the same:
 21613119    ///       <c>L1.LeafStart == L2.LeafStart</c>.
 21613120    ///       <br/>
 21613121    ///     - Two <see cref="Intermediate"/> I1 and I2 are equivalent if there is a 1-to-1 correspondence between
 21613122    ///       children edges and child nodes pointed by such edges are equivalent:
 21613123    ///       <c>for each edge e1 of I1.Children there exists exactly one equivalent edge e2 of I2.Children and
 21613124    ///       I1.Children[e1] is equivalent to I2.Children[e2] w.r.t. T</c>.
 21613125    ///     </para>
 21613126    ///     <para id="complexity">
 21613127    ///     COMPLEXITY
 21613128    ///     <br/>
 21613129    ///     - Checking for edges equivalence is a O(n) operation, where n is the number of nodes in the tree, since it
 21613130    ///       requires decompressing the labels of each of the edges being compare and compare for equality the two
 21613131    ///       resulting O(n) strings.
 21613132    ///       <br/>
 21613133    ///     - Checking for leaves equivalence is a O(1) operation, since it only requires comparing
 21613134    ///       <see cref="Leaf.LeafStart"/>, which has constant size.
 21613135    ///       <br/>
 21613136    ///     - Checking for intermediate nodes equivalence is a O(n) operation, amortized cost over the total number of
 21613137    ///       edges in the tree, since there are O(n) edges in total in the tree, an edge is visited multiple times
 21613138    ///       but always in the context of a single node, and the node equivalence check requires looking for the
 21613139    ///       equivalent edge.
 21613140    ///       <br/>
 21613141    ///     - In conclusion Time Complexity is O(n^2) and Space Complexity is O(n).
 21613142    ///     </para>
 21613143    /// </remarks>
 21613144    public abstract bool IsEquivalentTo(SuffixTreeNode other, params TextWithTerminator[] texts);
 21613145
 21613146    private static bool HaveEquivalentChildren(
 21613147        TextWithTerminator fullText,
 21613148        IDictionary<SuffixTreeEdge, SuffixTreeNode> thisChildren,
 21613149        IDictionary<SuffixTreeEdge, SuffixTreeNode> otherChildren)
 165150    {
 1434151        foreach (var (childEdge, childNode) in thisChildren)
 472152        {
 472153            var correspondingEdgeAndNode = otherChildren
 1686154                .Where(edgeAndNode => fullText[childEdge] == fullText[edgeAndNode.Key])
 472155                .ToList();
 472156            if (correspondingEdgeAndNode.Count != 1)
 3157                return false;
 469158            if (!childNode.IsEquivalentTo(correspondingEdgeAndNode[0].Value, fullText))
 2159                return false;
 467160        }
 21613161
 160162        return true;
 165163    }
 21613164}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

.ctor(System.Collections.Generic.IDictionary`2<MoreStructures.SuffixTrees.SuffixTreeEdge,MoreStructures.SuffixTrees.SuffixTreeNode>,System.Nullable`1<System.Int32>)
get_Children()
get_Start()
get_Item(MoreStructures.SuffixTrees.SuffixTreeEdge)
ToString()
HaveEquivalentChildren(MoreStructures.TextWithTerminator,System.Collections.Generic.IDictionary`2<MoreStructures.SuffixTrees.SuffixTreeEdge,MoreStructures.SuffixTrees.SuffixTreeNode>,System.Collections.Generic.IDictionary`2<MoreStructures.SuffixTrees.SuffixTreeEdge,MoreStructures.SuffixTrees.SuffixTreeNode>)