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