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