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.util;
021
022import static java.lang.String.format;
023import static java.util.Objects.requireNonNull;
024import static java.util.Spliterators.spliteratorUnknownSize;
025import static io.jenetics.internal.util.SerialIO.readIntArray;
026import static io.jenetics.internal.util.SerialIO.writeIntArray;
027
028import java.io.DataInput;
029import java.io.DataOutput;
030import java.io.IOException;
031import java.io.InvalidObjectException;
032import java.io.ObjectInputStream;
033import java.io.Serial;
034import java.io.Serializable;
035import java.lang.reflect.Array;
036import java.util.Arrays;
037import java.util.Iterator;
038import java.util.Objects;
039import java.util.Optional;
040import java.util.Spliterator;
041import java.util.Spliterators;
042import java.util.function.BiFunction;
043import java.util.function.Function;
044import java.util.stream.Stream;
045import java.util.stream.StreamSupport;
046
047import io.jenetics.util.ISeq;
048import io.jenetics.util.Self;
049
050/**
051 * General purpose tree structure. The interface only contains tree read methods.
052 * For a mutable tree implementation have a look at the {@link TreeNode} class.
053 *
054 * @see TreeNode
055 *
056 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
057 * @version 7.0
058 * @since 3.9
059 */
060public interface Tree<V, T extends Tree<V, T>> extends Self<T>, Iterable<T> {
061
062        /* *************************************************************************
063         * Basic (abstract) operations. All other tree operations can be derived
064         * from these methods.
065         **************************************************************************/
066
067        /**
068         * Return the value of the current {@code Tree} node. The value may be
069         * {@code null}.
070         *
071         * @return the value of the current {@code Tree} node
072         */
073        V value();
074
075        /**
076         * Return the <em>parent</em> node of this tree node.
077         *
078         * @return the parent node, or {@code Optional.empty()} if this node is the
079         *         root of the tree
080         */
081        Optional<T> parent();
082
083        /**
084         * Return the child node with the given index.
085         *
086         * @param index the child index
087         * @return the child node with the given index
088         * @throws IndexOutOfBoundsException  if the {@code index} is out of
089         *         bounds ({@code [0, childCount())})
090         */
091        T childAt(final int index);
092
093        /**
094         * Return the number of children this tree node consists of.
095         *
096         * @return the number of children this tree node consists of
097         */
098        int childCount();
099
100
101        /* *************************************************************************
102         * Derived operations
103         **************************************************************************/
104
105        /**
106         * Return an iterator of the children of this {@code Tree} node.
107         *
108         * @return an iterator of the children of this {@code Tree} node.
109         */
110        default Iterator<T> childIterator() {
111                return new TreeChildIterator<V, T>(self());
112        }
113
114        /**
115         * Return a forward-order stream of this node's children.
116         *
117         * @return a stream of children of {@code this} node
118         */
119        default Stream<T> childStream() {
120                return StreamSupport.stream(
121                        Spliterators.spliterator(
122                                childIterator(),
123                                childCount(),
124                                Spliterator.SIZED | Spliterator.ORDERED
125                        ),
126                        false
127                );
128        }
129
130        /**
131         * Returns {@code true} if this node is the root of the tree.
132         *
133         * @return {@code true} if this node is the root of its tree, {@code false}
134         *         otherwise
135         */
136        default boolean isRoot() {
137                return parent().isEmpty();
138        }
139
140        /**
141         * Returns the depth of the tree rooted at this node. The <i>depth</i> of a
142         * tree is the longest distance from {@code this} node to a leaf. If
143         * {@code this} node has no children, 0 is returned. This operation is much
144         * more expensive than {@link #level()} because it must effectively traverse
145         * the entire tree rooted at {@code this} node.
146         *
147         * @return the depth of the tree whose root is this node
148         */
149        default int depth() {
150                final Iterator<T> it = breadthFirstIterator();
151
152                T last = null;
153                while (it.hasNext()) {
154                        last = it.next();
155                }
156
157                assert last != null;
158                return last.level() - level();
159        }
160
161        /**
162         * Returns the number of levels above this node. The <i>level</i> of a tree
163         * is the distance from the root to {@code this} node. If {@code this} node
164         * is the root, returns 0.
165         *
166         * @return the number of levels above this node
167         */
168        default int level() {
169                Optional<T> ancestor = Optional.of(self());
170                int levels = 0;
171                while ((ancestor = ancestor.flatMap(Tree::parent)).isPresent()) {
172                        ++levels;
173                }
174
175                return levels;
176        }
177
178        /**
179         * Returns the index of the specified child in this node's child array, or
180         * {@code -1} if {@code this} node doesn't contain the given {@code child}.
181         * This method performs a linear search and is O(n) where {@code n} is the
182         * number of children.
183         *
184         * @param child  the TreeNode to search for among this node's children
185         * @throws NullPointerException if the given {@code child} is {@code null}
186         * @return the index of the node in this node's child array, or {@code -1}
187         *         if the node could not be found
188         */
189        default int indexOf(final Tree<?, ?> child) {
190                int index = -1;
191                for (int i = 0, n = childCount(); i < n && index == -1; ++i) {
192                        if (childAt(i).identical(child)) {
193                                index = i;
194                        }
195                }
196
197                return index;
198        }
199
200        /**
201         * Return the number of nodes of {@code this} node (subtree).
202         *
203         * @return the number of nodes of {@code this} node (subtree)
204         */
205        default int size() {
206                return Trees.countChildren(this) + 1;
207        }
208
209        /**
210         * A tree is considered <em>empty</em> if it's {@link #value()} is
211         * {@code null} and has no children and parent. A newly created tree node
212         * with no value is <em>empty</em>.
213         *
214         * {@snippet lang="java":
215         * final Tree<String, ?> tree = TreeNode.of();
216         * assert tree.isEmpty();
217         * }
218         *
219         * @since 7.0
220         *
221         * @return {@code true} if {@code this} tree is empty, {@code false}
222         *          otherwise
223         */
224        default boolean isEmpty() {
225                return value() == null && childCount() == 0 && parent().isEmpty();
226        }
227
228
229        /* *************************************************************************
230         * Query operations
231         **************************************************************************/
232
233        /**
234         * Return the child node at the given {@code path}. A path consists of the
235         * child index at a give level, starting with level 1. (The root note has
236         * level zero.) {@code tree.childAtPath(Path.of(2))} will return the third
237         * child node of {@code this} node, if it exists and
238         * {@code tree.childAtPath(Path.of(2, 0))} will return the first child of
239         * the third child of {@code this node}.
240         *
241         * @since 4.4
242         *
243         * @see #childAtPath(int...)
244         *
245         * @param path the child path
246         * @return the child node at the given {@code path}
247         * @throws NullPointerException if the given {@code path} array is
248         *         {@code null}
249         */
250        default Optional<T> childAtPath(final Path path) {
251                T node = self();
252                for (int i = 0; i < path.length() && node != null; ++i) {
253                        node = path.get(i) < node.childCount()
254                                ? node.childAt(path.get(i))
255                                : null;
256                }
257
258                return Optional.ofNullable(node);
259        }
260
261        /**
262         * Return the child node at the given {@code path}. A path consists of the
263         * child index at a give level, starting with level 1. (The root note has
264         * level zero.) {@code tree.childAtPath(2)} will return the third child node
265         * of {@code this} node, if it exists and {@code tree.childAtPath(2, 0)} will
266         * return the first child of the third child of {@code this node}.
267         *
268         * @since 4.3
269         *
270         * @see #childAtPath(Path)
271         *
272         * @param path the child path
273         * @return the child node at the given {@code path}
274         * @throws NullPointerException if the given {@code path} array is
275         *         {@code null}
276         * @throws IllegalArgumentException if one of the path elements is smaller
277         *         than zero
278         */
279        default Optional<T> childAtPath(final int... path) {
280                return childAtPath(Path.of(path));
281        }
282
283        /**
284         * Return {@code true} if the given {@code node} is an ancestor of
285         * {@code this} node. This operation is at worst {@code O(h)} where {@code h}
286         * is the distance from the root to {@code this} node.
287         *
288         * @param node the node to test
289         * @return {@code true} if the given {@code node} is an ancestor of
290         *         {@code this} node, {@code false} otherwise
291         * @throws NullPointerException if the given {@code node} is {@code null}
292         */
293        default boolean isAncestor(final Tree<?, ?> node) {
294                requireNonNull(node);
295
296                Optional<T> ancestor = Optional.of(self());
297                boolean result;
298                do {
299                        result = ancestor.filter(a -> a.identical(node)).isPresent();
300                } while (!result &&
301                                (ancestor = ancestor.flatMap(Tree::parent)).isPresent());
302
303                return result;
304        }
305
306        /**
307         * Return {@code true} if the given {@code node} is a descendant of
308         * {@code this} node. If the given {@code node} is {@code null},
309         * {@code false} is returned. This operation is at worst {@code O(h)} where
310         * {@code h} is the distance from the root to {@code this} node.
311         *
312         * @param node the node to test as descendant of this node
313         * @return {@code true} if this node is an ancestor of the given {@code node}
314         * @throws NullPointerException if the given {@code node} is {@code null}
315         */
316        default boolean isDescendant(final Tree<?, ?> node) {
317                return requireNonNull(node).isAncestor(this);
318        }
319
320        /**
321         * Returns the nearest common ancestor to this node and the given {@code node}.
322         * A node is considered an ancestor of itself.
323         *
324         * @param node {@code node} to find common ancestor with
325         * @return nearest ancestor common to this node and the given {@code node},
326         *         or {@link Optional#empty()} if no common ancestor exists.
327         * @throws NullPointerException if the given {@code node} is {@code null}
328         */
329        default Optional<T> sharedAncestor(final T node) {
330                requireNonNull(node);
331
332                T ancestor = null;
333                if (node.identical(this)) {
334                        ancestor = self();
335                } else {
336                        final int level1 = level();
337                        final int level2 = node.level();
338
339                        T node1;
340                        T node2;
341                        int diff;
342                        if (level2 > level1) {
343                                diff = level2 - level1;
344                                node1 = node;
345                                node2 = self();
346                        } else {
347                                diff = level1 - level2;
348                                node1 = self();
349                                node2 = node;
350                        }
351
352                        while (diff > 0 && node1 != null) {
353                                node1 = node1.parent().orElse(null);
354                                --diff;
355                        }
356
357                        do {
358                                if (node1 != null && node1.identical(node2)) {
359                                        ancestor = node1;
360                                }
361                                node1 = node1 != null
362                                        ? node1.parent().orElse(null)
363                                        : null;
364                                node2 = node2.parent().orElse(null);
365                        } while (node1 != null && node2 != null && ancestor == null);
366                }
367
368                return Optional.ofNullable(ancestor);
369        }
370
371        /**
372         * Returns true if and only if the given {@code node} is in the same tree as
373         * {@code this} node.
374         *
375         * @param node the other node to check
376         * @return true if the given {@code node} is in the same tree as {@code this}
377         *         node, {@code false} otherwise.
378         * @throws NullPointerException if the given {@code node} is {@code null}
379         */
380        default boolean isRelated(final Tree<?, ?> node) {
381                requireNonNull(node);
382                return node.root().identical(root());
383        }
384
385        /**
386         * Returns the path from the root, to get to this node. The last element in
387         * the path is this node.
388         *
389         * @since 5.1
390         *
391         * @return an array of TreeNode objects giving the path, where the
392         *         first element in the path is the root and the last
393         *         element is this node.
394         */
395        default ISeq<T> pathElements() {
396                return Trees.pathElementsFromRoot(self(), 0).toISeq();
397        }
398
399        /**
400         * Return the {@link Path} of {@code this} tree, such that
401         * {@snippet lang="java":
402         * final Tree<Integer, ?> tree = null; // @replace substring='null' replacement="..."
403         * final Tree.Path path = tree.path();
404         * assert tree == tree.getRoot()
405         *     .childAtPath(path)
406         *     .orElse(null);
407         * }
408         *
409         * @since 5.1
410         *
411         * @return the path from the root element to {@code this} node.
412         */
413        default Path path() {
414                final int[] p = Trees.pathFromRoot(self(), 0);
415                return Path.of(p);
416        }
417
418        /**
419         * Returns the root of the tree that contains this node. The root is the
420         * ancestor with no parent.
421         *
422         * @return the root of the tree that contains this node
423         */
424        default T root() {
425                T anc = self();
426                T prev;
427
428                do {
429                        prev = anc;
430                        anc = anc.parent().orElse(null);
431                } while (anc != null);
432
433                return prev;
434        }
435
436        /* *************************************************************************
437         * Child query operations
438         **************************************************************************/
439
440        /**
441         * Return {@code true} if the given {@code node} is a child of {@code this}
442         * node.
443         *
444         * @param node the other node to check
445         * @return {@code true} if {@code node}is a child, {@code false} otherwise
446         * @throws NullPointerException if the given {@code node} is {@code null}
447         */
448        default boolean isChild(final Tree<?, ?> node) {
449                requireNonNull(node);
450                return childCount() != 0 &&
451                        node.parent().equals(Optional.of(self()));
452        }
453
454        /**
455         * Return the first child of {@code this} node, or {@code Optional.empty()}
456         * if {@code this} node has no children.
457         *
458         * @return the first child of this node
459         */
460        default Optional<T> firstChild() {
461                return childCount() > 0
462                        ? Optional.of(childAt(0))
463                        : Optional.empty();
464        }
465
466        /**
467         * Return the last child of {@code this} node, or {@code Optional.empty()}
468         * if {@code this} node has no children.
469         *
470         * @return the last child of this node
471         */
472        default Optional<T> lastChild() {
473                return childCount() > 0
474                        ? Optional.of(childAt(childCount() - 1))
475                        : Optional.empty();
476        }
477
478        /**
479         * Return the child which comes immediately after {@code this} node. This
480         * method performs a linear search of this node's children for {@code child}
481         * and is {@code O(n)} where n is the number of children.
482         *
483         * @param child the child node
484         * @return  the child of this node that immediately follows the {@code child},
485         *          or {@code Optional.empty()} if the given {@code node} is the
486         *          first node.
487         * @throws NullPointerException if the given {@code child} is {@code null}
488         */
489        default Optional<T> childAfter(final Tree<?, ?> child) {
490                requireNonNull(child);
491
492                final int index = indexOf(child);
493                if (index == -1) {
494                        throw new IllegalArgumentException("The given node is not a child.");
495                }
496
497                return index < childCount() - 1
498                        ? Optional.of(childAt(index + 1))
499                        : Optional.empty();
500        }
501
502        /**
503         * Return the child which comes immediately before {@code this} node. This
504         * method performs a linear search of this node's children for {@code child}
505         * and is {@code O(n)} where n is the number of children.
506         *
507         * @param child the child node
508         * @return  the child of this node that immediately precedes the {@code child},
509         *          or {@code null} if the given {@code node} is the first node.
510         * @throws NullPointerException if the given {@code child} is {@code null}
511         */
512        default Optional<T> childBefore(final Tree<?, ?> child) {
513                requireNonNull(child);
514
515                final int index = indexOf(child);
516                if (index == -1) {
517                        throw new IllegalArgumentException("The given node is not a child.");
518                }
519
520                return index > 0
521                        ? Optional.of(childAt(index - 1))
522                        : Optional.empty();
523        }
524
525        /**
526         * Return the node that follows {@code this} node in a pre-order traversal
527         * of {@code this} tree node. Return {@code Optional.empty()} if this node
528         * is the last node of the traversal. This is an inefficient way to traverse
529         * the entire tree use an iterator instead.
530         *
531         * @see #preorderIterator
532         * @return the node that follows this node in a pre-order traversal, or
533         *        {@code Optional.empty()} if this node is last
534         */
535        default Optional<T> nextNode() {
536                Optional<T> next = Optional.empty();
537
538                if (childCount() == 0) {
539                        T node = self();
540                        while (node != null && (next = node.nextSibling()).isEmpty()) {
541                                node = node.parent().orElse(null);
542                        }
543                } else {
544                        next = Optional.of(childAt(0));
545                }
546
547                return next;
548        }
549
550        /**
551         * Return the node that precedes this node in a pre-order traversal of
552         * {@code this} tree node. Returns {@code Optional.empty()} if this node is
553         * the first node of the traversal, the root of the tree. This is an
554         * inefficient way to traverse the entire tree; use an iterator instead.
555         *
556         * @see #preorderIterator
557         * @return the node that precedes this node in a pre-order traversal, or
558         *         {@code Optional.empty()} if this node is the first
559         */
560        default Optional<T> previousNode() {
561                Optional<T> node = Optional.empty();
562
563                if (parent().isPresent()) {
564                        final Optional<T> prev = previousSibling();
565                        if (prev.isPresent()) {
566                                node = prev.get().childCount() == 0
567                                        ? prev
568                                        : prev.map(Tree::lastLeaf);
569                        } else {
570                                node = parent();
571                        }
572                }
573
574                return node;
575        }
576
577        /* *************************************************************************
578         * Sibling query operations
579         **************************************************************************/
580
581        /**
582         * Test if the given {@code node} is a sibling of {@code this} node.
583         *
584         * @param node node to test as sibling of this node
585         * @return {@code true} if the {@code node} is a sibling of {@code this}
586         *         node
587         * @throws NullPointerException if the given {@code node} is {@code null}
588         */
589        default boolean isSibling(final Tree<?, ?> node) {
590                return identical(requireNonNull(node)) ||
591                        parent().equals(node.parent());
592        }
593
594        /**
595         * Return the number of siblings of {@code this} node. A node is its own
596         * sibling (if it has no parent or no siblings, this method returns
597         * {@code 1}).
598         *
599         * @return the number of siblings of {@code this} node
600         */
601        default int siblingCount() {
602                return parent().map(Tree::childCount).orElse(1);
603        }
604
605        /**
606         * Return the next sibling of {@code this} node in the parent's children
607         * array, or {@code null} if {@code this} node has no parent, or it is the
608         * last child of the paren. This method performs a linear search that is
609         * {@code O(n)} where n is the number of children; to traverse the entire
610         * array, use the iterator of the parent instead.
611         *
612         * @see #childStream()
613         * @return the sibling of {@code this} node that immediately follows
614         *         {@code this} node
615         */
616        default Optional<T> nextSibling() {
617                return parent().flatMap(p -> p.childAfter(self()));
618        }
619
620        /**
621         * Return the previous sibling of {@code this} node in the parent's children
622         * list, or {@code Optional.empty()} if this node has no parent or is the
623         * parent's first child. This method performs a linear search that is O(n)
624         * where n is the number of children.
625         *
626         * @return the sibling of {@code this} node that immediately precedes this
627         *         node
628         */
629        default Optional<T> previousSibling() {
630                return parent().flatMap(p -> p.childBefore(self()));
631        }
632
633
634        /* *************************************************************************
635         * Leaf query operations
636         **************************************************************************/
637
638        /**
639         * Return {@code true} if {@code this} node has no children.
640         *
641         * @return {@code true} if {@code this} node has no children, {@code false}
642         *         otherwise
643         */
644        default boolean isLeaf() {
645                return childCount() == 0;
646        }
647
648        /**
649         * Return the first leaf that is a descendant of {@code this} node; either
650         * this node or its first child's first leaf. {@code this} node is returned
651         * if it is a leaf.
652         *
653         * @see #isLeaf
654         * @see  #isDescendant
655         * @return the first leaf in the subtree rooted at this node
656         */
657        default T firstLeaf() {
658                T leaf = self();
659                while (!leaf.isLeaf()) {
660                        leaf = leaf.firstChild().orElseThrow(AssertionError::new);
661                }
662
663                return leaf;
664        }
665
666        /**
667         * Return the last leaf that is a descendant of this node; either
668         * {@code this} node or its last child's last leaf. Returns {@code this}
669         * node if it is a leaf.
670         *
671         * @see #isLeaf
672         * @see #isDescendant
673         * @return the last leaf in this subtree
674         */
675        default T lastLeaf() {
676                T leaf = self();
677                while (!leaf.isLeaf()) {
678                        leaf = leaf.lastChild().orElseThrow(AssertionError::new);
679                }
680
681                return leaf;
682        }
683
684        /**
685         * Returns the leaf after {@code this} node or {@code Optional.empty()} if
686         * this node is the last leaf in the tree.
687         * <p>
688         * In order to determine the next node, this method first performs a linear
689         * search in the parent's child-list in order to find the current node.
690         * <p>
691         * That implementation makes the operation suitable for short traversals
692         * from a known position. But to traverse all the leaves in the tree, you
693         * should use {@link #depthFirstIterator()} to iterator the nodes in the
694         * tree and use {@link #isLeaf()} on each node to determine which are leaves.
695         *
696         * @see #depthFirstIterator
697         * @see #isLeaf
698         * @return return the next leaf past this node
699         */
700        default Optional<T> nextLeaf() {
701                return nextSibling()
702                        .map(Tree::firstLeaf)
703                        .or(() -> parent().flatMap(Tree::nextLeaf));
704        }
705
706        /**
707         * Return the leaf before {@code this} node or {@code null} if {@code this}
708         * node is the first leaf in the tree.
709         * <p>
710         * In order to determine the previous node, this method first performs a
711         * linear search in the parent's child-list in order to find the current
712         * node.
713         * <p>
714         * That implementation makes the operation suitable for short traversals
715         * from a known position. But to traverse all the leaves in the tree, you
716         * should use {@link #depthFirstIterator()} to iterate the nodes in the tree
717         * and use {@link #isLeaf()} on each node to determine which are leaves.
718         *
719         * @see #depthFirstIterator
720         * @see #isLeaf
721         * @return returns the leaf before {@code this} node
722         */
723        default Optional<T> previousLeaf() {
724                return previousSibling()
725                        .map(Tree::lastLeaf)
726                        .or(() -> parent().flatMap(Tree::previousLeaf));
727        }
728
729        /**
730         * Returns the total number of leaves that are descendants of this node.
731         * If this node is a leaf, returns {@code 1}. This method is {@code O(n)},
732         * where n is the number of descendants of {@code this} node.
733         *
734         * @see #isLeaf()
735         * @return the number of leaves beneath this node
736         */
737        default int leafCount() {
738                return (int)leaves().count();
739        }
740
741        /**
742         * Return a stream of leaves that are descendants of this node.
743         *
744         * @since 7.0
745         *
746         * @return a stream of leaves that are descendants of this node
747         */
748        default Stream<T> leaves() {
749                return breadthFirstStream().filter(Tree::isLeaf);
750        }
751
752        /* *************************************************************************
753         * Tree traversing.
754         **************************************************************************/
755
756        /**
757         * Return an iterator that traverses the subtree rooted at {@code this}
758         * node in breadth-first order. The first node returned by the iterator is
759         * {@code this} node.
760         * <p>
761         * Modifying the tree by inserting, removing, or moving a node invalidates
762         * any iterator created before the modification.
763         *
764         * @see #depthFirstIterator
765         * @return an iterator for traversing the tree in breadth-first order
766         */
767        default Iterator<T> breadthFirstIterator() {
768                return new TreeNodeBreadthFirstIterator<>(self());
769        }
770
771        /**
772         * Return an iterator that traverses the subtree rooted at {@code this}.
773         * The first node returned by the iterator is {@code this} node.
774         * <p>
775         * Modifying the tree by inserting, removing, or moving a node invalidates
776         * any iterator created before the modification.
777         *
778         * @see #breadthFirstIterator
779         * @return an iterator for traversing the tree in breadth-first order
780         */
781        @Override
782        default Iterator<T> iterator() {
783                return breadthFirstIterator();
784        }
785
786        /**
787         * Return a stream that traverses the subtree rooted at {@code this} node in
788         * breadth-first order. The first node returned by the stream is
789         * {@code this} node.
790         *
791         * @see #depthFirstIterator
792         * @see #stream()
793         * @return a stream for traversing the tree in breadth-first order
794         */
795        default Stream<T> breadthFirstStream() {
796                return StreamSupport
797                        .stream(spliteratorUnknownSize(breadthFirstIterator(), 0), false);
798        }
799
800        /**
801         * Return a stream that traverses the subtree rooted at {@code this} node in
802         * breadth-first order. The first node returned by the stream is
803         * {@code this} node.
804         *
805         * @see #breadthFirstStream
806         * @return a stream for traversing the tree in breadth-first order
807         */
808        default Stream<T> stream() {
809                return breadthFirstStream();
810        }
811
812        /**
813         * Return an iterator that traverses the subtree rooted at {@code this} node
814         * in pre-order. The first node returned by the iterator is {@code this}
815         * node.
816         * <p>
817         * Modifying the tree by inserting, removing, or moving a node invalidates
818         * any iterator created before the modification.
819         *
820         * @see #postorderIterator
821         * @return an iterator for traversing the tree in pre-order
822         */
823        default Iterator<T> preorderIterator() {
824                return new TreeNodePreorderIterator<>(self());
825        }
826
827        /**
828         * Return a stream that traverses the subtree rooted at {@code this} node
829         * in pre-order. The first node returned by the stream is {@code this} node.
830         * <p>
831         * Modifying the tree by inserting, removing, or moving a node invalidates
832         * any iterator created before the modification.
833         *
834         * @see #preorderIterator
835         * @return a stream for traversing the tree in pre-order
836         */
837        default Stream<T> preorderStream() {
838                return StreamSupport
839                        .stream(spliteratorUnknownSize(preorderIterator(), 0), false);
840        }
841
842        /**
843         * Return an iterator that traverses the subtree rooted at {@code this}
844         * node in post-order. The first node returned by the iterator is the
845         * leftmost leaf.  This is the same as a depth-first traversal.
846         *
847         * @see #depthFirstIterator
848         * @see #preorderIterator
849         * @return an iterator for traversing the tree in post-order
850         */
851        default Iterator<T> postorderIterator() {
852                return new TreeNodePostorderIterator<>(self());
853        }
854
855        /**
856         * Return a stream that traverses the subtree rooted at {@code this} node in
857         * post-order. The first node returned by the iterator is the leftmost leaf.
858         * This is the same as a depth-first traversal.
859         *
860         * @see #depthFirstIterator
861         * @see #preorderIterator
862         * @return a stream for traversing the tree in post-order
863         */
864        default Stream<T> postorderStream() {
865                return StreamSupport
866                        .stream(spliteratorUnknownSize(postorderIterator(), 0), false);
867        }
868
869        /**
870         * Return an iterator that traverses the subtree rooted at {@code this} node
871         * in depth-first order. The first node returned by the iterator is the
872         * leftmost leaf. This is the same as a postorder traversal.
873         * <p>
874         * Modifying the tree by inserting, removing, or moving a node invalidates
875         * any iterator created before the modification.
876         *
877         * @see #breadthFirstIterator
878         * @see #postorderIterator
879         * @return an iterator for traversing the tree in depth-first order
880         */
881        default Iterator<T> depthFirstIterator() {
882                return postorderIterator();
883        }
884
885        /**
886         * Return a stream that traverses the subtree rooted at {@code this} node in
887         * depth-first. The first node returned by the iterator is the leftmost leaf.
888         * This is the same as a post-order traversal.
889         *
890         * @see #depthFirstIterator
891         * @see #preorderIterator
892         * @return a stream for traversing the tree in post-order
893         */
894        default Stream<T> depthFirstStream() {
895                return postorderStream();
896        }
897
898        /**
899         * Return an iterator that follows the path from {@code ancestor} to
900         * {@code this} node. The iterator return {@code ancestor} as a first element,
901         * The creation of the iterator is O(m), where m is the number of nodes
902         * between {@code this} node and the {@code ancestor}, inclusive.
903         * <p>
904         * Modifying the tree by inserting, removing, or moving a node invalidates
905         * any iterator created before the modification.
906         *
907         * @see #isAncestor
908         * @see #isDescendant
909         * @param ancestor the ancestor node
910         * @return an iterator for following the path from an ancestor of {@code this}
911         *         node to this one
912         * @throws IllegalArgumentException if the {@code ancestor} is not an
913         *         ancestor of this node
914         * @throws NullPointerException if the given {@code ancestor} is {@code null}
915         */
916        default Iterator<T> pathFromAncestorIterator(final Tree<?, ?> ancestor) {
917                return new TreeNodePathIterator<>(ancestor, self());
918        }
919
920        /**
921         * Return the path of {@code this} child node from the root node. You will
922         * get {@code this} node, if you call {@link #childAtPath(Path)} on the
923         * root node of {@code this} node.
924         * {@snippet lang="java":
925         * final Tree<?, ?> node = null; // @replace substring='null' replacement="..."
926         * final Tree<?, ?> root = node.getRoot();
927         * final int[] path = node.childPath();
928         * assert node == root.childAtPath(path);
929         * }
930         *
931         * @since 4.4
932         *
933         * @see #childAtPath(Path)
934         *
935         * @return the path of {@code this} child node from the root node.
936         */
937        default Path childPath() {
938                final Iterator<T> it = pathFromAncestorIterator(root());
939                final int[] path = new int[level()];
940
941                T tree = null;
942                int index = 0;
943                while (it.hasNext()) {
944                        final T child = it.next();
945                        if (tree != null) {
946                                path[index++] = tree.indexOf(child);
947                        }
948
949                        tree = child;
950                }
951
952                assert index == path.length;
953
954                return new Path(path);
955        }
956
957        /**
958         * Tests whether {@code this} node is the same as the {@code other} node.
959         * The default implementation returns the object identity,
960         * {@code this == other}, of the two objects, but other implementations may
961         * use different criteria for checking the <i>identity</i>.
962         *
963         * @param other the {@code other} node
964         * @return {@code true} if the {@code other} node is the same as {@code this}
965         *         node.
966         */
967        default boolean identical(final Tree<?, ?> other) {
968                return this == other;
969        }
970
971        /**
972         * Performs a reduction on the elements of {@code this} tree, using an
973         * associative reduction function. This can be used for evaluating a given
974         * expression tree in pre-order.
975         * {@snippet lang="java":
976         * final Tree<String, ?> formula = TreeNode.parse("add(sub(6,div(230,10)),mul(5,6))");
977         * final double result = formula.reduce(new Double[0], (op, args) ->
978         *     switch (op) {
979         *         case "add" -> args[0] + args[1];
980         *         case "sub" -> args[0] - args[1];
981         *         case "mul" -> args[0] * args[1];
982         *         case "div" -> args[0] / args[1];
983         *         default -> Double.parseDouble(op);
984         *     }
985         * );
986         * assert result == 13.0;
987         * }
988         *
989         * @since 7.1
990         *
991         * @param neutral the neutral element of the reduction. In most cases this will
992         *        be {@code new U[0]}.
993         * @param reducer the reduce function
994         * @param <U> the result type
995         * @return the result of the reduction, or {@code null} if {@code this} tree
996         *         is empty ({@code isEmpty() == true})
997         */
998        default <U> U reduce(
999                final U[] neutral,
1000                final BiFunction<? super V, ? super U[], ? extends U> reducer
1001        ) {
1002                requireNonNull(neutral);
1003                requireNonNull(reducer);
1004
1005                @SuppressWarnings("unchecked")
1006                final class Reducing {
1007                        private U reduce(final Tree<V, ?> node) {
1008                                return node.isLeaf()
1009                                        ? reducer.apply(node.value(), neutral)
1010                                        : reducer.apply(node.value(), children(node));
1011                        }
1012                        private U[] children(final Tree<V, ?> node) {
1013                                final U[] values = (U[])Array.newInstance(
1014                                        neutral.getClass().getComponentType(),
1015                                        node.childCount()
1016                                );
1017                                for (int i = 0; i < node.childCount(); ++i) {
1018                                        values[i] = reduce(node.childAt(i));
1019                                }
1020                                return values;
1021                        }
1022                }
1023
1024                return isEmpty() ? null : new Reducing().reduce(this);
1025        }
1026
1027        /* *************************************************************************
1028         * 'toString' methods
1029         **************************************************************************/
1030
1031        /**
1032         * Return a compact string representation of the given tree. The tree
1033         * <pre>
1034         *  mul
1035         *  ├── div
1036         *  │   ├── cos
1037         *  │   │   └── 1.0
1038         *  │   └── cos
1039         *  │       └── π
1040         *  └── sin
1041         *      └── mul
1042         *          ├── 1.0
1043         *          └── z
1044         *  </pre>
1045         * is printed as
1046         * <pre>
1047         *  mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
1048         * </pre>
1049         *
1050         * @since 4.3
1051         *
1052         * @see #toParenthesesString()
1053         * @see TreeFormatter#PARENTHESES
1054         *
1055         * @param mapper the {@code mapper} which converts the tree value to a string
1056         * @return the string representation of the given tree
1057         */
1058        default String toParenthesesString(final Function<? super V, String> mapper) {
1059                return TreeFormatter.PARENTHESES.format(this, mapper);
1060        }
1061
1062        /**
1063         * Return a compact string representation of the given tree. The tree
1064         * <pre>
1065         *  mul
1066         *  ├── div
1067         *  │   ├── cos
1068         *  │   │   └── 1.0
1069         *  │   └── cos
1070         *  │       └── π
1071         *  └── sin
1072         *      └── mul
1073         *          ├── 1.0
1074         *          └── z
1075         *  </pre>
1076         * is printed as
1077         * <pre>
1078         *  mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
1079         * </pre>
1080         *
1081         * @since 4.3
1082         *
1083         * @see #toParenthesesString(Function)
1084         * @see TreeFormatter#PARENTHESES
1085         *
1086         * @return the string representation of the given tree
1087         * @throws NullPointerException if the {@code mapper} is {@code null}
1088         */
1089        default String toParenthesesString() {
1090                return toParenthesesString(Objects::toString);
1091        }
1092
1093        /* *************************************************************************
1094         * Static helper methods.
1095         **************************************************************************/
1096
1097        /**
1098         * Calculates the hash code of the given tree.
1099         *
1100         * @param tree the tree where the hash is calculated from
1101         * @return the hash code of the tree
1102         * @throws NullPointerException if the given {@code tree} is {@code null}
1103         */
1104        static int hashCode(final Tree<?, ?> tree) {
1105                return tree != null
1106                        ? tree.breadthFirstStream()
1107                                .mapToInt(node -> 31*Objects.hashCode(node.value()) + 37)
1108                                .sum() + 17
1109                        : 0;
1110        }
1111
1112        /**
1113         * Checks if the two given trees has the same structure with the same values.
1114         *
1115         * @param a the first tree
1116         * @param b the second tree
1117         * @return {@code true} if the two given trees are structurally equals,
1118         *         {@code false} otherwise
1119         */
1120        static boolean equals(final Tree<?, ?> a, final Tree<?, ?> b) {
1121                return Trees.equals(a, b);
1122        }
1123
1124        /**
1125         * Return a string representation of the given tree, like the following
1126         * example.
1127         *
1128         * <pre>
1129         *  mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
1130         * </pre>
1131         *
1132         * This method is intended to be used when override the
1133         * {@link Object#toString()} method.
1134         *
1135         * @param tree the input tree
1136         * @return the string representation of the given tree
1137         */
1138        static String toString(final Tree<?, ?> tree) {
1139                return tree.toParenthesesString();
1140        }
1141
1142
1143        /* *************************************************************************
1144         * Inner classes
1145         **************************************************************************/
1146
1147        /**
1148         * This class represents the path to child within a given tree. It allows
1149         * pointing (and fetch) a tree child.
1150         *
1151         * @see Tree#childAtPath(Path)
1152         *
1153         * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
1154         * @version 7.2
1155         * @since 4.4
1156         */
1157        final class Path implements Comparable<Path>, Serializable {
1158
1159                @Serial
1160                private static final long serialVersionUID = 1L;
1161
1162                private final int[] _path;
1163
1164                private Path(final int[] path) {
1165                        _path = requireNonNull(path);
1166                }
1167
1168                /**
1169                 * Return the path length, which is the level of the child {@code this}
1170                 * path points to.
1171                 *
1172                 * @return the path length
1173                 */
1174                public int length() {
1175                        return _path.length;
1176                }
1177
1178                /**
1179                 * Return the child index at the given index (child level).
1180                 *
1181                 * @param index the path index
1182                 * @return the child index at the given child level
1183                 * @throws IndexOutOfBoundsException if the index is not with the range
1184                 *         {@code [0, length())}
1185                 */
1186                public int get(final int index) {
1187                        return _path[index];
1188                }
1189
1190                /**
1191                 * Return the path as {@code int[]} array.
1192                 *
1193                 * @return the path as {@code int[]} array
1194                 */
1195                public int[] toArray() {
1196                        return _path.clone();
1197                }
1198
1199                /**
1200                 * Appends the given {@code path} to {@code this} one.
1201                 *
1202                 * @param path the path to append
1203                 * @return a new {@code Path} with the given {@code path} appended
1204                 * @throws NullPointerException if the given {@code path} is {@code null}
1205                 */
1206                public Path append(final Path path) {
1207                        final int[] p = new int[length() + path.length()];
1208                        System.arraycopy(_path, 0, p, 0, length());
1209                        System.arraycopy(path._path, 0, p, length(), path.length());
1210                        return new Path(p);
1211                }
1212
1213                @Override
1214                public int compareTo(final Path other) {
1215                        for (int i = 0, n = Math.min(length(), other.length()); i < n; ++i) {
1216                                final int cmp = Integer.compare(get(i), other.get(i));
1217                                if (cmp != 0) {
1218                                        return cmp;
1219                                }
1220                        }
1221
1222                        return Integer.compare(length(), other.length());
1223                }
1224
1225                @Override
1226                public int hashCode() {
1227                        return Arrays.hashCode(_path);
1228                }
1229
1230                @Override
1231                public boolean equals(final Object obj) {
1232                        return obj == this ||
1233                                obj instanceof Path other &&
1234                                Arrays.equals(_path, other._path);
1235                }
1236
1237                @Override
1238                public String toString() {
1239                        return Arrays.toString(_path);
1240                }
1241
1242                /**
1243                 * Create a new path object from the given child indexes.
1244                 *
1245                 * @param path the child indexes
1246                 * @return a new tree path
1247                 * @throws IllegalArgumentException if one of the path elements is
1248                 *         smaller than zero
1249                 */
1250                public static Path of(final int... path) {
1251                        for (int i = 0; i < path.length; ++i) {
1252                                if (path[i] < 0) {
1253                                        throw new IllegalArgumentException(format(
1254                                                "Path element at position %d is smaller than zero: %d",
1255                                                i, path[i]
1256                                        ));
1257                                }
1258                        }
1259
1260                        return new Path(path.clone());
1261                }
1262
1263
1264                /* *********************************************************************
1265                 *  Java object serialization
1266                 * ********************************************************************/
1267
1268                @Serial
1269                private Object writeReplace() {
1270                        return new SerialProxy(SerialProxy.TREE_PATH, this);
1271                }
1272
1273                @Serial
1274                private void readObject(final ObjectInputStream stream)
1275                        throws InvalidObjectException
1276                {
1277                        throw new InvalidObjectException("Serialization proxy required.");
1278                }
1279
1280
1281                void write(final DataOutput out) throws IOException {
1282                        writeIntArray(_path, out);
1283                }
1284
1285                static Object read(final DataInput in) throws IOException {
1286                        return Path.of(readIntArray(in));
1287                }
1288
1289        }
1290
1291}