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.grammar;
021
022import static java.util.Objects.requireNonNull;
023
024import java.util.Optional;
025
026import io.jenetics.ext.grammar.Cfg.NonTerminal;
027import io.jenetics.ext.grammar.Cfg.Symbol;
028import io.jenetics.ext.util.Tree;
029import io.jenetics.ext.util.TreeNode;
030
031/**
032 * Standard implementation of a derivation-tree generator. The following code
033 * snippet lets you generate a derivation tree from a given grammar.
034 * <pre>{@code
035 * final Cfg<String> cfg = Bnf.parse("""
036 *     <expr> ::= ( <expr> <op> <expr> ) | <num> | <var> |  <fun> ( <arg>, <arg> )
037 *     <fun>  ::= FUN1 | FUN2
038 *     <arg>  ::= <expr> | <var> | <num>
039 *     <op>   ::= + | - | * | /
040 *     <var>  ::= x | y
041 *     <num>  ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
042 *     """
043 * );
044 *
045 * final var random = RandomGenerator.of("L64X256MixRandom");
046 * final var generator = new DerivationTreeGenerator<String>(
047 *     SymbolIndex.of(random),
048 *     1_000
049 * );
050 * final Tree<Symbol<String>, ?> tree = generator.generate(cfg);
051 * }</pre>
052 *
053 * @see SentenceGenerator
054 *
055 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
056 * @since 7.1
057 * @version 7.1
058 */
059public final class DerivationTreeGenerator<T>
060        implements Generator<T, Tree<Symbol<T>, ?>>
061{
062
063        private final SymbolIndex _index;
064        private final int _limit;
065
066        /**
067         * Create a new derivation tree generator from the given parameters.
068         *
069         * @param index the symbol index function used for generating the derivation
070         *        tree
071         * @param limit the maximal allowed nodes of the tree. If the generated
072         *        tree exceeds this length, the generation is interrupted and
073         *        an empty tree is returned. If a tree is empty can be checked with
074         *        {@link Tree#isEmpty()}.
075         */
076        public DerivationTreeGenerator(
077                final SymbolIndex index,
078                final int limit
079        ) {
080                _index = requireNonNull(index);
081                _limit = limit;
082        }
083
084        /**
085         * Generates a new derivation tree from the given grammar, <em>cfg</em>.
086         *
087         * @see Tree#isEmpty()
088         *
089         * @param cfg the generating grammar
090         * @return a newly created derivation tree, or an empty tree if
091         *         the number of nodes exceeds the defined node limit
092         */
093        @Override
094        public Tree<Symbol<T>, ?> generate(final Cfg<? extends T> cfg) {
095                final Cfg<T> grammar = Cfg.upcast(cfg);
096                final NonTerminal<T> start = grammar.start();
097                final TreeNode<Symbol<T>> symbols = TreeNode.of(start);
098
099                int count = 1;
100                boolean expanded = true;
101                while (expanded) {
102                        final Optional<TreeNode<Symbol<T>>> tree = symbols.leaves()
103                                .filter(leave ->
104                                        leave.value() instanceof NonTerminal<T> nt &&
105                                        cfg.rule(nt).isPresent()
106                                )
107                                .findFirst();
108
109                        if (tree.isPresent()) {
110                                final var t = tree.orElseThrow();
111                                final var selection = Generator.select(
112                                        (NonTerminal<T>)t.value(),
113                                        grammar,
114                                        _index
115                                );
116                                count += selection.size();
117
118                                if (count > _limit) {
119                                        return TreeNode.of();
120                                }
121
122                                selection.forEach(t::attach);
123                        }
124
125                        expanded = tree.isPresent();
126                }
127
128                return symbols;
129        }
130
131}