| | | 1 | | using MoreStructures.SuffixTrees; |
| | | 2 | | using MoreStructures.SuffixTries; |
| | | 3 | | |
| | | 4 | | namespace MoreStructures.SuffixStructures.Conversions; |
| | | 5 | | |
| | | 6 | | /// <summary> |
| | | 7 | | /// <inheritdoc cref="IConverter"/> |
| | | 8 | | /// </summary> |
| | | 9 | | /// <remarks> |
| | | 10 | | /// Implemented fully recursively, with one level of recursion per level of the input <see cref="SuffixTrieNode"/>. |
| | | 11 | | /// Limited by call stack depth and usable with input trees of a "reasonable" height (i.e. trees having a height < |
| | | 12 | | /// ~1K nodes). |
| | | 13 | | /// </remarks> |
| | | 14 | | public class FullyRecursiveConverter : IConverter |
| | | 15 | | { |
| | | 16 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 17 | | /// <summary> |
| | | 18 | | /// <inheritdoc/> |
| | | 19 | | /// </summary> |
| | | 20 | | /// <remarks> |
| | | 21 | | /// <inheritdoc cref="FullyRecursiveConverter" path="/remarks"/> |
| | | 22 | | /// <inheritdoc cref="IConverter.TrieToTree(SuffixTrieNode)" path="/remarks"/> |
| | | 23 | | /// </remarks> |
| | | 24 | | public SuffixTreeNode TrieToTree(SuffixTrieNode trieNode) => |
| | 36 | 25 | | trieNode switch |
| | 36 | 26 | | { |
| | 36 | 27 | | SuffixTrieNode.Leaf(var leafStart) => |
| | 18 | 28 | | new SuffixTreeNode.Leaf(leafStart), |
| | 36 | 29 | | |
| | 36 | 30 | | SuffixTrieNode.Intermediate(var trieNodeChildren) => |
| | 17 | 31 | | new SuffixTreeNode.Intermediate(new Dictionary<SuffixTreeEdge, SuffixTreeNode>( |
| | 17 | 32 | | from trieChild in trieNodeChildren |
| | 24 | 33 | | let treeChildEdge = new SuffixTreeEdge(trieChild.Key.Start, trieChild.Key.Length) |
| | 24 | 34 | | let coaleascedChild = RecursiveCoalesce(treeChildEdge, trieChild.Value) |
| | 23 | 35 | | let treeChildEdge1 = coaleascedChild.Item1 |
| | 23 | 36 | | let trieChildNode1 = coaleascedChild.Item2 |
| | 23 | 37 | | select KeyValuePair.Create(treeChildEdge1, TrieToTree(trieChildNode1)) |
| | 17 | 38 | | )), |
| | 36 | 39 | | |
| | 1 | 40 | | _ => throw new NotSupportedException($"{trieNode} of type {trieNode.GetType().Name} not supported"), |
| | 36 | 41 | | }; |
| | | 42 | | |
| | | 43 | | private static (SuffixTreeEdge, SuffixTrieNode) RecursiveCoalesce( |
| | | 44 | | SuffixTreeEdge treeEdge, SuffixTrieNode trieNode) => |
| | 143 | 45 | | trieNode switch |
| | 143 | 46 | | { |
| | 143 | 47 | | SuffixTrieNode.Leaf => |
| | 17 | 48 | | (treeEdge, trieNode), |
| | 143 | 49 | | |
| | 125 | 50 | | SuffixTrieNode.Intermediate(var children) when children.Count != 1 => |
| | 6 | 51 | | (treeEdge, trieNode), |
| | 143 | 52 | | |
| | 119 | 53 | | SuffixTrieNode.Intermediate(var children) when children.Single() is var (trieChildEdge, trieChildNode) => |
| | 119 | 54 | | RecursiveCoalesce( |
| | 119 | 55 | | new SuffixTreeEdge(treeEdge.Start, treeEdge.Length + trieChildEdge.Length), trieChildNode), |
| | 143 | 56 | | |
| | 1 | 57 | | _ => throw new NotSupportedException($"{trieNode} of type {trieNode.GetType().Name} not supported"), |
| | 143 | 58 | | }; |
| | | 59 | | |
| | | 60 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 61 | | /// <summary> |
| | | 62 | | /// <inheritdoc/> |
| | | 63 | | /// </summary> |
| | | 64 | | /// <remarks> |
| | | 65 | | /// <inheritdoc cref="FullyRecursiveConverter" path="/remarks"/> |
| | | 66 | | /// <inheritdoc cref="IConverter.TreeToTrie(SuffixTreeNode)" path="/remarks"/> |
| | | 67 | | /// </remarks> |
| | | 68 | | public SuffixTrieNode TreeToTrie(SuffixTreeNode treeNode) => |
| | 37 | 69 | | treeNode switch |
| | 37 | 70 | | { |
| | 37 | 71 | | SuffixTreeNode.Leaf(var leafStart) => |
| | 18 | 72 | | new SuffixTrieNode.Leaf(leafStart), |
| | 37 | 73 | | |
| | 37 | 74 | | SuffixTreeNode.Intermediate(var nodeChildren) => |
| | 17 | 75 | | new SuffixTrieNode.Intermediate(new Dictionary<SuffixTrieEdge, SuffixTrieNode>( |
| | 17 | 76 | | from treeChild in nodeChildren |
| | 24 | 77 | | let expandedChild = RecursiveExpand(treeChild.Key, TreeToTrie(treeChild.Value), 0) |
| | 39 | 78 | | select KeyValuePair.Create(expandedChild.expandedTrieEdge, expandedChild.expandedTrieNode))), |
| | 37 | 79 | | |
| | 2 | 80 | | _ => throw new NotSupportedException($"{treeNode} of type {treeNode.GetType().Name} not supported"), |
| | 37 | 81 | | }; |
| | | 82 | | |
| | | 83 | | private static (SuffixTrieEdge expandedTrieEdge, SuffixTrieNode expandedTrieNode) RecursiveExpand( |
| | | 84 | | SuffixTreeEdge treeEdge, SuffixTrieNode trieNode, int edgeIndexDelta) |
| | 141 | 85 | | { |
| | 141 | 86 | | var expandedTrieEdge = new SuffixTrieEdge(treeEdge.Start + edgeIndexDelta); |
| | | 87 | | |
| | 141 | 88 | | if (treeEdge.Length == edgeIndexDelta + 1) |
| | 22 | 89 | | return (expandedTrieEdge, trieNode); |
| | | 90 | | |
| | 119 | 91 | | var (childExpandedTrieEdge, childExpandedTrieNode) = RecursiveExpand(treeEdge, trieNode, edgeIndexDelta + 1); |
| | 119 | 92 | | return (expandedTrieEdge, |
| | 119 | 93 | | new SuffixTrieNode.Intermediate(new Dictionary<SuffixTrieEdge, SuffixTrieNode> |
| | 119 | 94 | | { |
| | 119 | 95 | | [childExpandedTrieEdge] = childExpandedTrieNode |
| | 119 | 96 | | })); |
| | 141 | 97 | | } |
| | | 98 | | } |