| | | 1 | | namespace MoreStructures.SuffixTrees.Builders.Ukkonen; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// A node (root, internal or leaf) of the tree structure built by <see cref="UkkonenSuffixTreeBuilder"/>. |
| | | 5 | | /// </summary> |
| | | 6 | | /// <param name="Id"> |
| | | 7 | | /// A unique identifier of the node in the tree. Useful for debugging and tracing. |
| | | 8 | | /// </param> |
| | | 9 | | /// <param name="LeafStart"> |
| | | 10 | | /// The index of the character, the path from the root leading to this leaf starts with. Non-null for leaves only. |
| | | 11 | | /// </param> |
| | | 12 | | /// <param name="SuffixLink"> |
| | | 13 | | /// The Suffix Link associated to this node. Defined for internal nodes only. |
| | | 14 | | /// </param> |
| | | 15 | | /// <param name="IncomingEdge"> |
| | | 16 | | /// The <see cref="MutableEdge"/> pointing to this <see cref="MutableNode"/>. Null for the root. |
| | | 17 | | /// Used in Rule 2 Extension, when the <see cref="IterationState.ActiveNode"/> has no <see cref="Children"/> (i.e. |
| | | 18 | | /// it's a leaf) and no intermediate node has to be created. |
| | | 19 | | /// <br/> |
| | | 20 | | /// Ín such scenario, the leaf becomes parent of a new leaf, and stop having the <see cref="MutableEdge.End"/> of |
| | | 21 | | /// its incoming <see cref="MutableEdge"/> pointing to the <see cref="IterationState.GlobalEnd"/>. |
| | | 22 | | /// </param> |
| | | 23 | | /// <remarks> |
| | | 24 | | /// Mutable and having a <see cref="SuffixLink"/> to have Rule 2 Extension applied in constant time. |
| | | 25 | | /// </remarks> |
| | 7805 | 26 | | internal record MutableNode(int Id, int? LeafStart, MutableNode? SuffixLink, MutableEdge? IncomingEdge = null) |
| | 534 | 27 | | { |
| | 534 | 28 | | /// <summary> |
| | 534 | 29 | | /// The children of this node. Empty for leaves, non-empty for root and internal nodes. |
| | 534 | 30 | | /// </summary> |
| | 7038 | 31 | | public Dictionary<MutableEdge, MutableNode> Children { get; } = new(); |
| | 534 | 32 | | |
| | 534 | 33 | | /// <summary> |
| | 534 | 34 | | /// <inheritdoc cref="MutableNode" path="/param[@name='SuffixLink']"/> |
| | 534 | 35 | | /// </summary> |
| | 5463 | 36 | | public MutableNode? SuffixLink { get; set; } = SuffixLink; |
| | 534 | 37 | | |
| | 534 | 38 | | /// <inheritdoc/> |
| | 5037 | 39 | | public override string ToString() => $"{Id}"; |
| | 534 | 40 | | |
| | 534 | 41 | | /// <summary> |
| | 534 | 42 | | /// Settings for the <see cref="Dump(DumpParams)"/> method. |
| | 534 | 43 | | /// </summary> |
| | 534 | 44 | | /// <param name="Text">The text, on which the Ukkonen algorithm is being run.</param> |
| | 534 | 45 | | /// <param name="GlobalEnd">The global end instantiated by the <see cref="IterationState"/>.</param> |
| | 534 | 46 | | /// <param name="EdgeNodeSeparator">The string separator between pointing edge and pointed node.</param> |
| | 534 | 47 | | /// <param name="SuffixLinkSeparator">The string separator between node indicator and its suffix link.</param> |
| | 534 | 48 | | /// <param name="IndentationChar">The char to be used for indentation.</param> |
| | 496 | 49 | | public record DumpParams( |
| | 3703 | 50 | | TextWithTerminator Text, |
| | 3703 | 51 | | MovingEnd GlobalEnd, |
| | 3703 | 52 | | string EdgeNodeSeparator = "->", |
| | 1333 | 53 | | string SuffixLinkSeparator = "~>", |
| | 4199 | 54 | | char IndentationChar = '\t'); |
| | 534 | 55 | | |
| | 534 | 56 | | /// <summary> |
| | 534 | 57 | | /// Dump the state of this node (with its entire <see cref="Children"/> structure. |
| | 534 | 58 | | /// </summary> |
| | 534 | 59 | | /// <param name="dumpParams">The parameters to be used to generate the output.</param> |
| | 534 | 60 | | /// <returns>A string showing the state of the structure under this node.</returns> |
| | 534 | 61 | | public string Dump(DumpParams dumpParams) => |
| | 496 | 62 | | DumpR(dumpParams, null, 0); |
| | 534 | 63 | | |
| | 534 | 64 | | private string DumpR(DumpParams dumpParams, string? prefix, int level) => |
| | 3703 | 65 | | string.Join( |
| | 3703 | 66 | | Environment.NewLine, |
| | 3703 | 67 | | Enumerable |
| | 3703 | 68 | | .Repeat( |
| | 3703 | 69 | | (prefix == null ? "" : $"{prefix} {dumpParams.EdgeNodeSeparator} ") + |
| | 3703 | 70 | | ToString() + |
| | 3703 | 71 | | (SuffixLink == null ? "" : $" {dumpParams.SuffixLinkSeparator} {SuffixLink}"), |
| | 3703 | 72 | | 1) |
| | 3703 | 73 | | .Concat( |
| | 3703 | 74 | | from c in Children |
| | 3207 | 75 | | let indentation = new string(dumpParams.IndentationChar, level + 1) |
| | 3207 | 76 | | let edgeText = $"'{dumpParams.Text[c.Key.Start..(c.Key.End.Value + 1)]}'" |
| | 3207 | 77 | | let edgeCompressed = c.Key.ToString(dumpParams.GlobalEnd) |
| | 6910 | 78 | | select c.Value.DumpR(dumpParams, $"{indentation}{edgeText}{edgeCompressed}", level + 1))); |
| | 534 | 79 | | } |