| | | 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 | | /// Conversion is iteratively for no-branching paths (i.e. on nodes having a single child) and recursively on |
| | | 13 | | /// branching of the input <see cref="SuffixTrieNode"/>, with occasional mutation of internal state of the |
| | | 14 | | /// conversion. |
| | | 15 | | /// Limited by stack depth (but less than <see cref="FullyRecursiveConverter"/>) and usable with output trees of a |
| | | 16 | | /// "reasonable" height (i.e. trees having a height < ~1K nodes). |
| | | 17 | | /// </remarks> |
| | | 18 | | public class PartiallyIterativeConverter : IConverter |
| | | 19 | | { |
| | | 20 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 21 | | /// <summary> |
| | | 22 | | /// <inheritdoc/> |
| | | 23 | | /// </summary> |
| | | 24 | | /// <remarks> |
| | | 25 | | /// <inheritdoc cref="PartiallyIterativeConverter" path="/remarks"/> |
| | | 26 | | /// <inheritdoc cref="IConverter.TrieToTree(SuffixTrieNode)" path="/remarks"/> |
| | | 27 | | /// </remarks> |
| | | 28 | | public SuffixTreeNode TrieToTree(SuffixTrieNode trieNode) => |
| | 36 | 29 | | trieNode switch |
| | 36 | 30 | | { |
| | 36 | 31 | | SuffixTrieNode.Leaf(var leafStart) => |
| | 18 | 32 | | new SuffixTreeNode.Leaf(leafStart), |
| | 36 | 33 | | |
| | 36 | 34 | | SuffixTrieNode.Intermediate(var trieNodeChildren) => |
| | 17 | 35 | | new SuffixTreeNode.Intermediate(new Dictionary<SuffixTreeEdge, SuffixTreeNode>( |
| | 17 | 36 | | from trieChild in trieNodeChildren |
| | 24 | 37 | | let coalescedChild = IterativeCoalesce(trieChild.Key, trieChild.Value) |
| | 23 | 38 | | let coalescedTreeChildNode = TrieToTree(coalescedChild.coalescedTrieNode) |
| | 39 | 39 | | select KeyValuePair.Create(coalescedChild.coalescedTreeEdge, coalescedTreeChildNode))), |
| | 36 | 40 | | |
| | 1 | 41 | | _ => throw new NotSupportedException($"{trieNode} of type {trieNode.GetType().Name} not supported") |
| | 36 | 42 | | }; |
| | | 43 | | |
| | | 44 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 45 | | /// <summary> |
| | | 46 | | /// <inheritdoc/> |
| | | 47 | | /// </summary> |
| | | 48 | | /// <remarks> |
| | | 49 | | /// <inheritdoc cref="PartiallyIterativeConverter" path="/remarks"/> |
| | | 50 | | /// <inheritdoc cref="IConverter.TreeToTrie(SuffixTreeNode)" path="/remarks"/> |
| | | 51 | | /// </remarks> |
| | | 52 | | public SuffixTrieNode TreeToTrie(SuffixTreeNode treeNode) => |
| | 37 | 53 | | treeNode switch |
| | 37 | 54 | | { |
| | 37 | 55 | | SuffixTreeNode.Leaf(var leafStart) => |
| | 18 | 56 | | new SuffixTrieNode.Leaf(leafStart), |
| | 37 | 57 | | |
| | 37 | 58 | | SuffixTreeNode.Intermediate(var treeNodeChildren) => |
| | 17 | 59 | | new SuffixTrieNode.Intermediate(new Dictionary<SuffixTrieEdge, SuffixTrieNode>( |
| | 17 | 60 | | from treeChild in treeNodeChildren |
| | 24 | 61 | | let expandedLastTrieNode = TreeToTrie(treeChild.Value) |
| | 22 | 62 | | let expandedChild = IterativeExpand(treeChild.Key, expandedLastTrieNode) |
| | 39 | 63 | | select KeyValuePair.Create(expandedChild.expandedTrieEdge, expandedChild.expandedTrieNode))), |
| | 37 | 64 | | |
| | 2 | 65 | | _ => throw new NotSupportedException($"{treeNode} of type {treeNode.GetType().Name} not supported") |
| | 37 | 66 | | }; |
| | | 67 | | } |