001/* 002 * Java Genetic Algorithm Library (jenetics-5.1.0). 003 * Copyright (c) 2007-2019 Franz Wilhelmstötter 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 * 017 * Author: 018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com) 019 */ 020package io.jenetics.ext.util; 021 022import static java.lang.String.format; 023import static java.util.Objects.requireNonNull; 024import static java.util.Spliterators.spliteratorUnknownSize; 025 026import java.io.Serializable; 027import java.util.Arrays; 028import java.util.Iterator; 029import java.util.Objects; 030import java.util.Optional; 031import java.util.function.Function; 032import java.util.stream.Stream; 033import java.util.stream.StreamSupport; 034 035import io.jenetics.util.ISeq; 036 037/** 038 * General purpose tree structure. The interface only contains tree read methods. 039 * For a mutable tree implementation have a look at the {@link TreeNode} class. 040 * 041 * @see TreeNode 042 * 043 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a> 044 * @version 5.1 045 * @since 3.9 046 */ 047public interface Tree<V, T extends Tree<V, T>> extends Iterable<T> { 048 049 /* ************************************************************************* 050 * Basic (abstract) operations. All other tree operations can be derived 051 * from this methods. 052 **************************************************************************/ 053 054 /** 055 * Return the value of the current {@code Tree} node. The value may be 056 * {@code null}. 057 * 058 * @return the value of the current {@code Tree} node 059 */ 060 public V getValue(); 061 062 /** 063 * Return the <em>parent</em> node of this tree node. 064 * 065 * @return the parent node, or {@code Optional.empty()} if this node is the 066 * root of the tree 067 */ 068 public Optional<T> getParent(); 069 070 /** 071 * Return the child node with the given index. 072 * 073 * @param index the child index 074 * @return the child node with the given index 075 * @throws IndexOutOfBoundsException if the {@code index} is out of 076 * bounds ({@code [0, childCount())}) 077 */ 078 public T childAt(final int index); 079 080 /** 081 * Return the number of children this tree node consists of. 082 * 083 * @return the number of children this tree node consists of 084 */ 085 public int childCount(); 086 087 088 /* ************************************************************************* 089 * Derived operations 090 **************************************************************************/ 091 092 /** 093 * Return an iterator of the children of this {@code Tree} node. 094 * 095 * @return an iterator of the children of this {@code Tree} node. 096 */ 097 public default Iterator<T> childIterator() { 098 return new TreeChildIterator<V, T>(Trees.self(this)); 099 } 100 101 /** 102 * Return a forward-order stream of this node's children. 103 * 104 * @return a stream of children of {@code this} node 105 */ 106 public default Stream<T> childStream() { 107 return StreamSupport 108 .stream(spliteratorUnknownSize(childIterator(), 0), false); 109 } 110 111 /** 112 * Returns {@code true} if this node is the root of the tree. 113 * 114 * @return {@code true} if this node is the root of its tree, {@code false} 115 * otherwise 116 */ 117 public default boolean isRoot() { 118 return !getParent().isPresent(); 119 } 120 121 /** 122 * Returns the depth of the tree rooted at this node. The <i>depth</i> of a 123 * tree is the longest distance from {@code this} node to a leaf. If 124 * {@code this} node has no children, 0 is returned. This operation is much 125 * more expensive than {@link #level()} because it must effectively traverse 126 * the entire tree rooted at {@code this} node. 127 * 128 * @return the depth of the tree whose root is this node 129 */ 130 public default int depth() { 131 final Iterator<T> it = breadthFirstIterator(); 132 133 T last = null; 134 while (it.hasNext()) { 135 last = it.next(); 136 } 137 138 assert last != null; 139 return last.level() - level(); 140 } 141 142 /** 143 * Returns the number of levels above this node. The <i>level</i> of a tree 144 * is the distance from the root to {@code this} node. If {@code this} node 145 * is the root, returns 0. 146 * 147 * @return the number of levels above this node 148 */ 149 public default int level() { 150 Optional<T> ancestor = Optional.of(Trees.self(this)); 151 int levels = 0; 152 while ((ancestor = ancestor.flatMap(Tree<V, T>::getParent)).isPresent()) { 153 ++levels; 154 } 155 156 return levels; 157 } 158 159 /** 160 * Returns the index of the specified child in this node's child array, or 161 * {@code -1} if {@code this} node doesn't contain the given {@code child}. 162 * This method performs a linear search and is O(n) where {@code n} is the 163 * number of children. 164 * 165 * @param child the TreeNode to search for among this node's children 166 * @throws NullPointerException if the given {@code child} is {@code null} 167 * @return the index of the node in this node's child array, or {@code -1} 168 * if the node could not be found 169 */ 170 public default int indexOf(final Tree<?, ?> child) { 171 int index = -1; 172 for (int i = 0, n = childCount(); i < n && index == -1; ++i) { 173 if (childAt(i).identical(child)) { 174 index = i; 175 } 176 } 177 178 return index; 179 } 180 181 /** 182 * Return the number of nodes of {@code this} node (sub-tree). 183 * 184 * @return the number of nodes of {@code this} node (sub-tree) 185 */ 186 public default int size() { 187 return Trees.countChildren(this) + 1; 188 } 189 190 191 /* ************************************************************************* 192 * Query operations 193 **************************************************************************/ 194 195 /** 196 * Return the child node at the given {@code path}. A path consists of the 197 * child index at a give level, starting with level 1. (The root note has 198 * level zero.) {@code tree.childAtPath(Path.of(2))} will return the third 199 * child node of {@code this} node, if it exists and 200 * {@code tree.childAtPath(Path.of(2, 0))} will return the first child of 201 * the third child of {@code this node}. 202 * 203 * @since 4.4 204 * 205 * @see #childAtPath(int...) 206 * 207 * @param path the child path 208 * @return the child node at the given {@code path} 209 * @throws NullPointerException if the given {@code path} array is 210 * {@code null} 211 */ 212 public default Optional<T> childAtPath(final Path path) { 213 T node = Trees.self(this); 214 for (int i = 0; i < path.length() && node != null; ++i) { 215 node = path.get(i) < node.childCount() 216 ? node.childAt(path.get(i)) 217 : null; 218 } 219 220 return Optional.ofNullable(node); 221 } 222 223 /** 224 * Return the child node at the given {@code path}. A path consists of the 225 * child index at a give level, starting with level 1. (The root note has 226 * level zero.) {@code tree.childAtPath(2)} will return the third child node 227 * of {@code this} node, if it exists and {@code tree.childAtPath(2, 0)} will 228 * return the first child of the third child of {@code this node}. 229 * 230 * @since 4.3 231 * 232 * @see #childAtPath(Path) 233 * 234 * @param path the child path 235 * @return the child node at the given {@code path} 236 * @throws NullPointerException if the given {@code path} array is 237 * {@code null} 238 * @throws IllegalArgumentException if one of the path elements is smaller 239 * than zero 240 */ 241 public default Optional<T> childAtPath(final int... path) { 242 return childAtPath(Path.of(path)); 243 } 244 245 /** 246 * Return {@code true} if the given {@code node} is an ancestor of 247 * {@code this} node. This operation is at worst {@code O(h)} where {@code h} 248 * is the distance from the root to {@code this} node. 249 * 250 * @param node the node to test 251 * @return {@code true} if the given {@code node} is an ancestor of 252 * {@code this} node, {@code false} otherwise 253 * @throws NullPointerException if the given {@code node} is {@code null} 254 */ 255 public default boolean isAncestor(final Tree<?, ?> node) { 256 requireNonNull(node); 257 258 Optional<T> ancestor = Optional.of(Trees.self(this)); 259 boolean result; 260 do { 261 result = ancestor.filter(a -> a.identical(node)).isPresent(); 262 } while (!result && 263 (ancestor = ancestor.flatMap(Tree<V, T>::getParent)).isPresent()); 264 265 return result; 266 } 267 268 /** 269 * Return {@code true} if the given {@code node} is a descendant of 270 * {@code this} node. If the given {@code node} is {@code null}, 271 * {@code false} is returned. This operation is at worst {@code O(h)} where 272 * {@code h} is the distance from the root to {@code this} node. 273 * 274 * @param node the node to test as descendant of this node 275 * @return {@code true} if this node is an ancestor of the given {@code node} 276 * @throws NullPointerException if the given {@code node} is {@code null} 277 */ 278 public default boolean isDescendant(final Tree<?, ?> node) { 279 return requireNonNull(node).isAncestor(this); 280 } 281 282 /** 283 * Returns the nearest common ancestor to this node and the given {@code node}. 284 * A node is considered an ancestor of itself. 285 * 286 * @param node {@code node} to find common ancestor with 287 * @return nearest ancestor common to this node and the given {@code node}, 288 * or {@link Optional#empty()} if no common ancestor exists. 289 * @throws NullPointerException if the given {@code node} is {@code null} 290 */ 291 public default Optional<T> sharedAncestor(final Tree<?, ?> node) { 292 requireNonNull(node); 293 294 T ancestor = null; 295 if (node.identical(this)) { 296 ancestor = Trees.self(this); 297 } else { 298 final int level1 = level(); 299 final int level2 = node.level(); 300 301 Tree<?, ?> node1; 302 Tree<?, ?> node2; 303 int diff; 304 if (level2 > level1) { 305 diff = level2 - level1; 306 node1 = node; 307 node2 = Trees.self(this); 308 } else { 309 diff = level1 - level2; 310 node1 = Trees.self(this); 311 node2 = node; 312 } 313 314 while (diff > 0 && node1 != null) { 315 node1 = node1.getParent().orElse(null); 316 --diff; 317 } 318 319 do { 320 if (node1 != null && node1.identical(node2)) { 321 ancestor = Trees.self(node1); 322 } 323 node1 = node1 != null 324 ? node1.getParent().orElse(null) 325 : null; 326 node2 = node2.getParent().orElse(null); 327 } while (node1 != null && node2 != null && ancestor == null); 328 } 329 330 return Optional.ofNullable(ancestor); 331 } 332 333 /** 334 * Returns true if and only if the given {@code node} is in the same tree as 335 * {@code this} node. 336 * 337 * @param node the other node to check 338 * @return true if the given {@code node} is in the same tree as {@code this} 339 * node, {@code false} otherwise. 340 * @throws NullPointerException if the given {@code node} is {@code null} 341 */ 342 public default boolean isRelated(final Tree<?, ?> node) { 343 requireNonNull(node); 344 return node.getRoot().identical(getRoot()); 345 } 346 347 /** 348 * Returns the path from the root, to get to this node. The last element in 349 * the path is this node. 350 * 351 * @return an array of TreeNode objects giving the path, where the 352 * first element in the path is the root and the last 353 * element is this node. 354 * @deprecated Use {@link #pathElements()} instead 355 */ 356 @Deprecated 357 public default ISeq<T> getPath() { 358 return Trees.pathElementsFromRoot(Trees.<V, T>self(this), 0).toISeq(); 359 } 360 361 /** 362 * Returns the path from the root, to get to this node. The last element in 363 * the path is this node. 364 * 365 * @since 5.1 366 * 367 * @return an array of TreeNode objects giving the path, where the 368 * first element in the path is the root and the last 369 * element is this node. 370 */ 371 public default ISeq<T> pathElements() { 372 return Trees.pathElementsFromRoot(Trees.<V, T>self(this), 0).toISeq(); 373 } 374 375 /** 376 * Return the {@link Path} of {@code this} tree, such that 377 * <pre>{@code 378 * final Tree<Integer, ?> tree = ...; 379 * final Tree.Path path = tree.path(); 380 * assert tree == tree.getRoot() 381 * .childAtPath(path) 382 * .orElse(null); 383 * }</pre> 384 * 385 * @since 5.1 386 * 387 * @return the path from the root element to {@code this} node. 388 */ 389 public default Path path() { 390 final int[] p = Trees.pathFromRoot(Trees.<V, T>self(this), 0); 391 return Path.of(p); 392 } 393 394 /** 395 * Returns the root of the tree that contains this node. The root is the 396 * ancestor with no parent. 397 * 398 * @return the root of the tree that contains this node 399 */ 400 public default T getRoot() { 401 T anc = Trees.self(this); 402 T prev; 403 404 do { 405 prev = anc; 406 anc = anc.getParent().orElse(null); 407 } while (anc != null); 408 409 return prev; 410 } 411 412 /* ************************************************************************* 413 * Child query operations 414 **************************************************************************/ 415 416 /** 417 * Return {@code true} if the given {@code node} is a child of {@code this} 418 * node. 419 * 420 * @param node the other node to check 421 * @return {@code true} if {@code node}is a child, {@code false} otherwise 422 * @throws NullPointerException if the given {@code node} is {@code null} 423 */ 424 public default boolean isChild(final Tree<?, ?> node) { 425 requireNonNull(node); 426 return childCount() != 0 && 427 node.getParent().equals(Optional.of(Trees.<V, T>self(this))); 428 } 429 430 /** 431 * Return the first child of {@code this} node, or {@code Optional.empty()} 432 * if {@code this} node has no children. 433 * 434 * @return the first child of this node 435 */ 436 public default Optional<T> firstChild() { 437 return childCount() > 0 438 ? Optional.of(childAt(0)) 439 : Optional.empty(); 440 } 441 442 /** 443 * Return the last child of {@code this} node, or {@code Optional.empty()} 444 * if {@code this} node has no children. 445 * 446 * @return the last child of this node 447 */ 448 public default Optional<T> lastChild() { 449 return childCount() > 0 450 ? Optional.of(childAt(childCount() - 1)) 451 : Optional.empty(); 452 } 453 454 /** 455 * Return the child which comes immediately after {@code this} node. This 456 * method performs a linear search of this node's children for {@code child} 457 * and is {@code O(n)} where n is the number of children. 458 * 459 * @param child the child node 460 * @return the child of this node that immediately follows the {@code child}, 461 * or {@code Optional.empty()} if the given {@code node} is the 462 * first node. 463 * @throws NullPointerException if the given {@code child} is {@code null} 464 */ 465 public default Optional<T> childAfter(final Tree<?, ?> child) { 466 requireNonNull(child); 467 468 final int index = indexOf(child); 469 if (index == -1) { 470 throw new IllegalArgumentException("The given node is not a child."); 471 } 472 473 return index < childCount() - 1 474 ? Optional.of(childAt(index + 1)) 475 : Optional.empty(); 476 } 477 478 /** 479 * Return the child which comes immediately before {@code this} node. This 480 * method performs a linear search of this node's children for {@code child} 481 * and is {@code O(n)} where n is the number of children. 482 * 483 * @param child the child node 484 * @return the child of this node that immediately precedes the {@code child}, 485 * or {@code null} if the given {@code node} is the first node. 486 * @throws NullPointerException if the given {@code child} is {@code null} 487 */ 488 public default Optional<T> childBefore(final Tree<?, ?> child) { 489 requireNonNull(child); 490 491 final int index = indexOf(child); 492 if (index == -1) { 493 throw new IllegalArgumentException("The given node is not a child."); 494 } 495 496 return index > 0 497 ? Optional.of(childAt(index - 1)) 498 : Optional.empty(); 499 } 500 501 /** 502 * Return the node that follows {@code this} node in a pre-order traversal 503 * of {@code this} tree node. Return {@code Optional.empty()} if this node 504 * is the last node of the traversal. This is an inefficient way to traverse 505 * the entire tree use an iterator instead. 506 * 507 * @see #preorderIterator 508 * @return the node that follows this node in a pre-order traversal, or 509 * {@code Optional.empty()} if this node is last 510 */ 511 public default Optional<T> nextNode() { 512 Optional<T> next = Optional.empty(); 513 514 if (childCount() == 0) { 515 T node = Trees.self(this); 516 while (node != null && !(next = node.nextSibling()).isPresent()) { 517 node = node.getParent().orElse(null); 518 } 519 } else { 520 next = Optional.of(childAt(0)); 521 } 522 523 return next; 524 } 525 526 /** 527 * Return the node that precedes this node in a pre-order traversal of 528 * {@code this} tree node. Returns {@code Optional.empty()} if this node is 529 * the first node of the traversal, the root of the tree. This is an 530 * inefficient way to traverse the entire tree; use an iterator instead. 531 * 532 * @see #preorderIterator 533 * @return the node that precedes this node in a pre-order traversal, or 534 * {@code Optional.empty()} if this node is the first 535 */ 536 public default Optional<T> previousNode() { 537 Optional<T> node = Optional.empty(); 538 539 if (getParent().isPresent()) { 540 final Optional<T> prev = previousSibling(); 541 if (prev.isPresent()) { 542 node = prev.get().childCount() == 0 543 ? prev 544 : prev.map(Tree<V, T>::lastLeaf); 545 } else { 546 node = getParent(); 547 } 548 } 549 550 return node; 551 } 552 553 /* ************************************************************************* 554 * Sibling query operations 555 **************************************************************************/ 556 557 /** 558 * Test if the given {@code node} is a sibling of {@code this} node. 559 * 560 * @param node node to test as sibling of this node 561 * @return {@code true} if the {@code node} is a sibling of {@code this} 562 * node 563 * @throws NullPointerException if the given {@code node} is {@code null} 564 */ 565 public default boolean isSibling(final Tree<?, ?> node) { 566 return identical(requireNonNull(node)) || 567 getParent().equals(node.getParent()); 568 } 569 570 /** 571 * Return the number of siblings of {@code this} node. A node is its own 572 * sibling (if it has no parent or no siblings, this method returns 573 * {@code 1}). 574 * 575 * @return the number of siblings of {@code this} node 576 */ 577 public default int siblingCount() { 578 return getParent().map(Tree<V, T>::childCount).orElse(1); 579 } 580 581 /** 582 * Return the next sibling of {@code this} node in the parent's children 583 * array, or {@code null} if {@code this} node has no parent or it is the 584 * last child of the paren. This method performs a linear search that is 585 * {@code O(n)} where n is the number of children; to traverse the entire 586 * array, use the iterator of the parent instead. 587 * 588 * @see #childStream() 589 * @return the sibling of {@code this} node that immediately follows 590 * {@code this} node 591 */ 592 public default Optional<T> nextSibling() { 593 return getParent().flatMap(p -> p.childAfter(Trees.<V, T>self(this))); 594 } 595 596 /** 597 * Return the previous sibling of {@code this} node in the parent's children 598 * list, or {@code Optional.empty()} if this node has no parent or is the 599 * parent's first child. This method performs a linear search that is O(n) 600 * where n is the number of children. 601 * 602 * @return the sibling of {@code this} node that immediately precedes this 603 * node 604 */ 605 public default Optional<T> previousSibling() { 606 return getParent().flatMap(p -> p.childBefore(Trees.<V, T>self(this))); 607 } 608 609 610 /* ************************************************************************* 611 * Leaf query operations 612 **************************************************************************/ 613 614 /** 615 * Return {@code true} if {@code this} node has no children. 616 * 617 * @return {@code true} if {@code this} node has no children, {@code false} 618 * otherwise 619 */ 620 public default boolean isLeaf() { 621 return childCount() == 0; 622 } 623 624 /** 625 * Return the first leaf that is a descendant of {@code this} node; either 626 * this node or its first child's first leaf. {@code this} node is returned 627 * if it is a leaf. 628 * 629 * @see #isLeaf 630 * @see #isDescendant 631 * @return the first leaf in the subtree rooted at this node 632 */ 633 public default T firstLeaf() { 634 T leaf = Trees.self(this); 635 while (!leaf.isLeaf()) { 636 leaf = leaf.firstChild().orElseThrow(AssertionError::new); 637 } 638 639 return leaf; 640 } 641 642 /** 643 * Return the last leaf that is a descendant of this node; either 644 * {@code this} node or its last child's last leaf. Returns {@code this} 645 * node if it is a leaf. 646 * 647 * @see #isLeaf 648 * @see #isDescendant 649 * @return the last leaf in this subtree 650 */ 651 public default T lastLeaf() { 652 T leaf = Trees.self(this); 653 while (!leaf.isLeaf()) { 654 leaf = leaf.lastChild().orElseThrow(AssertionError::new); 655 } 656 657 return leaf; 658 } 659 660 /** 661 * Returns the leaf after {@code this} node or {@code Optional.empty()} if 662 * this node is the last leaf in the tree. 663 * <p> 664 * In order to determine the next node, this method first performs a linear 665 * search in the parent's child-list in order to find the current node. 666 * <p> 667 * That implementation makes the operation suitable for short traversals 668 * from a known position. But to traverse all of the leaves in the tree, you 669 * should use {@link #depthFirstIterator()} to iterator the nodes in the 670 * tree and use {@link #isLeaf()} on each node to determine which are leaves. 671 * 672 * @see #depthFirstIterator 673 * @see #isLeaf 674 * @return return the next leaf past this node 675 */ 676 public default Optional<T> nextLeaf() { 677 return nextSibling() 678 .map(s -> Optional.of(s.firstLeaf())) 679 .orElseGet(() -> getParent().flatMap(Tree<V, T>::nextLeaf)); 680 } 681 682 /** 683 * Return the leaf before {@code this} node or {@code null} if {@code this} 684 * node is the first leaf in the tree. 685 * <p> 686 * In order to determine the previous node, this method first performs a 687 * linear search in the parent's child-list in order to find the current 688 * node. 689 * <p> 690 * That implementation makes the operation suitable for short traversals 691 * from a known position. But to traverse all of the leaves in the tree, you 692 * should use {@link #depthFirstIterator()} to iterate the nodes in the tree 693 * and use {@link #isLeaf()} on each node to determine which are leaves. 694 * 695 * @see #depthFirstIterator 696 * @see #isLeaf 697 * @return returns the leaf before {@code this} node 698 */ 699 public default Optional<T> previousLeaf() { 700 return previousSibling() 701 .map(s -> Optional.of(s.lastLeaf())) 702 .orElseGet(() -> getParent().flatMap(Tree<V, T>::previousLeaf)); 703 } 704 705 /** 706 * Returns the total number of leaves that are descendants of this node. 707 * If this node is a leaf, returns {@code 1}. This method is {@code O(n)}, 708 * where n is the number of descendants of {@code this} node. 709 * 710 * @see #isLeaf() 711 * @return the number of leaves beneath this node 712 */ 713 public default int leafCount() { 714 return (int)breadthFirstStream() 715 .filter(Tree<V, T>::isLeaf) 716 .count(); 717 } 718 719 /* ************************************************************************* 720 * Tree traversing. 721 **************************************************************************/ 722 723 /** 724 * Return an iterator that traverses the subtree rooted at {@code this} 725 * node in breadth-first order. The first node returned by the iterator is 726 * {@code this} node. 727 * <p> 728 * Modifying the tree by inserting, removing, or moving a node invalidates 729 * any iterator created before the modification. 730 * 731 * @see #depthFirstIterator 732 * @return an iterator for traversing the tree in breadth-first order 733 */ 734 public default Iterator<T> breadthFirstIterator() { 735 return new TreeNodeBreadthFirstIterator<>(Trees.<V, T>self(this)); 736 } 737 738 /** 739 * Return an iterator that traverses the subtree rooted at {@code this}. 740 * The first node returned by the iterator is {@code this} node. 741 * <p> 742 * Modifying the tree by inserting, removing, or moving a node invalidates 743 * any iterator created before the modification. 744 * 745 * @see #breadthFirstIterator 746 * @return an iterator for traversing the tree in breadth-first order 747 */ 748 @Override 749 public default Iterator<T> iterator() { 750 return breadthFirstIterator(); 751 } 752 753 /** 754 * Return a stream that traverses the subtree rooted at {@code this} node in 755 * breadth-first order. The first node returned by the stream is 756 * {@code this} node. 757 * 758 * @see #depthFirstIterator 759 * @see #stream() 760 * @return a stream for traversing the tree in breadth-first order 761 */ 762 public default Stream<T> breadthFirstStream() { 763 return StreamSupport 764 .stream(spliteratorUnknownSize(breadthFirstIterator(), 0), false); 765 } 766 767 /** 768 * Return a stream that traverses the subtree rooted at {@code this} node in 769 * breadth-first order. The first node returned by the stream is 770 * {@code this} node. 771 * 772 * @see #breadthFirstStream 773 * @return a stream for traversing the tree in breadth-first order 774 */ 775 public default Stream<T> stream() { 776 return breadthFirstStream(); 777 } 778 779 /** 780 * Return an iterator that traverses the subtree rooted at {@code this} node 781 * in pre-order. The first node returned by the iterator is {@code this} 782 * node. 783 * <p> 784 * Modifying the tree by inserting, removing, or moving a node invalidates 785 * any iterator created before the modification. 786 * 787 * @see #postorderIterator 788 * @return an iterator for traversing the tree in pre-order 789 */ 790 public default Iterator<T> preorderIterator() { 791 return new TreeNodePreorderIterator<>(Trees.<V, T>self(this)); 792 } 793 794 /** 795 * Return a stream that traverses the subtree rooted at {@code this} node 796 * in pre-order. The first node returned by the stream is {@code this} node. 797 * <p> 798 * Modifying the tree by inserting, removing, or moving a node invalidates 799 * any iterator created before the modification. 800 * 801 * @see #preorderIterator 802 * @return a stream for traversing the tree in pre-order 803 */ 804 public default Stream<T> preorderStream() { 805 return StreamSupport 806 .stream(spliteratorUnknownSize(preorderIterator(), 0), false); 807 } 808 809 /** 810 * Return an iterator that traverses the subtree rooted at {@code this} 811 * node in post-order. The first node returned by the iterator is the 812 * leftmost leaf. This is the same as a depth-first traversal. 813 * 814 * @see #depthFirstIterator 815 * @see #preorderIterator 816 * @return an iterator for traversing the tree in post-order 817 */ 818 public default Iterator<T> postorderIterator() { 819 return new TreeNodePostorderIterator<>(Trees.<V, T>self(this)); 820 } 821 822 /** 823 * Return a stream that traverses the subtree rooted at {@code this} node in 824 * post-order. The first node returned by the iterator is the leftmost leaf. 825 * This is the same as a depth-first traversal. 826 * 827 * @see #depthFirstIterator 828 * @see #preorderIterator 829 * @return a stream for traversing the tree in post-order 830 */ 831 public default Stream<T> postorderStream() { 832 return StreamSupport 833 .stream(spliteratorUnknownSize(postorderIterator(), 0), false); 834 } 835 836 /** 837 * Return an iterator that traverses the subtree rooted at {@code this} node 838 * in depth-first order. The first node returned by the iterator is the 839 * leftmost leaf. This is the same as a postorder traversal. 840 * <p> 841 * Modifying the tree by inserting, removing, or moving a node invalidates 842 * any iterator created before the modification. 843 * 844 * @see #breadthFirstIterator 845 * @see #postorderIterator 846 * @return an iterator for traversing the tree in depth-first order 847 */ 848 public default Iterator<T> depthFirstIterator() { 849 return postorderIterator(); 850 } 851 852 /** 853 * Return a stream that traverses the subtree rooted at {@code this} node in 854 * depth-first. The first node returned by the iterator is the leftmost leaf. 855 * This is the same as a post-order traversal. 856 * 857 * @see #depthFirstIterator 858 * @see #preorderIterator 859 * @return a stream for traversing the tree in post-order 860 */ 861 public default Stream<T> depthFirstStream() { 862 return postorderStream(); 863 } 864 865 /** 866 * Return an iterator that follows the path from {@code ancestor} to 867 * {@code this} node. The iterator return {@code ancestor} as first element, 868 * The creation of the iterator is O(m), where m is the number of nodes 869 * between {@code this} node and the {@code ancestor}, inclusive. 870 * <p> 871 * Modifying the tree by inserting, removing, or moving a node invalidates 872 * any iterator created before the modification. 873 * 874 * @see #isAncestor 875 * @see #isDescendant 876 * @param ancestor the ancestor node 877 * @return an iterator for following the path from an ancestor of {@code this} 878 * node to this one 879 * @throws IllegalArgumentException if the {@code ancestor} is not an 880 * ancestor of this node 881 * @throws NullPointerException if the given {@code ancestor} is {@code null} 882 */ 883 public default Iterator<T> 884 pathFromAncestorIterator(final Tree<?, ?> ancestor) { 885 return new TreeNodePathIterator<>(ancestor, Trees.<V, T>self(this)); 886 } 887 888 /** 889 * Return the path of {@code this} child node from the root node. You will 890 * get {@code this} node, if you call {@link #childAtPath(Path)} on the 891 * root node of {@code this} node. 892 * <pre>{@code 893 * final Tree<?, ?> node = ...; 894 * final Tree<?, ?> root = node.getRoot(); 895 * final int[] path = node.childPath(); 896 * assert node == root.childAtPath(path); 897 * }</pre> 898 * 899 * @since 4.4 900 * 901 * @see #childAtPath(Path) 902 * 903 * @return the path of {@code this} child node from the root node. 904 */ 905 public default Path childPath() { 906 final Iterator<T> it = pathFromAncestorIterator(getRoot()); 907 final int[] path = new int[level()]; 908 909 T tree = null; 910 int index = 0; 911 while (it.hasNext()) { 912 final T child = it.next(); 913 if (tree != null) { 914 path[index++] = tree.indexOf(child); 915 } 916 917 tree = child; 918 } 919 920 assert index == path.length; 921 922 return new Path(path); 923 } 924 925 /** 926 * Tests whether {@code this} node is the same as the {@code other} node. 927 * The default implementation returns the object identity, 928 * {@code this == other}, of the two objects, but other implementations may 929 * use different criteria for checking the <i>identity</i>. 930 * 931 * @param other the {@code other} node 932 * @return {@code true} if the {@code other} node is the same as {@code this} 933 * node. 934 */ 935 public default boolean identical(final Tree<?, ?> other) { 936 return this == other; 937 } 938 939 /* ************************************************************************* 940 * 'toString' methods 941 **************************************************************************/ 942 943 /** 944 * Return a compact string representation of the given tree. The tree 945 * <pre> 946 * mul 947 * ├── div 948 * │ ├── cos 949 * │ │ └── 1.0 950 * │ └── cos 951 * │ └── π 952 * └── sin 953 * └── mul 954 * ├── 1.0 955 * └── z 956 * </pre> 957 * is printed as 958 * <pre> 959 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z))) 960 * </pre> 961 * 962 * @since 4.3 963 * 964 * @see #toParenthesesString() 965 * @see TreeFormatter#PARENTHESES 966 * 967 * @param mapper the {@code mapper} which converts the tree value to a string 968 * @return the string representation of the given tree 969 */ 970 public default String 971 toParenthesesString(final Function<? super V, String> mapper) { 972 return TreeFormatter.PARENTHESES.format(this, mapper); 973 } 974 975 /** 976 * Return a compact string representation of the given tree. The tree 977 * <pre> 978 * mul 979 * ├── div 980 * │ ├── cos 981 * │ │ └── 1.0 982 * │ └── cos 983 * │ └── π 984 * └── sin 985 * └── mul 986 * ├── 1.0 987 * └── z 988 * </pre> 989 * is printed as 990 * <pre> 991 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z))) 992 * </pre> 993 * 994 * @since 4.3 995 * 996 * @see #toParenthesesString(Function) 997 * @see TreeFormatter#PARENTHESES 998 * 999 * @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}