TRS.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-5.1.0).
003  * Copyright (c) 2007-2019 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 outthrows 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 TRS read(final ObjectInput in)
178         throws IOException, ClassNotFoundException
179     {
180         final int length = readInt(in);
181         final MSeq 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 }