| | | 1 | | namespace MoreStructures.RecImmTrees.Conversions; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// <inheritdoc/> |
| | | 5 | | /// <br/> |
| | | 6 | | /// Iterative implementation. |
| | | 7 | | /// </summary> |
| | | 8 | | /// <typeparam name="TEdge">The type of edges of the specific structure.</typeparam> |
| | | 9 | | /// <typeparam name="TNode">The type of nodes of the specific structure.</typeparam> |
| | | 10 | | /// <remarks> |
| | | 11 | | /// <inheritdoc cref="IStringifier{TEdge, TNode}" path="/remarks"/> |
| | | 12 | | /// <para id="advantages"> |
| | | 13 | | /// ADVANTAGES AND DISADVANTAGES |
| | | 14 | | /// <br/> |
| | | 15 | | /// <inheritdoc cref="DocFragments" path="/remarks/para[@id='fully-iterative-advantages']"/> |
| | | 16 | | /// </para> |
| | | 17 | | /// </remarks> |
| | | 18 | | public class FullyIterativeStringifier<TEdge, TNode> |
| | | 19 | | : StringifierBase<TEdge, TNode>, IStringifier<TEdge, TNode> |
| | | 20 | | where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode> |
| | | 21 | | where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode> |
| | | 22 | | { |
| | | 23 | | /// <summary> |
| | | 24 | | /// The maximum level at which indentation should not be done anymore. Default is <see cref="int.MaxValue"/>. |
| | | 25 | | /// </summary> |
| | | 26 | | /// <remarks> |
| | | 27 | | /// <para id="complexity"> |
| | | 28 | | /// COMPLEXITY |
| | | 29 | | /// <br/> |
| | | 30 | | /// - When trying to render a very deep structure to string, the resulting string can become extremely big due |
| | | 31 | | /// to indentation. |
| | | 32 | | /// <br/> |
| | | 33 | | /// - This can easily happen with structures like <see cref="SuffixTries.SuffixTrieNode"/>. Less with |
| | | 34 | | /// <see cref="SuffixTrees.SuffixTreeNode"/>, due to their coalescing of paths of nodes with single child. |
| | | 35 | | /// <br/> |
| | | 36 | | /// - For example if the structure is a linear chain of n in depth, 4 chars of indentation per line would yield |
| | | 37 | | /// a string of 2n(n-1) chars = O(n^2). |
| | | 38 | | /// <br/> |
| | | 39 | | /// - For n = 10000 nodes the produced string would be ~ 200M. |
| | | 40 | | /// <br/> |
| | | 41 | | /// - To avoid that <see cref="StopIndentingLevel"/> can be set to a constant c, limiting the size of the |
| | | 42 | | /// resulting string by an upper bound of cn = O(n). |
| | | 43 | | /// <br/> |
| | | 44 | | /// - For n = 10000 nodes and c = 10 levels the produced string would be 100K. |
| | | 45 | | /// </para> |
| | | 46 | | /// </remarks> |
| | 11045 | 47 | | public int StopIndentingLevel { get; set; } = int.MaxValue; |
| | | 48 | | |
| | | 49 | | /// <summary> |
| | | 50 | | /// Whether the actual level should be prepended to the line, once the maximum level of indentation defined at |
| | | 51 | | /// <see cref="StopIndentingLevel"/> has been reached. Default is <see langword="true"/>. |
| | | 52 | | /// </summary> |
| | 11043 | 53 | | public bool PrependLevelAfterStopIndenting { get; set; } = true; |
| | | 54 | | |
| | | 55 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 56 | | /// <inheritdoc cref="FullyIterativeStringifier{TEdge, TNode}" path="/remarks"/> |
| | | 57 | | public FullyIterativeStringifier( |
| | | 58 | | Func<TNode, string> rootStringifier, Func<TEdge, TNode, string> edgeAndNodeStringifier) |
| | 20 | 59 | | : base(rootStringifier, edgeAndNodeStringifier) |
| | 20 | 60 | | { |
| | 20 | 61 | | } |
| | | 62 | | |
| | | 63 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 64 | | /// <inheritdoc cref="FullyIterativeStringifier{TEdge, TNode}" path="/remarks"/> |
| | | 65 | | public override string Stringify(TNode node) |
| | 165 | 66 | | { |
| | 165 | 67 | | var stringBuilder = new StringBuilder(); |
| | 165 | 68 | | stringBuilder.Append(RootStringifier(node)); |
| | | 69 | | |
| | 165 | 70 | | var stack = new Stack<(TEdge edge, TNode node, int level)> { }; |
| | 2166 | 71 | | foreach (var (childEdge, childNode) in node.Children.OrderByDescending(c => c.Key)) |
| | 557 | 72 | | stack.Push((childEdge, childNode, 1)); |
| | | 73 | | |
| | 11184 | 74 | | while (stack.Count > 0) |
| | 11019 | 75 | | Stringify(stringBuilder, stack); |
| | 165 | 76 | | return stringBuilder.ToString(); |
| | 165 | 77 | | } |
| | | 78 | | |
| | | 79 | | private void Stringify(StringBuilder stringBuilder, Stack<(TEdge edge, TNode node, int level)> stack) |
| | 11019 | 80 | | { |
| | 11019 | 81 | | var (edge, node, level) = stack.Pop(); |
| | | 82 | | |
| | 11019 | 83 | | stringBuilder.Append(NewLine); |
| | 11019 | 84 | | var indentationDepth = Math.Min(StopIndentingLevel, level); |
| | 100035236 | 85 | | for (int i = 0; i < indentationDepth; i++) |
| | 50006599 | 86 | | stringBuilder.Append(Indent); |
| | 11019 | 87 | | if (PrependLevelAfterStopIndenting && level != indentationDepth) |
| | 8 | 88 | | stringBuilder.Append($"[level {level}]"); |
| | | 89 | | |
| | 11019 | 90 | | stringBuilder.Append(EdgeAndNodeStringifier(edge, node)); |
| | | 91 | | |
| | 64443 | 92 | | foreach (var (childEdge, childNode) in node.Children.OrderByDescending(c => c.Key)) |
| | 10462 | 93 | | stack.Push((childEdge, childNode, level + 1)); |
| | 11019 | 94 | | } |
| | | 95 | | |
| | | 96 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 97 | | /// <inheritdoc cref="FullyIterativeStringifier{TEdge, TNode}" path="/remarks"/> |
| | | 98 | | public override string Stringify(TreePath<TEdge, TNode> path) |
| | 9 | 99 | | { |
| | 9 | 100 | | if (!path.PathNodes.Any()) |
| | 2 | 101 | | return string.Empty; |
| | | 102 | | |
| | 7 | 103 | | var stringBuilder = new StringBuilder(); |
| | | 104 | | |
| | 7 | 105 | | var (firstEdge, firstNode) = path.PathNodes.First(); |
| | 7 | 106 | | stringBuilder.Append(EdgeAndNodeStringifier(firstEdge, firstNode)); |
| | | 107 | | |
| | 75 | 108 | | foreach (var (edge, node) in path.PathNodes.Skip(1)) |
| | 27 | 109 | | { |
| | 27 | 110 | | stringBuilder.Append(PathSeparator); |
| | 27 | 111 | | stringBuilder.Append(EdgeAndNodeStringifier(edge, node)); |
| | 27 | 112 | | } |
| | | 113 | | |
| | 7 | 114 | | return stringBuilder.ToString(); |
| | 9 | 115 | | } |
| | | 116 | | } |