| | | 1 | | using MoreStructures.SuffixTrees; |
| | | 2 | | using MoreStructures.SuffixTrees.Builders; |
| | | 3 | | |
| | | 4 | | namespace MoreStructures.MutableTrees; |
| | | 5 | | |
| | | 6 | | /// <summary> |
| | | 7 | | /// An <b>internal</b> representation of a mutable, recursive, dictionary indexed, tree structure, used by algorithms |
| | | 8 | | /// which build a tree iteratively, by performing mutations. |
| | | 9 | | /// </summary> |
| | | 10 | | /// <remarks> |
| | | 11 | | /// - Allows mutation of each of its field and properties. |
| | | 12 | | /// <br/> |
| | | 13 | | /// - Its sub-collections, such as <see cref="Node.Children"/>, which only makes sense for intermediate nodes, are |
| | | 14 | | /// mutable. Same applies to <see cref="Node.LeafStart"/>, which only makes sense for leaves. |
| | | 15 | | /// <br/> |
| | | 16 | | /// - The <see cref="Node.Children"/> collection is initialized to an empty collection. Then, children can be added and |
| | | 17 | | /// removed at any time. That means that each node is created a leaf, but can become an intermediate node, and can be |
| | | 18 | | /// back to be leaf, by the algorithm operating on the collection of its children. |
| | | 19 | | /// <br/> |
| | | 20 | | /// - Used by <see cref="SuffixAndLcpArraysBasedSuffixTreeBuilder"/> to build its working copy of the tree, before |
| | | 21 | | /// producing the final <see cref="SuffixTreeNode"/> structure, which is immutable. |
| | | 22 | | /// <br/> |
| | | 23 | | /// - Not used by <see cref="UkkonenSuffixTreeBuilder"/>, as the Ukkonen algorithm for Suffix Tree construction |
| | | 24 | | /// requires edges with a global moving end, in order to execute Rule 1 Extension at the beginning of every phase on |
| | | 25 | | /// all leaves at the same time in O(1). |
| | | 26 | | /// </remarks> |
| | | 27 | | internal static class MutableTree |
| | | 28 | | { |
| | | 29 | | /// <summary> |
| | | 30 | | /// The edge of a <see cref="MutableTree"/>, indentified by the <see cref="Start"/> index in the text and the |
| | | 31 | | /// <see cref="Length"/> of the label associated with the edge (a technique to efficiently store labels in a |
| | | 32 | | /// Suffix Tree also known as <b>Edge Compression</b>). |
| | | 33 | | /// </summary> |
| | | 34 | | public sealed class Edge |
| | | 35 | | { |
| | | 36 | | /// <summary> |
| | | 37 | | /// The index in the text of the char by which the label of this edge starts. |
| | | 38 | | /// </summary> |
| | | 39 | | /// <remarks> |
| | | 40 | | /// Should be non-negative and smaller than text length (where length includes the terminator, if any). |
| | | 41 | | /// </remarks> |
| | | 42 | | public int Start; |
| | | 43 | | |
| | | 44 | | /// <summary> |
| | | 45 | | /// The length of the label of this edge. |
| | | 46 | | /// </summary> |
| | | 47 | | /// <remarks> |
| | | 48 | | /// Should be positive (empty edges not allowed), with <see cref="Start"/> + <see cref="Length"/> <= text |
| | | 49 | | /// length. |
| | | 50 | | /// </remarks> |
| | | 51 | | public int Length; |
| | | 52 | | |
| | 766 | 53 | | private Edge(int start, int length) |
| | 766 | 54 | | { |
| | 766 | 55 | | Start = start; |
| | 766 | 56 | | Length = length; |
| | 766 | 57 | | } |
| | | 58 | | |
| | | 59 | | /// <summary> |
| | | 60 | | /// Builds a <see cref="Edge"/> with the provided <paramref name="start"/> and <paramref name="length"/>. |
| | | 61 | | /// </summary> |
| | | 62 | | /// <param name="start"></param> |
| | | 63 | | /// <param name="length"></param> |
| | | 64 | | /// <returns></returns> |
| | | 65 | | public static Edge Build(int start, int length) => |
| | 766 | 66 | | new(start, length); |
| | | 67 | | } |
| | | 68 | | |
| | | 69 | | /// <summary> |
| | | 70 | | /// The node of a <see cref="MutableTree"/>, with a back-reference to its <see cref="ParentNode"/>, a |
| | | 71 | | /// back-reference to its <see cref="IncomingEdge"/>, a collection of <see cref="Children"/> (non-empty for |
| | | 72 | | /// intermediate nodes only) and a <see cref="LeafStart"/> index (non-null for leaves only). |
| | | 73 | | /// </summary> |
| | | 74 | | public sealed class Node |
| | | 75 | | { |
| | | 76 | | /// <summary> |
| | | 77 | | /// A back-reference to the <see cref="Node"/> above this one in the tree. |
| | | 78 | | /// </summary> |
| | | 79 | | /// <remarks> |
| | | 80 | | /// It's the node itself for the root of the tree, built via <see cref="BuildRoot"/>. |
| | | 81 | | /// </remarks> |
| | | 82 | | public Node ParentNode; |
| | | 83 | | |
| | | 84 | | /// <summary> |
| | | 85 | | /// A back-reference to the <see cref="Edge"/> pointing to this node from the <see cref="ParentNode"/>. |
| | | 86 | | /// </summary> |
| | | 87 | | /// <remarks> |
| | | 88 | | /// It's a dummy edge (0, 0) for the root of the tree, built via <see cref="BuildRoot"/>. |
| | | 89 | | /// </remarks> |
| | | 90 | | public Edge IncomingEdge; |
| | | 91 | | |
| | | 92 | | /// <summary> |
| | | 93 | | /// A mutable collection of <see cref="Node"/> instances, indexed by <see cref="Edge"/> instances. |
| | | 94 | | /// </summary> |
| | | 95 | | public Dictionary<Edge, Node> Children; |
| | | 96 | | |
| | | 97 | | /// <summary> |
| | | 98 | | /// The leaf start index in the text, of this node. Only applicable to leaves. |
| | | 99 | | /// </summary> |
| | | 100 | | public int? LeafStart; |
| | | 101 | | |
| | 620 | 102 | | private Node(Node? parent, Edge incomingEdge, int? leafStart) |
| | 620 | 103 | | { |
| | 620 | 104 | | ParentNode = parent ?? this; |
| | 620 | 105 | | IncomingEdge = incomingEdge; |
| | 620 | 106 | | Children = new Dictionary<Edge, Node>(); |
| | 620 | 107 | | LeafStart = leafStart; |
| | 620 | 108 | | } |
| | | 109 | | |
| | | 110 | | /// <summary> |
| | | 111 | | /// Builds a <see cref="Node"/> instance, representing the root node of a tree, with <see cref="ParentNode"/> |
| | | 112 | | /// equal to the node itself (circular reference), a dummy edge (0, 0) as <see cref="IncomingEdge"/> and null |
| | | 113 | | /// <see cref="LeafStart"/>. |
| | | 114 | | /// </summary> |
| | | 115 | | /// <returns>A <see cref="Node"/> instance.</returns> |
| | | 116 | | public static Node BuildRoot() => |
| | 59 | 117 | | new(null, Edge.Build(0, 0), null); |
| | | 118 | | |
| | | 119 | | /// <summary> |
| | | 120 | | /// Builds a <see cref="Node"/> instance, representing a non-root node of a tree (intermediate or leaf), with |
| | | 121 | | /// the provided <paramref name="parentNode"/>, <paramref name="incomingEdge"/> and |
| | | 122 | | /// <paramref name="leafStart"/> (only applicable for leaves). |
| | | 123 | | /// </summary> |
| | | 124 | | /// <param name="parentNode"> |
| | | 125 | | /// <inheritdoc cref="ParentNode" path="/summary"/> |
| | | 126 | | /// </param> |
| | | 127 | | /// <param name="incomingEdge"> |
| | | 128 | | /// <inheritdoc cref="IncomingEdge" path="/summary"/> |
| | | 129 | | /// </param> |
| | | 130 | | /// <param name="leafStart"> |
| | | 131 | | /// <inheritdoc cref="LeafStart" path="/summary"/> |
| | | 132 | | /// </param> |
| | | 133 | | /// <returns>A <see cref="Node"/> instance.</returns> |
| | | 134 | | public static Node Build(Node parentNode, Edge incomingEdge, int? leafStart) => |
| | 561 | 135 | | new(parentNode, incomingEdge, leafStart); |
| | | 136 | | } |
| | | 137 | | } |