001 /*
002 * Java Genetic Algorithm Library (jenetics-6.0.0).
003 * Copyright (c) 2007-2020 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 the 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 the 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 }
|