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