001/*
002 * Java Genetic Algorithm Library (jenetics-7.2.0).
003 * Copyright (c) 2007-2023 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.util;
021
022import static java.util.Objects.requireNonNull;
023import static io.jenetics.internal.util.SerialIO.readIntArray;
024import static io.jenetics.internal.util.SerialIO.readObjectArray;
025import static io.jenetics.internal.util.SerialIO.writeIntArray;
026import static io.jenetics.internal.util.SerialIO.writeObjectArray;
027
028import java.io.IOException;
029import java.io.InvalidObjectException;
030import java.io.ObjectInput;
031import java.io.ObjectInputStream;
032import java.io.ObjectOutput;
033import java.io.Serial;
034import java.io.Serializable;
035import java.lang.reflect.Array;
036import java.util.Arrays;
037import java.util.Iterator;
038import java.util.Optional;
039import java.util.function.BiFunction;
040import java.util.function.Function;
041import java.util.stream.IntStream;
042import java.util.stream.Stream;
043
044import io.jenetics.util.ISeq;
045
046/**
047 * Default implementation of the {@link FlatTree} interface. Beside the
048 * flattened and dense layout it is also an <em>immutable</em> implementation of
049 * the {@link Tree} interface. It can only be created from an existing tree.
050 *
051 * <pre>{@code
052 * final Tree<String, ?> immutable = FlatTreeNode.ofTree(TreeNode.parse(...));
053 * }</pre>
054 *
055 * @implNote
056 * This class is immutable and thread-safe.
057 *
058 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
059 * @version 7.1
060 * @since 3.9
061 */
062public final class FlatTreeNode<V>
063        implements
064                FlatTree<V, FlatTreeNode<V>>,
065                Serializable
066{
067
068        /**
069         * The flattened tree nodes.
070         */
071        private record Nodes(Object[] values, int[] childOffsets, int[] childCounts) {
072                Nodes(final int size) {
073                        this(new Object[size], new int[size], new int[size]);
074                }
075        }
076
077        @Serial
078        private static final long serialVersionUID = 3L;
079
080        private static final int NULL_INDEX = -1;
081
082        private final Nodes _nodes;
083        private final int _index;
084
085        private FlatTreeNode(final Nodes nodes, final int index) {
086                _nodes = requireNonNull(nodes);
087                _index = index;
088        }
089
090        private FlatTreeNode(final Nodes nodes) {
091                this(nodes, 0);
092        }
093
094        /**
095         * Returns the root of the tree that contains this node. The root is the
096         * ancestor with no parent. This implementation has a runtime complexity
097         * of O(1).
098         *
099         * @return the root of the tree that contains this node
100         */
101        @Override
102        public FlatTreeNode<V> root() {
103                return nodeAt(0);
104        }
105
106        @Override
107        public boolean isRoot() {
108                return _index == 0;
109        }
110
111        private FlatTreeNode<V> nodeAt(final int index) {
112                return new FlatTreeNode<>(_nodes, index);
113        }
114
115        @SuppressWarnings("unchecked")
116        @Override
117        public V value() {
118                return (V)_nodes.values[_index];
119        }
120
121        @Override
122        public Optional<FlatTreeNode<V>> parent() {
123                int index = NULL_INDEX;
124                for (int i = _index; --i >= 0 && index == NULL_INDEX;) {
125                        if (isParent(i)) {
126                                index = i;
127                        }
128                }
129
130                return index != NULL_INDEX
131                        ? Optional.of(nodeAt(index))
132                        : Optional.empty();
133        }
134
135        private boolean isParent(final int index) {
136                return _nodes.childCounts[index] > 0 &&
137                        _nodes.childOffsets[index] <= _index &&
138                        _nodes.childOffsets[index] + _nodes.childCounts[index] > _index;
139        }
140
141        @Override
142        public FlatTreeNode<V> childAt(final int index) {
143                if (index < 0 || index >= childCount()) {
144                        throw new IndexOutOfBoundsException(Integer.toString(index));
145                }
146
147                return nodeAt(childOffset() + index);
148        }
149
150        @Override
151        public int childCount() {
152                return _nodes.childCounts[_index];
153        }
154
155        /**
156         * Return the index of the first child node in the underlying node array.
157         * {@code -1} is returned if {@code this} node is a leaf.
158         *
159         * @return Return the index of the first child node in the underlying node
160         *         array, or {@code -1} if {@code this} node is a leaf
161         */
162        @Override
163        public int childOffset() {
164                return _nodes.childOffsets[_index];
165        }
166
167        @Override
168        public ISeq<FlatTreeNode<V>> flattenedNodes() {
169                return stream().collect(ISeq.toISeq());
170        }
171
172        @Override
173        public Iterator<FlatTreeNode<V>> breadthFirstIterator() {
174                return isRoot()
175                        ? new IntFunctionIterator<>(this::nodeAt, _nodes.values.length)
176                        : FlatTree.super.breadthFirstIterator();
177        }
178
179        @Override
180        public Stream<FlatTreeNode<V>> breadthFirstStream() {
181                return isRoot()
182                        ? IntStream.range(0, _nodes.values.length).mapToObj(this::nodeAt)
183                        : FlatTree.super.breadthFirstStream();
184        }
185
186        /**
187         * Return a sequence of all <em>mapped</em> nodes of the whole underlying
188         * tree. This is a convenient method for
189         * <pre>{@code
190         * final ISeq<B> seq = stream()
191         *     .map(mapper)
192         *     .collect(ISeq.toISeq())
193         * }</pre>
194         *
195         * @param mapper the mapper function
196         * @param <B> the mapped type
197         * @return a sequence of all <em>mapped</em> nodes
198         */
199        public <B> ISeq<B>
200        map(final Function<? super FlatTreeNode<V>, ? extends B> mapper) {
201                return stream()
202                        .map(mapper)
203                        .collect(ISeq.toISeq());
204        }
205
206        @Override
207        public boolean identical(final Tree<?, ?> other) {
208                return other == this ||
209                        other instanceof FlatTreeNode<?> node &&
210                        node._index == _index &&
211                        node._nodes == _nodes;
212        }
213
214        @Override
215        public <U> U reduce(
216                final U[] neutral,
217                final BiFunction<? super V, ? super U[], ? extends U> reducer
218        ) {
219                requireNonNull(neutral);
220                requireNonNull(reducer);
221
222                @SuppressWarnings("unchecked")
223                final class Reducing {
224                        private U reduce(final int index) {
225                                return _nodes.childCounts[index] == 0
226                                        ? reducer.apply((V)_nodes.values[index], neutral)
227                                        : reducer.apply((V)_nodes.values[index], children(index));
228                        }
229                        private U[] children(final int index) {
230                                final U[] values = (U[])Array.newInstance(
231                                        neutral.getClass().getComponentType(),
232                                        _nodes.childCounts[index]
233                                );
234                                for (int i = 0; i < _nodes.childCounts[index]; ++i) {
235                                        values[i] = reduce(_nodes.childOffsets[index] + i);
236                                }
237                                return values;
238                        }
239                }
240
241                return isEmpty() ? null : new Reducing().reduce(_index);
242        }
243
244        @Override
245        public int hashCode() {
246                return Tree.hashCode(this);
247        }
248
249        @Override
250        public boolean equals(final Object obj) {
251                return obj == this ||
252                        (obj instanceof FlatTreeNode<?> ftn && equals(ftn)) ||
253                        (obj instanceof Tree<?, ?> tree && Tree.equals(tree, this));
254        }
255
256        private boolean equals(final FlatTreeNode<?> tree) {
257                return tree._index == _index &&
258                        Arrays.equals(tree._nodes.values, _nodes.values) &&
259                        Arrays.equals(tree._nodes.childCounts, _nodes.childCounts) &&
260                        Arrays.equals(tree._nodes.childOffsets, _nodes.childOffsets);
261        }
262
263        @Override
264        public String toString() {
265                return toParenthesesString();
266        }
267
268        @Override
269        public int size() {
270                return isRoot()
271                        ? _nodes.values.length
272                        : countChildren(_index) + 1;
273        }
274
275        private int countChildren(final int index) {
276                int count = _nodes.childCounts[index];
277                for (int i = 0; i < _nodes.childCounts[index]; ++i) {
278                        count += countChildren(_nodes.childOffsets[index] + i);
279                }
280                return count;
281        }
282
283        /* *************************************************************************
284         *  Static factories
285         * ************************************************************************/
286
287        /**
288         * Create a new, immutable {@code FlatTreeNode} from the given {@code tree}.
289         *
290         * @param tree the source tree
291         * @param <V> the tree value types
292         * @return a {@code FlatTreeNode} from the given {@code tree}
293         * @throws NullPointerException if the given {@code tree} is {@code null}
294         */
295        public static <V> FlatTreeNode<V> ofTree(final Tree<? extends V, ?> tree) {
296                requireNonNull(tree);
297
298                if (tree instanceof FlatTreeNode<?> ft && ft.isRoot()) {
299                        @SuppressWarnings("unchecked")
300                        final var result = (FlatTreeNode<V>)ft;
301                        return result;
302                }
303
304                final int size = tree.size();
305                assert size >= 1;
306
307                final var nodes = new Nodes(size);
308
309                int childOffset = 1;
310                int index = 0;
311
312                for (var node : tree) {
313                        nodes.values[index] = node.value();
314                        nodes.childCounts[index] = node.childCount();
315                        nodes.childOffsets[index] = node.isLeaf() ? NULL_INDEX : childOffset;
316
317                        childOffset += node.childCount();
318                        ++index;
319                }
320                assert index == size;
321
322                return new FlatTreeNode<>(nodes);
323        }
324
325        /**
326         * Parses a (parentheses) tree string, created with
327         * {@link Tree#toParenthesesString()}. The tree string might look like this:
328         * <pre>
329         *  mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
330         * </pre>
331         *
332         * @see Tree#toParenthesesString(Function)
333         * @see Tree#toParenthesesString()
334         * @see TreeNode#parse(String)
335         *
336         * @since 5.0
337         *
338         * @param tree the parentheses tree string
339         * @return the parsed tree
340         * @throws NullPointerException if the given {@code tree} string is
341         *         {@code null}
342         * @throws IllegalArgumentException if the given tree string could not be
343         *         parsed
344         */
345        public static FlatTreeNode<String> parse(final String tree) {
346                return ofTree(ParenthesesTreeParser.parse(tree, Function.identity()));
347        }
348
349        /**
350         * Parses a (parentheses) tree string, created with
351         * {@link Tree#toParenthesesString()}. The tree string might look like this
352         * <pre>
353         *  0(1(4,5),2(6),3(7(10,11),8,9))
354         * </pre>
355         * and can be parsed to an integer tree with the following code:
356         * <pre>{@code
357         * final Tree<Integer, ?> tree = FlatTreeNode.parse(
358         *     "0(1(4,5),2(6),3(7(10,11),8,9))",
359         *     Integer::parseInt
360         * );
361         * }</pre>
362         *
363         * @see Tree#toParenthesesString(Function)
364         * @see Tree#toParenthesesString()
365         * @see TreeNode#parse(String, Function)
366         *
367         * @since 5.0
368         *
369         * @param <B> the tree node value type
370         * @param tree the parentheses tree string
371         * @param mapper the mapper which converts the serialized string value to
372         *        the desired type
373         * @return the parsed tree object
374         * @throws NullPointerException if one of the arguments is {@code null}
375         * @throws IllegalArgumentException if the given parentheses tree string
376         *         doesn't represent a valid tree
377         */
378        public static <B> FlatTreeNode<B> parse(
379                final String tree,
380                final Function<? super String, ? extends B> mapper
381        ) {
382                return ofTree(ParenthesesTreeParser.parse(tree, mapper));
383        }
384
385
386        /* *************************************************************************
387         *  Java object serialization
388         * ************************************************************************/
389
390        @Serial
391        private Object writeReplace() {
392                return new SerialProxy(SerialProxy.FLAT_TREE_NODE, this);
393        }
394
395        @Serial
396        private void readObject(final ObjectInputStream stream)
397                throws InvalidObjectException
398        {
399                throw new InvalidObjectException("Serialization proxy required.");
400        }
401
402
403        void write(final ObjectOutput out) throws IOException {
404                final FlatTreeNode<V> node = isRoot()
405                        ? this
406                        : FlatTreeNode.ofTree(this);
407
408                writeObjectArray(node._nodes.values, out);
409                writeIntArray(node._nodes.childOffsets, out);
410                writeIntArray(node._nodes.childCounts, out);
411        }
412
413        @SuppressWarnings("rawtypes")
414        static FlatTreeNode read(final ObjectInput in)
415                throws IOException, ClassNotFoundException
416        {
417                return new FlatTreeNode(new Nodes(
418                        readObjectArray(in),
419                        readIntArray(in),
420                        readIntArray(in)
421                ));
422        }
423
424}