TreeFormatter.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-6.3.0).
003  * Copyright (c) 2007-2021 Franz Wilhelmstötter
004  *
005  * Licensed under the Apache License, Version 2.0 (the "License");
006  * you may not use this file except in compliance with the License.
007  * You may obtain a copy of the License at
008  *
009  *      http://www.apache.org/licenses/LICENSE-2.0
010  *
011  * Unless required by applicable law or agreed to in writing, software
012  * distributed under the License is distributed on an "AS IS" BASIS,
013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014  * See the License for the specific language governing permissions and
015  * limitations under the License.
016  *
017  * Author:
018  *    Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com)
019  */
020 package io.jenetics.ext.util;
021 
022 import static java.util.Objects.requireNonNull;
023 
024 import java.util.ArrayList;
025 import java.util.HashMap;
026 import java.util.Iterator;
027 import java.util.List;
028 import java.util.Map;
029 import java.util.Objects;
030 import java.util.function.Function;
031 import java.util.stream.Collectors;
032 
033 /**
034  * Definition of different tree formatter strategies.
035  *
036  @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
037  @version 5.0
038  @since 5.0
039  */
040 public abstract class TreeFormatter {
041 
042     /**
043      * Formats a given tree to a <em>tree</em> string representation.
044      <pre>
045      *     mul
046      *     ├── div
047      *     │   ├── cos
048      *     │   │   └── 1.0
049      *     │   └── cos
050      *     │       └── π
051      *     └── sin
052      *         └── mul
053      *             ├── 1.0
054      *             └── z
055      *  </pre>
056      */
057     public static final TreeFormatter TREE = new TreeFormatter() {
058 
059         @Override
060         public <V> String format(
061             final Tree<V, ?> tree,
062             final Function<? super V, ? extends CharSequence> mapper
063         ) {
064             requireNonNull(tree);
065             requireNonNull(mapper);
066 
067             return toStrings(tree, mapper).stream()
068                 .map(StringBuilder::toString)
069                 .collect(Collectors.joining("\n"));
070         }
071 
072         private <V> List<StringBuilder> toStrings(
073             final Tree<V, ?> tree,
074             final Function<? super V, ? extends CharSequence> mapper
075         ) {
076             final List<StringBuilder> result = new ArrayList<>();
077             result.add(new StringBuilder().append(mapper.apply(tree.value())));
078 
079             final Iterator<? extends Tree<V, ?>> it = tree.childIterator();
080             while (it.hasNext()) {
081                 final List<StringBuilder> subtree = toStrings(it.next(), mapper);
082                 if (it.hasNext()) {
083                     subtree(result, subtree, mapper);
084                 else {
085                     lastSubtree(result, subtree);
086                 }
087             }
088             return result;
089         }
090 
091         private <V> void subtree(
092             final List<StringBuilder> result,
093             final List<StringBuilder> subtree,
094             final Function<? super V, ? extends CharSequence> mapper
095         ) {
096             final Iterator<StringBuilder> it = subtree.iterator();
097             result.add(it.next().insert(0"├── "));
098             while (it.hasNext()) {
099                 result.add(it.next().insert(0"│   "));
100             }
101         }
102 
103         private void lastSubtree(
104             final List<StringBuilder> result,
105             final List<StringBuilder> subtree
106         ) {
107             final Iterator<StringBuilder> it = subtree.iterator();
108             result.add(it.next().insert(0"└── "));
109             while (it.hasNext()) {
110                 result.add(it.next().insert(0"    "));
111             }
112         }
113     };
114 
115     /**
116      * Formats a given tree to a parentheses string representation.
117      <pre>
118      *     mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
119      </pre>
120      */
121     public static final TreeFormatter PARENTHESES = new TreeFormatter() {
122         @Override
123         public <V> String format(
124             final Tree<V, ?> tree,
125             final Function<? super V, ? extends CharSequence> mapper
126         ) {
127             requireNonNull(tree);
128             requireNonNull(mapper);
129             return ParenthesesTrees.toString(tree, mapper);
130         }
131     };
132 
133     /**
134      * Formats a given tree to a lisp string representation.
135      <pre>
136      *     (mul (div (cos 1.0) (cos π)) (sin (mul 1.0 z)))
137      </pre>
138      */
139     public static final TreeFormatter LISP = new TreeFormatter() {
140         @Override
141         public <V> String format(
142             final Tree<V, ?> tree,
143             final Function<? super V, ? extends CharSequence> mapper
144         ) {
145             final CharSequence value = mapper.apply(tree.value());
146             if (tree.isLeaf()) {
147                 return value.toString();
148             else {
149                 final String children = tree.childStream()
150                     .map(child -> format(child, mapper))
151                     .collect(Collectors.joining(" "));
152                 return "(" + value + " " + children + ")";
153             }
154         }
155     };
156 
157     /**
158      * A tree formatter for .dot string representations. This strings can be
159      * used to create nice looking tree images. The tree
160      <pre>
161      *     mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
162      </pre>
163      * is rendered into this dot string
164      <pre>
165      * digraph Tree {
166      *     node_001 [label="div"];
167      *     node_002 [label="cos"];
168      *     node_003 [label="1.0"];
169      *     node_004 [label="cos"];
170      *     node_000 [label="mul"];
171      *     node_009 [label="z"];
172      *     node_005 [label="π"];
173      *     node_006 [label="sin"];
174      *     node_007 [label="mul"];
175      *     node_008 [label="1.0"];
176      *     node_000 -&gt; node_001;
177      *     node_001 -&gt; node_002;
178      *     node_002 -&gt; node_003;
179      *     node_001 -&gt; node_004;
180      *     node_004 -&gt; node_005;
181      *     node_000 -&gt; node_006;
182      *     node_006 -&gt; node_007;
183      *     node_007 -&gt; node_008;
184      *     node_007 -&gt; node_009;
185      * }
186      </pre>
187      * This dot string can be rendered into the following graph:
188      <p>
189      <img alt="Dot-tree" src="doc-files/dot-tree.svg" width="400" height="252" >
190      </p>
191      */
192     public static final TreeFormatter DOT = dot("Tree");
193 
194     protected TreeFormatter() {
195     }
196 
197     /**
198      * Formats the given {@code tree} to its string representation. The given
199      * {@code mapper} is used for converting the node type {@code V} to a string
200      * value.
201      *
202      @param tree the input tree to format
203      @param mapper the tree node value mapper
204      @param <V> the tree node type
205      @return the string representation of the given {@code tree}
206      @throws NullPointerException if one of the arguments is {@code null}
207      */
208     public abstract  <V> String format(
209         final Tree<V, ?> tree,
210         final Function<? super V, ? extends CharSequence> mapper
211     );
212 
213     /**
214      * Formats the given {@code tree} to its string representation.
215      *
216      @param tree the input tree to format
217      @return the string representation of the given {@code tree}
218      @throws NullPointerException if the {@code tree} is {@code null}
219      */
220     public String format(final Tree<?, ?> tree) {
221         return format(tree, Objects::toString);
222     }
223 
224     /**
225      * A tree formatter for .dot string representations. This strings can be
226      * used to create nice looking tree images. The tree
227      <pre>
228      *     mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
229      </pre>
230      * is rendered into this dot string
231      <pre>
232      * digraph Tree {
233      *     node_001 [label="div"];
234      *     node_002 [label="cos"];
235      *     node_003 [label="1.0"];
236      *     node_004 [label="cos"];
237      *     node_000 [label="mul"];
238      *     node_009 [label="z"];
239      *     node_005 [label="π"];
240      *     node_006 [label="sin"];
241      *     node_007 [label="mul"];
242      *     node_008 [label="1.0"];
243      *     node_000 -&gt; node_001;
244      *     node_001 -&gt; node_002;
245      *     node_002 -&gt; node_003;
246      *     node_001 -&gt; node_004;
247      *     node_004 -&gt; node_005;
248      *     node_000 -&gt; node_006;
249      *     node_006 -&gt; node_007;
250      *     node_007 -&gt; node_008;
251      *     node_007 -&gt; node_009;
252      * }
253      </pre>
254      * This dot string can be rendered into the following graph:
255      <p>
256      <img alt="Dot-tree" src="doc-files/dot-tree.svg" width="400" height="252" >
257      </p>
258      *
259      @param treeName the name of the digraph
260      @return a dot string formatter
261      @throws NullPointerException if the given tree name is {@code null}
262      */
263     public static TreeFormatter dot(final String treeName) {
264         return new Dotty(treeName);
265     }
266 
267 
268     /* *************************************************************************
269      * Some helper classes.
270      * ************************************************************************/
271 
272     /**
273      * This formatter converts a tree to the .dot representation.
274      */
275     private static final class Dotty extends TreeFormatter {
276         private final String _name;
277 
278         Dotty(final String name) {
279             _name = requireNonNull(name);
280         }
281 
282         @Override
283         public <V> String format(
284             final Tree<V, ?> tree,
285             final Function<? super V, ? extends CharSequence> mapper
286         ) {
287             return new Helper<>(_name, tree, mapper).draw();
288         }
289 
290         private static final class Helper<V> {
291             private final String _name;
292             private final Function<? super V, ? extends CharSequence> _mapper;
293 
294             private final Map<String, CharSequence> _labels = new HashMap<>();
295             private final List<String> _edges = new ArrayList<>();
296 
297             Helper(
298                 final String name,
299                 final Tree<V, ?> tree,
300                 final Function<? super V, ? extends CharSequence> mapper
301             ) {
302                 _name = requireNonNull(name);
303                 _mapper = requireNonNull(mapper);
304                 init(tree, null, 0);
305             }
306 
307             private int init(
308                 final Tree<V, ?> tree,
309                 final String parentLabel,
310                 final int index
311             ) {
312                 int idx = index;
313                 final CharSequence value = _mapper.apply(tree.value());
314                 final String label = String.format("node_%03d", idx);
315                 _labels.put(label, value);
316 
317                 if (parentLabel != null) {
318                     _edges.add(parentLabel + " -> " + label);
319                 }
320                 for (int i = 0; i < tree.childCount(); ++i) {
321                     final Tree<V, ?> child = tree.childAt(i);
322                     idx = init(child, label, idx + 1);
323                 }
324                 return idx;
325             }
326 
327             String draw() {
328                 final StringBuilder builder = new StringBuilder();
329                 builder
330                     .append("digraph ")
331                     .append(_name)
332                     .append(" {\n");
333 
334                 _labels.forEach((key, value->
335                     builder
336                         .append("    ")
337                         .append(key)
338                         .append(" [label=\"")
339                         .append(value.toString().replace("\"""\\\""))
340                         .append("\"];\n")
341                 );
342 
343                 _edges.forEach(edge ->
344                     builder
345                         .append("    ")
346                         .append(edge)
347                         .append(";\n")
348                 );
349                 builder.append("}\n");
350 
351                 return builder.toString();
352             }
353         }
354     }
355 
356 }