001/* 002 * Java Genetic Algorithm Library (jenetics-4.4.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 4.4 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 getChild(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.<V, T>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 getIndex(final Tree<?, ?> child) { 171 int index = -1; 172 for (int i = 0, n = childCount(); i < n && index == -1; ++i) { 173 if (getChild(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 (int)breadthFirstStream().count(); 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.getChild(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.<V, T>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.<V, T>self(this); 308 } else { 309 diff = level1 - level2; 310 node1 = Trees.<V, T>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.<V, T>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 */ 355 public default ISeq<T> getPath() { 356 return Trees.pathToRoot(Trees.<V, T>self(this), 0).toISeq(); 357 } 358 359 /** 360 * Returns the root of the tree that contains this node. The root is the 361 * ancestor with no parent. 362 * 363 * @return the root of the tree that contains this node 364 */ 365 public default T getRoot() { 366 T anc = Trees.self(this); 367 T prev; 368 369 do { 370 prev = anc; 371 anc = anc.getParent().orElse(null); 372 } while (anc != null); 373 374 return prev; 375 } 376 377 /* ************************************************************************* 378 * Child query operations 379 **************************************************************************/ 380 381 /** 382 * Return {@code true} if the given {@code node} is a child of {@code this} 383 * node. 384 * 385 * @param node the other node to check 386 * @return {@code true} if {@code node}is a child, {@code false} otherwise 387 * @throws NullPointerException if the given {@code node} is {@code null} 388 */ 389 public default boolean isChild(final Tree<?, ?> node) { 390 requireNonNull(node); 391 return childCount() != 0 && 392 node.getParent().equals(Optional.of(Trees.<V, T>self(this))); 393 } 394 395 /** 396 * Return the first child of {@code this} node, or {@code Optional.empty()} 397 * if {@code this} node has no children. 398 * 399 * @return the first child of this node 400 */ 401 public default Optional<T> firstChild() { 402 return childCount() > 0 403 ? Optional.of(getChild(0)) 404 : Optional.empty(); 405 } 406 407 /** 408 * Return the last child of {@code this} node, or {@code Optional.empty()} 409 * if {@code this} node has no children. 410 * 411 * @return the last child of this node 412 */ 413 public default Optional<T> lastChild() { 414 return childCount() > 0 415 ? Optional.of(getChild(childCount() - 1)) 416 : Optional.empty(); 417 } 418 419 /** 420 * Return the child which comes immediately after {@code this} node. This 421 * method performs a linear search of this node's children for {@code child} 422 * and is {@code O(n)} where n is the number of children. 423 * 424 * @param child the child node 425 * @return the child of this node that immediately follows the {@code child}, 426 * or {@code Optional.empty()} if the given {@code node} is the 427 * first node. 428 * @throws NullPointerException if the given {@code child} is {@code null} 429 */ 430 public default Optional<T> childAfter(final Tree<?, ?> child) { 431 requireNonNull(child); 432 433 final int index = getIndex(child); 434 if (index == -1) { 435 throw new IllegalArgumentException("The given node is not a child."); 436 } 437 438 return index < childCount() - 1 439 ? Optional.of(getChild(index + 1)) 440 : Optional.empty(); 441 } 442 443 /** 444 * Return the child which comes immediately before {@code this} node. This 445 * method performs a linear search of this node's children for {@code child} 446 * and is {@code O(n)} where n is the number of children. 447 * 448 * @param child the child node 449 * @return the child of this node that immediately precedes the {@code child}, 450 * or {@code null} if the given {@code node} is the first node. 451 * @throws NullPointerException if the given {@code child} is {@code null} 452 */ 453 public default Optional<T> childBefore(final Tree<?, ?> child) { 454 requireNonNull(child); 455 456 final int index = getIndex(child); 457 if (index == -1) { 458 throw new IllegalArgumentException("The given node is not a child."); 459 } 460 461 return index > 0 462 ? Optional.of(getChild(index - 1)) 463 : Optional.empty(); 464 } 465 466 /** 467 * Return the node that follows {@code this} node in a pre-order traversal 468 * of {@code this} tree node. Return {@code Optional.empty()} if this node 469 * is the last node of the traversal. This is an inefficient way to traverse 470 * the entire tree use an iterator instead. 471 * 472 * @see #preorderIterator 473 * @return the node that follows this node in a pre-order traversal, or 474 * {@code Optional.empty()} if this node is last 475 */ 476 public default Optional<T> nextNode() { 477 Optional<T> next = Optional.empty(); 478 479 if (childCount() == 0) { 480 T node = Trees.<V, T>self(this); 481 while (node != null && !(next = node.nextSibling()).isPresent()) { 482 node = node.getParent().orElse(null); 483 } 484 } else { 485 next = Optional.of(getChild(0)); 486 } 487 488 return next; 489 } 490 491 /** 492 * Return the node that precedes this node in a pre-order traversal of 493 * {@code this} tree node. Returns {@code Optional.empty()} if this node is 494 * the first node of the traversal, the root of the tree. This is an 495 * inefficient way to traverse the entire tree; use an iterator instead. 496 * 497 * @see #preorderIterator 498 * @return the node that precedes this node in a pre-order traversal, or 499 * {@code Optional.empty()} if this node is the first 500 */ 501 public default Optional<T> previousNode() { 502 Optional<T> node = Optional.empty(); 503 504 if (getParent().isPresent()) { 505 final Optional<T> prev = previousSibling(); 506 if (prev.isPresent()) { 507 node = prev.get().childCount() == 0 508 ? prev 509 : prev.map(Tree<V, T>::lastLeaf); 510 } else { 511 node = getParent(); 512 } 513 } 514 515 return node; 516 } 517 518 /* ************************************************************************* 519 * Sibling query operations 520 **************************************************************************/ 521 522 /** 523 * Test if the given {@code node} is a sibling of {@code this} node. 524 * 525 * @param node node to test as sibling of this node 526 * @return {@code true} if the {@code node} is a sibling of {@code this} 527 * node 528 * @throws NullPointerException if the given {@code node} is {@code null} 529 */ 530 public default boolean isSibling(final Tree<?, ?> node) { 531 return identical(requireNonNull(node)) || 532 getParent().equals(node.getParent()); 533 } 534 535 /** 536 * Return the number of siblings of {@code this} node. A node is its own 537 * sibling (if it has no parent or no siblings, this method returns 538 * {@code 1}). 539 * 540 * @return the number of siblings of {@code this} node 541 */ 542 public default int siblingCount() { 543 return getParent().map(Tree<V, T>::childCount).orElse(1); 544 } 545 546 /** 547 * Return the next sibling of {@code this} node in the parent's children 548 * array, or {@code null} if {@code this} node has no parent or it is the 549 * last child of the paren. This method performs a linear search that is 550 * {@code O(n)} where n is the number of children; to traverse the entire 551 * array, use the iterator of the parent instead. 552 * 553 * @see #childStream() 554 * @return the sibling of {@code this} node that immediately follows 555 * {@code this} node 556 */ 557 public default Optional<T> nextSibling() { 558 return getParent().flatMap(p -> p.childAfter(Trees.<V, T>self(this))); 559 } 560 561 /** 562 * Return the previous sibling of {@code this} node in the parent's children 563 * list, or {@code Optional.empty()} if this node has no parent or is the 564 * parent's first child. This method performs a linear search that is O(n) 565 * where n is the number of children. 566 * 567 * @return the sibling of {@code this} node that immediately precedes this 568 * node 569 */ 570 public default Optional<T> previousSibling() { 571 return getParent().flatMap(p -> p.childBefore(Trees.<V, T>self(this))); 572 } 573 574 575 /* ************************************************************************* 576 * Leaf query operations 577 **************************************************************************/ 578 579 /** 580 * Return {@code true} if {@code this} node has no children. 581 * 582 * @return {@code true} if {@code this} node has no children, {@code false} 583 * otherwise 584 */ 585 public default boolean isLeaf() { 586 return childCount() == 0; 587 } 588 589 /** 590 * Return the first leaf that is a descendant of {@code this} node; either 591 * this node or its first child's first leaf. {@code this} node is returned 592 * if it is a leaf. 593 * 594 * @see #isLeaf 595 * @see #isDescendant 596 * @return the first leaf in the subtree rooted at this node 597 */ 598 public default T firstLeaf() { 599 T leaf = Trees.<V, T>self(this); 600 while (!leaf.isLeaf()) { 601 leaf = leaf.firstChild().orElseThrow(AssertionError::new); 602 } 603 604 return leaf; 605 } 606 607 /** 608 * Return the last leaf that is a descendant of this node; either 609 * {@code this} node or its last child's last leaf. Returns {@code this} 610 * node if it is a leaf. 611 * 612 * @see #isLeaf 613 * @see #isDescendant 614 * @return the last leaf in this subtree 615 */ 616 public default T lastLeaf() { 617 T leaf = Trees.<V, T>self(this); 618 while (!leaf.isLeaf()) { 619 leaf = leaf.lastChild().orElseThrow(AssertionError::new); 620 } 621 622 return leaf; 623 } 624 625 /** 626 * Returns the leaf after {@code this} node or {@code Optional.empty()} if 627 * this node is the last leaf in the tree. 628 * <p> 629 * In order to determine the next node, this method first performs a linear 630 * search in the parent's child-list in order to find the current node. 631 * <p> 632 * That implementation makes the operation suitable for short traversals 633 * from a known position. But to traverse all of the leaves in the tree, you 634 * should use {@link #depthFirstIterator()} to iterator the nodes in the 635 * tree and use {@link #isLeaf()} on each node to determine which are leaves. 636 * 637 * @see #depthFirstIterator 638 * @see #isLeaf 639 * @return return the next leaf past this node 640 */ 641 public default Optional<T> nextLeaf() { 642 return nextSibling() 643 .map(s -> Optional.of(s.firstLeaf())) 644 .orElseGet(() -> getParent().flatMap(Tree<V, T>::nextLeaf)); 645 } 646 647 /** 648 * Return the leaf before {@code this} node or {@code null} if {@code this} 649 * node is the first leaf in the tree. 650 * <p> 651 * In order to determine the previous node, this method first performs a 652 * linear search in the parent's child-list in order to find the current 653 * node. 654 * <p> 655 * That implementation makes the operation suitable for short traversals 656 * from a known position. But to traverse all of the leaves in the tree, you 657 * should use {@link #depthFirstIterator()} to iterate the nodes in the tree 658 * and use {@link #isLeaf()} on each node to determine which are leaves. 659 * 660 * @see #depthFirstIterator 661 * @see #isLeaf 662 * @return returns the leaf before {@code this} node 663 */ 664 public default Optional<T> previousLeaf() { 665 return previousSibling() 666 .map(s -> Optional.of(s.lastLeaf())) 667 .orElseGet(() -> getParent().flatMap(Tree<V, T>::previousLeaf)); 668 } 669 670 /** 671 * Returns the total number of leaves that are descendants of this node. 672 * If this node is a leaf, returns {@code 1}. This method is {@code O(n)}, 673 * where n is the number of descendants of {@code this} node. 674 * 675 * @see #isLeaf() 676 * @return the number of leaves beneath this node 677 */ 678 public default int leafCount() { 679 return (int) breadthFirstStream() 680 .filter(Tree<V, T>::isLeaf) 681 .count(); 682 } 683 684 /* ************************************************************************* 685 * Tree traversing. 686 **************************************************************************/ 687 688 /** 689 * Return an iterator that traverses the subtree rooted at {@code this} 690 * node in breadth-first order. The first node returned by the iterator is 691 * {@code this} node. 692 * <p> 693 * Modifying the tree by inserting, removing, or moving a node invalidates 694 * any iterator created before the modification. 695 * 696 * @see #depthFirstIterator 697 * @return an iterator for traversing the tree in breadth-first order 698 */ 699 public default Iterator<T> breadthFirstIterator() { 700 return new TreeNodeBreadthFirstIterator<>(Trees.<V, T>self(this)); 701 } 702 703 /** 704 * Return an iterator that traverses the subtree rooted at {@code this}. 705 * The first node returned by the iterator is {@code this} node. 706 * <p> 707 * Modifying the tree by inserting, removing, or moving a node invalidates 708 * any iterator created before the modification. 709 * 710 * @see #breadthFirstIterator 711 * @return an iterator for traversing the tree in breadth-first order 712 */ 713 @Override 714 public default Iterator<T> iterator() { 715 return breadthFirstIterator(); 716 } 717 718 /** 719 * Return a stream that traverses the subtree rooted at {@code this} node in 720 * breadth-first order. The first node returned by the stream is 721 * {@code this} node. 722 * 723 * @see #depthFirstIterator 724 * @see #stream() 725 * @return a stream for traversing the tree in breadth-first order 726 */ 727 public default Stream<T> breadthFirstStream() { 728 return StreamSupport 729 .stream(spliteratorUnknownSize(breadthFirstIterator(), 0), false); 730 } 731 732 /** 733 * Return a stream that traverses the subtree rooted at {@code this} node in 734 * breadth-first order. The first node returned by the stream is 735 * {@code this} node. 736 * 737 * @see #breadthFirstStream 738 * @return a stream for traversing the tree in breadth-first order 739 */ 740 public default Stream<T> stream() { 741 return breadthFirstStream(); 742 } 743 744 /** 745 * Return an iterator that traverses the subtree rooted at {@code this} node 746 * in pre-order. The first node returned by the iterator is {@code this} 747 * node. 748 * <p> 749 * Modifying the tree by inserting, removing, or moving a node invalidates 750 * any iterator created before the modification. 751 * 752 * @see #postorderIterator 753 * @return an iterator for traversing the tree in pre-order 754 */ 755 public default Iterator<T> preorderIterator() { 756 return new TreeNodePreorderIterator<>(Trees.<V, T>self(this)); 757 } 758 759 /** 760 * Return a stream that traverses the subtree rooted at {@code this} node 761 * in pre-order. The first node returned by the stream is {@code this} node. 762 * <p> 763 * Modifying the tree by inserting, removing, or moving a node invalidates 764 * any iterator created before the modification. 765 * 766 * @see #preorderIterator 767 * @return a stream for traversing the tree in pre-order 768 */ 769 public default Stream<T> preorderStream() { 770 return StreamSupport 771 .stream(spliteratorUnknownSize(preorderIterator(), 0), false); 772 } 773 774 /** 775 * Return an iterator that traverses the subtree rooted at {@code this} 776 * node in post-order. The first node returned by the iterator is the 777 * leftmost leaf. This is the same as a depth-first traversal. 778 * 779 * @see #depthFirstIterator 780 * @see #preorderIterator 781 * @return an iterator for traversing the tree in post-order 782 */ 783 public default Iterator<T> postorderIterator() { 784 return new TreeNodePostorderIterator<>(Trees.<V, T>self(this)); 785 } 786 787 /** 788 * Return a stream that traverses the subtree rooted at {@code this} node in 789 * post-order. The first node returned by the iterator is the leftmost leaf. 790 * This is the same as a depth-first traversal. 791 * 792 * @see #depthFirstIterator 793 * @see #preorderIterator 794 * @return a stream for traversing the tree in post-order 795 */ 796 public default Stream<T> postorderStream() { 797 return StreamSupport 798 .stream(spliteratorUnknownSize(postorderIterator(), 0), false); 799 } 800 801 /** 802 * Return an iterator that traverses the subtree rooted at {@code this} node 803 * in depth-first order. The first node returned by the iterator is the 804 * leftmost leaf. This is the same as a postorder traversal. 805 * <p> 806 * Modifying the tree by inserting, removing, or moving a node invalidates 807 * any iterator created before the modification. 808 * 809 * @see #breadthFirstIterator 810 * @see #postorderIterator 811 * @return an iterator for traversing the tree in depth-first order 812 */ 813 public default Iterator<T> depthFirstIterator() { 814 return postorderIterator(); 815 } 816 817 /** 818 * Return a stream that traverses the subtree rooted at {@code this} node in 819 * depth-first. The first node returned by the iterator is the leftmost leaf. 820 * This is the same as a post-order traversal. 821 * 822 * @see #depthFirstIterator 823 * @see #preorderIterator 824 * @return a stream for traversing the tree in post-order 825 */ 826 public default Stream<T> depthFirstStream() { 827 return postorderStream(); 828 } 829 830 /** 831 * Return an iterator that follows the path from {@code ancestor} to 832 * {@code this} node. The iterator return {@code ancestor} as first element, 833 * The creation of the iterator is O(m), where m is the number of nodes 834 * between {@code this} node and the {@code ancestor}, inclusive. 835 * <p> 836 * Modifying the tree by inserting, removing, or moving a node invalidates 837 * any iterator created before the modification. 838 * 839 * @see #isAncestor 840 * @see #isDescendant 841 * @param ancestor the ancestor node 842 * @return an iterator for following the path from an ancestor of {@code this} 843 * node to this one 844 * @throws IllegalArgumentException if the {@code ancestor} is not an 845 * ancestor of this node 846 * @throws NullPointerException if the given {@code ancestor} is {@code null} 847 */ 848 public default Iterator<T> 849 pathFromAncestorIterator(final Tree<?, ?> ancestor) { 850 return new TreeNodePathIterator<>(ancestor, Trees.<V, T>self(this)); 851 } 852 853 /** 854 * Return the path of {@code this} child node from the root node. You will 855 * get {@code this} node, if you call {@link #childAtPath(Path)} on the 856 * root node of {@code this} node. 857 * <pre>{@code 858 * final Tree<?, ?> node = ...; 859 * final Tree<?, ?> root = node.getRoot(); 860 * final int[] path = node.childPath(); 861 * assert node == root.childAtPath(path); 862 * }</pre> 863 * 864 * @since 4.4 865 * 866 * @see #childAtPath(Path) 867 * 868 * @return the path of {@code this} child node from the root node. 869 */ 870 public default Path childPath() { 871 final Iterator<T> it = pathFromAncestorIterator(getRoot()); 872 final int[] path = new int[level()]; 873 874 T tree = null; 875 int index = 0; 876 while (it.hasNext()) { 877 final T child = it.next(); 878 if (tree != null) { 879 path[index++] = tree.getIndex(child); 880 } 881 882 tree = child; 883 } 884 885 assert index == path.length; 886 887 return new Path(path); 888 } 889 890 /** 891 * Tests whether {@code this} node is the same as the {@code other} node. 892 * The default implementation returns the object identity, 893 * {@code this == other}, of the two objects, but other implementations may 894 * use different criteria for checking the <i>identity</i>. 895 * 896 * @param other the {@code other} node 897 * @return {@code true} if the {@code other} node is the same as {@code this} 898 * node. 899 */ 900 public default boolean identical(final Tree<?, ?> other) { 901 return this == other; 902 } 903 904 /* ************************************************************************* 905 * 'toString' methods 906 **************************************************************************/ 907 908 /** 909 * Return a compact string representation of the given tree. The tree 910 * <pre> 911 * mul 912 * ├── div 913 * │ ├── cos 914 * │ │ └── 1.0 915 * │ └── cos 916 * │ └── π 917 * └── sin 918 * └── mul 919 * ├── 1.0 920 * └── z 921 * </pre> 922 * is printed as 923 * <pre> 924 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z))) 925 * </pre> 926 * 927 * @since 4.3 928 * 929 * @see #toParenthesesString() 930 * 931 * @param mapper the {@code mapper} which converts the tree value to a string 932 * @return the string representation of the given tree 933 */ 934 public default String 935 toParenthesesString(final Function<? super V, String> mapper) { 936 requireNonNull(mapper); 937 return ParenthesesTrees.toString(Trees.<V, T>self(this), mapper); 938 } 939 940 /** 941 * Return a compact string representation of the given tree. The tree 942 * <pre> 943 * mul 944 * ├── div 945 * │ ├── cos 946 * │ │ └── 1.0 947 * │ └── cos 948 * │ └── π 949 * └── sin 950 * └── mul 951 * ├── 1.0 952 * └── z 953 * </pre> 954 * is printed as 955 * <pre> 956 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z))) 957 * </pre> 958 * 959 * @since 4.3 960 * 961 * @see #toParenthesesString(Function) 962 * 963 * @return the string representation of the given tree 964 * @throws NullPointerException if the {@code mapper} is {@code null} 965 */ 966 public default String toParenthesesString() { 967 return toParenthesesString(Objects::toString); 968 } 969 970 971 /* ************************************************************************* 972 * Static helper methods. 973 **************************************************************************/ 974 975 /** 976 * Calculates the hash code of the given tree. 977 * 978 * @param tree the tree where the hash is calculated from 979 * @return the hash code of the tree 980 * @throws NullPointerException if the given {@code tree} is {@code null} 981 */ 982 public static int hashCode(final Tree<?, ?> tree) { 983 return tree != null 984 ? tree.breadthFirstStream() 985 .mapToInt(node -> 31*Objects.hashCode(node.getValue()) + 37) 986 .sum() + 17 987 : 0; 988 } 989 990 /** 991 * Checks if the two given trees has the same structure with the same values. 992 * 993 * @param a the first tree 994 * @param b the second tree 995 * @return {@code true} if the two given trees are structurally equals, 996 * {@code false} otherwise 997 */ 998 public static boolean equals(final Tree<?, ?> a, final Tree<?, ?> b) { 999 return Trees.equals(a, b); 1000 } 1001 1002 /** 1003 * Return a string representation of the given tree, like the following 1004 * example. 1005 * 1006 * <pre> 1007 * 0 1008 * ├── 1 1009 * │ ├── 4 1010 * │ └── 5 1011 * ├── 2 1012 * │ └── 6 1013 * └── 3 1014 * ├── 7 1015 * │ ├── 10 1016 * │ └── 11 1017 * ├── 8 1018 * └── 9 1019 * </pre> 1020 * 1021 * This method is intended to be used when override the 1022 * {@link Object#toString()} method. 1023 * 1024 * @param tree the input tree 1025 * @return the string representation of the given tree 1026 */ 1027 public static String toString(final Tree<?, ?> tree) { 1028 return Trees.toString(tree); 1029 } 1030 1031 1032 /** 1033 * Return a compact string representation of the given tree. The tree 1034 * <pre> 1035 * mul 1036 * ├── div 1037 * │ ├── cos 1038 * │ │ └── 1.0 1039 * │ └── cos 1040 * │ └── π 1041 * └── sin 1042 * └── mul 1043 * ├── 1.0 1044 * └── z 1045 * </pre> 1046 * is printed as 1047 * <pre> 1048 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z))) 1049 * </pre> 1050 * 1051 * @param tree the input tree 1052 * @return the string representation of the given tree 1053 * 1054 * @deprecated Use {@link #toParenthesesString()} instead 1055 */ 1056 @Deprecated 1057 @SuppressWarnings("unchecked") 1058 public static String toCompactString(final Tree<?, ?> tree) { 1059 return ParenthesesTrees.toString((Tree)tree, Objects::toString); 1060 } 1061 1062 /** 1063 * Return a string representation of the given {@code tree} in dotty syntax. 1064 * 1065 * @param tree the input tree 1066 * @return the string representation of the given tree 1067 * 1068 * @deprecated Will be removed; very special to-string method. 1069 */ 1070 @Deprecated 1071 public static String toDottyString(final Tree<?, ?> tree) { 1072 return Trees.toDottyString("T", tree); 1073 } 1074 1075 1076 /* ************************************************************************* 1077 * Inner classes 1078 **************************************************************************/ 1079 1080 /** 1081 * This class represents the path to child within a given tree. It allows to 1082 * point (and fetch) a tree child. 1083 *s 1084 * @see Tree#childAtPath(Path) 1085 * 1086 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a> 1087 * @version 4.4 1088 * @since 4.4 1089 */ 1090 public static final class Path implements Serializable { 1091 private static final long serialVersionUID = 1L; 1092 1093 private final int[] _path; 1094 1095 private Path(final int[] path) { 1096 _path = requireNonNull(path); 1097 } 1098 1099 /** 1100 * Return the path length, which is the level of the child {@code this} 1101 * path points to. 1102 * 1103 * @return the path length 1104 */ 1105 public int length() { 1106 return _path.length; 1107 } 1108 1109 /** 1110 * Return the child index at the given index (child level). 1111 * 1112 * @param index the path index 1113 * @return the child index at the given child level 1114 * @throws IndexOutOfBoundsException if the index is not with the range 1115 * {@code [0, length())} 1116 */ 1117 public int get(final int index) { 1118 return _path[index]; 1119 } 1120 1121 /** 1122 * Return the path as {@code int[]} array. 1123 * 1124 * @return the path as {@code int[]} array 1125 */ 1126 public int[] toArray() { 1127 return _path.clone(); 1128 } 1129 1130 /** 1131 * Appends the given {@code path} to {@code this} one. 1132 * 1133 * @param path the path to append 1134 * @return a new {@code Path} with the given {@code path} appended 1135 * @throws NullPointerException if the given {@code path} is {@code null} 1136 */ 1137 public Path append(final Path path) { 1138 final int[] p = new int[length() + path.length()]; 1139 System.arraycopy(_path, 0, p, 0, length()); 1140 System.arraycopy(path._path, 0, p, length(), path.length()); 1141 return new Path(p); 1142 } 1143 1144 @Override 1145 public int hashCode() { 1146 return Arrays.hashCode(_path); 1147 } 1148 1149 @Override 1150 public boolean equals(final Object obj) { 1151 return obj == this || 1152 obj instanceof Path && 1153 Arrays.equals(_path, ((Path)obj)._path); 1154 } 1155 1156 @Override 1157 public String toString() { 1158 return Arrays.toString(_path); 1159 } 1160 1161 /** 1162 * Create a new path object from the given child indexes. 1163 * 1164 * @param path the child indexes 1165 * @return a new tree path 1166 * @throws IllegalArgumentException if one of the path elements is 1167 * smaller than zero 1168 */ 1169 public static Path of(final int... path) { 1170 for (int i = 0; i < path.length; ++i) { 1171 if (path[i] < 0) { 1172 throw new IllegalArgumentException(format( 1173 "Path element at position %d is smaller than zero: %d", 1174 i, path[i] 1175 )); 1176 } 1177 } 1178 1179 return new Path(path.clone()); 1180 } 1181 } 1182 1183}