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