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.rewriting;
021
022import static java.lang.String.format;
023import static java.util.Objects.requireNonNull;
024
025import java.util.List;
026
027import io.jenetics.ext.util.TreeNode;
028
029/**
030 * Interface for rewriting a given tree. The rewrite is performed on a mutable
031 * {@link TreeNode} and is done in place.
032 * <p>
033 * <b>Description from <a href="https://en.wikipedia.org/wiki/Rewriting">
034 *     Wikipedia: </a></b>
035 * <em>
036 *     In mathematics, computer science, and logic, rewriting covers a wide
037 *     range of (potentially non-deterministic) methods of replacing sub-terms
038 *     of a formula with other terms. In their most basic form, they consist of
039 *     a set of objects, plus relations on how to transform those objects.
040 *     Rewriting can be non-deterministic. One rule to rewrite a term could be
041 *     applied in many different ways to that term, or more than one rule could
042 *     be applicable. Rewriting systems then do not provide an algorithm for
043 *     changing one term to another, but a set of possible rule applications.
044 *     When combined with an appropriate algorithm, however, rewrite systems can
045 *     be viewed as computer programs, and several theorem provers and
046 *     declarative programming languages are based on term rewriting.
047 * </em>
048 * </p>
049 *
050 * @apiNote
051 * The rewriting is done in place, to a mutable {@link TreeNode} object.
052 *
053 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
054 * @version 5.0
055 * @since 5.0
056 */
057@FunctionalInterface
058public interface TreeRewriter<V> {
059
060        /**
061         * Applies the rewriting to the given (mutable) {@code tree}. The tree
062         * rewrite is done in place. Via the {@code limit} parameter, the termination
063         * of the tree-rewrite process can be guaranteed.
064         *
065         * @param tree the tree to be rewritten
066         * @param limit the maximal number this rewrite rule is applied to the given
067         *        tree. This guarantees the termination of the rewrite method.
068         * @return the number of rewrites applied to the input {@code tree}
069         * @throws NullPointerException if the given {@code tree} is {@code null}
070         * @throws IllegalArgumentException if the {@code limit} is smaller than
071         *         one
072         */
073        int rewrite(final TreeNode<V> tree, final int limit);
074
075        /**
076         * Applies the rewriting to the given (mutable) {@code tree}. The tree
077         * rewrite is done in place. The limit of the applied rewrites is set
078         * unlimited ({@link Integer#MAX_VALUE}).
079         *
080         * @see #rewrite(TreeNode, int)
081         *
082         * @param tree the tree to be rewritten
083         * @return {@code true} if the tree has been changed (rewritten) by this
084         *         method, {@code false} if the tree hasn't been changed
085         * @throws NullPointerException if the given {@code tree} is {@code null}
086         */
087        default int rewrite(final TreeNode<V> tree) {
088                return rewrite(tree, Integer.MAX_VALUE);
089        }
090
091
092        /* *************************************************************************
093         * Static helper functions.
094         * *************************************************************************/
095
096        /**
097         * Rewrites the given {@code tree} by applying the given {@code rewriters}.
098         * This method to apply all rewriters, in the order they are given in
099         * the sequence, until the tree stays unchanged.
100         *
101         * @param <V> the tree value type
102         * @param tree the tree to rewrite
103         * @param limit the maximal number this rewrite rule is applied to the given
104         *        tree. This guarantees the termination of the rewrite method.
105         * @param rewriters the rewriters applied to the tree
106         * @return {@code true} if the tree has been changed (rewritten) by this
107         *         method, {@code false} if the tree hasn't been changed
108         * @throws NullPointerException if one of the arguments is {@code null}
109         * @throws IllegalArgumentException if the {@code limit} is smaller than
110         *         zero
111         */
112        static <V> int rewrite(
113                final TreeNode<V> tree,
114                final int limit,
115                final Iterable<? extends TreeRewriter<V>> rewriters
116        ) {
117                requireNonNull(tree);
118                requireNonNull(rewriters);
119                if (limit < 0) {
120                        throw new IllegalArgumentException(format(
121                                "Limit is smaller then zero: %d", limit
122                        ));
123                }
124
125                int rewritten = 0;
126                int count = 0;
127                do {
128                        count = 0;
129                        for (TreeRewriter<V> rw : rewriters) {
130                                count += rw.rewrite(tree, limit - rewritten);
131                        }
132
133                        rewritten += count;
134                } while(count > 0 && rewritten < limit);
135
136                return rewritten;
137        }
138
139        /**
140         * Rewrites the given {@code tree} by applying the given {@code rewriters}.
141         * This method to apply all rewriters, in the order they are given in
142         * the sequence, until the tree stays unchanged.
143         *
144         * @see #rewrite(TreeNode, int, Iterable)
145         *
146         * @param tree the tree to rewrite
147         * @param rewriters the rewriters applied to the tree
148         * @param <V> the tree value type
149         * @return {@code true} if the tree has been changed (rewritten) by this
150         *         method, {@code false} if the tree hasn't been changed
151         * @throws NullPointerException if one of the arguments is {@code null}
152         */
153        static <V> int rewrite(
154                final TreeNode<V> tree,
155                final Iterable<? extends TreeRewriter<V>> rewriters
156        ) {
157                return rewrite(tree, Integer.MAX_VALUE, rewriters);
158        }
159
160        /**
161         * Concat the given {@code rewriters} to one tree-rewriter.
162         *
163         * @param rewriters the tree-rewriter to concatenate
164         * @param <V> the tree value type
165         * @return a new tree-rewriter which concatenates the given one
166         * @throws NullPointerException if the given {@code rewriters} are
167         *         {@code null}
168         * @throws IllegalArgumentException if the {@code limit} is smaller than
169         *         zero
170         */
171        @SafeVarargs
172        static <V> TreeRewriter<V>
173        concat(final TreeRewriter<V>... rewriters) {
174                if (rewriters.length == 0) {
175                        throw new IllegalArgumentException(
176                                "The given rewriter array must not be empty."
177                        );
178                }
179
180                return (tree, limit) -> rewrite(tree, limit, List.of(rewriters));
181        }
182}