| | | 1 | | using MoreStructures.SuffixTrees; |
| | | 2 | | using MoreStructures.SuffixTries; |
| | | 3 | | |
| | | 4 | | namespace MoreStructures.SuffixStructures.Conversions; |
| | | 5 | | |
| | | 6 | | using static ConverterHelpers; |
| | | 7 | | |
| | | 8 | | /// <summary> |
| | | 9 | | /// <inheritdoc cref="IConverter"/> |
| | | 10 | | /// </summary> |
| | | 11 | | /// <remarks> |
| | | 12 | | /// <para id="advantages"> |
| | | 13 | | /// ADVANTAGES AND DISADVANTAGES |
| | | 14 | | /// <br/> |
| | | 15 | | /// Conversion is done iteratively both for branching and no-branching paths (i.e. on nodes having a single child) |
| | | 16 | | /// of the input <see cref="SuffixTrieNode"/>, with occasional mutation of internal state of the conversion and the |
| | | 17 | | /// use of a stack to store nodes to process. |
| | | 18 | | /// <br/> |
| | | 19 | | /// Not limited by call stack depth. |
| | | 20 | | /// <br/> |
| | | 21 | | /// Convenient with deep trees (i.e. trees having a height > ~1K nodes). |
| | | 22 | | /// </para> |
| | | 23 | | /// </remarks> |
| | | 24 | | public class FullyIterativeConverter : IConverter |
| | | 25 | | { |
| | | 26 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 27 | | /// <summary> |
| | | 28 | | /// <inheritdoc/> |
| | | 29 | | /// </summary> |
| | | 30 | | /// <remarks> |
| | | 31 | | /// <inheritdoc cref="FullyIterativeConverter" path="/remarks"/> |
| | | 32 | | /// <inheritdoc cref="IConverter.TrieToTree(SuffixTrieNode)" path="/remarks"/> |
| | | 33 | | /// </remarks> |
| | | 34 | | public SuffixTreeNode TrieToTree(SuffixTrieNode trieNode) |
| | 14 | 35 | | { |
| | 14 | 36 | | var stack = new Stack<StackFrameTrieToTree>(); |
| | 14 | 37 | | var dictionaryToRoot = new Dictionary<SuffixTreeEdge, SuffixTreeNode>() { }; |
| | 14 | 38 | | var edgeToRoot = new SuffixTreeEdge(0, 1); |
| | 14 | 39 | | stack.Push(new StackFrameTrieToTree(null, dictionaryToRoot, edgeToRoot, trieNode)); |
| | | 40 | | |
| | 30064 | 41 | | while (stack.Count > 0) |
| | 30052 | 42 | | ProcessTrieToTreeStack(stack); |
| | | 43 | | |
| | 12 | 44 | | return dictionaryToRoot[edgeToRoot]; |
| | 12 | 45 | | } |
| | | 46 | | |
| | | 47 | | private record struct StackFrameTrieToTree( |
| | | 48 | | // Non-null on second pass only, when children have already been processed (done only for intermediate nodes) |
| | 60106 | 49 | | IDictionary<SuffixTreeEdge, SuffixTreeNode>? TreeNodeChildrenMaybe, |
| | 60106 | 50 | | IDictionary<SuffixTreeEdge, SuffixTreeNode> TreeNodeParentChildren, |
| | 60106 | 51 | | SuffixTreeEdge TreeEdge, |
| | 60106 | 52 | | SuffixTrieNode TrieNode); |
| | | 53 | | |
| | | 54 | | private static void ProcessTrieToTreeStack(Stack<StackFrameTrieToTree> stack) |
| | 30052 | 55 | | { |
| | 30052 | 56 | | var (treeNodeChildrenMaybe, treeNodeParentChildren, treeEdge, trieNode) = stack.Pop(); |
| | | 57 | | |
| | 30052 | 58 | | if (trieNode is SuffixTrieNode.Leaf(var leafStart)) |
| | 10019 | 59 | | { |
| | 10019 | 60 | | treeNodeParentChildren[treeEdge] = new SuffixTreeNode.Leaf(leafStart); |
| | 10019 | 61 | | return; |
| | | 62 | | } |
| | | 63 | | |
| | 20033 | 64 | | if (trieNode is SuffixTrieNode.Intermediate(var trieNodeChildren)) |
| | 20032 | 65 | | { |
| | 20032 | 66 | | if (treeNodeChildrenMaybe is IDictionary<SuffixTreeEdge, SuffixTreeNode> treeNodeChildren) |
| | 10015 | 67 | | { |
| | 10015 | 68 | | treeNodeParentChildren[treeEdge] = new SuffixTreeNode.Intermediate(treeNodeChildren); |
| | 10015 | 69 | | } |
| | | 70 | | else |
| | 10017 | 71 | | { |
| | 10017 | 72 | | treeNodeChildren = new Dictionary<SuffixTreeEdge, SuffixTreeNode> { }; |
| | | 73 | | |
| | 10017 | 74 | | stack.Push(new StackFrameTrieToTree(treeNodeChildren, treeNodeParentChildren, treeEdge, trieNode)); |
| | | 75 | | |
| | 70098 | 76 | | foreach (var (trieChildEdge, trieChildNode) in trieNodeChildren) |
| | 20024 | 77 | | { |
| | 20024 | 78 | | var (coalescedChildEdge, coalescedChildNode) = IterativeCoalesce(trieChildEdge, trieChildNode); |
| | 20023 | 79 | | stack.Push(new StackFrameTrieToTree(null, treeNodeChildren, coalescedChildEdge, coalescedChildNode)) |
| | 20023 | 80 | | } |
| | 10016 | 81 | | } |
| | | 82 | | |
| | 20031 | 83 | | return; |
| | | 84 | | } |
| | | 85 | | |
| | 1 | 86 | | throw new NotSupportedException($"{trieNode} of type {trieNode.GetType().Name} not supported"); |
| | 30050 | 87 | | } |
| | | 88 | | |
| | | 89 | | private record struct StackFrameTreeToTrie( |
| | | 90 | | // Non-null on second pass only, when children have already been processed (done only for intermediate nodes) |
| | 108 | 91 | | IDictionary<SuffixTrieEdge, SuffixTrieNode>? TrieNodeChildrenMaybe, |
| | 108 | 92 | | SuffixTreeEdge TreeEdge, |
| | 108 | 93 | | SuffixTreeNode TreeNode, |
| | 108 | 94 | | IDictionary<SuffixTrieEdge, SuffixTrieNode> ParentChildren); |
| | | 95 | | |
| | | 96 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 97 | | /// <summary> |
| | | 98 | | /// <inheritdoc/> |
| | | 99 | | /// </summary> |
| | | 100 | | /// <remarks> |
| | | 101 | | /// <inheritdoc cref="FullyIterativeConverter" path="/remarks"/> |
| | | 102 | | /// <inheritdoc cref="IConverter.TreeToTrie(SuffixTreeNode)" path="/remarks"/> |
| | | 103 | | /// </remarks> |
| | | 104 | | public SuffixTrieNode TreeToTrie(SuffixTreeNode treeNode) |
| | 13 | 105 | | { |
| | 13 | 106 | | var stack = new Stack<StackFrameTreeToTrie>(); |
| | 13 | 107 | | var edgeToRoot = new SuffixTrieEdge(0); |
| | 13 | 108 | | var parentChildren = new Dictionary<SuffixTrieEdge, SuffixTrieNode> { }; |
| | 13 | 109 | | stack.Push(new(null, edgeToRoot, treeNode, parentChildren)); |
| | 64 | 110 | | while (stack.Count > 0) |
| | 53 | 111 | | ProcessTreeToTrieStack(stack); |
| | | 112 | | |
| | 11 | 113 | | return parentChildren[edgeToRoot]; |
| | 11 | 114 | | } |
| | | 115 | | |
| | | 116 | | private static void ProcessTreeToTrieStack(Stack<StackFrameTreeToTrie> stack) |
| | 53 | 117 | | { |
| | 53 | 118 | | var (trieNodeChildrenMaybe, treeEdge, treeNode, parentChildren) = stack.Pop(); |
| | | 119 | | |
| | 53 | 120 | | if (treeNode is SuffixTreeNode.Leaf(var leafStart)) |
| | 19 | 121 | | { |
| | 19 | 122 | | var (expandedTrieEdge, expandedTrieNode) = IterativeExpand(treeEdge, new SuffixTrieNode.Leaf(leafStart)); |
| | 19 | 123 | | parentChildren[expandedTrieEdge] = expandedTrieNode; |
| | 19 | 124 | | return; |
| | | 125 | | } |
| | | 126 | | |
| | 34 | 127 | | if (treeNode is SuffixTreeNode.Intermediate(var treeNodeChildren)) |
| | 32 | 128 | | { |
| | 32 | 129 | | if (trieNodeChildrenMaybe is IDictionary<SuffixTrieEdge, SuffixTrieNode> trieNodeChildren) |
| | 15 | 130 | | { |
| | 15 | 131 | | var (expandedTrieEdge, expandedTrieNode) = IterativeExpand( |
| | 15 | 132 | | treeEdge, new SuffixTrieNode.Intermediate(trieNodeChildren)); |
| | 15 | 133 | | parentChildren[expandedTrieEdge] = expandedTrieNode; |
| | 15 | 134 | | } |
| | | 135 | | else |
| | 17 | 136 | | { |
| | 17 | 137 | | trieNodeChildren = new Dictionary<SuffixTrieEdge, SuffixTrieNode> { }; |
| | 17 | 138 | | stack.Push(new(trieNodeChildren, treeEdge, treeNode, parentChildren)); |
| | 101 | 139 | | foreach (var child in treeNodeChildren) |
| | 25 | 140 | | stack.Push(new(null, child.Key, child.Value, trieNodeChildren)); |
| | 17 | 141 | | } |
| | | 142 | | |
| | 32 | 143 | | return; |
| | | 144 | | } |
| | | 145 | | |
| | 2 | 146 | | throw new NotSupportedException($"{treeNode} of type {treeNode.GetType().Name} not supported"); |
| | 51 | 147 | | } |
| | | 148 | | } |