001 /*
002 * Java Genetic Algorithm Library (jenetics-6.2.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 -> node_001;
177 * node_001 -> node_002;
178 * node_002 -> node_003;
179 * node_001 -> node_004;
180 * node_004 -> node_005;
181 * node_000 -> node_006;
182 * node_006 -> node_007;
183 * node_007 -> node_008;
184 * node_007 -> 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 -> node_001;
244 * node_001 -> node_002;
245 * node_002 -> node_003;
246 * node_001 -> node_004;
247 * node_004 -> node_005;
248 * node_000 -> node_006;
249 * node_006 -> node_007;
250 * node_007 -> node_008;
251 * node_007 -> 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 }
|