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