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 io.jenetics.internal.util.SerialIO.readInt;
023 import static io.jenetics.internal.util.SerialIO.writeInt;
024
025 import java.io.IOException;
026 import java.io.InvalidObjectException;
027 import java.io.ObjectInput;
028 import java.io.ObjectOutput;
029 import java.io.ObjectOutputStream;
030 import java.io.Serializable;
031 import java.util.Objects;
032 import java.util.function.Function;
033 import java.util.stream.Collectors;
034
035 import io.jenetics.util.ISeq;
036 import io.jenetics.util.MSeq;
037
038 import io.jenetics.ext.util.TreeNode;
039
040 /**
041 * This class represents a Tree Rewrite System, which consists of a set of
042 * Tree Rewrite Rules.
043 * <pre>{@code
044 * final TRS<String> trs = TRS.parse(
045 * "add(0,$x) -> $x",
046 * "add(S($x),$y) -> S(add($x,$y))",
047 * "mul(0,$x) -> 0",
048 * "mul(S($x),$y) -> add(mul($x,$y),$y)"
049 * );
050 *
051 * // Converting the input tree into its normal form.
052 * final TreeNode<String> tree = TreeNode.parse("add(S(0),S(mul(S(0),S(S(0)))))");
053 * trs.rewrite(tree);
054 * assert tree.equals(TreeNode.parse("S(S(S(S(0))))"));
055 * }</pre>
056 *
057 * @see TreeRewriteRule
058 * @see <a href="https://en.wikipedia.org/wiki/Rewriting">TRS</a>
059 *
060 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
061 * @version 5.0
062 * @since 5.0
063 */
064 public final class TRS<V> implements TreeRewriter<V>, Serializable {
065
066 private static final long serialVersionUID = 1L;
067
068 private final ISeq<TreeRewriteRule<V>> _rules;
069
070 /**
071 * Create a new TRS from the given rewrite rules.
072 *
073 * @param rules the rewrite rules the TRS consists of
074 * @throws NullPointerException if the given {@code rules} are {@code null}
075 * @throws IllegalArgumentException if the given {@code rules} sequence is
076 * empty
077 */
078 public TRS(final ISeq<TreeRewriteRule<V>> rules) {
079 if (rules.isEmpty()) {
080 throw new IllegalArgumentException("Rewrite rules must not be empty.");
081 }
082 _rules = rules;
083 }
084
085 @Override
086 public int rewrite(final TreeNode<V> tree, final int limit) {
087 return TreeRewriter.rewrite(tree, limit, _rules);
088 }
089
090 /**
091 * Maps {@code this} TRS from type {@code V} to type {@code B}.
092 *
093 * @param mapper the type mapper
094 * @param <B> the target type
095 * @return a new TRS for the mapped type
096 * @throws NullPointerException if the {@code mapper} is {@code null}
097 */
098 public <B> TRS<B> map(final Function<? super V, ? extends B> mapper) {
099 return new TRS<>(_rules.map(rule -> rule.map(mapper)));
100 }
101
102 @Override
103 public int hashCode() {
104 return _rules.hashCode();
105 }
106
107 @Override
108 public boolean equals(final Object obj) {
109 return obj == this ||
110 obj instanceof TRS &&
111 _rules.equals(((TRS)obj)._rules);
112 }
113
114 @Override
115 public String toString() {
116 return _rules.stream()
117 .map(Objects::toString)
118 .collect(Collectors.joining("; "));
119 }
120
121 /**
122 * Create a new TRS from the given rewrite rules and type mapper.
123 *
124 * @param mapper the tree value type mapper
125 * @param rules the rewrite rules
126 * @param <V> the tree value type the rewriter is working on
127 * @return a new TRS
128 * @throws NullPointerException if one of the arguments is {@code null}
129 * @throws IllegalArgumentException if the given {@code rules} sequence is
130 * empty
131 */
132 public static <V> TRS<V> parse(
133 final Function<? super String, ? extends V> mapper,
134 final String... rules
135 ) {
136 return new TRS<>(
137 ISeq.of(rules)
138 .map(rule -> TreeRewriteRule.parse(rule, mapper))
139 );
140 }
141
142 /**
143 * Create a new TRS from the given rewrite rules.
144 *
145 * @param rules the rewrite rules
146 * @return a new TRS
147 * @throws NullPointerException if one of the arguments is {@code null}
148 * @throws IllegalArgumentException if the given {@code rules} sequence is
149 * empty
150 */
151 public static TRS<String> parse(final String... rules) {
152 return parse(Function.identity(), rules);
153 }
154
155 /* *************************************************************************
156 * Java object serialization
157 * ************************************************************************/
158
159 private Object writeReplace() {
160 return new Serial(Serial.TRS_KEY, this);
161 }
162
163 private void readObject(final ObjectOutputStream stream)
164 throws InvalidObjectException
165 {
166 throw new InvalidObjectException("Serialization proxy required.");
167 }
168
169 void write(final ObjectOutput out) throws IOException {
170 writeInt(_rules.length(), out);
171 for (int i = 0; i < _rules.length(); ++i) {
172 out.writeObject(_rules.get(i));
173 }
174 }
175
176 @SuppressWarnings({"unchecked", "rawtypes"})
177 static Object read(final ObjectInput in)
178 throws IOException, ClassNotFoundException
179 {
180 final var length = readInt(in);
181 final var rules = MSeq.ofLength(length);
182 for (int i = 0; i < length; ++i) {
183 rules.set(i, in.readObject());
184 }
185
186 return new TRS(rules.toISeq());
187 }
188
189 }
|