001/* 002 * Java Genetic Algorithm Library (jenetics-6.3.0). 003 * Copyright (c) 2007-2021 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; 025import static io.jenetics.internal.util.SerialIO.readIntArray; 026import static io.jenetics.internal.util.SerialIO.writeIntArray; 027 028import java.io.DataInput; 029import java.io.DataOutput; 030import java.io.IOException; 031import java.io.InvalidObjectException; 032import java.io.ObjectInputStream; 033import java.io.Serializable; 034import java.util.Arrays; 035import java.util.Iterator; 036import java.util.Objects; 037import java.util.Optional; 038import java.util.Spliterator; 039import java.util.Spliterators; 040import java.util.function.Function; 041import java.util.stream.Stream; 042import java.util.stream.StreamSupport; 043 044import io.jenetics.util.ISeq; 045 046/** 047 * General purpose tree structure. The interface only contains tree read methods. 048 * For a mutable tree implementation have a look at the {@link TreeNode} class. 049 * 050 * @see TreeNode 051 * 052 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a> 053 * @version 6.0 054 * @since 3.9 055 */ 056public interface Tree<V, T extends Tree<V, T>> extends Iterable<T> { 057 058 /* ************************************************************************* 059 * Basic (abstract) operations. All other tree operations can be derived 060 * from this methods. 061 **************************************************************************/ 062 063 /** 064 * Return the value of the current {@code Tree} node. The value may be 065 * {@code null}. 066 * 067 * @return the value of the current {@code Tree} node 068 */ 069 V value(); 070 071 /** 072 * Return the <em>parent</em> node of this tree node. 073 * 074 * @return the parent node, or {@code Optional.empty()} if this node is the 075 * root of the tree 076 */ 077 Optional<T> parent(); 078 079 /** 080 * Return the child node with the given index. 081 * 082 * @param index the child index 083 * @return the child node with the given index 084 * @throws IndexOutOfBoundsException if the {@code index} is out of 085 * bounds ({@code [0, childCount())}) 086 */ 087 T childAt(final int index); 088 089 /** 090 * Return the number of children this tree node consists of. 091 * 092 * @return the number of children this tree node consists of 093 */ 094 int childCount(); 095 096 097 /* ************************************************************************* 098 * Derived operations 099 **************************************************************************/ 100 101 /** 102 * Return an iterator of the children of this {@code Tree} node. 103 * 104 * @return an iterator of the children of this {@code Tree} node. 105 */ 106 default Iterator<T> childIterator() { 107 return new TreeChildIterator<V, T>(Trees.self(this)); 108 } 109 110 /** 111 * Return a forward-order stream of this node's children. 112 * 113 * @return a stream of children of {@code this} node 114 */ 115 default Stream<T> childStream() { 116 return StreamSupport.stream( 117 Spliterators.spliterator( 118 childIterator(), 119 childCount(), 120 Spliterator.SIZED | Spliterator.ORDERED 121 ), 122 false 123 ); 124 } 125 126 /** 127 * Returns {@code true} if this node is the root of the tree. 128 * 129 * @return {@code true} if this node is the root of its tree, {@code false} 130 * otherwise 131 */ 132 default boolean isRoot() { 133 return parent().isEmpty(); 134 } 135 136 /** 137 * Returns the depth of the tree rooted at this node. The <i>depth</i> of a 138 * tree is the longest distance from {@code this} node to a leaf. If 139 * {@code this} node has no children, 0 is returned. This operation is much 140 * more expensive than {@link #level()} because it must effectively traverse 141 * the entire tree rooted at {@code this} node. 142 * 143 * @return the depth of the tree whose root is this node 144 */ 145 default int depth() { 146 final Iterator<T> it = breadthFirstIterator(); 147 148 T last = null; 149 while (it.hasNext()) { 150 last = it.next(); 151 } 152 153 assert last != null; 154 return last.level() - level(); 155 } 156 157 /** 158 * Returns the number of levels above this node. The <i>level</i> of a tree 159 * is the distance from the root to {@code this} node. If {@code this} node 160 * is the root, returns 0. 161 * 162 * @return the number of levels above this node 163 */ 164 default int level() { 165 Optional<T> ancestor = Optional.of(Trees.self(this)); 166 int levels = 0; 167 while ((ancestor = ancestor.flatMap(Tree::parent)).isPresent()) { 168 ++levels; 169 } 170 171 return levels; 172 } 173 174 /** 175 * Returns the index of the specified child in this node's child array, or 176 * {@code -1} if {@code this} node doesn't contain the given {@code child}. 177 * This method performs a linear search and is O(n) where {@code n} is the 178 * number of children. 179 * 180 * @param child the TreeNode to search for among this node's children 181 * @throws NullPointerException if the given {@code child} is {@code null} 182 * @return the index of the node in this node's child array, or {@code -1} 183 * if the node could not be found 184 */ 185 default int indexOf(final Tree<?, ?> child) { 186 int index = -1; 187 for (int i = 0, n = childCount(); i < n && index == -1; ++i) { 188 if (childAt(i).identical(child)) { 189 index = i; 190 } 191 } 192 193 return index; 194 } 195 196 /** 197 * Return the number of nodes of {@code this} node (sub-tree). 198 * 199 * @return the number of nodes of {@code this} node (sub-tree) 200 */ 201 default int size() { 202 return Trees.countChildren(this) + 1; 203 } 204 205 206 /* ************************************************************************* 207 * Query operations 208 **************************************************************************/ 209 210 /** 211 * Return the child node at the given {@code path}. A path consists of the 212 * child index at a give level, starting with level 1. (The root note has 213 * level zero.) {@code tree.childAtPath(Path.of(2))} will return the third 214 * child node of {@code this} node, if it exists and 215 * {@code tree.childAtPath(Path.of(2, 0))} will return the first child of 216 * the third child of {@code this node}. 217 * 218 * @since 4.4 219 * 220 * @see #childAtPath(int...) 221 * 222 * @param path the child path 223 * @return the child node at the given {@code path} 224 * @throws NullPointerException if the given {@code path} array is 225 * {@code null} 226 */ 227 default Optional<T> childAtPath(final Path path) { 228 T node = Trees.self(this); 229 for (int i = 0; i < path.length() && node != null; ++i) { 230 node = path.get(i) < node.childCount() 231 ? node.childAt(path.get(i)) 232 : null; 233 } 234 235 return Optional.ofNullable(node); 236 } 237 238 /** 239 * Return the child node at the given {@code path}. A path consists of the 240 * child index at a give level, starting with level 1. (The root note has 241 * level zero.) {@code tree.childAtPath(2)} will return the third child node 242 * of {@code this} node, if it exists and {@code tree.childAtPath(2, 0)} will 243 * return the first child of the third child of {@code this node}. 244 * 245 * @since 4.3 246 * 247 * @see #childAtPath(Path) 248 * 249 * @param path the child path 250 * @return the child node at the given {@code path} 251 * @throws NullPointerException if the given {@code path} array is 252 * {@code null} 253 * @throws IllegalArgumentException if one of the path elements is smaller 254 * than zero 255 */ 256 default Optional<T> childAtPath(final int... path) { 257 return childAtPath(Path.of(path)); 258 } 259 260 /** 261 * Return {@code true} if the given {@code node} is an ancestor of 262 * {@code this} node. This operation is at worst {@code O(h)} where {@code h} 263 * is the distance from the root to {@code this} node. 264 * 265 * @param node the node to test 266 * @return {@code true} if the given {@code node} is an ancestor of 267 * {@code this} node, {@code false} otherwise 268 * @throws NullPointerException if the given {@code node} is {@code null} 269 */ 270 default boolean isAncestor(final Tree<?, ?> node) { 271 requireNonNull(node); 272 273 Optional<T> ancestor = Optional.of(Trees.self(this)); 274 boolean result; 275 do { 276 result = ancestor.filter(a -> a.identical(node)).isPresent(); 277 } while (!result && 278 (ancestor = ancestor.flatMap(Tree::parent)).isPresent()); 279 280 return result; 281 } 282 283 /** 284 * Return {@code true} if the given {@code node} is a descendant of 285 * {@code this} node. If the given {@code node} is {@code null}, 286 * {@code false} is returned. This operation is at worst {@code O(h)} where 287 * {@code h} is the distance from the root to {@code this} node. 288 * 289 * @param node the node to test as descendant of this node 290 * @return {@code true} if this node is an ancestor of the given {@code node} 291 * @throws NullPointerException if the given {@code node} is {@code null} 292 */ 293 default boolean isDescendant(final Tree<?, ?> node) { 294 return requireNonNull(node).isAncestor(this); 295 } 296 297 /** 298 * Returns the nearest common ancestor to this node and the given {@code node}. 299 * A node is considered an ancestor of itself. 300 * 301 * @param node {@code node} to find common ancestor with 302 * @return nearest ancestor common to this node and the given {@code node}, 303 * or {@link Optional#empty()} if no common ancestor exists. 304 * @throws NullPointerException if the given {@code node} is {@code null} 305 */ 306 default Optional<T> sharedAncestor(final Tree<?, ?> node) { 307 requireNonNull(node); 308 309 T ancestor = null; 310 if (node.identical(this)) { 311 ancestor = Trees.self(this); 312 } else { 313 final int level1 = level(); 314 final int level2 = node.level(); 315 316 Tree<?, ?> node1; 317 Tree<?, ?> node2; 318 int diff; 319 if (level2 > level1) { 320 diff = level2 - level1; 321 node1 = node; 322 node2 = Trees.self(this); 323 } else { 324 diff = level1 - level2; 325 node1 = Trees.self(this); 326 node2 = node; 327 } 328 329 while (diff > 0 && node1 != null) { 330 node1 = node1.parent().orElse(null); 331 --diff; 332 } 333 334 do { 335 if (node1 != null && node1.identical(node2)) { 336 ancestor = Trees.self(node1); 337 } 338 node1 = node1 != null 339 ? node1.parent().orElse(null) 340 : null; 341 node2 = node2.parent().orElse(null); 342 } while (node1 != null && node2 != null && ancestor == null); 343 } 344 345 return Optional.ofNullable(ancestor); 346 } 347 348 /** 349 * Returns true if and only if the given {@code node} is in the same tree as 350 * {@code this} node. 351 * 352 * @param node the other node to check 353 * @return true if the given {@code node} is in the same tree as {@code this} 354 * node, {@code false} otherwise. 355 * @throws NullPointerException if the given {@code node} is {@code null} 356 */ 357 default boolean isRelated(final Tree<?, ?> node) { 358 requireNonNull(node); 359 return node.root().identical(root()); 360 } 361 362 /** 363 * Returns the path from the root, to get to this node. The last element in 364 * the path is this node. 365 * 366 * @since 5.1 367 * 368 * @return an array of TreeNode objects giving the path, where the 369 * first element in the path is the root and the last 370 * element is this node. 371 */ 372 default ISeq<T> pathElements() { 373 return Trees.pathElementsFromRoot(Trees.<V, T>self(this), 0).toISeq(); 374 } 375 376 /** 377 * Return the {@link Path} of {@code this} tree, such that 378 * <pre>{@code 379 * final Tree<Integer, ?> tree = ...; 380 * final Tree.Path path = tree.path(); 381 * assert tree == tree.getRoot() 382 * .childAtPath(path) 383 * .orElse(null); 384 * }</pre> 385 * 386 * @since 5.1 387 * 388 * @return the path from the root element to {@code this} node. 389 */ 390 default Path path() { 391 final int[] p = Trees.pathFromRoot(Trees.<V, T>self(this), 0); 392 return Path.of(p); 393 } 394 395 /** 396 * Returns the root of the tree that contains this node. The root is the 397 * ancestor with no parent. 398 * 399 * @return the root of the tree that contains this node 400 */ 401 default T root() { 402 T anc = Trees.self(this); 403 T prev; 404 405 do { 406 prev = anc; 407 anc = anc.parent().orElse(null); 408 } while (anc != null); 409 410 return prev; 411 } 412 413 /* ************************************************************************* 414 * Child query operations 415 **************************************************************************/ 416 417 /** 418 * Return {@code true} if the given {@code node} is a child of {@code this} 419 * node. 420 * 421 * @param node the other node to check 422 * @return {@code true} if {@code node}is a child, {@code false} otherwise 423 * @throws NullPointerException if the given {@code node} is {@code null} 424 */ 425 default boolean isChild(final Tree<?, ?> node) { 426 requireNonNull(node); 427 return childCount() != 0 && 428 node.parent().equals(Optional.of(Trees.<V, T>self(this))); 429 } 430 431 /** 432 * Return the first child of {@code this} node, or {@code Optional.empty()} 433 * if {@code this} node has no children. 434 * 435 * @return the first child of this node 436 */ 437 default Optional<T> firstChild() { 438 return childCount() > 0 439 ? Optional.of(childAt(0)) 440 : Optional.empty(); 441 } 442 443 /** 444 * Return the last child of {@code this} node, or {@code Optional.empty()} 445 * if {@code this} node has no children. 446 * 447 * @return the last child of this node 448 */ 449 default Optional<T> lastChild() { 450 return childCount() > 0 451 ? Optional.of(childAt(childCount() - 1)) 452 : Optional.empty(); 453 } 454 455 /** 456 * Return the child which comes immediately after {@code this} node. This 457 * method performs a linear search of this node's children for {@code child} 458 * and is {@code O(n)} where n is the number of children. 459 * 460 * @param child the child node 461 * @return the child of this node that immediately follows the {@code child}, 462 * or {@code Optional.empty()} if the given {@code node} is the 463 * first node. 464 * @throws NullPointerException if the given {@code child} is {@code null} 465 */ 466 default Optional<T> childAfter(final Tree<?, ?> child) { 467 requireNonNull(child); 468 469 final int index = indexOf(child); 470 if (index == -1) { 471 throw new IllegalArgumentException("The given node is not a child."); 472 } 473 474 return index < childCount() - 1 475 ? Optional.of(childAt(index + 1)) 476 : Optional.empty(); 477 } 478 479 /** 480 * Return the child which comes immediately before {@code this} node. This 481 * method performs a linear search of this node's children for {@code child} 482 * and is {@code O(n)} where n is the number of children. 483 * 484 * @param child the child node 485 * @return the child of this node that immediately precedes the {@code child}, 486 * or {@code null} if the given {@code node} is the first node. 487 * @throws NullPointerException if the given {@code child} is {@code null} 488 */ 489 default Optional<T> childBefore(final Tree<?, ?> child) { 490 requireNonNull(child); 491 492 final int index = indexOf(child); 493 if (index == -1) { 494 throw new IllegalArgumentException("The given node is not a child."); 495 } 496 497 return index > 0 498 ? Optional.of(childAt(index - 1)) 499 : Optional.empty(); 500 } 501 502 /** 503 * Return the node that follows {@code this} node in a pre-order traversal 504 * of {@code this} tree node. Return {@code Optional.empty()} if this node 505 * is the last node of the traversal. This is an inefficient way to traverse 506 * the entire tree use an iterator instead. 507 * 508 * @see #preorderIterator 509 * @return the node that follows this node in a pre-order traversal, or 510 * {@code Optional.empty()} if this node is last 511 */ 512 default Optional<T> nextNode() { 513 Optional<T> next = Optional.empty(); 514 515 if (childCount() == 0) { 516 T node = Trees.self(this); 517 while (node != null && (next = node.nextSibling()).isEmpty()) { 518 node = node.parent().orElse(null); 519 } 520 } else { 521 next = Optional.of(childAt(0)); 522 } 523 524 return next; 525 } 526 527 /** 528 * Return the node that precedes this node in a pre-order traversal of 529 * {@code this} tree node. Returns {@code Optional.empty()} if this node is 530 * the first node of the traversal, the root of the tree. This is an 531 * inefficient way to traverse the entire tree; use an iterator instead. 532 * 533 * @see #preorderIterator 534 * @return the node that precedes this node in a pre-order traversal, or 535 * {@code Optional.empty()} if this node is the first 536 */ 537 default Optional<T> previousNode() { 538 Optional<T> node = Optional.empty(); 539 540 if (parent().isPresent()) { 541 final Optional<T> prev = previousSibling(); 542 if (prev.isPresent()) { 543 node = prev.get().childCount() == 0 544 ? prev 545 : prev.map(Tree::lastLeaf); 546 } else { 547 node = parent(); 548 } 549 } 550 551 return node; 552 } 553 554 /* ************************************************************************* 555 * Sibling query operations 556 **************************************************************************/ 557 558 /** 559 * Test if the given {@code node} is a sibling of {@code this} node. 560 * 561 * @param node node to test as sibling of this node 562 * @return {@code true} if the {@code node} is a sibling of {@code this} 563 * node 564 * @throws NullPointerException if the given {@code node} is {@code null} 565 */ 566 default boolean isSibling(final Tree<?, ?> node) { 567 return identical(requireNonNull(node)) || 568 parent().equals(node.parent()); 569 } 570 571 /** 572 * Return the number of siblings of {@code this} node. A node is its own 573 * sibling (if it has no parent or no siblings, this method returns 574 * {@code 1}). 575 * 576 * @return the number of siblings of {@code this} node 577 */ 578 default int siblingCount() { 579 return parent().map(Tree::childCount).orElse(1); 580 } 581 582 /** 583 * Return the next sibling of {@code this} node in the parent's children 584 * array, or {@code null} if {@code this} node has no parent or it is the 585 * last child of the paren. This method performs a linear search that is 586 * {@code O(n)} where n is the number of children; to traverse the entire 587 * array, use the iterator of the parent instead. 588 * 589 * @see #childStream() 590 * @return the sibling of {@code this} node that immediately follows 591 * {@code this} node 592 */ 593 default Optional<T> nextSibling() { 594 return parent().flatMap(p -> p.childAfter(Trees.<V, T>self(this))); 595 } 596 597 /** 598 * Return the previous sibling of {@code this} node in the parent's children 599 * list, or {@code Optional.empty()} if this node has no parent or is the 600 * parent's first child. This method performs a linear search that is O(n) 601 * where n is the number of children. 602 * 603 * @return the sibling of {@code this} node that immediately precedes this 604 * node 605 */ 606 default Optional<T> previousSibling() { 607 return parent().flatMap(p -> p.childBefore(Trees.<V, T>self(this))); 608 } 609 610 611 /* ************************************************************************* 612 * Leaf query operations 613 **************************************************************************/ 614 615 /** 616 * Return {@code true} if {@code this} node has no children. 617 * 618 * @return {@code true} if {@code this} node has no children, {@code false} 619 * otherwise 620 */ 621 default boolean isLeaf() { 622 return childCount() == 0; 623 } 624 625 /** 626 * Return the first leaf that is a descendant of {@code this} node; either 627 * this node or its first child's first leaf. {@code this} node is returned 628 * if it is a leaf. 629 * 630 * @see #isLeaf 631 * @see #isDescendant 632 * @return the first leaf in the subtree rooted at this node 633 */ 634 default T firstLeaf() { 635 T leaf = Trees.self(this); 636 while (!leaf.isLeaf()) { 637 leaf = leaf.firstChild().orElseThrow(AssertionError::new); 638 } 639 640 return leaf; 641 } 642 643 /** 644 * Return the last leaf that is a descendant of this node; either 645 * {@code this} node or its last child's last leaf. Returns {@code this} 646 * node if it is a leaf. 647 * 648 * @see #isLeaf 649 * @see #isDescendant 650 * @return the last leaf in this subtree 651 */ 652 default T lastLeaf() { 653 T leaf = Trees.self(this); 654 while (!leaf.isLeaf()) { 655 leaf = leaf.lastChild().orElseThrow(AssertionError::new); 656 } 657 658 return leaf; 659 } 660 661 /** 662 * Returns the leaf after {@code this} node or {@code Optional.empty()} if 663 * this node is the last leaf in the tree. 664 * <p> 665 * In order to determine the next node, this method first performs a linear 666 * search in the parent's child-list in order to find the current node. 667 * <p> 668 * That implementation makes the operation suitable for short traversals 669 * from a known position. But to traverse all of the leaves in the tree, you 670 * should use {@link #depthFirstIterator()} to iterator the nodes in the 671 * tree and use {@link #isLeaf()} on each node to determine which are leaves. 672 * 673 * @see #depthFirstIterator 674 * @see #isLeaf 675 * @return return the next leaf past this node 676 */ 677 default Optional<T> nextLeaf() { 678 return nextSibling() 679 .map(Tree::firstLeaf) 680 .or(() -> parent().flatMap(Tree::nextLeaf)); 681 } 682 683 /** 684 * Return the leaf before {@code this} node or {@code null} if {@code this} 685 * node is the first leaf in the tree. 686 * <p> 687 * In order to determine the previous node, this method first performs a 688 * linear search in the parent's child-list in order to find the current 689 * node. 690 * <p> 691 * That implementation makes the operation suitable for short traversals 692 * from a known position. But to traverse all of the leaves in the tree, you 693 * should use {@link #depthFirstIterator()} to iterate the nodes in the tree 694 * and use {@link #isLeaf()} on each node to determine which are leaves. 695 * 696 * @see #depthFirstIterator 697 * @see #isLeaf 698 * @return returns the leaf before {@code this} node 699 */ 700 default Optional<T> previousLeaf() { 701 return previousSibling() 702 .map(Tree::lastLeaf) 703 .or(() -> parent().flatMap(Tree::previousLeaf)); 704 } 705 706 /** 707 * Returns the total number of leaves that are descendants of this node. 708 * If this node is a leaf, returns {@code 1}. This method is {@code O(n)}, 709 * where n is the number of descendants of {@code this} node. 710 * 711 * @see #isLeaf() 712 * @return the number of leaves beneath this node 713 */ 714 default int leafCount() { 715 return (int)breadthFirstStream() 716 .filter(Tree::isLeaf) 717 .count(); 718 } 719 720 /* ************************************************************************* 721 * Tree traversing. 722 **************************************************************************/ 723 724 /** 725 * Return an iterator that traverses the subtree rooted at {@code this} 726 * node in breadth-first order. The first node returned by the iterator is 727 * {@code this} node. 728 * <p> 729 * Modifying the tree by inserting, removing, or moving a node invalidates 730 * any iterator created before the modification. 731 * 732 * @see #depthFirstIterator 733 * @return an iterator for traversing the tree in breadth-first order 734 */ 735 default Iterator<T> breadthFirstIterator() { 736 return new TreeNodeBreadthFirstIterator<>(Trees.<V, T>self(this)); 737 } 738 739 /** 740 * Return an iterator that traverses the subtree rooted at {@code this}. 741 * The first node returned by the iterator is {@code this} node. 742 * <p> 743 * Modifying the tree by inserting, removing, or moving a node invalidates 744 * any iterator created before the modification. 745 * 746 * @see #breadthFirstIterator 747 * @return an iterator for traversing the tree in breadth-first order 748 */ 749 @Override 750 default Iterator<T> iterator() { 751 return breadthFirstIterator(); 752 } 753 754 /** 755 * Return a stream that traverses the subtree rooted at {@code this} node in 756 * breadth-first order. The first node returned by the stream is 757 * {@code this} node. 758 * 759 * @see #depthFirstIterator 760 * @see #stream() 761 * @return a stream for traversing the tree in breadth-first order 762 */ 763 default Stream<T> breadthFirstStream() { 764 return StreamSupport 765 .stream(spliteratorUnknownSize(breadthFirstIterator(), 0), false); 766 } 767 768 /** 769 * Return a stream that traverses the subtree rooted at {@code this} node in 770 * breadth-first order. The first node returned by the stream is 771 * {@code this} node. 772 * 773 * @see #breadthFirstStream 774 * @return a stream for traversing the tree in breadth-first order 775 */ 776 default Stream<T> stream() { 777 return breadthFirstStream(); 778 } 779 780 /** 781 * Return an iterator that traverses the subtree rooted at {@code this} node 782 * in pre-order. The first node returned by the iterator is {@code this} 783 * node. 784 * <p> 785 * Modifying the tree by inserting, removing, or moving a node invalidates 786 * any iterator created before the modification. 787 * 788 * @see #postorderIterator 789 * @return an iterator for traversing the tree in pre-order 790 */ 791 default Iterator<T> preorderIterator() { 792 return new TreeNodePreorderIterator<>(Trees.<V, T>self(this)); 793 } 794 795 /** 796 * Return a stream that traverses the subtree rooted at {@code this} node 797 * in pre-order. The first node returned by the stream is {@code this} node. 798 * <p> 799 * Modifying the tree by inserting, removing, or moving a node invalidates 800 * any iterator created before the modification. 801 * 802 * @see #preorderIterator 803 * @return a stream for traversing the tree in pre-order 804 */ 805 default Stream<T> preorderStream() { 806 return StreamSupport 807 .stream(spliteratorUnknownSize(preorderIterator(), 0), false); 808 } 809 810 /** 811 * Return an iterator that traverses the subtree rooted at {@code this} 812 * node in post-order. The first node returned by the iterator is the 813 * leftmost leaf. This is the same as a depth-first traversal. 814 * 815 * @see #depthFirstIterator 816 * @see #preorderIterator 817 * @return an iterator for traversing the tree in post-order 818 */ 819 default Iterator<T> postorderIterator() { 820 return new TreeNodePostorderIterator<>(Trees.<V, T>self(this)); 821 } 822 823 /** 824 * Return a stream that traverses the subtree rooted at {@code this} node in 825 * post-order. The first node returned by the iterator is the leftmost leaf. 826 * This is the same as a depth-first traversal. 827 * 828 * @see #depthFirstIterator 829 * @see #preorderIterator 830 * @return a stream for traversing the tree in post-order 831 */ 832 default Stream<T> postorderStream() { 833 return StreamSupport 834 .stream(spliteratorUnknownSize(postorderIterator(), 0), false); 835 } 836 837 /** 838 * Return an iterator that traverses the subtree rooted at {@code this} node 839 * in depth-first order. The first node returned by the iterator is the 840 * leftmost leaf. This is the same as a postorder traversal. 841 * <p> 842 * Modifying the tree by inserting, removing, or moving a node invalidates 843 * any iterator created before the modification. 844 * 845 * @see #breadthFirstIterator 846 * @see #postorderIterator 847 * @return an iterator for traversing the tree in depth-first order 848 */ 849 default Iterator<T> depthFirstIterator() { 850 return postorderIterator(); 851 } 852 853 /** 854 * Return a stream that traverses the subtree rooted at {@code this} node in 855 * depth-first. The first node returned by the iterator is the leftmost leaf. 856 * This is the same as a post-order traversal. 857 * 858 * @see #depthFirstIterator 859 * @see #preorderIterator 860 * @return a stream for traversing the tree in post-order 861 */ 862 default Stream<T> depthFirstStream() { 863 return postorderStream(); 864 } 865 866 /** 867 * Return an iterator that follows the path from {@code ancestor} to 868 * {@code this} node. The iterator return {@code ancestor} as first element, 869 * The creation of the iterator is O(m), where m is the number of nodes 870 * between {@code this} node and the {@code ancestor}, inclusive. 871 * <p> 872 * Modifying the tree by inserting, removing, or moving a node invalidates 873 * any iterator created before the modification. 874 * 875 * @see #isAncestor 876 * @see #isDescendant 877 * @param ancestor the ancestor node 878 * @return an iterator for following the path from an ancestor of {@code this} 879 * node to this one 880 * @throws IllegalArgumentException if the {@code ancestor} is not an 881 * ancestor of this node 882 * @throws NullPointerException if the given {@code ancestor} is {@code null} 883 */ 884 default Iterator<T> 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 default Path childPath() { 906 final Iterator<T> it = pathFromAncestorIterator(root()); 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 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 default String toParenthesesString(final Function<? super V, String> mapper) { 971 return TreeFormatter.PARENTHESES.format(this, mapper); 972 } 973 974 /** 975 * Return a compact string representation of the given tree. The tree 976 * <pre> 977 * mul 978 * ├── div 979 * │ ├── cos 980 * │ │ └── 1.0 981 * │ └── cos 982 * │ └── π 983 * └── sin 984 * └── mul 985 * ├── 1.0 986 * └── z 987 * </pre> 988 * is printed as 989 * <pre> 990 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z))) 991 * </pre> 992 * 993 * @since 4.3 994 * 995 * @see #toParenthesesString(Function) 996 * @see TreeFormatter#PARENTHESES 997 * 998 * @return the string representation of the given tree 999 * @throws NullPointerException if the {@code mapper} is {@code null} 1000 */ 1001 default String toParenthesesString() { 1002 return toParenthesesString(Objects::toString); 1003 } 1004 1005 /* ************************************************************************* 1006 * Static helper methods. 1007 **************************************************************************/ 1008 1009 /** 1010 * Calculates the hash code of the given tree. 1011 * 1012 * @param tree the tree where the hash is calculated from 1013 * @return the hash code of the tree 1014 * @throws NullPointerException if the given {@code tree} is {@code null} 1015 */ 1016 static int hashCode(final Tree<?, ?> tree) { 1017 return tree != null 1018 ? tree.breadthFirstStream() 1019 .mapToInt(node -> 31*Objects.hashCode(node.value()) + 37) 1020 .sum() + 17 1021 : 0; 1022 } 1023 1024 /** 1025 * Checks if the two given trees has the same structure with the same values. 1026 * 1027 * @param a the first tree 1028 * @param b the second tree 1029 * @return {@code true} if the two given trees are structurally equals, 1030 * {@code false} otherwise 1031 */ 1032 static boolean equals(final Tree<?, ?> a, final Tree<?, ?> b) { 1033 return Trees.equals(a, b); 1034 } 1035 1036 /** 1037 * Return a string representation of the given tree, like the following 1038 * example. 1039 * 1040 * <pre> 1041 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z))) 1042 * </pre> 1043 * 1044 * This method is intended to be used when override the 1045 * {@link Object#toString()} method. 1046 * 1047 * @param tree the input tree 1048 * @return the string representation of the given tree 1049 */ 1050 static String toString(final Tree<?, ?> tree) { 1051 return tree.toParenthesesString(); 1052 } 1053 1054 1055 /* ************************************************************************* 1056 * Inner classes 1057 **************************************************************************/ 1058 1059 /** 1060 * This class represents the path to child within a given tree. It allows to 1061 * point (and fetch) a tree child. 1062 * 1063 * @see Tree#childAtPath(Path) 1064 * 1065 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a> 1066 * @version 6.0 1067 * @since 4.4 1068 */ 1069 final class Path implements Serializable { 1070 private static final long serialVersionUID = 1L; 1071 1072 private final int[] _path; 1073 1074 private Path(final int[] path) { 1075 _path = requireNonNull(path); 1076 } 1077 1078 /** 1079 * Return the path length, which is the level of the child {@code this} 1080 * path points to. 1081 * 1082 * @return the path length 1083 */ 1084 public int length() { 1085 return _path.length; 1086 } 1087 1088 /** 1089 * Return the child index at the given index (child level). 1090 * 1091 * @param index the path index 1092 * @return the child index at the given child level 1093 * @throws IndexOutOfBoundsException if the index is not with the range 1094 * {@code [0, length())} 1095 */ 1096 public int get(final int index) { 1097 return _path[index]; 1098 } 1099 1100 /** 1101 * Return the path as {@code int[]} array. 1102 * 1103 * @return the path as {@code int[]} array 1104 */ 1105 public int[] toArray() { 1106 return _path.clone(); 1107 } 1108 1109 /** 1110 * Appends the given {@code path} to {@code this} one. 1111 * 1112 * @param path the path to append 1113 * @return a new {@code Path} with the given {@code path} appended 1114 * @throws NullPointerException if the given {@code path} is {@code null} 1115 */ 1116 public Path append(final Path path) { 1117 final int[] p = new int[length() + path.length()]; 1118 System.arraycopy(_path, 0, p, 0, length()); 1119 System.arraycopy(path._path, 0, p, length(), path.length()); 1120 return new Path(p); 1121 } 1122 1123 @Override 1124 public int hashCode() { 1125 return Arrays.hashCode(_path); 1126 } 1127 1128 @Override 1129 public boolean equals(final Object obj) { 1130 return obj == this || 1131 obj instanceof Path && 1132 Arrays.equals(_path, ((Path)obj)._path); 1133 } 1134 1135 @Override 1136 public String toString() { 1137 return Arrays.toString(_path); 1138 } 1139 1140 /** 1141 * Create a new path object from the given child indexes. 1142 * 1143 * @param path the child indexes 1144 * @return a new tree path 1145 * @throws IllegalArgumentException if one of the path elements is 1146 * smaller than zero 1147 */ 1148 public static Path of(final int... path) { 1149 for (int i = 0; i < path.length; ++i) { 1150 if (path[i] < 0) { 1151 throw new IllegalArgumentException(format( 1152 "Path element at position %d is smaller than zero: %d", 1153 i, path[i] 1154 )); 1155 } 1156 } 1157 1158 return new Path(path.clone()); 1159 } 1160 1161 1162 /* ********************************************************************* 1163 * Java object serialization 1164 * ********************************************************************/ 1165 1166 private Object writeReplace() { 1167 return new Serial(Serial.TREE_PATH, this); 1168 } 1169 1170 private void readObject(final ObjectInputStream stream) 1171 throws InvalidObjectException 1172 { 1173 throw new InvalidObjectException("Serialization proxy required."); 1174 } 1175 1176 1177 void write(final DataOutput out) throws IOException { 1178 writeIntArray(_path, out); 1179 } 1180 1181 static Object read(final DataInput in) throws IOException { 1182 return Path.of(readIntArray(in)); 1183 } 1184 1185 } 1186 1187}