0001 /*
0002 * Java Genetic Algorithm Library (jenetics-6.1.0).
0003 * Copyright (c) 2007-2020 Franz Wilhelmstötter
0004 *
0005 * Licensed under the Apache License, Version 2.0 (the "License");
0006 * you may not use this file except in compliance with the License.
0007 * You may obtain a copy of the License at
0008 *
0009 * http://www.apache.org/licenses/LICENSE-2.0
0010 *
0011 * Unless required by applicable law or agreed to in writing, software
0012 * distributed under the License is distributed on an "AS IS" BASIS,
0013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014 * See the License for the specific language governing permissions and
0015 * limitations under the License.
0016 *
0017 * Author:
0018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com)
0019 */
0020 package io.jenetics.ext.util;
0021
0022 import static java.lang.String.format;
0023 import static java.util.Objects.requireNonNull;
0024 import static java.util.Spliterators.spliteratorUnknownSize;
0025 import static io.jenetics.internal.util.SerialIO.readIntArray;
0026 import static io.jenetics.internal.util.SerialIO.writeIntArray;
0027
0028 import java.io.DataInput;
0029 import java.io.DataOutput;
0030 import java.io.IOException;
0031 import java.io.InvalidObjectException;
0032 import java.io.ObjectInputStream;
0033 import java.io.Serializable;
0034 import java.util.Arrays;
0035 import java.util.Iterator;
0036 import java.util.Objects;
0037 import java.util.Optional;
0038 import java.util.Spliterator;
0039 import java.util.Spliterators;
0040 import java.util.function.Function;
0041 import java.util.stream.Stream;
0042 import java.util.stream.StreamSupport;
0043
0044 import io.jenetics.util.ISeq;
0045
0046 /**
0047 * General purpose tree structure. The interface only contains tree read methods.
0048 * For a mutable tree implementation have a look at the {@link TreeNode} class.
0049 *
0050 * @see TreeNode
0051 *
0052 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
0053 * @version 6.0
0054 * @since 3.9
0055 */
0056 public interface Tree<V, T extends Tree<V, T>> extends Iterable<T> {
0057
0058 /* *************************************************************************
0059 * Basic (abstract) operations. All other tree operations can be derived
0060 * from this methods.
0061 **************************************************************************/
0062
0063 /**
0064 * Return the value of the current {@code Tree} node. The value may be
0065 * {@code null}.
0066 *
0067 * @return the value of the current {@code Tree} node
0068 */
0069 V value();
0070
0071 /**
0072 * Return the <em>parent</em> node of this tree node.
0073 *
0074 * @return the parent node, or {@code Optional.empty()} if this node is the
0075 * root of the tree
0076 */
0077 Optional<T> parent();
0078
0079 /**
0080 * Return the child node with the given index.
0081 *
0082 * @param index the child index
0083 * @return the child node with the given index
0084 * @throws IndexOutOfBoundsException if the {@code index} is out of
0085 * bounds ({@code [0, childCount())})
0086 */
0087 T childAt(final int index);
0088
0089 /**
0090 * Return the number of children this tree node consists of.
0091 *
0092 * @return the number of children this tree node consists of
0093 */
0094 int childCount();
0095
0096
0097 /* *************************************************************************
0098 * Derived operations
0099 **************************************************************************/
0100
0101 /**
0102 * Return an iterator of the children of this {@code Tree} node.
0103 *
0104 * @return an iterator of the children of this {@code Tree} node.
0105 */
0106 default Iterator<T> childIterator() {
0107 return new TreeChildIterator<V, T>(Trees.self(this));
0108 }
0109
0110 /**
0111 * Return a forward-order stream of this node's children.
0112 *
0113 * @return a stream of children of {@code this} node
0114 */
0115 default Stream<T> childStream() {
0116 return StreamSupport.stream(
0117 Spliterators.spliterator(
0118 childIterator(),
0119 childCount(),
0120 Spliterator.SIZED | Spliterator.ORDERED
0121 ),
0122 false
0123 );
0124 }
0125
0126 /**
0127 * Returns {@code true} if this node is the root of the tree.
0128 *
0129 * @return {@code true} if this node is the root of its tree, {@code false}
0130 * otherwise
0131 */
0132 default boolean isRoot() {
0133 return parent().isEmpty();
0134 }
0135
0136 /**
0137 * Returns the depth of the tree rooted at this node. The <i>depth</i> of a
0138 * tree is the longest distance from {@code this} node to a leaf. If
0139 * {@code this} node has no children, 0 is returned. This operation is much
0140 * more expensive than {@link #level()} because it must effectively traverse
0141 * the entire tree rooted at {@code this} node.
0142 *
0143 * @return the depth of the tree whose root is this node
0144 */
0145 default int depth() {
0146 final Iterator<T> it = breadthFirstIterator();
0147
0148 T last = null;
0149 while (it.hasNext()) {
0150 last = it.next();
0151 }
0152
0153 assert last != null;
0154 return last.level() - level();
0155 }
0156
0157 /**
0158 * Returns the number of levels above this node. The <i>level</i> of a tree
0159 * is the distance from the root to {@code this} node. If {@code this} node
0160 * is the root, returns 0.
0161 *
0162 * @return the number of levels above this node
0163 */
0164 default int level() {
0165 Optional<T> ancestor = Optional.of(Trees.self(this));
0166 int levels = 0;
0167 while ((ancestor = ancestor.flatMap(Tree::parent)).isPresent()) {
0168 ++levels;
0169 }
0170
0171 return levels;
0172 }
0173
0174 /**
0175 * Returns the index of the specified child in this node's child array, or
0176 * {@code -1} if {@code this} node doesn't contain the given {@code child}.
0177 * This method performs a linear search and is O(n) where {@code n} is the
0178 * number of children.
0179 *
0180 * @param child the TreeNode to search for among this node's children
0181 * @throws NullPointerException if the given {@code child} is {@code null}
0182 * @return the index of the node in this node's child array, or {@code -1}
0183 * if the node could not be found
0184 */
0185 default int indexOf(final Tree<?, ?> child) {
0186 int index = -1;
0187 for (int i = 0, n = childCount(); i < n && index == -1; ++i) {
0188 if (childAt(i).identical(child)) {
0189 index = i;
0190 }
0191 }
0192
0193 return index;
0194 }
0195
0196 /**
0197 * Return the number of nodes of {@code this} node (sub-tree).
0198 *
0199 * @return the number of nodes of {@code this} node (sub-tree)
0200 */
0201 default int size() {
0202 return Trees.countChildren(this) + 1;
0203 }
0204
0205
0206 /* *************************************************************************
0207 * Query operations
0208 **************************************************************************/
0209
0210 /**
0211 * Return the child node at the given {@code path}. A path consists of the
0212 * child index at a give level, starting with level 1. (The root note has
0213 * level zero.) {@code tree.childAtPath(Path.of(2))} will return the third
0214 * child node of {@code this} node, if it exists and
0215 * {@code tree.childAtPath(Path.of(2, 0))} will return the first child of
0216 * the third child of {@code this node}.
0217 *
0218 * @since 4.4
0219 *
0220 * @see #childAtPath(int...)
0221 *
0222 * @param path the child path
0223 * @return the child node at the given {@code path}
0224 * @throws NullPointerException if the given {@code path} array is
0225 * {@code null}
0226 */
0227 default Optional<T> childAtPath(final Path path) {
0228 T node = Trees.self(this);
0229 for (int i = 0; i < path.length() && node != null; ++i) {
0230 node = path.get(i) < node.childCount()
0231 ? node.childAt(path.get(i))
0232 : null;
0233 }
0234
0235 return Optional.ofNullable(node);
0236 }
0237
0238 /**
0239 * Return the child node at the given {@code path}. A path consists of the
0240 * child index at a give level, starting with level 1. (The root note has
0241 * level zero.) {@code tree.childAtPath(2)} will return the third child node
0242 * of {@code this} node, if it exists and {@code tree.childAtPath(2, 0)} will
0243 * return the first child of the third child of {@code this node}.
0244 *
0245 * @since 4.3
0246 *
0247 * @see #childAtPath(Path)
0248 *
0249 * @param path the child path
0250 * @return the child node at the given {@code path}
0251 * @throws NullPointerException if the given {@code path} array is
0252 * {@code null}
0253 * @throws IllegalArgumentException if one of the path elements is smaller
0254 * than zero
0255 */
0256 default Optional<T> childAtPath(final int... path) {
0257 return childAtPath(Path.of(path));
0258 }
0259
0260 /**
0261 * Return {@code true} if the given {@code node} is an ancestor of
0262 * {@code this} node. This operation is at worst {@code O(h)} where {@code h}
0263 * is the distance from the root to {@code this} node.
0264 *
0265 * @param node the node to test
0266 * @return {@code true} if the given {@code node} is an ancestor of
0267 * {@code this} node, {@code false} otherwise
0268 * @throws NullPointerException if the given {@code node} is {@code null}
0269 */
0270 default boolean isAncestor(final Tree<?, ?> node) {
0271 requireNonNull(node);
0272
0273 Optional<T> ancestor = Optional.of(Trees.self(this));
0274 boolean result;
0275 do {
0276 result = ancestor.filter(a -> a.identical(node)).isPresent();
0277 } while (!result &&
0278 (ancestor = ancestor.flatMap(Tree::parent)).isPresent());
0279
0280 return result;
0281 }
0282
0283 /**
0284 * Return {@code true} if the given {@code node} is a descendant of
0285 * {@code this} node. If the given {@code node} is {@code null},
0286 * {@code false} is returned. This operation is at worst {@code O(h)} where
0287 * {@code h} is the distance from the root to {@code this} node.
0288 *
0289 * @param node the node to test as descendant of this node
0290 * @return {@code true} if this node is an ancestor of the given {@code node}
0291 * @throws NullPointerException if the given {@code node} is {@code null}
0292 */
0293 default boolean isDescendant(final Tree<?, ?> node) {
0294 return requireNonNull(node).isAncestor(this);
0295 }
0296
0297 /**
0298 * Returns the nearest common ancestor to this node and the given {@code node}.
0299 * A node is considered an ancestor of itself.
0300 *
0301 * @param node {@code node} to find common ancestor with
0302 * @return nearest ancestor common to this node and the given {@code node},
0303 * or {@link Optional#empty()} if no common ancestor exists.
0304 * @throws NullPointerException if the given {@code node} is {@code null}
0305 */
0306 default Optional<T> sharedAncestor(final Tree<?, ?> node) {
0307 requireNonNull(node);
0308
0309 T ancestor = null;
0310 if (node.identical(this)) {
0311 ancestor = Trees.self(this);
0312 } else {
0313 final int level1 = level();
0314 final int level2 = node.level();
0315
0316 Tree<?, ?> node1;
0317 Tree<?, ?> node2;
0318 int diff;
0319 if (level2 > level1) {
0320 diff = level2 - level1;
0321 node1 = node;
0322 node2 = Trees.self(this);
0323 } else {
0324 diff = level1 - level2;
0325 node1 = Trees.self(this);
0326 node2 = node;
0327 }
0328
0329 while (diff > 0 && node1 != null) {
0330 node1 = node1.parent().orElse(null);
0331 --diff;
0332 }
0333
0334 do {
0335 if (node1 != null && node1.identical(node2)) {
0336 ancestor = Trees.self(node1);
0337 }
0338 node1 = node1 != null
0339 ? node1.parent().orElse(null)
0340 : null;
0341 node2 = node2.parent().orElse(null);
0342 } while (node1 != null && node2 != null && ancestor == null);
0343 }
0344
0345 return Optional.ofNullable(ancestor);
0346 }
0347
0348 /**
0349 * Returns true if and only if the given {@code node} is in the same tree as
0350 * {@code this} node.
0351 *
0352 * @param node the other node to check
0353 * @return true if the given {@code node} is in the same tree as {@code this}
0354 * node, {@code false} otherwise.
0355 * @throws NullPointerException if the given {@code node} is {@code null}
0356 */
0357 default boolean isRelated(final Tree<?, ?> node) {
0358 requireNonNull(node);
0359 return node.root().identical(root());
0360 }
0361
0362 /**
0363 * Returns the path from the root, to get to this node. The last element in
0364 * the path is this node.
0365 *
0366 * @since 5.1
0367 *
0368 * @return an array of TreeNode objects giving the path, where the
0369 * first element in the path is the root and the last
0370 * element is this node.
0371 */
0372 default ISeq<T> pathElements() {
0373 return Trees.pathElementsFromRoot(Trees.<V, T>self(this), 0).toISeq();
0374 }
0375
0376 /**
0377 * Return the {@link Path} of {@code this} tree, such that
0378 * <pre>{@code
0379 * final Tree<Integer, ?> tree = ...;
0380 * final Tree.Path path = tree.path();
0381 * assert tree == tree.getRoot()
0382 * .childAtPath(path)
0383 * .orElse(null);
0384 * }</pre>
0385 *
0386 * @since 5.1
0387 *
0388 * @return the path from the root element to {@code this} node.
0389 */
0390 default Path path() {
0391 final int[] p = Trees.pathFromRoot(Trees.<V, T>self(this), 0);
0392 return Path.of(p);
0393 }
0394
0395 /**
0396 * Returns the root of the tree that contains this node. The root is the
0397 * ancestor with no parent.
0398 *
0399 * @return the root of the tree that contains this node
0400 */
0401 default T root() {
0402 T anc = Trees.self(this);
0403 T prev;
0404
0405 do {
0406 prev = anc;
0407 anc = anc.parent().orElse(null);
0408 } while (anc != null);
0409
0410 return prev;
0411 }
0412
0413 /* *************************************************************************
0414 * Child query operations
0415 **************************************************************************/
0416
0417 /**
0418 * Return {@code true} if the given {@code node} is a child of {@code this}
0419 * node.
0420 *
0421 * @param node the other node to check
0422 * @return {@code true} if {@code node}is a child, {@code false} otherwise
0423 * @throws NullPointerException if the given {@code node} is {@code null}
0424 */
0425 default boolean isChild(final Tree<?, ?> node) {
0426 requireNonNull(node);
0427 return childCount() != 0 &&
0428 node.parent().equals(Optional.of(Trees.<V, T>self(this)));
0429 }
0430
0431 /**
0432 * Return the first child of {@code this} node, or {@code Optional.empty()}
0433 * if {@code this} node has no children.
0434 *
0435 * @return the first child of this node
0436 */
0437 default Optional<T> firstChild() {
0438 return childCount() > 0
0439 ? Optional.of(childAt(0))
0440 : Optional.empty();
0441 }
0442
0443 /**
0444 * Return the last child of {@code this} node, or {@code Optional.empty()}
0445 * if {@code this} node has no children.
0446 *
0447 * @return the last child of this node
0448 */
0449 default Optional<T> lastChild() {
0450 return childCount() > 0
0451 ? Optional.of(childAt(childCount() - 1))
0452 : Optional.empty();
0453 }
0454
0455 /**
0456 * Return the child which comes immediately after {@code this} node. This
0457 * method performs a linear search of this node's children for {@code child}
0458 * and is {@code O(n)} where n is the number of children.
0459 *
0460 * @param child the child node
0461 * @return the child of this node that immediately follows the {@code child},
0462 * or {@code Optional.empty()} if the given {@code node} is the
0463 * first node.
0464 * @throws NullPointerException if the given {@code child} is {@code null}
0465 */
0466 default Optional<T> childAfter(final Tree<?, ?> child) {
0467 requireNonNull(child);
0468
0469 final int index = indexOf(child);
0470 if (index == -1) {
0471 throw new IllegalArgumentException("The given node is not a child.");
0472 }
0473
0474 return index < childCount() - 1
0475 ? Optional.of(childAt(index + 1))
0476 : Optional.empty();
0477 }
0478
0479 /**
0480 * Return the child which comes immediately before {@code this} node. This
0481 * method performs a linear search of this node's children for {@code child}
0482 * and is {@code O(n)} where n is the number of children.
0483 *
0484 * @param child the child node
0485 * @return the child of this node that immediately precedes the {@code child},
0486 * or {@code null} if the given {@code node} is the first node.
0487 * @throws NullPointerException if the given {@code child} is {@code null}
0488 */
0489 default Optional<T> childBefore(final Tree<?, ?> child) {
0490 requireNonNull(child);
0491
0492 final int index = indexOf(child);
0493 if (index == -1) {
0494 throw new IllegalArgumentException("The given node is not a child.");
0495 }
0496
0497 return index > 0
0498 ? Optional.of(childAt(index - 1))
0499 : Optional.empty();
0500 }
0501
0502 /**
0503 * Return the node that follows {@code this} node in a pre-order traversal
0504 * of {@code this} tree node. Return {@code Optional.empty()} if this node
0505 * is the last node of the traversal. This is an inefficient way to traverse
0506 * the entire tree use an iterator instead.
0507 *
0508 * @see #preorderIterator
0509 * @return the node that follows this node in a pre-order traversal, or
0510 * {@code Optional.empty()} if this node is last
0511 */
0512 default Optional<T> nextNode() {
0513 Optional<T> next = Optional.empty();
0514
0515 if (childCount() == 0) {
0516 T node = Trees.self(this);
0517 while (node != null && (next = node.nextSibling()).isEmpty()) {
0518 node = node.parent().orElse(null);
0519 }
0520 } else {
0521 next = Optional.of(childAt(0));
0522 }
0523
0524 return next;
0525 }
0526
0527 /**
0528 * Return the node that precedes this node in a pre-order traversal of
0529 * {@code this} tree node. Returns {@code Optional.empty()} if this node is
0530 * the first node of the traversal, the root of the tree. This is an
0531 * inefficient way to traverse the entire tree; use an iterator instead.
0532 *
0533 * @see #preorderIterator
0534 * @return the node that precedes this node in a pre-order traversal, or
0535 * {@code Optional.empty()} if this node is the first
0536 */
0537 default Optional<T> previousNode() {
0538 Optional<T> node = Optional.empty();
0539
0540 if (parent().isPresent()) {
0541 final Optional<T> prev = previousSibling();
0542 if (prev.isPresent()) {
0543 node = prev.get().childCount() == 0
0544 ? prev
0545 : prev.map(Tree::lastLeaf);
0546 } else {
0547 node = parent();
0548 }
0549 }
0550
0551 return node;
0552 }
0553
0554 /* *************************************************************************
0555 * Sibling query operations
0556 **************************************************************************/
0557
0558 /**
0559 * Test if the given {@code node} is a sibling of {@code this} node.
0560 *
0561 * @param node node to test as sibling of this node
0562 * @return {@code true} if the {@code node} is a sibling of {@code this}
0563 * node
0564 * @throws NullPointerException if the given {@code node} is {@code null}
0565 */
0566 default boolean isSibling(final Tree<?, ?> node) {
0567 return identical(requireNonNull(node)) ||
0568 parent().equals(node.parent());
0569 }
0570
0571 /**
0572 * Return the number of siblings of {@code this} node. A node is its own
0573 * sibling (if it has no parent or no siblings, this method returns
0574 * {@code 1}).
0575 *
0576 * @return the number of siblings of {@code this} node
0577 */
0578 default int siblingCount() {
0579 return parent().map(Tree::childCount).orElse(1);
0580 }
0581
0582 /**
0583 * Return the next sibling of {@code this} node in the parent's children
0584 * array, or {@code null} if {@code this} node has no parent or it is the
0585 * last child of the paren. This method performs a linear search that is
0586 * {@code O(n)} where n is the number of children; to traverse the entire
0587 * array, use the iterator of the parent instead.
0588 *
0589 * @see #childStream()
0590 * @return the sibling of {@code this} node that immediately follows
0591 * {@code this} node
0592 */
0593 default Optional<T> nextSibling() {
0594 return parent().flatMap(p -> p.childAfter(Trees.<V, T>self(this)));
0595 }
0596
0597 /**
0598 * Return the previous sibling of {@code this} node in the parent's children
0599 * list, or {@code Optional.empty()} if this node has no parent or is the
0600 * parent's first child. This method performs a linear search that is O(n)
0601 * where n is the number of children.
0602 *
0603 * @return the sibling of {@code this} node that immediately precedes this
0604 * node
0605 */
0606 default Optional<T> previousSibling() {
0607 return parent().flatMap(p -> p.childBefore(Trees.<V, T>self(this)));
0608 }
0609
0610
0611 /* *************************************************************************
0612 * Leaf query operations
0613 **************************************************************************/
0614
0615 /**
0616 * Return {@code true} if {@code this} node has no children.
0617 *
0618 * @return {@code true} if {@code this} node has no children, {@code false}
0619 * otherwise
0620 */
0621 default boolean isLeaf() {
0622 return childCount() == 0;
0623 }
0624
0625 /**
0626 * Return the first leaf that is a descendant of {@code this} node; either
0627 * this node or its first child's first leaf. {@code this} node is returned
0628 * if it is a leaf.
0629 *
0630 * @see #isLeaf
0631 * @see #isDescendant
0632 * @return the first leaf in the subtree rooted at this node
0633 */
0634 default T firstLeaf() {
0635 T leaf = Trees.self(this);
0636 while (!leaf.isLeaf()) {
0637 leaf = leaf.firstChild().orElseThrow(AssertionError::new);
0638 }
0639
0640 return leaf;
0641 }
0642
0643 /**
0644 * Return the last leaf that is a descendant of this node; either
0645 * {@code this} node or its last child's last leaf. Returns {@code this}
0646 * node if it is a leaf.
0647 *
0648 * @see #isLeaf
0649 * @see #isDescendant
0650 * @return the last leaf in this subtree
0651 */
0652 default T lastLeaf() {
0653 T leaf = Trees.self(this);
0654 while (!leaf.isLeaf()) {
0655 leaf = leaf.lastChild().orElseThrow(AssertionError::new);
0656 }
0657
0658 return leaf;
0659 }
0660
0661 /**
0662 * Returns the leaf after {@code this} node or {@code Optional.empty()} if
0663 * this node is the last leaf in the tree.
0664 * <p>
0665 * In order to determine the next node, this method first performs a linear
0666 * search in the parent's child-list in order to find the current node.
0667 * <p>
0668 * That implementation makes the operation suitable for short traversals
0669 * from a known position. But to traverse all of the leaves in the tree, you
0670 * should use {@link #depthFirstIterator()} to iterator the nodes in the
0671 * tree and use {@link #isLeaf()} on each node to determine which are leaves.
0672 *
0673 * @see #depthFirstIterator
0674 * @see #isLeaf
0675 * @return return the next leaf past this node
0676 */
0677 default Optional<T> nextLeaf() {
0678 return nextSibling()
0679 .map(Tree::firstLeaf)
0680 .or(() -> parent().flatMap(Tree::nextLeaf));
0681 }
0682
0683 /**
0684 * Return the leaf before {@code this} node or {@code null} if {@code this}
0685 * node is the first leaf in the tree.
0686 * <p>
0687 * In order to determine the previous node, this method first performs a
0688 * linear search in the parent's child-list in order to find the current
0689 * node.
0690 * <p>
0691 * That implementation makes the operation suitable for short traversals
0692 * from a known position. But to traverse all of the leaves in the tree, you
0693 * should use {@link #depthFirstIterator()} to iterate the nodes in the tree
0694 * and use {@link #isLeaf()} on each node to determine which are leaves.
0695 *
0696 * @see #depthFirstIterator
0697 * @see #isLeaf
0698 * @return returns the leaf before {@code this} node
0699 */
0700 default Optional<T> previousLeaf() {
0701 return previousSibling()
0702 .map(Tree::lastLeaf)
0703 .or(() -> parent().flatMap(Tree::previousLeaf));
0704 }
0705
0706 /**
0707 * Returns the total number of leaves that are descendants of this node.
0708 * If this node is a leaf, returns {@code 1}. This method is {@code O(n)},
0709 * where n is the number of descendants of {@code this} node.
0710 *
0711 * @see #isLeaf()
0712 * @return the number of leaves beneath this node
0713 */
0714 default int leafCount() {
0715 return (int)breadthFirstStream()
0716 .filter(Tree::isLeaf)
0717 .count();
0718 }
0719
0720 /* *************************************************************************
0721 * Tree traversing.
0722 **************************************************************************/
0723
0724 /**
0725 * Return an iterator that traverses the subtree rooted at {@code this}
0726 * node in breadth-first order. The first node returned by the iterator is
0727 * {@code this} node.
0728 * <p>
0729 * Modifying the tree by inserting, removing, or moving a node invalidates
0730 * any iterator created before the modification.
0731 *
0732 * @see #depthFirstIterator
0733 * @return an iterator for traversing the tree in breadth-first order
0734 */
0735 default Iterator<T> breadthFirstIterator() {
0736 return new TreeNodeBreadthFirstIterator<>(Trees.<V, T>self(this));
0737 }
0738
0739 /**
0740 * Return an iterator that traverses the subtree rooted at {@code this}.
0741 * The first node returned by the iterator is {@code this} node.
0742 * <p>
0743 * Modifying the tree by inserting, removing, or moving a node invalidates
0744 * any iterator created before the modification.
0745 *
0746 * @see #breadthFirstIterator
0747 * @return an iterator for traversing the tree in breadth-first order
0748 */
0749 @Override
0750 default Iterator<T> iterator() {
0751 return breadthFirstIterator();
0752 }
0753
0754 /**
0755 * Return a stream that traverses the subtree rooted at {@code this} node in
0756 * breadth-first order. The first node returned by the stream is
0757 * {@code this} node.
0758 *
0759 * @see #depthFirstIterator
0760 * @see #stream()
0761 * @return a stream for traversing the tree in breadth-first order
0762 */
0763 default Stream<T> breadthFirstStream() {
0764 return StreamSupport
0765 .stream(spliteratorUnknownSize(breadthFirstIterator(), 0), false);
0766 }
0767
0768 /**
0769 * Return a stream that traverses the subtree rooted at {@code this} node in
0770 * breadth-first order. The first node returned by the stream is
0771 * {@code this} node.
0772 *
0773 * @see #breadthFirstStream
0774 * @return a stream for traversing the tree in breadth-first order
0775 */
0776 default Stream<T> stream() {
0777 return breadthFirstStream();
0778 }
0779
0780 /**
0781 * Return an iterator that traverses the subtree rooted at {@code this} node
0782 * in pre-order. The first node returned by the iterator is {@code this}
0783 * node.
0784 * <p>
0785 * Modifying the tree by inserting, removing, or moving a node invalidates
0786 * any iterator created before the modification.
0787 *
0788 * @see #postorderIterator
0789 * @return an iterator for traversing the tree in pre-order
0790 */
0791 default Iterator<T> preorderIterator() {
0792 return new TreeNodePreorderIterator<>(Trees.<V, T>self(this));
0793 }
0794
0795 /**
0796 * Return a stream that traverses the subtree rooted at {@code this} node
0797 * in pre-order. The first node returned by the stream is {@code this} node.
0798 * <p>
0799 * Modifying the tree by inserting, removing, or moving a node invalidates
0800 * any iterator created before the modification.
0801 *
0802 * @see #preorderIterator
0803 * @return a stream for traversing the tree in pre-order
0804 */
0805 default Stream<T> preorderStream() {
0806 return StreamSupport
0807 .stream(spliteratorUnknownSize(preorderIterator(), 0), false);
0808 }
0809
0810 /**
0811 * Return an iterator that traverses the subtree rooted at {@code this}
0812 * node in post-order. The first node returned by the iterator is the
0813 * leftmost leaf. This is the same as a depth-first traversal.
0814 *
0815 * @see #depthFirstIterator
0816 * @see #preorderIterator
0817 * @return an iterator for traversing the tree in post-order
0818 */
0819 default Iterator<T> postorderIterator() {
0820 return new TreeNodePostorderIterator<>(Trees.<V, T>self(this));
0821 }
0822
0823 /**
0824 * Return a stream that traverses the subtree rooted at {@code this} node in
0825 * post-order. The first node returned by the iterator is the leftmost leaf.
0826 * This is the same as a depth-first traversal.
0827 *
0828 * @see #depthFirstIterator
0829 * @see #preorderIterator
0830 * @return a stream for traversing the tree in post-order
0831 */
0832 default Stream<T> postorderStream() {
0833 return StreamSupport
0834 .stream(spliteratorUnknownSize(postorderIterator(), 0), false);
0835 }
0836
0837 /**
0838 * Return an iterator that traverses the subtree rooted at {@code this} node
0839 * in depth-first order. The first node returned by the iterator is the
0840 * leftmost leaf. This is the same as a postorder traversal.
0841 * <p>
0842 * Modifying the tree by inserting, removing, or moving a node invalidates
0843 * any iterator created before the modification.
0844 *
0845 * @see #breadthFirstIterator
0846 * @see #postorderIterator
0847 * @return an iterator for traversing the tree in depth-first order
0848 */
0849 default Iterator<T> depthFirstIterator() {
0850 return postorderIterator();
0851 }
0852
0853 /**
0854 * Return a stream that traverses the subtree rooted at {@code this} node in
0855 * depth-first. The first node returned by the iterator is the leftmost leaf.
0856 * This is the same as a post-order traversal.
0857 *
0858 * @see #depthFirstIterator
0859 * @see #preorderIterator
0860 * @return a stream for traversing the tree in post-order
0861 */
0862 default Stream<T> depthFirstStream() {
0863 return postorderStream();
0864 }
0865
0866 /**
0867 * Return an iterator that follows the path from {@code ancestor} to
0868 * {@code this} node. The iterator return {@code ancestor} as first element,
0869 * The creation of the iterator is O(m), where m is the number of nodes
0870 * between {@code this} node and the {@code ancestor}, inclusive.
0871 * <p>
0872 * Modifying the tree by inserting, removing, or moving a node invalidates
0873 * any iterator created before the modification.
0874 *
0875 * @see #isAncestor
0876 * @see #isDescendant
0877 * @param ancestor the ancestor node
0878 * @return an iterator for following the path from an ancestor of {@code this}
0879 * node to this one
0880 * @throws IllegalArgumentException if the {@code ancestor} is not an
0881 * ancestor of this node
0882 * @throws NullPointerException if the given {@code ancestor} is {@code null}
0883 */
0884 default Iterator<T> pathFromAncestorIterator(final Tree<?, ?> ancestor) {
0885 return new TreeNodePathIterator<>(ancestor, Trees.<V, T>self(this));
0886 }
0887
0888 /**
0889 * Return the path of {@code this} child node from the root node. You will
0890 * get {@code this} node, if you call {@link #childAtPath(Path)} on the
0891 * root node of {@code this} node.
0892 * <pre>{@code
0893 * final Tree<?, ?> node = ...;
0894 * final Tree<?, ?> root = node.getRoot();
0895 * final int[] path = node.childPath();
0896 * assert node == root.childAtPath(path);
0897 * }</pre>
0898 *
0899 * @since 4.4
0900 *
0901 * @see #childAtPath(Path)
0902 *
0903 * @return the path of {@code this} child node from the root node.
0904 */
0905 default Path childPath() {
0906 final Iterator<T> it = pathFromAncestorIterator(root());
0907 final int[] path = new int[level()];
0908
0909 T tree = null;
0910 int index = 0;
0911 while (it.hasNext()) {
0912 final T child = it.next();
0913 if (tree != null) {
0914 path[index++] = tree.indexOf(child);
0915 }
0916
0917 tree = child;
0918 }
0919
0920 assert index == path.length;
0921
0922 return new Path(path);
0923 }
0924
0925 /**
0926 * Tests whether {@code this} node is the same as the {@code other} node.
0927 * The default implementation returns the object identity,
0928 * {@code this == other}, of the two objects, but other implementations may
0929 * use different criteria for checking the <i>identity</i>.
0930 *
0931 * @param other the {@code other} node
0932 * @return {@code true} if the {@code other} node is the same as {@code this}
0933 * node.
0934 */
0935 default boolean identical(final Tree<?, ?> other) {
0936 return this == other;
0937 }
0938
0939 /* *************************************************************************
0940 * 'toString' methods
0941 **************************************************************************/
0942
0943 /**
0944 * Return a compact string representation of the given tree. The tree
0945 * <pre>
0946 * mul
0947 * ├── div
0948 * │ ├── cos
0949 * │ │ └── 1.0
0950 * │ └── cos
0951 * │ └── π
0952 * └── sin
0953 * └── mul
0954 * ├── 1.0
0955 * └── z
0956 * </pre>
0957 * is printed as
0958 * <pre>
0959 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
0960 * </pre>
0961 *
0962 * @since 4.3
0963 *
0964 * @see #toParenthesesString()
0965 * @see TreeFormatter#PARENTHESES
0966 *
0967 * @param mapper the {@code mapper} which converts the tree value to a string
0968 * @return the string representation of the given tree
0969 */
0970 default String toParenthesesString(final Function<? super V, String> mapper) {
0971 return TreeFormatter.PARENTHESES.format(this, mapper);
0972 }
0973
0974 /**
0975 * Return a compact string representation of the given tree. The tree
0976 * <pre>
0977 * mul
0978 * ├── div
0979 * │ ├── cos
0980 * │ │ └── 1.0
0981 * │ └── cos
0982 * │ └── π
0983 * └── sin
0984 * └── mul
0985 * ├── 1.0
0986 * └── z
0987 * </pre>
0988 * is printed as
0989 * <pre>
0990 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
0991 * </pre>
0992 *
0993 * @since 4.3
0994 *
0995 * @see #toParenthesesString(Function)
0996 * @see TreeFormatter#PARENTHESES
0997 *
0998 * @return the string representation of the given tree
0999 * @throws NullPointerException if the {@code mapper} is {@code null}
1000 */
1001 default String toParenthesesString() {
1002 return toParenthesesString(Objects::toString);
1003 }
1004
1005 /* *************************************************************************
1006 * Static helper methods.
1007 **************************************************************************/
1008
1009 /**
1010 * Calculates the hash code of the given tree.
1011 *
1012 * @param tree the tree where the hash is calculated from
1013 * @return the hash code of the tree
1014 * @throws NullPointerException if the given {@code tree} is {@code null}
1015 */
1016 static int hashCode(final Tree<?, ?> tree) {
1017 return tree != null
1018 ? tree.breadthFirstStream()
1019 .mapToInt(node -> 31*Objects.hashCode(node.value()) + 37)
1020 .sum() + 17
1021 : 0;
1022 }
1023
1024 /**
1025 * Checks if the two given trees has the same structure with the same values.
1026 *
1027 * @param a the first tree
1028 * @param b the second tree
1029 * @return {@code true} if the two given trees are structurally equals,
1030 * {@code false} otherwise
1031 */
1032 static boolean equals(final Tree<?, ?> a, final Tree<?, ?> b) {
1033 return Trees.equals(a, b);
1034 }
1035
1036 /**
1037 * Return a string representation of the given tree, like the following
1038 * example.
1039 *
1040 * <pre>
1041 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
1042 * </pre>
1043 *
1044 * This method is intended to be used when override the
1045 * {@link Object#toString()} method.
1046 *
1047 * @param tree the input tree
1048 * @return the string representation of the given tree
1049 */
1050 static String toString(final Tree<?, ?> tree) {
1051 return tree.toParenthesesString();
1052 }
1053
1054
1055 /* *************************************************************************
1056 * Inner classes
1057 **************************************************************************/
1058
1059 /**
1060 * This class represents the path to child within a given tree. It allows to
1061 * point (and fetch) a tree child.
1062 *
1063 * @see Tree#childAtPath(Path)
1064 *
1065 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
1066 * @version 6.0
1067 * @since 4.4
1068 */
1069 final class Path implements Serializable {
1070 private static final long serialVersionUID = 1L;
1071
1072 private final int[] _path;
1073
1074 private Path(final int[] path) {
1075 _path = requireNonNull(path);
1076 }
1077
1078 /**
1079 * Return the path length, which is the level of the child {@code this}
1080 * path points to.
1081 *
1082 * @return the path length
1083 */
1084 public int length() {
1085 return _path.length;
1086 }
1087
1088 /**
1089 * Return the child index at the given index (child level).
1090 *
1091 * @param index the path index
1092 * @return the child index at the given child level
1093 * @throws IndexOutOfBoundsException if the index is not with the range
1094 * {@code [0, length())}
1095 */
1096 public int get(final int index) {
1097 return _path[index];
1098 }
1099
1100 /**
1101 * Return the path as {@code int[]} array.
1102 *
1103 * @return the path as {@code int[]} array
1104 */
1105 public int[] toArray() {
1106 return _path.clone();
1107 }
1108
1109 /**
1110 * Appends the given {@code path} to {@code this} one.
1111 *
1112 * @param path the path to append
1113 * @return a new {@code Path} with the given {@code path} appended
1114 * @throws NullPointerException if the given {@code path} is {@code null}
1115 */
1116 public Path append(final Path path) {
1117 final int[] p = new int[length() + path.length()];
1118 System.arraycopy(_path, 0, p, 0, length());
1119 System.arraycopy(path._path, 0, p, length(), path.length());
1120 return new Path(p);
1121 }
1122
1123 @Override
1124 public int hashCode() {
1125 return Arrays.hashCode(_path);
1126 }
1127
1128 @Override
1129 public boolean equals(final Object obj) {
1130 return obj == this ||
1131 obj instanceof Path &&
1132 Arrays.equals(_path, ((Path)obj)._path);
1133 }
1134
1135 @Override
1136 public String toString() {
1137 return Arrays.toString(_path);
1138 }
1139
1140 /**
1141 * Create a new path object from the given child indexes.
1142 *
1143 * @param path the child indexes
1144 * @return a new tree path
1145 * @throws IllegalArgumentException if one of the path elements is
1146 * smaller than zero
1147 */
1148 public static Path of(final int... path) {
1149 for (int i = 0; i < path.length; ++i) {
1150 if (path[i] < 0) {
1151 throw new IllegalArgumentException(format(
1152 "Path element at position %d is smaller than zero: %d",
1153 i, path[i]
1154 ));
1155 }
1156 }
1157
1158 return new Path(path.clone());
1159 }
1160
1161
1162 /* *********************************************************************
1163 * Java object serialization
1164 * ********************************************************************/
1165
1166 private Object writeReplace() {
1167 return new Serial(Serial.TREE_PATH, this);
1168 }
1169
1170 private void readObject(final ObjectInputStream stream)
1171 throws InvalidObjectException
1172 {
1173 throw new InvalidObjectException("Serialization proxy required.");
1174 }
1175
1176
1177 void write(final DataOutput out) throws IOException {
1178 writeIntArray(_path, out);
1179 }
1180
1181 static Object read(final DataInput in) throws IOException {
1182 return Path.of(readIntArray(in));
1183 }
1184
1185 }
1186
1187 }
|