001/*
002 * Java Genetic Algorithm Library (jenetics-7.2.0).
003 * Copyright (c) 2007-2023 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 */
020package io.jenetics.ext.util;
021
022import static java.util.Objects.requireNonNull;
023
024import java.util.ArrayList;
025import java.util.HashMap;
026import java.util.Iterator;
027import java.util.List;
028import java.util.Map;
029import java.util.Objects;
030import java.util.function.Function;
031import 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 */
040public 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);
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                ) {
095                        final Iterator<StringBuilder> it = subtree.iterator();
096                        result.add(it.next().insert(0, "├── "));
097                        while (it.hasNext()) {
098                                result.add(it.next().insert(0, "│   "));
099                        }
100                }
101
102                private void lastSubtree(
103                        final List<StringBuilder> result,
104                        final List<StringBuilder> subtree
105                ) {
106                        final Iterator<StringBuilder> it = subtree.iterator();
107                        result.add(it.next().insert(0, "└── "));
108                        while (it.hasNext()) {
109                                result.add(it.next().insert(0, "    "));
110                        }
111                }
112        };
113
114        /**
115         * Formats a given tree to a parentheses string representation.
116         * <pre>
117         *     mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
118         * </pre>
119         */
120        public static final TreeFormatter PARENTHESES = new TreeFormatter() {
121                @Override
122                public <V> String format(
123                        final Tree<V, ?> tree,
124                        final Function<? super V, ? extends CharSequence> mapper
125                ) {
126                        requireNonNull(tree);
127                        requireNonNull(mapper);
128                        return ParenthesesTrees.toString(tree, mapper);
129                }
130        };
131
132        /**
133         * Formats a given tree to a lisp string representation.
134         * <pre>
135         *     (mul (div (cos 1.0) (cos π)) (sin (mul 1.0 z)))
136         * </pre>
137         */
138        public static final TreeFormatter LISP = new TreeFormatter() {
139                @Override
140                public <V> String format(
141                        final Tree<V, ?> tree,
142                        final Function<? super V, ? extends CharSequence> mapper
143                ) {
144                        final CharSequence value = mapper.apply(tree.value());
145                        if (tree.isLeaf()) {
146                                return value.toString();
147                        } else {
148                                final String children = tree.childStream()
149                                        .map(child -> format(child, mapper))
150                                        .collect(Collectors.joining(" "));
151                                return "(" + value + " " + children + ")";
152                        }
153                }
154        };
155
156        /**
157         * A tree formatter for .dot string representations. This strings can be
158         * used to create nice looking tree images. The tree
159         * <pre>
160         *     mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
161         * </pre>
162         * is rendered into this dot string
163         * <pre>
164         * digraph Tree {
165         *     node_001 [label="div"];
166         *     node_002 [label="cos"];
167         *     node_003 [label="1.0"];
168         *     node_004 [label="cos"];
169         *     node_000 [label="mul"];
170         *     node_009 [label="z"];
171         *     node_005 [label="π"];
172         *     node_006 [label="sin"];
173         *     node_007 [label="mul"];
174         *     node_008 [label="1.0"];
175         *     node_000 -&gt; node_001;
176         *     node_001 -&gt; node_002;
177         *     node_002 -&gt; node_003;
178         *     node_001 -&gt; node_004;
179         *     node_004 -&gt; node_005;
180         *     node_000 -&gt; node_006;
181         *     node_006 -&gt; node_007;
182         *     node_007 -&gt; node_008;
183         *     node_007 -&gt; node_009;
184         * }
185         * </pre>
186         * This dot string can be rendered into the following graph:
187         * <p>
188         * <img alt="Dot-tree" src="doc-files/dot-tree.svg" width="400" height="252" >
189         * </p>
190         */
191        public static final TreeFormatter DOT = dot("Tree");
192
193        protected TreeFormatter() {
194        }
195
196        /**
197         * Formats the given {@code tree} to its string representation. The given
198         * {@code mapper} is used for converting the node type {@code V} to a string
199         * value.
200         *
201         * @param tree the input tree to format
202         * @param mapper the tree node value mapper
203         * @param <V> the tree node type
204         * @return the string representation of the given {@code tree}
205         * @throws NullPointerException if one of the arguments is {@code null}
206         */
207        public abstract  <V> String format(
208                final Tree<V, ?> tree,
209                final Function<? super V, ? extends CharSequence> mapper
210        );
211
212        /**
213         * Formats the given {@code tree} to its string representation.
214         *
215         * @param tree the input tree to format
216         * @return the string representation of the given {@code tree}
217         * @throws NullPointerException if the {@code tree} is {@code null}
218         */
219        public String format(final Tree<?, ?> tree) {
220                return format(tree, Objects::toString);
221        }
222
223        /**
224         * A tree formatter for .dot string representations. This strings can be
225         * used to create nice looking tree images. The tree
226         * <pre>
227         *     mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
228         * </pre>
229         * is rendered into this dot string
230         * <pre>
231         * digraph Tree {
232         *     node_001 [label="div"];
233         *     node_002 [label="cos"];
234         *     node_003 [label="1.0"];
235         *     node_004 [label="cos"];
236         *     node_000 [label="mul"];
237         *     node_009 [label="z"];
238         *     node_005 [label="π"];
239         *     node_006 [label="sin"];
240         *     node_007 [label="mul"];
241         *     node_008 [label="1.0"];
242         *     node_000 -&gt; node_001;
243         *     node_001 -&gt; node_002;
244         *     node_002 -&gt; node_003;
245         *     node_001 -&gt; node_004;
246         *     node_004 -&gt; node_005;
247         *     node_000 -&gt; node_006;
248         *     node_006 -&gt; node_007;
249         *     node_007 -&gt; node_008;
250         *     node_007 -&gt; node_009;
251         * }
252         * </pre>
253         * This dot string can be rendered into the following graph:
254         * <p>
255         * <img alt="Dot-tree" src="doc-files/dot-tree.svg" width="400" height="252" >
256         * </p>
257         *
258         * @param treeName the name of the digraph
259         * @return a dot string formatter
260         * @throws NullPointerException if the given tree name is {@code null}
261         */
262        public static TreeFormatter dot(final String treeName) {
263                return new Dotty(treeName);
264        }
265
266
267        /* *************************************************************************
268         * Some helper classes.
269         * ************************************************************************/
270
271        /**
272         * This formatter converts a tree to the .dot representation.
273         */
274        private static final class Dotty extends TreeFormatter {
275                private final String _name;
276
277                Dotty(final String name) {
278                        _name = requireNonNull(name);
279                }
280
281                @Override
282                public <V> String format(
283                        final Tree<V, ?> tree,
284                        final Function<? super V, ? extends CharSequence> mapper
285                ) {
286                        return new Helper<>(_name, tree, mapper).draw();
287                }
288
289                private static final class Helper<V> {
290                        private final String _name;
291                        private final Function<? super V, ? extends CharSequence> _mapper;
292
293                        private final Map<String, CharSequence> _labels = new HashMap<>();
294                        private final List<String> _edges = new ArrayList<>();
295
296                        Helper(
297                                final String name,
298                                final Tree<V, ?> tree,
299                                final Function<? super V, ? extends CharSequence> mapper
300                        ) {
301                                _name = requireNonNull(name);
302                                _mapper = requireNonNull(mapper);
303                                init(tree, null, 0);
304                        }
305
306                        private int init(
307                                final Tree<V, ?> tree,
308                                final String parentLabel,
309                                final int index
310                        ) {
311                                int idx = index;
312                                final CharSequence value = _mapper.apply(tree.value());
313                                final String label = String.format("node_%03d", idx);
314                                _labels.put(label, value);
315
316                                if (parentLabel != null) {
317                                        _edges.add(parentLabel + " -> " + label);
318                                }
319                                for (int i = 0; i < tree.childCount(); ++i) {
320                                        final Tree<V, ?> child = tree.childAt(i);
321                                        idx = init(child, label, idx + 1);
322                                }
323                                return idx;
324                        }
325
326                        String draw() {
327                                final StringBuilder builder = new StringBuilder();
328                                builder
329                                        .append("digraph ")
330                                        .append(_name)
331                                        .append(" {\n");
332
333                                _labels.forEach((key, value) ->
334                                        builder
335                                                .append("    ")
336                                                .append(key)
337                                                .append(" [label=\"")
338                                                .append(value.toString().replace("\"", "\\\""))
339                                                .append("\"];\n")
340                                );
341
342                                _edges.forEach(edge ->
343                                        builder
344                                                .append("    ")
345                                                .append(edge)
346                                                .append(";\n")
347                                );
348                                builder.append("}\n");
349
350                                return builder.toString();
351                        }
352                }
353        }
354
355}