001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.0).
003 * Copyright (c) 2007-2024 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.prog.op;
021
022import static java.lang.String.format;
023import static java.util.Objects.requireNonNull;
024import static io.jenetics.internal.util.Hashes.hash;
025
026import java.io.Serial;
027import java.io.Serializable;
028import java.util.Objects;
029import java.util.function.BiFunction;
030import java.util.function.Function;
031import java.util.random.RandomGenerator;
032
033import io.jenetics.util.ISeq;
034import io.jenetics.util.RandomRegistry;
035
036import io.jenetics.ext.util.FlatTree;
037import io.jenetics.ext.util.Tree;
038import io.jenetics.ext.util.TreeNode;
039
040/**
041 * This class composes a given operation tree to a new operation, which can
042 * serve as a sub <em>program</em> in another operation tree.
043 *
044 * @param <T> the argument type of the operation
045 *
046 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
047 * @version 4.1
048 * @since 3.9
049 */
050public class Program<T> implements Op<T>, Serializable {
051
052        @Serial
053        private static final long serialVersionUID = 1L;
054
055        private final String _name;
056        private final Tree<? extends Op<T>, ?> _tree;
057
058        /**
059         * Create a new program with the given name and the given operation tree.
060         * The arity of the program is calculated from the given operation tree and
061         * set to the maximal arity of the operations of the tree.
062         *
063         * @param name the program name
064         * @param tree the operation tree
065         * @throws NullPointerException if one of the given arguments is {@code null}
066         * @throws IllegalArgumentException if the given operation tree is invalid,
067         *         which means there is at least one node where the operation arity
068         *         and the node child count differ.
069         */
070        public Program(final String name, final Tree<? extends Op<T>, ?> tree) {
071                _name = requireNonNull(name);
072                _tree = requireNonNull(tree);
073                check(tree);
074        }
075
076        @Override
077        public String name() {
078                return _name;
079        }
080
081        @Override
082        public int arity() {
083                return 0;
084        }
085
086        /**
087         * Return the underlying expression tree.
088         *
089         * @since 4.1
090         *
091         * @return the underlying expression tree
092         */
093        public Tree<Op<T>, ?> tree() {
094                return TreeNode.ofTree(_tree);
095        }
096
097        @Override
098        public T apply(final T[] args) {
099                if (args.length < arity()) {
100                        throw new IllegalArgumentException(format(
101                                "Arguments length is smaller than program arity: %d < %d",
102                                args.length, arity()
103                        ));
104                }
105
106                return eval(_tree, args);
107        }
108
109        /**
110         * Convenient method, which lets you apply the program function without
111         * explicitly create a wrapper array.
112         *
113         * @see #apply(Object[])
114         *
115         * @param args the function arguments
116         * @return the evaluated value
117         * @throws NullPointerException if the given variable array is {@code null}
118         * @throws IllegalArgumentException if the length of the argument array
119         *         is smaller than the program arity
120         */
121        @SafeVarargs
122        public final T eval(final T... args) {
123                return apply(args);
124        }
125
126        @Override
127        public int hashCode() {
128                return hash(_name, hash(_tree));
129        }
130
131        @Override
132        public boolean equals(final Object obj) {
133                return obj == this ||
134                        obj instanceof Program<?> other &&
135                        Objects.equals(other._name, _name) &&
136                        Objects.equals(other._tree, _tree);
137        }
138
139        @Override
140        public String toString() {
141                return _name;
142        }
143
144
145        /* *************************************************************************
146         * Static helper methods.
147         * ************************************************************************/
148
149        /**
150         * Evaluates the given operation tree with the given variables. This method
151         * is equivalent to
152         * {@snippet lang="java":
153         * final T result = tree.reduce(variables, Op::apply);
154         * }
155         * but handles the variable sized {@code variables} array more conveniently.
156         *
157         * @see Tree#reduce(Object[], BiFunction)
158         *
159         * @param <T> the argument type
160         * @param tree the operation tree
161         * @param variables the input variables
162         * @return the result of the operation tree evaluation
163         * @throws NullPointerException if one of the arguments is {@code null}
164         * @throws IllegalArgumentException if the length of the variable array
165         *         is smaller than the program arity
166         */
167        @SafeVarargs
168        public static <T> T eval(
169                final Tree<? extends Op<T>, ?> tree,
170                final T... variables
171        ) {
172                return tree.reduce(variables, Function::apply);
173        }
174
175        /**
176         * Validates the given program tree.
177         *
178         * @param program the program to validate
179         * @throws NullPointerException if the given {@code program} is {@code null}
180         * @throws IllegalArgumentException if the given operation tree is invalid,
181         *         which means there is at least one node where the operation arity
182         *         and the node child count differ.
183         */
184        public static void check(final Tree<? extends Op<?>, ?> program) {
185                program.forEach(Program::checkArity);
186        }
187
188        private static void checkArity(final Tree<? extends Op<?>, ?> node) {
189                if (node.value() != null &&
190                        node.value().arity() != node.childCount())
191                {
192                        throw new IllegalArgumentException(format(
193                                "Op arity != child count: %d != %d",
194                                node.value().arity(), node.childCount()
195                        ));
196                }
197        }
198
199        /**
200         * Create a new, random program from the given (non) terminal operations
201         * with the desired depth. The created program tree is a <em>full</em> tree.
202         *
203         * @since 4.1
204         *
205         * @param name the program name
206         * @param depth the desired depth of the program tree
207         * @param operations the list of <em>non</em>-terminal operations
208         * @param terminals the list of terminal operations
209         * @param <A> the operational type
210         * @return a new program
211         * @throws NullPointerException if one of the given operations is
212         *        {@code null}
213         * @throws IllegalArgumentException if the given tree depth is smaller than
214         *         zero
215         */
216        public static <A> Program<A> of(
217                final String name,
218                final int depth,
219                final ISeq<? extends Op<A>> operations,
220                final ISeq<? extends Op<A>> terminals
221        ) {
222                return new Program<>(name, of(depth, operations, terminals));
223        }
224
225        /**
226         * Create a new, random program from the given (non) terminal operations
227         * with the desired depth. The created program tree is a <em>full</em> tree.
228         *
229         * @since 4.1
230         *
231         * @param name the program name
232         * @param depth the desired depth of the program tree
233         * @param operations the list of <em>non</em>-terminal operations
234         * @param terminals the list of terminal operations
235         * @param random the random engine used for creating the program
236         * @param <A> the operational type
237         * @return a new program
238         * @throws NullPointerException if one of the given operations is
239         *        {@code null}
240         * @throws IllegalArgumentException if the given tree depth is smaller than
241         *         zero
242         */
243        public static <A> Program<A> of(
244                final String name,
245                final int depth,
246                final ISeq<? extends Op<A>> operations,
247                final ISeq<? extends Op<A>> terminals,
248                final RandomGenerator random
249        ) {
250                return new Program<>(name, of(depth, operations, terminals, random));
251        }
252
253        /**
254         * Create a new, random program tree from the given (non) terminal
255         * operations with the desired depth. The created program tree is a
256         * <em>full</em> tree.
257         *
258         * @param depth the desired depth of the program tree
259         * @param operations the list of <em>non</em>-terminal operations
260         * @param terminals the list of terminal operations
261         * @param <A> the operational type
262         * @return a new program tree
263         * @throws NullPointerException if one of the given operations is
264         *        {@code null}
265         * @throws IllegalArgumentException if the given tree depth is smaller than
266         *         zero
267         */
268        public static <A> TreeNode<Op<A>> of(
269                final int depth,
270                final ISeq<? extends Op<A>> operations,
271                final ISeq<? extends Op<A>> terminals
272        ) {
273                return of(depth, operations, terminals, RandomRegistry.random());
274        }
275
276        /**
277         * Create a new, random program tree from the given (non) terminal
278         * operations with the desired depth. The created program tree is a
279         * <em>full</em> tree.
280         *
281         * @since 4.1
282         *
283         * @param depth the desired depth of the program tree
284         * @param operations the list of <em>non</em>-terminal operations
285         * @param terminals the list of terminal operations
286         * @param random the random engine used for creating the program
287         * @param <A> the operational type
288         * @return a new program tree
289         * @throws NullPointerException if one of the given operations is
290         *        {@code null}
291         * @throws IllegalArgumentException if the given tree depth is smaller than
292         *         zero
293         */
294        public static <A> TreeNode<Op<A>> of(
295                final int depth,
296                final ISeq<? extends Op<A>> operations,
297                final ISeq<? extends Op<A>> terminals,
298                final RandomGenerator random
299        ) {
300                if (depth < 0) {
301                        throw new IllegalArgumentException(
302                                "Tree depth is smaller than zero: " + depth
303                        );
304                }
305                if (!operations.forAll(o -> !o.isTerminal())) {
306                        throw new IllegalArgumentException(
307                                "Operation list contains terminal op."
308                        );
309                }
310                if (!terminals.forAll(Op::isTerminal)) {
311                        throw new IllegalArgumentException(
312                                "Terminal list contains non-terminal op."
313                        );
314                }
315
316                final TreeNode<Op<A>> root = TreeNode.of();
317                fill(depth, root, operations, terminals, random);
318                return root;
319        }
320
321        private static <A> void fill(
322                final int level,
323                final TreeNode<Op<A>> tree,
324                final ISeq<? extends Op<A>> operations,
325                final ISeq<? extends Op<A>> terminals,
326                final RandomGenerator random
327        ) {
328                final Op<A> op = level == 0
329                        ? terminals.get(random.nextInt(terminals.size()))
330                        : operations.get(random.nextInt(operations.size()));
331
332                tree.value(op);
333
334                if (level > 1) {
335                        for (int i = 0; i < op.arity(); ++i) {
336                                final TreeNode<Op<A>> node = TreeNode.of();
337                                fill(level - 1, node, operations, terminals, random);
338                                tree.attach(node);
339                        }
340                } else {
341                        for (int i = 0; i < op.arity(); ++i) {
342                                final Op<A> term = terminals.get(random.nextInt(terminals.size()));
343                                tree.attach(TreeNode.of(term));
344                        }
345                }
346        }
347
348        /**
349         * Creates a valid program tree from the given flattened sequence of
350         * op nodes. The given {@code operations} and {@code termination} nodes are
351         * used for <em>repairing</em> the program tree, if necessary.
352         *
353         * @param nodes the flattened, possible corrupt, program tree
354         * @param terminals the usable non-terminal operation nodes to use for
355         *        reparation
356         * @param <A> the operation argument type
357         * @return a new valid program tree build from the flattened program tree
358         * @throws NullPointerException if one of the arguments is {@code null}
359         * @throws IllegalArgumentException if the {@code nodes} sequence is empty
360         */
361        public static <A> TreeNode<Op<A>> toTree(
362                final ISeq<? extends FlatTree<? extends Op<A>, ?>> nodes,
363                final ISeq<? extends Op<A>> terminals
364        ) {
365                if (nodes.isEmpty()) {
366                        throw new IllegalArgumentException("Tree nodes must not be empty.");
367                }
368
369                final Op<A> op = requireNonNull(nodes.get(0).value());
370                final TreeNode<Op<A>> tree = TreeNode.of(op);
371                return toTree(
372                        tree,
373                        0,
374                        nodes,
375                        offsets(nodes),
376                        terminals,
377                        RandomRegistry.random()
378                );
379        }
380
381        private static <A> TreeNode<Op<A>> toTree(
382                final TreeNode<Op<A>> root,
383                final int index,
384                final ISeq<? extends FlatTree<? extends Op<A>, ?>> nodes,
385                final int[] offsets,
386                final ISeq<? extends Op<A>> terminals,
387                final RandomGenerator random
388        ) {
389                if (index < nodes.size()) {
390                        final FlatTree<? extends Op<A>, ?> node = nodes.get(index);
391                        final Op<A> op = node.value();
392
393                        for (int i  = 0; i < op.arity(); ++i) {
394                                assert offsets[index] != -1;
395
396                                final TreeNode<Op<A>> treeNode = TreeNode.of();
397                                if (offsets[index] + i < nodes.size()) {
398                                        treeNode.value(nodes.get(offsets[index] + i).value());
399                                } else {
400                                        treeNode.value(terminals.get(random.nextInt(terminals.size())));
401                                }
402
403                                toTree(
404                                        treeNode,
405                                        offsets[index] + i,
406                                        nodes,
407                                        offsets,
408                                        terminals,
409                                        random
410                                );
411                                root.attach(treeNode);
412                        }
413                }
414
415                return root;
416        }
417
418        /**
419         * Create the offset array for the given nodes. The offsets are calculated
420         * using the arity of the stored operations.
421         *
422         * @param nodes the flattened tree nodes
423         * @return the offset array for the given nodes
424         */
425        static int[]
426        offsets(final ISeq<? extends FlatTree<? extends Op<?>, ?>> nodes) {
427                final int[] offsets = new int[nodes.size()];
428
429                int offset = 1;
430                for (int i = 0; i < offsets.length; ++i) {
431                        final Op<?> op = nodes.get(i).value();
432
433                        offsets[i] = op.isTerminal() ? -1 : offset;
434                        offset += op.arity();
435                }
436
437                return offsets;
438        }
439
440}