0001 /*
0002 * Java Genetic Algorithm Library (jenetics-5.1.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 5.1
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 childAt(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.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 indexOf(final Tree<?, ?> child) {
0171 int index = -1;
0172 for (int i = 0, n = childCount(); i < n && index == -1; ++i) {
0173 if (childAt(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 Trees.countChildren(this) + 1;
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.childAt(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.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.self(this);
0308 } else {
0309 diff = level1 - level2;
0310 node1 = Trees.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.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 * @deprecated Use {@link #pathElements()} instead
0355 */
0356 @Deprecated
0357 public default ISeq<T> getPath() {
0358 return Trees.pathElementsFromRoot(Trees.<V, T>self(this), 0).toISeq();
0359 }
0360
0361 /**
0362 * Returns the path from the root, to get to this node. The last element in
0363 * the path is this node.
0364 *
0365 * @since 5.1
0366 *
0367 * @return an array of TreeNode objects giving the path, where the
0368 * first element in the path is the root and the last
0369 * element is this node.
0370 */
0371 public default ISeq<T> pathElements() {
0372 return Trees.pathElementsFromRoot(Trees.<V, T>self(this), 0).toISeq();
0373 }
0374
0375 /**
0376 * Return the {@link Path} of {@code this} tree, such that
0377 * <pre>{@code
0378 * final Tree<Integer, ?> tree = ...;
0379 * final Tree.Path path = tree.path();
0380 * assert tree == tree.getRoot()
0381 * .childAtPath(path)
0382 * .orElse(null);
0383 * }</pre>
0384 *
0385 * @since 5.1
0386 *
0387 * @return the path from the root element to {@code this} node.
0388 */
0389 public default Path path() {
0390 final int[] p = Trees.pathFromRoot(Trees.<V, T>self(this), 0);
0391 return Path.of(p);
0392 }
0393
0394 /**
0395 * Returns the root of the tree that contains this node. The root is the
0396 * ancestor with no parent.
0397 *
0398 * @return the root of the tree that contains this node
0399 */
0400 public default T getRoot() {
0401 T anc = Trees.self(this);
0402 T prev;
0403
0404 do {
0405 prev = anc;
0406 anc = anc.getParent().orElse(null);
0407 } while (anc != null);
0408
0409 return prev;
0410 }
0411
0412 /* *************************************************************************
0413 * Child query operations
0414 **************************************************************************/
0415
0416 /**
0417 * Return {@code true} if the given {@code node} is a child of {@code this}
0418 * node.
0419 *
0420 * @param node the other node to check
0421 * @return {@code true} if {@code node}is a child, {@code false} otherwise
0422 * @throws NullPointerException if the given {@code node} is {@code null}
0423 */
0424 public default boolean isChild(final Tree<?, ?> node) {
0425 requireNonNull(node);
0426 return childCount() != 0 &&
0427 node.getParent().equals(Optional.of(Trees.<V, T>self(this)));
0428 }
0429
0430 /**
0431 * Return the first child of {@code this} node, or {@code Optional.empty()}
0432 * if {@code this} node has no children.
0433 *
0434 * @return the first child of this node
0435 */
0436 public default Optional<T> firstChild() {
0437 return childCount() > 0
0438 ? Optional.of(childAt(0))
0439 : Optional.empty();
0440 }
0441
0442 /**
0443 * Return the last child of {@code this} node, or {@code Optional.empty()}
0444 * if {@code this} node has no children.
0445 *
0446 * @return the last child of this node
0447 */
0448 public default Optional<T> lastChild() {
0449 return childCount() > 0
0450 ? Optional.of(childAt(childCount() - 1))
0451 : Optional.empty();
0452 }
0453
0454 /**
0455 * Return the child which comes immediately after {@code this} node. This
0456 * method performs a linear search of this node's children for {@code child}
0457 * and is {@code O(n)} where n is the number of children.
0458 *
0459 * @param child the child node
0460 * @return the child of this node that immediately follows the {@code child},
0461 * or {@code Optional.empty()} if the given {@code node} is the
0462 * first node.
0463 * @throws NullPointerException if the given {@code child} is {@code null}
0464 */
0465 public default Optional<T> childAfter(final Tree<?, ?> child) {
0466 requireNonNull(child);
0467
0468 final int index = indexOf(child);
0469 if (index == -1) {
0470 throw new IllegalArgumentException("The given node is not a child.");
0471 }
0472
0473 return index < childCount() - 1
0474 ? Optional.of(childAt(index + 1))
0475 : Optional.empty();
0476 }
0477
0478 /**
0479 * Return the child which comes immediately before {@code this} node. This
0480 * method performs a linear search of this node's children for {@code child}
0481 * and is {@code O(n)} where n is the number of children.
0482 *
0483 * @param child the child node
0484 * @return the child of this node that immediately precedes the {@code child},
0485 * or {@code null} if the given {@code node} is the first node.
0486 * @throws NullPointerException if the given {@code child} is {@code null}
0487 */
0488 public default Optional<T> childBefore(final Tree<?, ?> child) {
0489 requireNonNull(child);
0490
0491 final int index = indexOf(child);
0492 if (index == -1) {
0493 throw new IllegalArgumentException("The given node is not a child.");
0494 }
0495
0496 return index > 0
0497 ? Optional.of(childAt(index - 1))
0498 : Optional.empty();
0499 }
0500
0501 /**
0502 * Return the node that follows {@code this} node in a pre-order traversal
0503 * of {@code this} tree node. Return {@code Optional.empty()} if this node
0504 * is the last node of the traversal. This is an inefficient way to traverse
0505 * the entire tree use an iterator instead.
0506 *
0507 * @see #preorderIterator
0508 * @return the node that follows this node in a pre-order traversal, or
0509 * {@code Optional.empty()} if this node is last
0510 */
0511 public default Optional<T> nextNode() {
0512 Optional<T> next = Optional.empty();
0513
0514 if (childCount() == 0) {
0515 T node = Trees.self(this);
0516 while (node != null && !(next = node.nextSibling()).isPresent()) {
0517 node = node.getParent().orElse(null);
0518 }
0519 } else {
0520 next = Optional.of(childAt(0));
0521 }
0522
0523 return next;
0524 }
0525
0526 /**
0527 * Return the node that precedes this node in a pre-order traversal of
0528 * {@code this} tree node. Returns {@code Optional.empty()} if this node is
0529 * the first node of the traversal, the root of the tree. This is an
0530 * inefficient way to traverse the entire tree; use an iterator instead.
0531 *
0532 * @see #preorderIterator
0533 * @return the node that precedes this node in a pre-order traversal, or
0534 * {@code Optional.empty()} if this node is the first
0535 */
0536 public default Optional<T> previousNode() {
0537 Optional<T> node = Optional.empty();
0538
0539 if (getParent().isPresent()) {
0540 final Optional<T> prev = previousSibling();
0541 if (prev.isPresent()) {
0542 node = prev.get().childCount() == 0
0543 ? prev
0544 : prev.map(Tree<V, T>::lastLeaf);
0545 } else {
0546 node = getParent();
0547 }
0548 }
0549
0550 return node;
0551 }
0552
0553 /* *************************************************************************
0554 * Sibling query operations
0555 **************************************************************************/
0556
0557 /**
0558 * Test if the given {@code node} is a sibling of {@code this} node.
0559 *
0560 * @param node node to test as sibling of this node
0561 * @return {@code true} if the {@code node} is a sibling of {@code this}
0562 * node
0563 * @throws NullPointerException if the given {@code node} is {@code null}
0564 */
0565 public default boolean isSibling(final Tree<?, ?> node) {
0566 return identical(requireNonNull(node)) ||
0567 getParent().equals(node.getParent());
0568 }
0569
0570 /**
0571 * Return the number of siblings of {@code this} node. A node is its own
0572 * sibling (if it has no parent or no siblings, this method returns
0573 * {@code 1}).
0574 *
0575 * @return the number of siblings of {@code this} node
0576 */
0577 public default int siblingCount() {
0578 return getParent().map(Tree<V, T>::childCount).orElse(1);
0579 }
0580
0581 /**
0582 * Return the next sibling of {@code this} node in the parent's children
0583 * array, or {@code null} if {@code this} node has no parent or it is the
0584 * last child of the paren. This method performs a linear search that is
0585 * {@code O(n)} where n is the number of children; to traverse the entire
0586 * array, use the iterator of the parent instead.
0587 *
0588 * @see #childStream()
0589 * @return the sibling of {@code this} node that immediately follows
0590 * {@code this} node
0591 */
0592 public default Optional<T> nextSibling() {
0593 return getParent().flatMap(p -> p.childAfter(Trees.<V, T>self(this)));
0594 }
0595
0596 /**
0597 * Return the previous sibling of {@code this} node in the parent's children
0598 * list, or {@code Optional.empty()} if this node has no parent or is the
0599 * parent's first child. This method performs a linear search that is O(n)
0600 * where n is the number of children.
0601 *
0602 * @return the sibling of {@code this} node that immediately precedes this
0603 * node
0604 */
0605 public default Optional<T> previousSibling() {
0606 return getParent().flatMap(p -> p.childBefore(Trees.<V, T>self(this)));
0607 }
0608
0609
0610 /* *************************************************************************
0611 * Leaf query operations
0612 **************************************************************************/
0613
0614 /**
0615 * Return {@code true} if {@code this} node has no children.
0616 *
0617 * @return {@code true} if {@code this} node has no children, {@code false}
0618 * otherwise
0619 */
0620 public default boolean isLeaf() {
0621 return childCount() == 0;
0622 }
0623
0624 /**
0625 * Return the first leaf that is a descendant of {@code this} node; either
0626 * this node or its first child's first leaf. {@code this} node is returned
0627 * if it is a leaf.
0628 *
0629 * @see #isLeaf
0630 * @see #isDescendant
0631 * @return the first leaf in the subtree rooted at this node
0632 */
0633 public default T firstLeaf() {
0634 T leaf = Trees.self(this);
0635 while (!leaf.isLeaf()) {
0636 leaf = leaf.firstChild().orElseThrow(AssertionError::new);
0637 }
0638
0639 return leaf;
0640 }
0641
0642 /**
0643 * Return the last leaf that is a descendant of this node; either
0644 * {@code this} node or its last child's last leaf. Returns {@code this}
0645 * node if it is a leaf.
0646 *
0647 * @see #isLeaf
0648 * @see #isDescendant
0649 * @return the last leaf in this subtree
0650 */
0651 public default T lastLeaf() {
0652 T leaf = Trees.self(this);
0653 while (!leaf.isLeaf()) {
0654 leaf = leaf.lastChild().orElseThrow(AssertionError::new);
0655 }
0656
0657 return leaf;
0658 }
0659
0660 /**
0661 * Returns the leaf after {@code this} node or {@code Optional.empty()} if
0662 * this node is the last leaf in the tree.
0663 * <p>
0664 * In order to determine the next node, this method first performs a linear
0665 * search in the parent's child-list in order to find the current node.
0666 * <p>
0667 * That implementation makes the operation suitable for short traversals
0668 * from a known position. But to traverse all of the leaves in the tree, you
0669 * should use {@link #depthFirstIterator()} to iterator the nodes in the
0670 * tree and use {@link #isLeaf()} on each node to determine which are leaves.
0671 *
0672 * @see #depthFirstIterator
0673 * @see #isLeaf
0674 * @return return the next leaf past this node
0675 */
0676 public default Optional<T> nextLeaf() {
0677 return nextSibling()
0678 .map(s -> Optional.of(s.firstLeaf()))
0679 .orElseGet(() -> getParent().flatMap(Tree<V, T>::nextLeaf));
0680 }
0681
0682 /**
0683 * Return the leaf before {@code this} node or {@code null} if {@code this}
0684 * node is the first leaf in the tree.
0685 * <p>
0686 * In order to determine the previous node, this method first performs a
0687 * linear search in the parent's child-list in order to find the current
0688 * node.
0689 * <p>
0690 * That implementation makes the operation suitable for short traversals
0691 * from a known position. But to traverse all of the leaves in the tree, you
0692 * should use {@link #depthFirstIterator()} to iterate the nodes in the tree
0693 * and use {@link #isLeaf()} on each node to determine which are leaves.
0694 *
0695 * @see #depthFirstIterator
0696 * @see #isLeaf
0697 * @return returns the leaf before {@code this} node
0698 */
0699 public default Optional<T> previousLeaf() {
0700 return previousSibling()
0701 .map(s -> Optional.of(s.lastLeaf()))
0702 .orElseGet(() -> getParent().flatMap(Tree<V, T>::previousLeaf));
0703 }
0704
0705 /**
0706 * Returns the total number of leaves that are descendants of this node.
0707 * If this node is a leaf, returns {@code 1}. This method is {@code O(n)},
0708 * where n is the number of descendants of {@code this} node.
0709 *
0710 * @see #isLeaf()
0711 * @return the number of leaves beneath this node
0712 */
0713 public default int leafCount() {
0714 return (int)breadthFirstStream()
0715 .filter(Tree<V, T>::isLeaf)
0716 .count();
0717 }
0718
0719 /* *************************************************************************
0720 * Tree traversing.
0721 **************************************************************************/
0722
0723 /**
0724 * Return an iterator that traverses the subtree rooted at {@code this}
0725 * node in breadth-first order. The first node returned by the iterator is
0726 * {@code this} node.
0727 * <p>
0728 * Modifying the tree by inserting, removing, or moving a node invalidates
0729 * any iterator created before the modification.
0730 *
0731 * @see #depthFirstIterator
0732 * @return an iterator for traversing the tree in breadth-first order
0733 */
0734 public default Iterator<T> breadthFirstIterator() {
0735 return new TreeNodeBreadthFirstIterator<>(Trees.<V, T>self(this));
0736 }
0737
0738 /**
0739 * Return an iterator that traverses the subtree rooted at {@code this}.
0740 * The first node returned by the iterator is {@code this} node.
0741 * <p>
0742 * Modifying the tree by inserting, removing, or moving a node invalidates
0743 * any iterator created before the modification.
0744 *
0745 * @see #breadthFirstIterator
0746 * @return an iterator for traversing the tree in breadth-first order
0747 */
0748 @Override
0749 public default Iterator<T> iterator() {
0750 return breadthFirstIterator();
0751 }
0752
0753 /**
0754 * Return a stream that traverses the subtree rooted at {@code this} node in
0755 * breadth-first order. The first node returned by the stream is
0756 * {@code this} node.
0757 *
0758 * @see #depthFirstIterator
0759 * @see #stream()
0760 * @return a stream for traversing the tree in breadth-first order
0761 */
0762 public default Stream<T> breadthFirstStream() {
0763 return StreamSupport
0764 .stream(spliteratorUnknownSize(breadthFirstIterator(), 0), false);
0765 }
0766
0767 /**
0768 * Return a stream that traverses the subtree rooted at {@code this} node in
0769 * breadth-first order. The first node returned by the stream is
0770 * {@code this} node.
0771 *
0772 * @see #breadthFirstStream
0773 * @return a stream for traversing the tree in breadth-first order
0774 */
0775 public default Stream<T> stream() {
0776 return breadthFirstStream();
0777 }
0778
0779 /**
0780 * Return an iterator that traverses the subtree rooted at {@code this} node
0781 * in pre-order. The first node returned by the iterator is {@code this}
0782 * node.
0783 * <p>
0784 * Modifying the tree by inserting, removing, or moving a node invalidates
0785 * any iterator created before the modification.
0786 *
0787 * @see #postorderIterator
0788 * @return an iterator for traversing the tree in pre-order
0789 */
0790 public default Iterator<T> preorderIterator() {
0791 return new TreeNodePreorderIterator<>(Trees.<V, T>self(this));
0792 }
0793
0794 /**
0795 * Return a stream that traverses the subtree rooted at {@code this} node
0796 * in pre-order. The first node returned by the stream is {@code this} node.
0797 * <p>
0798 * Modifying the tree by inserting, removing, or moving a node invalidates
0799 * any iterator created before the modification.
0800 *
0801 * @see #preorderIterator
0802 * @return a stream for traversing the tree in pre-order
0803 */
0804 public default Stream<T> preorderStream() {
0805 return StreamSupport
0806 .stream(spliteratorUnknownSize(preorderIterator(), 0), false);
0807 }
0808
0809 /**
0810 * Return an iterator that traverses the subtree rooted at {@code this}
0811 * node in post-order. The first node returned by the iterator is the
0812 * leftmost leaf. This is the same as a depth-first traversal.
0813 *
0814 * @see #depthFirstIterator
0815 * @see #preorderIterator
0816 * @return an iterator for traversing the tree in post-order
0817 */
0818 public default Iterator<T> postorderIterator() {
0819 return new TreeNodePostorderIterator<>(Trees.<V, T>self(this));
0820 }
0821
0822 /**
0823 * Return a stream that traverses the subtree rooted at {@code this} node in
0824 * post-order. The first node returned by the iterator is the leftmost leaf.
0825 * This is the same as a depth-first traversal.
0826 *
0827 * @see #depthFirstIterator
0828 * @see #preorderIterator
0829 * @return a stream for traversing the tree in post-order
0830 */
0831 public default Stream<T> postorderStream() {
0832 return StreamSupport
0833 .stream(spliteratorUnknownSize(postorderIterator(), 0), false);
0834 }
0835
0836 /**
0837 * Return an iterator that traverses the subtree rooted at {@code this} node
0838 * in depth-first order. The first node returned by the iterator is the
0839 * leftmost leaf. This is the same as a postorder traversal.
0840 * <p>
0841 * Modifying the tree by inserting, removing, or moving a node invalidates
0842 * any iterator created before the modification.
0843 *
0844 * @see #breadthFirstIterator
0845 * @see #postorderIterator
0846 * @return an iterator for traversing the tree in depth-first order
0847 */
0848 public default Iterator<T> depthFirstIterator() {
0849 return postorderIterator();
0850 }
0851
0852 /**
0853 * Return a stream that traverses the subtree rooted at {@code this} node in
0854 * depth-first. The first node returned by the iterator is the leftmost leaf.
0855 * This is the same as a post-order traversal.
0856 *
0857 * @see #depthFirstIterator
0858 * @see #preorderIterator
0859 * @return a stream for traversing the tree in post-order
0860 */
0861 public default Stream<T> depthFirstStream() {
0862 return postorderStream();
0863 }
0864
0865 /**
0866 * Return an iterator that follows the path from {@code ancestor} to
0867 * {@code this} node. The iterator return {@code ancestor} as first element,
0868 * The creation of the iterator is O(m), where m is the number of nodes
0869 * between {@code this} node and the {@code ancestor}, inclusive.
0870 * <p>
0871 * Modifying the tree by inserting, removing, or moving a node invalidates
0872 * any iterator created before the modification.
0873 *
0874 * @see #isAncestor
0875 * @see #isDescendant
0876 * @param ancestor the ancestor node
0877 * @return an iterator for following the path from an ancestor of {@code this}
0878 * node to this one
0879 * @throws IllegalArgumentException if the {@code ancestor} is not an
0880 * ancestor of this node
0881 * @throws NullPointerException if the given {@code ancestor} is {@code null}
0882 */
0883 public default Iterator<T>
0884 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 public default Path childPath() {
0906 final Iterator<T> it = pathFromAncestorIterator(getRoot());
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 public 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 public default String
0971 toParenthesesString(final Function<? super V, String> mapper) {
0972 return TreeFormatter.PARENTHESES.format(this, mapper);
0973 }
0974
0975 /**
0976 * Return a compact string representation of the given tree. The tree
0977 * <pre>
0978 * mul
0979 * ├── div
0980 * │ ├── cos
0981 * │ │ └── 1.0
0982 * │ └── cos
0983 * │ └── π
0984 * └── sin
0985 * └── mul
0986 * ├── 1.0
0987 * └── z
0988 * </pre>
0989 * is printed as
0990 * <pre>
0991 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
0992 * </pre>
0993 *
0994 * @since 4.3
0995 *
0996 * @see #toParenthesesString(Function)
0997 * @see TreeFormatter#PARENTHESES
0998 *
0999 * @return the string representation of the given tree
1000 * @throws NullPointerException if the {@code mapper} is {@code null}
1001 */
1002 public default String toParenthesesString() {
1003 return toParenthesesString(Objects::toString);
1004 }
1005
1006 /* *************************************************************************
1007 * Static helper methods.
1008 **************************************************************************/
1009
1010 /**
1011 * Calculates the hash code of the given tree.
1012 *
1013 * @param tree the tree where the hash is calculated from
1014 * @return the hash code of the tree
1015 * @throws NullPointerException if the given {@code tree} is {@code null}
1016 */
1017 public static int hashCode(final Tree<?, ?> tree) {
1018 return tree != null
1019 ? tree.breadthFirstStream()
1020 .mapToInt(node -> 31*Objects.hashCode(node.getValue()) + 37)
1021 .sum() + 17
1022 : 0;
1023 }
1024
1025 /**
1026 * Checks if the two given trees has the same structure with the same values.
1027 *
1028 * @param a the first tree
1029 * @param b the second tree
1030 * @return {@code true} if the two given trees are structurally equals,
1031 * {@code false} otherwise
1032 */
1033 public static boolean equals(final Tree<?, ?> a, final Tree<?, ?> b) {
1034 return Trees.equals(a, b);
1035 }
1036
1037 /**
1038 * Return a string representation of the given tree, like the following
1039 * example.
1040 *
1041 * <pre>
1042 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
1043 * </pre>
1044 *
1045 * This method is intended to be used when override the
1046 * {@link Object#toString()} method.
1047 *
1048 * @param tree the input tree
1049 * @return the string representation of the given tree
1050 */
1051 public static String toString(final Tree<?, ?> tree) {
1052 return tree.toParenthesesString();
1053 }
1054
1055
1056 /* *************************************************************************
1057 * Inner classes
1058 **************************************************************************/
1059
1060 /**
1061 * This class represents the path to child within a given tree. It allows to
1062 * point (and fetch) a tree child.
1063 *
1064 * @see Tree#childAtPath(Path)
1065 *
1066 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
1067 * @version 4.4
1068 * @since 4.4
1069 */
1070 public static final class Path implements Serializable {
1071 private static final long serialVersionUID = 1L;
1072
1073 private final int[] _path;
1074
1075 private Path(final int[] path) {
1076 _path = requireNonNull(path);
1077 }
1078
1079 /**
1080 * Return the path length, which is the level of the child {@code this}
1081 * path points to.
1082 *
1083 * @return the path length
1084 */
1085 public int length() {
1086 return _path.length;
1087 }
1088
1089 /**
1090 * Return the child index at the given index (child level).
1091 *
1092 * @param index the path index
1093 * @return the child index at the given child level
1094 * @throws IndexOutOfBoundsException if the index is not with the range
1095 * {@code [0, length())}
1096 */
1097 public int get(final int index) {
1098 return _path[index];
1099 }
1100
1101 /**
1102 * Return the path as {@code int[]} array.
1103 *
1104 * @return the path as {@code int[]} array
1105 */
1106 public int[] toArray() {
1107 return _path.clone();
1108 }
1109
1110 /**
1111 * Appends the given {@code path} to {@code this} one.
1112 *
1113 * @param path the path to append
1114 * @return a new {@code Path} with the given {@code path} appended
1115 * @throws NullPointerException if the given {@code path} is {@code null}
1116 */
1117 public Path append(final Path path) {
1118 final int[] p = new int[length() + path.length()];
1119 System.arraycopy(_path, 0, p, 0, length());
1120 System.arraycopy(path._path, 0, p, length(), path.length());
1121 return new Path(p);
1122 }
1123
1124 @Override
1125 public int hashCode() {
1126 return Arrays.hashCode(_path);
1127 }
1128
1129 @Override
1130 public boolean equals(final Object obj) {
1131 return obj == this ||
1132 obj instanceof Path &&
1133 Arrays.equals(_path, ((Path)obj)._path);
1134 }
1135
1136 @Override
1137 public String toString() {
1138 return Arrays.toString(_path);
1139 }
1140
1141 /**
1142 * Create a new path object from the given child indexes.
1143 *
1144 * @param path the child indexes
1145 * @return a new tree path
1146 * @throws IllegalArgumentException if one of the path elements is
1147 * smaller than zero
1148 */
1149 public static Path of(final int... path) {
1150 for (int i = 0; i < path.length; ++i) {
1151 if (path[i] < 0) {
1152 throw new IllegalArgumentException(format(
1153 "Path element at position %d is smaller than zero: %d",
1154 i, path[i]
1155 ));
1156 }
1157 }
1158
1159 return new Path(path.clone());
1160 }
1161 }
1162
1163 }
|