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.lang.String.format;
023import static java.util.Objects.requireNonNull;
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.ArrayList;
033import java.util.Collections;
034import java.util.Iterator;
035import java.util.List;
036import java.util.Optional;
037import java.util.function.Function;
038import java.util.stream.Stream;
039
040import io.jenetics.util.Copyable;
041
042/**
043 * A general purpose node in a tree data-structure. The {@code TreeNode} is a
044 * mutable implementation of the {@link Tree} interface.
045 *
046 * @param <T> the value type of the tree node
047 *
048 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
049 * @version 5.2
050 * @since 3.9
051 */
052public final class TreeNode<T>
053        implements
054                Tree<T, TreeNode<T>>,
055                Iterable<TreeNode<T>>,
056                Copyable<TreeNode<T>>,
057                Serializable
058{
059        @Serial
060        private static final long serialVersionUID = 2L;
061
062        private T _value;
063        private TreeNode<T> _parent;
064        private List<TreeNode<T>> _children;
065
066        /**
067         * Create a new tree node with no parent and children, but with the given
068         * user {@code value}.
069         *
070         * @param value the user value of the new tree node
071         */
072        private TreeNode(final T value) {
073                _value = value;
074        }
075
076
077        /* *************************************************************************
078         * Basic operations
079         **************************************************************************/
080
081        /**
082         * Sets the user object for this node.
083         *
084         * @param value the node {@code value}
085         */
086        public void value(final T value) {
087                _value = value;
088        }
089
090        /**
091         * Return the node value
092         *
093         * @return the node value
094         */
095        @Override
096        public T value() {
097                return _value;
098        }
099
100        /**
101         * Returns this node's parent if available.
102         *
103         * @return the tree-node, or an empty value if this node has no parent
104         */
105        @Override
106        public Optional<TreeNode<T>> parent() {
107                return Optional.ofNullable(_parent);
108        }
109
110        /**
111         * Sets this node's parent, but does not change the parent's child array.
112         * This method is called from {@code insert()} and {@code remove()} to
113         * reassign a child's parent, and it should not be messaged from anywhere
114         * else.
115         *
116         * @param parent this node's new parent
117         */
118        void parent(final TreeNode<T> parent) {
119                _parent = parent;
120        }
121
122        /**
123         * Returns the child at the specified index in this node's child array.
124         *
125         * @param index   an index into this node's child array
126         * @return the tree-node in this node's child array at the specified index
127         * @throws ArrayIndexOutOfBoundsException  if the {@code index} is out of
128         *         bounds
129         */
130        @Override
131        public TreeNode<T> childAt(final int index) {
132                if (_children == null) {
133                        throw new ArrayIndexOutOfBoundsException(format(
134                                "Child index is out of bounds: %s", index
135                        ));
136                }
137
138                return _children.get(index);
139        }
140
141        @Override
142        public int childCount() {
143                return _children != null ? _children.size() : 0;
144        }
145
146        @Override
147        public Iterator<TreeNode<T>> childIterator() {
148                return _children != null
149                        ? _children.iterator()
150                        : Collections.emptyIterator();
151        }
152
153        @Override
154        public Stream<TreeNode<T>> childStream() {
155                return _children != null
156                        ? _children.stream()
157                        : Stream.empty();
158        }
159
160        /**
161         * Removes the {@code child} from its present parent (if it has one), sets
162         * the child's parent to this node, and then adds the child to this node's
163         * child array at index {@code index}. The new {@code child} must not be
164         * {@code null} and must not be an ancestor of {@code this} node.
165         *
166         * @param index the index in the child array where this node is to be
167         *        inserted
168         * @param child the sub-node to be inserted
169         * @return {@code this} tree-node, for method chaining
170         * @throws ArrayIndexOutOfBoundsException if {@code index} is out of bounds
171         * @throws IllegalArgumentException if {@code child} is an ancestor of
172         *         {@code this} node
173         * @throws NullPointerException if the given {@code child} is {@code null}
174         */
175        public TreeNode<T> insert(final int index, final TreeNode<T> child) {
176                requireNonNull(child);
177                if (isAncestor(child)) {
178                        throw new IllegalArgumentException("The new child is an ancestor.");
179                }
180
181                if (child._parent != null) {
182                        child._parent.remove(child);
183                }
184
185                child.parent(this);
186                createChildrenIfMissing();
187                _children.add(index, child);
188
189                return this;
190        }
191
192        // Only entry point for checking and creating a non-existing children list.
193        private void createChildrenIfMissing() {
194                if (_children == null) {
195                        _children = new ArrayList<>(2);
196                }
197        }
198
199        /**
200         * Replaces the child at the give index with the given {@code child}
201         *
202         * @param index the index of the child which will be replaced
203         * @param child the new child
204         * @return {@code this} tree-node, for method chaining
205         * @throws ArrayIndexOutOfBoundsException  if the {@code index} is out of
206         *         bounds
207         * @throws IllegalArgumentException if {@code child} is an ancestor of
208         *         {@code this} node
209         * @throws NullPointerException if the given {@code child} is {@code null}
210         */
211        public TreeNode<T> replace(final int index, final TreeNode<T> child) {
212                requireNonNull(child);
213                if (_children == null) {
214                        throw new ArrayIndexOutOfBoundsException(format(
215                                "Child index is out of bounds: %s", index
216                        ));
217                }
218                if (isAncestor(child)) {
219                        throw new IllegalArgumentException("The new child is an ancestor.");
220                }
221
222                final TreeNode<T> oldChild = _children.set(index, child);
223                assert oldChild != null;
224                assert oldChild._parent == this;
225
226                oldChild.parent(null);
227                child.parent(this);
228
229                return this;
230        }
231
232        /**
233         * Removes the child at the specified index from this node's children and
234         * sets that node's parent to {@code null}.
235         *
236         * @param index the index in this node's child array of the child to remove
237         * @return {@code this} tree-node, for method chaining
238         * @throws ArrayIndexOutOfBoundsException  if the {@code index} is out of
239         *         bounds
240         */
241        public TreeNode<T> remove(final int index) {
242                if (_children == null) {
243                        throw new ArrayIndexOutOfBoundsException(format(
244                                "Child index is out of bounds: %s", index
245                        ));
246                }
247
248                final TreeNode<T> child = _children.remove(index);
249                assert child._parent == this;
250                child.parent(null);
251
252                if (_children.isEmpty()) {
253                        _children = null;
254                }
255
256                return this;
257        }
258
259        /**
260         * Removes the child at the given {@code path}. If no child exists on the
261         * given path, nothing is removed.
262         *
263         * @since 4.4
264         *
265         * @param path the path of the child to replace
266         * @return {@code true} if a child at the given {@code path} existed and
267         *         has been removed
268         * @throws NullPointerException if one of the given arguments is {@code null}
269         */
270        public boolean removeAtPath(final Path path) {
271                final Optional<TreeNode<T>> parent = childAtPath(path)
272                        .flatMap(Tree::parent);
273
274                parent.ifPresent(p -> p.remove(path.get(path.length() - 1)));
275                return parent.isPresent();
276        }
277
278        /**
279         * Replaces the child at the given {@code path} with the given new
280         * {@code child}. If no child exists on the given path, nothing is replaced.
281         *
282         * @since 4.4
283         *
284         * @param path the path of the child to replace
285         * @param child the new child
286         * @return {@code true} if a child at the given {@code path} existed and
287         *         has been replaced
288         * @throws NullPointerException if one of the given arguments is {@code null}
289         */
290        public boolean replaceAtPath(final Path path, final TreeNode<T> child) {
291                requireNonNull(path);
292                requireNonNull(child);
293
294                final Optional<TreeNode<T>> old = childAtPath(path);
295                final Optional<TreeNode<T>> parent = old.flatMap(TreeNode::parent);
296
297                parent.ifPresentOrElse(
298                        p -> p.replace(path.get(path.length() - 1), child),
299                        () -> {
300                                removeAllChildren();
301                                value(child.value());
302
303                                // Need to create a copy of the children, before attaching it.
304                                final List<TreeNode<T>> nodes = child._children != null
305                                        ? List.copyOf(child._children)
306                                        : List.of();
307
308                                nodes.forEach(this::attach);
309                        }
310                );
311
312                return old.isPresent();
313        }
314
315        /* *************************************************************************
316         * Derived operations
317         **************************************************************************/
318
319        /**
320         * Detaches the subtree rooted at {@code this} node from the tree, giving
321         * {@code this} node a {@code null} parent. Does nothing if {@code this}
322         * node is the root of its tree.
323         *
324         * @return {@code this}
325         */
326        public TreeNode<T> detach() {
327                if (_parent != null) {
328                        _parent.remove(this);
329                }
330
331                return this;
332        }
333
334        /**
335         * Remove the {@code child} from {@code this} node's child array, giving it
336         * a {@code null} parent.
337         *
338         * @param child the child of this node to remove
339         * @throws NullPointerException if the given {@code child} is {@code null}
340         * @throws IllegalArgumentException if the given {@code child} is not a
341         *         child of this node
342         */
343        public void remove(final Tree<?, ?> child) {
344                requireNonNull(child);
345
346                if (!isChild(child)) {
347                        throw new IllegalArgumentException("The given child is not a child.");
348                }
349                remove(indexOf(child));
350        }
351
352        /**
353         * Removes all children fo {@code this} node and setting their parents to
354         * {@code null}. If {@code this} node has no children, this method does
355         * nothing.
356         */
357        public void removeAllChildren() {
358                if (_children != null) {
359                        for (TreeNode<T> child : _children) {
360                                child.parent(null);
361                        }
362
363                        _children = null;
364                }
365        }
366
367        /**
368         * Remove the given {@code child} from its parent and makes it a child of
369         * this node by adding it to the end of this node's child array.
370         *
371         * @param child the new child added to this node
372         * @return {@code this} tree-node, for method chaining
373         * @throws NullPointerException if the given {@code child} is {@code null}
374         */
375        public TreeNode<T> attach(final TreeNode<T> child) {
376                requireNonNull(child);
377
378                if (child._parent == this) {
379                        insert(childCount() - 1, child);
380                } else {
381                        insert(childCount(), child);
382                }
383
384                return this;
385        }
386
387        /**
388         * Attaches the given {@code children} to {@code this} node.
389         *
390         * @param children the children to attach to {@code this} node
391         * @return {@code this} tree-node, for method chaining
392         * @throws NullPointerException if the given {@code children} array is
393         *         {@code null}
394         */
395        @SafeVarargs
396        public final TreeNode<T> attach(final T... children) {
397                for (T child : children) {
398                        attach(TreeNode.of(child));
399                }
400
401                return this;
402        }
403
404        /**
405         * Attaches the given {@code child} to {@code this} node.
406         *
407         * @param child the child to attach to {@code this} node
408         * @return {@code this} tree-node, for method chaining
409         */
410        public TreeNode<T> attach(final T child) {
411                return attach(TreeNode.of(child));
412        }
413
414        @Override
415        public TreeNode<T> copy() {
416                return ofTree(this);
417        }
418
419        /**
420         * Returns a new {@code TreeNode} consisting of all nodes of {@code this}
421         * tree, but with a different value type, created by applying the given
422         * function to the node values of {@code this} tree.
423         *
424         * @param mapper the node value mapper
425         * @param <B> the new node type
426         * @return a new tree consisting of all nodes of {@code this} tree
427         * @throws NullPointerException if the given {@code mapper} function is
428         *         {@code null}
429         */
430        public <B> TreeNode<B> map(final Function<? super T, ? extends B> mapper) {
431                final TreeNode<B> target = TreeNode.of(mapper.apply(value()));
432                copy(this, target, mapper);
433                return target;
434        }
435
436
437        @Override
438        public int hashCode() {
439                return Tree.hashCode(this);
440        }
441
442        @Override
443        public boolean equals(final Object obj) {
444                return obj instanceof Tree<?, ?> other && Tree.equals(this, other);
445        }
446
447        @Override
448        public String toString() {
449                return toParenthesesString();
450        }
451
452
453
454        /* *************************************************************************
455         * Static factory methods.
456         **************************************************************************/
457
458        /**
459         * Return a new {@code TreeNode} with a {@code null} tree value.
460         *
461         * @param <T> the tree-node type
462         * @return a new tree-node
463         */
464        public static <T> TreeNode<T> of() {
465                return TreeNode.of(null);
466        }
467
468        /**
469         * Return a new {@code TreeNode} with the given node {@code value}.
470         *
471         * @param value the node value
472         * @param <T> the tree-node type
473         * @return a new tree-node
474         */
475        public static <T> TreeNode<T> of(final T value) {
476                return new TreeNode<>(value);
477        }
478
479        /**
480         * Return a new {@code TreeNode} from the given source {@code tree}. The
481         * whole tree is copied.
482         *
483         * @param tree the source tree the new tree-node is created from
484         * @param mapper the tree value mapper function
485         * @param <T> the current tree value type
486         * @param <B> the mapped tree value type
487         * @return a new {@code TreeNode} from the given source {@code tree}
488         * @throws NullPointerException if one of the arguments is {@code null}
489         */
490        public static <T, B> TreeNode<B> ofTree(
491                final Tree<? extends T, ?> tree,
492                final Function<? super T, ? extends B> mapper
493        ) {
494                final TreeNode<B> target = of(mapper.apply(tree.value()));
495                copy(tree, target, mapper);
496                return target;
497        }
498
499        private static <T, B> void copy(
500                final Tree<? extends T, ?> source,
501                final TreeNode<B> target,
502                final Function<? super T, ? extends B> mapper
503        ) {
504                for (int i = 0; i < source.childCount(); ++i) {
505                        final var child = source.childAt(i);
506                        final TreeNode<B> targetChild = of(mapper.apply(child.value()));
507                        target.attach(targetChild);
508                        copy(child, targetChild, mapper);
509                }
510        }
511
512        /**
513         * Return a new {@code TreeNode} from the given source {@code tree}. The
514         * whole tree is copied.
515         *
516         * @param tree the source tree the new tree-node is created from
517         * @param <T> the current tree value type
518         * @return a new {@code TreeNode} from the given source {@code tree}
519         * @throws NullPointerException if the source {@code tree} is {@code null}
520         */
521        public static <T> TreeNode<T> ofTree(final Tree<? extends T, ?> tree) {
522                return ofTree(tree, Function.identity());
523        }
524
525        /**
526         * Parses a (parentheses) tree string, created with
527         * {@link Tree#toParenthesesString()}. The tree string might look like this:
528         * <pre>
529         *  mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
530         * </pre>
531         *
532         * The parse method doesn't strip the space between the parentheses and
533         * the commas. If you want to remove this <em>formatting</em> space,
534         * you should do the parsing with an addition <em>mapper</em> function.
535         * <pre>{@code
536         * final TreeNode<String> tree = TreeNode.parse(
537         *     "mul(  div(cos( 1.0) , cos(π )), sin(mul(1.0, z) ) )",
538         *     String::trim
539         * );
540         * }</pre>
541         * The code above will trim all tree nodes during the parsing process.
542         *
543         * @see Tree#toParenthesesString(Function)
544         * @see Tree#toParenthesesString()
545         * @see TreeNode#parse(String, Function)
546         *
547         * @since 4.3
548         *
549         * @param tree the parentheses tree string
550         * @return the parsed tree
551         * @throws NullPointerException if the given {@code tree} string is
552         *         {@code null}
553         * @throws IllegalArgumentException if the given tree string could not be
554         *         parsed
555         */
556        public static TreeNode<String> parse(final String tree) {
557                return ParenthesesTreeParser.parse(tree, Function.identity());
558        }
559
560        /**
561         * Parses a (parentheses) tree string, created with
562         * {@link Tree#toParenthesesString()}. The tree string might look like this
563         * <pre>
564         *  0(1(4,5),2(6),3(7(10,11),8,9))
565         * </pre>
566         * and can be parsed to an integer tree with the following code:
567         * <pre>{@code
568         * final Tree<Integer, ?> tree = TreeNode.parse(
569         *     "0(1(4,5),2(6),3(7(10,11),8,9))",
570         *     Integer::parseInt
571         * );
572         * }</pre>
573         *
574         * @see Tree#toParenthesesString(Function)
575         * @see Tree#toParenthesesString()
576         * @see TreeNode#parse(String)
577         *
578         * @since 4.3
579         *
580         * @param <B> the tree node value type
581         * @param tree the parentheses tree string
582         * @param mapper the mapper which converts the serialized string value to
583         *        the desired type
584         * @return the parsed tree object
585         * @throws NullPointerException if one of the arguments is {@code null}
586         * @throws IllegalArgumentException if the given parentheses tree string
587         *         doesn't represent a valid tree
588         */
589        public static <B> TreeNode<B> parse(
590                final String tree,
591                final Function<? super String, ? extends B> mapper
592        ) {
593                return ParenthesesTreeParser.parse(tree, mapper);
594        }
595
596
597        /* *************************************************************************
598         *  Java object serialization
599         * ************************************************************************/
600
601        @Serial
602        private Object writeReplace() {
603                return new SerialProxy(SerialProxy.TREE_NODE, this);
604        }
605
606        @Serial
607        private void readObject(final ObjectInputStream stream)
608                throws InvalidObjectException
609        {
610                throw new InvalidObjectException("Serialization proxy required.");
611        }
612
613
614        void write(final ObjectOutput out) throws IOException {
615                FlatTreeNode.ofTree(this).write(out);
616        }
617
618        @SuppressWarnings("unchecked")
619        static Object read(final ObjectInput in)
620                throws IOException, ClassNotFoundException
621        {
622                return TreeNode.ofTree(FlatTreeNode.read(in));
623        }
624
625}