| | | 1 | | using MoreStructures.RecImmTrees; |
| | | 2 | | using MoreStructures.RecImmTrees.Conversions; |
| | | 3 | | using MoreStructures.SuffixStructures; |
| | | 4 | | using MoreStructures.Utilities; |
| | | 5 | | |
| | | 6 | | namespace MoreStructures.SuffixTries; |
| | | 7 | | |
| | | 8 | | /// <summary> |
| | | 9 | | /// An immutable node of an immutable Suffix Trie, recursively pointing to its children nodes via |
| | | 10 | | /// <see cref="SuffixTrieEdge"/> instances, associated with selector characters. |
| | | 11 | | /// </summary> |
| | | 12 | | /// <param name="Children">The collection of children for the node, indexed by single char 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 | | /// Compare to suffix trees, suffix tries, although less performant and optimized on many operations, are simpler |
| | | 21 | | /// to build, navigate and understand. |
| | | 22 | | /// </para> |
| | | 23 | | /// <para id="immutability"> |
| | | 24 | | /// IMMUTABILITY |
| | | 25 | | /// <br/> |
| | | 26 | | /// Immutability is guaranteed by using <see cref="ValueReadOnlyCollection{T}"/>. |
| | | 27 | | /// </para> |
| | | 28 | | /// </remarks> |
| | 22289 | 29 | | public abstract record SuffixTrieNode(IDictionary<SuffixTrieEdge, SuffixTrieNode> Children, int? Start) |
| | 22289 | 30 | | : ISuffixStructureNode<SuffixTrieEdge, SuffixTrieNode> |
| | 22289 | 31 | | { |
| | 22289 | 32 | | /// <summary> |
| | 22289 | 33 | | /// Builds an intermediate node, i.e. a node with children and their corresponding incoming edges. |
| | 22289 | 34 | | /// </summary> |
| | 22289 | 35 | | public record Intermediate(IDictionary<SuffixTrieEdge, SuffixTrieNode> Children) |
| | 11709 | 36 | | : SuffixTrieNode(Children, null); |
| | 22289 | 37 | | |
| | 22289 | 38 | | /// <summary> |
| | 22289 | 39 | | /// Builds a leaf, i.e. a node with no children and the start index of the suffix in the text. |
| | 22289 | 40 | | /// </summary> |
| | 20630 | 41 | | public record Leaf(int LeafStart) |
| | 10575 | 42 | | : SuffixTrieNode(new Dictionary<SuffixTrieEdge, SuffixTrieNode> { }, LeafStart); |
| | 22289 | 43 | | |
| | 22289 | 44 | | /// <inheritdoc/> |
| | 46186 | 45 | | public IDictionary<SuffixTrieEdge, SuffixTrieNode> Children { get; } |
| | 22292 | 46 | | = (Children.Any() == (Start == null)) && Start.GetValueOrDefault(0) >= 0 |
| | 22292 | 47 | | ? Children.ToValueReadOnlyDictionary() |
| | 22292 | 48 | | : throw new ArgumentException($"Leafs needs to specificy a non-negative {nameof(Start)}.", nameof(Children)); |
| | 22289 | 49 | | |
| | 22289 | 50 | | /// <inheritdoc/> |
| | 22435 | 51 | | public int? Start { get; } = Start; |
| | 22289 | 52 | | |
| | 22289 | 53 | | /// <summary> |
| | 22289 | 54 | | /// Indexes into the children of this node, by edge, which is a single char selector. |
| | 22289 | 55 | | /// </summary> |
| | 79 | 56 | | public SuffixTrieNode this[SuffixTrieEdge edge] => Children[edge]; |
| | 22289 | 57 | | |
| | 1 | 58 | | private static readonly IStringifier<SuffixTrieEdge, SuffixTrieNode> Stringifier = |
| | 1 | 59 | | new FullyIterativeStringifier<SuffixTrieEdge, SuffixTrieNode>( |
| | 9 | 60 | | r => r.IsLeaf() ? $"R from {r.Start}" : "R", |
| | 20 | 61 | | (e, n) => $"{e} -> {(n.IsLeaf() ? $"L from {n.Start}" : "I")}") |
| | 1 | 62 | | { |
| | 1 | 63 | | StopIndentingLevel = 10, |
| | 1 | 64 | | }; |
| | 22289 | 65 | | |
| | 22289 | 66 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | 22289 | 67 | | /// <summary> |
| | 22289 | 68 | | /// <inheritdoc/> |
| | 22289 | 69 | | /// <br/> |
| | 22289 | 70 | | /// Uses a <see cref="IStringifier{TEdge, TNode}"/> to generate the string which show the node and its |
| | 22289 | 71 | | /// underlying structure. |
| | 22289 | 72 | | /// </summary> |
| | 22289 | 73 | | /// <remarks> |
| | 22289 | 74 | | /// Sealed to prevent compiler from superceding <see cref="ToString()"/> in derived record. |
| | 22289 | 75 | | /// </remarks> |
| | 9 | 76 | | public sealed override string ToString() => Stringifier.Stringify(this); |
| | 22289 | 77 | | } |