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