TreeRewriter.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-8.0.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  */
020 package io.jenetics.ext.rewriting;
021 
022 import static java.lang.String.format;
023 import static java.util.Objects.requireNonNull;
024 
025 import java.util.List;
026 
027 import 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
058 public 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 > && 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 }