| | | 1 | | using MoreStructures.SuffixTrees; |
| | | 2 | | using MoreStructures.SuffixTries; |
| | | 3 | | |
| | | 4 | | namespace MoreStructures.SuffixStructures.Conversions; |
| | | 5 | | |
| | | 6 | | /// <summary> |
| | | 7 | | /// Provides functionalities useful to multiple implementations of <see cref="IConverter"/> |
| | | 8 | | /// </summary> |
| | | 9 | | internal static class ConverterHelpers |
| | | 10 | | { |
| | | 11 | | /// <summary> |
| | | 12 | | /// Iteratively coalesces all <see cref="SuffixTrieNode.Intermediate"/> nodes, starting from the one provided and |
| | | 13 | | /// going down the <see cref="SuffixTrieNode"/> structure, which have a single child. |
| | | 14 | | /// </summary> |
| | | 15 | | /// <param name="trieEdge">The edge pointing to the node to be coalesced with its descendants.</param> |
| | | 16 | | /// <param name="trieNode">The node to be coalesced with its descendants.</param> |
| | | 17 | | /// <returns> |
| | | 18 | | /// The couple of coalesced <see cref="SuffixTreeEdge"/> and the corresponding <see cref="SuffixTrieNode"/>. |
| | | 19 | | /// </returns> |
| | | 20 | | /// <exception cref="NotSupportedException"> |
| | | 21 | | /// If a node with children of a type different than <see cref="SuffixTrieNode.Intermediate"/> is encountered. |
| | | 22 | | /// </exception> |
| | | 23 | | /// <remarks> |
| | | 24 | | /// Example: the trie nodes path N -(1)-> N -(3)-> N -(5)-> N is coalesced into the tree nodes path N -(1,3)-> N. |
| | | 25 | | /// </remarks> |
| | | 26 | | internal static (SuffixTreeEdge coalescedTreeEdge, SuffixTrieNode coalescedTrieNode) IterativeCoalesce( |
| | | 27 | | SuffixTrieEdge trieEdge, SuffixTrieNode trieNode) |
| | 20048 | 28 | | { |
| | 20048 | 29 | | var coalescedTreeEdge = new SuffixTreeEdge(trieEdge.Start, trieEdge.Length); |
| | 20048 | 30 | | var coalescedTrieNode = trieNode; |
| | | 31 | | |
| | 20286 | 32 | | while (coalescedTrieNode.Children.Count == 1) |
| | 240 | 33 | | { |
| | 240 | 34 | | if (coalescedTrieNode is not SuffixTrieNode.Intermediate) |
| | 2 | 35 | | throw new NotSupportedException( |
| | 2 | 36 | | $"{coalescedTrieNode} of type {coalescedTrieNode.GetType().Name} not supported"); |
| | | 37 | | |
| | 238 | 38 | | var trieChild = coalescedTrieNode.Children.Single(); |
| | 238 | 39 | | coalescedTreeEdge = new SuffixTreeEdge( |
| | 238 | 40 | | coalescedTreeEdge.Start, coalescedTreeEdge.Length + trieChild.Key.Length); |
| | 238 | 41 | | coalescedTrieNode = coalescedTrieNode.Children.Single().Value; |
| | 238 | 42 | | } |
| | | 43 | | |
| | 20046 | 44 | | return (coalescedTreeEdge, coalescedTrieNode); |
| | 20046 | 45 | | } |
| | | 46 | | |
| | | 47 | | /// <summary> |
| | | 48 | | /// Iteratively expands the provided <see cref="SuffixTreeEdge"/>, into a chain of <see cref="SuffixTrieEdge"/> and |
| | | 49 | | /// <see cref="SuffixTrieNode"/> instances, where each node has a single child and where the last node points to |
| | | 50 | | /// the provided <see cref="SuffixTrieNode"/>. |
| | | 51 | | /// </summary> |
| | | 52 | | /// <param name="treeEdge">The edge pointing to the node to be expandend.</param> |
| | | 53 | | /// <param name="trieNode">The node to be attached to the last expanded node in the chain.</param> |
| | | 54 | | /// <returns> |
| | | 55 | | /// The couple of expanded <see cref="SuffixTrieEdge"/> and the corresponding <see cref="SuffixTrieNode"/>. |
| | | 56 | | /// </returns> |
| | | 57 | | /// <remarks> |
| | | 58 | | /// Example: the tree edge -(1,3)-> N is expanded into the trie nodes path -(1)-> N -(2)-> N -(3)-> N*. |
| | | 59 | | /// Where N* is the provided <see cref="SuffixTrieNode"/>. |
| | | 60 | | /// </remarks> |
| | | 61 | | internal static (SuffixTrieEdge expandedTrieEdge, SuffixTrieNode expandedTrieNode) IterativeExpand( |
| | | 62 | | SuffixTreeEdge treeEdge, SuffixTrieNode trieNode) |
| | 56 | 63 | | { |
| | 56 | 64 | | var treeEdgeStart = treeEdge.Start; |
| | 56 | 65 | | var expandedTrieEdge = new SuffixTrieEdge(treeEdgeStart); |
| | 56 | 66 | | var expandedTrieNode = trieNode; |
| | 596 | 67 | | for (var i = treeEdge.Length - 1; i >= 1; i--) |
| | 242 | 68 | | expandedTrieNode = new SuffixTrieNode.Intermediate(new Dictionary<SuffixTrieEdge, SuffixTrieNode> |
| | 242 | 69 | | { |
| | 242 | 70 | | [new(treeEdgeStart + i)] = expandedTrieNode, |
| | 242 | 71 | | }); |
| | | 72 | | |
| | 56 | 73 | | return (expandedTrieEdge, expandedTrieNode); |
| | 56 | 74 | | } |
| | | 75 | | } |