Interface Tree<V,T extends Tree<V,T>>
-
- All Superinterfaces:
Iterable<T>
- All Known Implementing Classes:
AbstractTreeGene
,FlatTreeNode
,TreeNode
public interface Tree<V,T extends Tree<V,T>> extends Iterable<T>
General purpose tree structure. The interface only contains tree read methods. For a mutable tree implementation have a look at theTreeNode
class.- Since:
- 3.9
- Version:
- 6.0
- See Also:
TreeNode
-
-
Nested Class Summary
Nested Classes Modifier and Type Interface Description static class
Tree.Path
This class represents the path to child within a given tree.
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Default Methods Modifier and Type Method Description default Iterator<T>
breadthFirstIterator()
Return an iterator that traverses the subtree rooted atthis
node in breadth-first order.default Stream<T>
breadthFirstStream()
Return a stream that traverses the subtree rooted atthis
node in breadth-first order.default Optional<T>
childAfter(Tree<?,?> child)
Return the child which comes immediately afterthis
node.T
childAt(int index)
Return the child node with the given index.default Optional<T>
childAtPath(int... path)
Return the child node at the givenpath
.default Optional<T>
childAtPath(Tree.Path path)
Return the child node at the givenpath
.default Optional<T>
childBefore(Tree<?,?> child)
Return the child which comes immediately beforethis
node.int
childCount()
Return the number of children this tree node consists of.default Iterator<T>
childIterator()
Return an iterator of the children of thisTree
node.default Tree.Path
childPath()
Return the path ofthis
child node from the root node.default Stream<T>
childStream()
Return a forward-order stream of this node's children.default int
depth()
Returns the depth of the tree rooted at this node.default Iterator<T>
depthFirstIterator()
Return an iterator that traverses the subtree rooted atthis
node in depth-first order.default Stream<T>
depthFirstStream()
Return a stream that traverses the subtree rooted atthis
node in depth-first.static boolean
equals(Tree<?,?> a, Tree<?,?> b)
Checks if the two given trees has the same structure with the same values.default Optional<T>
firstChild()
Return the first child ofthis
node, orOptional.empty()
ifthis
node has no children.default T
firstLeaf()
Return the first leaf that is a descendant ofthis
node; either this node or its first child's first leaf.static int
hashCode(Tree<?,?> tree)
Calculates the hash code of the given tree.default boolean
identical(Tree<?,?> other)
Tests whetherthis
node is the same as theother
node.default int
indexOf(Tree<?,?> child)
Returns the index of the specified child in this node's child array, or-1
ifthis
node doesn't contain the givenchild
.default boolean
isAncestor(Tree<?,?> node)
Returntrue
if the givennode
is an ancestor ofthis
node.default boolean
isChild(Tree<?,?> node)
Returntrue
if the givennode
is a child ofthis
node.default boolean
isDescendant(Tree<?,?> node)
Returntrue
if the givennode
is a descendant ofthis
node.default boolean
isLeaf()
Returntrue
ifthis
node has no children.default boolean
isRelated(Tree<?,?> node)
Returns true if and only if the givennode
is in the same tree asthis
node.default boolean
isRoot()
Returnstrue
if this node is the root of the tree.default boolean
isSibling(Tree<?,?> node)
Test if the givennode
is a sibling ofthis
node.default Iterator<T>
iterator()
Return an iterator that traverses the subtree rooted atthis
.default Optional<T>
lastChild()
Return the last child ofthis
node, orOptional.empty()
ifthis
node has no children.default T
lastLeaf()
Return the last leaf that is a descendant of this node; eitherthis
node or its last child's last leaf.default int
leafCount()
Returns the total number of leaves that are descendants of this node.default int
level()
Returns the number of levels above this node.default Optional<T>
nextLeaf()
Returns the leaf afterthis
node orOptional.empty()
if this node is the last leaf in the tree.default Optional<T>
nextNode()
Return the node that followsthis
node in a pre-order traversal ofthis
tree node.default Optional<T>
nextSibling()
Return the next sibling ofthis
node in the parent's children array, ornull
ifthis
node has no parent or it is the last child of the paren.Optional<T>
parent()
Return the parent node of this tree node.default Tree.Path
path()
Return theTree.Path
ofthis
tree, such thatdefault ISeq<T>
pathElements()
Returns the path from the root, to get to this node.default Iterator<T>
pathFromAncestorIterator(Tree<?,?> ancestor)
Return an iterator that follows the path fromancestor
tothis
node.default Iterator<T>
postorderIterator()
Return an iterator that traverses the subtree rooted atthis
node in post-order.default Stream<T>
postorderStream()
Return a stream that traverses the subtree rooted atthis
node in post-order.default Iterator<T>
preorderIterator()
Return an iterator that traverses the subtree rooted atthis
node in pre-order.default Stream<T>
preorderStream()
Return a stream that traverses the subtree rooted atthis
node in pre-order.default Optional<T>
previousLeaf()
Return the leaf beforethis
node ornull
ifthis
node is the first leaf in the tree.default Optional<T>
previousNode()
Return the node that precedes this node in a pre-order traversal ofthis
tree node.default Optional<T>
previousSibling()
Return the previous sibling ofthis
node in the parent's children list, orOptional.empty()
if this node has no parent or is the parent's first child.default T
root()
Returns the root of the tree that contains this node.default Optional<T>
sharedAncestor(Tree<?,?> node)
Returns the nearest common ancestor to this node and the givennode
.default int
siblingCount()
Return the number of siblings ofthis
node.default int
size()
Return the number of nodes ofthis
node (sub-tree).default Stream<T>
stream()
Return a stream that traverses the subtree rooted atthis
node in breadth-first order.default String
toParenthesesString()
Return a compact string representation of the given tree.default String
toParenthesesString(Function<? super V,String> mapper)
Return a compact string representation of the given tree.static String
toString(Tree<?,?> tree)
Return a string representation of the given tree, like the following example.V
value()
Return the value of the currentTree
node.-
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
-
-
-
Method Detail
-
value
V value()
Return the value of the currentTree
node. The value may benull
.- Returns:
- the value of the current
Tree
node
-
parent
Optional<T> parent()
Return the parent node of this tree node.- Returns:
- the parent node, or
Optional.empty()
if this node is the root of the tree
-
childAt
T childAt(int index)
Return the child node with the given index.- Parameters:
index
- the child index- Returns:
- the child node with the given index
- Throws:
IndexOutOfBoundsException
- if theindex
is out of bounds ([0, childCount())
)
-
childCount
int childCount()
Return the number of children this tree node consists of.- Returns:
- the number of children this tree node consists of
-
childIterator
default Iterator<T> childIterator()
Return an iterator of the children of thisTree
node.- Returns:
- an iterator of the children of this
Tree
node.
-
childStream
default Stream<T> childStream()
Return a forward-order stream of this node's children.- Returns:
- a stream of children of
this
node
-
isRoot
default boolean isRoot()
Returnstrue
if this node is the root of the tree.- Returns:
true
if this node is the root of its tree,false
otherwise
-
depth
default int depth()
Returns the depth of the tree rooted at this node. The depth of a tree is the longest distance fromthis
node to a leaf. Ifthis
node has no children, 0 is returned. This operation is much more expensive thanlevel()
because it must effectively traverse the entire tree rooted atthis
node.- Returns:
- the depth of the tree whose root is this node
-
level
default int level()
Returns the number of levels above this node. The level of a tree is the distance from the root tothis
node. Ifthis
node is the root, returns 0.- Returns:
- the number of levels above this node
-
indexOf
default int indexOf(Tree<?,?> child)
Returns the index of the specified child in this node's child array, or-1
ifthis
node doesn't contain the givenchild
. This method performs a linear search and is O(n) wheren
is the number of children.- Parameters:
child
- the TreeNode to search for among this node's children- Returns:
- the index of the node in this node's child array, or
-1
if the node could not be found - Throws:
NullPointerException
- if the givenchild
isnull
-
size
default int size()
Return the number of nodes ofthis
node (sub-tree).- Returns:
- the number of nodes of
this
node (sub-tree)
-
childAtPath
default Optional<T> childAtPath(Tree.Path path)
Return the child node at the givenpath
. A path consists of the child index at a give level, starting with level 1. (The root note has level zero.)tree.childAtPath(Path.of(2))
will return the third child node ofthis
node, if it exists andtree.childAtPath(Path.of(2, 0))
will return the first child of the third child ofthis node
.- Parameters:
path
- the child path- Returns:
- the child node at the given
path
- Throws:
NullPointerException
- if the givenpath
array isnull
- Since:
- 4.4
- See Also:
childAtPath(int...)
-
childAtPath
default Optional<T> childAtPath(int... path)
Return the child node at the givenpath
. A path consists of the child index at a give level, starting with level 1. (The root note has level zero.)tree.childAtPath(2)
will return the third child node ofthis
node, if it exists andtree.childAtPath(2, 0)
will return the first child of the third child ofthis node
.- Parameters:
path
- the child path- Returns:
- the child node at the given
path
- Throws:
NullPointerException
- if the givenpath
array isnull
IllegalArgumentException
- if one of the path elements is smaller than zero- Since:
- 4.3
- See Also:
childAtPath(Path)
-
isAncestor
default boolean isAncestor(Tree<?,?> node)
Returntrue
if the givennode
is an ancestor ofthis
node. This operation is at worstO(h)
whereh
is the distance from the root tothis
node.- Parameters:
node
- the node to test- Returns:
true
if the givennode
is an ancestor ofthis
node,false
otherwise- Throws:
NullPointerException
- if the givennode
isnull
-
isDescendant
default boolean isDescendant(Tree<?,?> node)
Returntrue
if the givennode
is a descendant ofthis
node. If the givennode
isnull
,false
is returned. This operation is at worstO(h)
whereh
is the distance from the root tothis
node.- Parameters:
node
- the node to test as descendant of this node- Returns:
true
if this node is an ancestor of the givennode
- Throws:
NullPointerException
- if the givennode
isnull
-
sharedAncestor
default Optional<T> sharedAncestor(Tree<?,?> node)
Returns the nearest common ancestor to this node and the givennode
. A node is considered an ancestor of itself.- Parameters:
node
-node
to find common ancestor with- Returns:
- nearest ancestor common to this node and the given
node
, orOptional.empty()
if no common ancestor exists. - Throws:
NullPointerException
- if the givennode
isnull
-
isRelated
default boolean isRelated(Tree<?,?> node)
Returns true if and only if the givennode
is in the same tree asthis
node.- Parameters:
node
- the other node to check- Returns:
- true if the given
node
is in the same tree asthis
node,false
otherwise. - Throws:
NullPointerException
- if the givennode
isnull
-
pathElements
default ISeq<T> pathElements()
Returns the path from the root, to get to this node. The last element in the path is this node.- Returns:
- an array of TreeNode objects giving the path, where the first element in the path is the root and the last element is this node.
- Since:
- 5.1
-
path
default Tree.Path path()
Return theTree.Path
ofthis
tree, such thatfinal Tree<Integer, ?> tree = ...; final Tree.Path path = tree.path(); assert tree == tree.getRoot() .childAtPath(path) .orElse(null);
- Returns:
- the path from the root element to
this
node. - Since:
- 5.1
-
root
default T root()
Returns the root of the tree that contains this node. The root is the ancestor with no parent.- Returns:
- the root of the tree that contains this node
-
isChild
default boolean isChild(Tree<?,?> node)
Returntrue
if the givennode
is a child ofthis
node.- Parameters:
node
- the other node to check- Returns:
true
ifnode
is a child,false
otherwise- Throws:
NullPointerException
- if the givennode
isnull
-
firstChild
default Optional<T> firstChild()
Return the first child ofthis
node, orOptional.empty()
ifthis
node has no children.- Returns:
- the first child of this node
-
lastChild
default Optional<T> lastChild()
Return the last child ofthis
node, orOptional.empty()
ifthis
node has no children.- Returns:
- the last child of this node
-
childAfter
default Optional<T> childAfter(Tree<?,?> child)
Return the child which comes immediately afterthis
node. This method performs a linear search of this node's children forchild
and isO(n)
where n is the number of children.- Parameters:
child
- the child node- Returns:
- the child of this node that immediately follows the
child
, orOptional.empty()
if the givennode
is the first node. - Throws:
NullPointerException
- if the givenchild
isnull
-
childBefore
default Optional<T> childBefore(Tree<?,?> child)
Return the child which comes immediately beforethis
node. This method performs a linear search of this node's children forchild
and isO(n)
where n is the number of children.- Parameters:
child
- the child node- Returns:
- the child of this node that immediately precedes the
child
, ornull
if the givennode
is the first node. - Throws:
NullPointerException
- if the givenchild
isnull
-
nextNode
default Optional<T> nextNode()
Return the node that followsthis
node in a pre-order traversal ofthis
tree node. ReturnOptional.empty()
if this node is the last node of the traversal. This is an inefficient way to traverse the entire tree use an iterator instead.- Returns:
- the node that follows this node in a pre-order traversal, or
Optional.empty()
if this node is last - See Also:
preorderIterator()
-
previousNode
default Optional<T> previousNode()
Return the node that precedes this node in a pre-order traversal ofthis
tree node. ReturnsOptional.empty()
if this node is the first node of the traversal, the root of the tree. This is an inefficient way to traverse the entire tree; use an iterator instead.- Returns:
- the node that precedes this node in a pre-order traversal, or
Optional.empty()
if this node is the first - See Also:
preorderIterator()
-
isSibling
default boolean isSibling(Tree<?,?> node)
Test if the givennode
is a sibling ofthis
node.- Parameters:
node
- node to test as sibling of this node- Returns:
true
if thenode
is a sibling ofthis
node- Throws:
NullPointerException
- if the givennode
isnull
-
siblingCount
default int siblingCount()
Return the number of siblings ofthis
node. A node is its own sibling (if it has no parent or no siblings, this method returns1
).- Returns:
- the number of siblings of
this
node
-
nextSibling
default Optional<T> nextSibling()
Return the next sibling ofthis
node in the parent's children array, ornull
ifthis
node has no parent or it is the last child of the paren. This method performs a linear search that isO(n)
where n is the number of children; to traverse the entire array, use the iterator of the parent instead.- Returns:
- the sibling of
this
node that immediately followsthis
node - See Also:
childStream()
-
previousSibling
default Optional<T> previousSibling()
Return the previous sibling ofthis
node in the parent's children list, orOptional.empty()
if this node has no parent or is the parent's first child. This method performs a linear search that is O(n) where n is the number of children.- Returns:
- the sibling of
this
node that immediately precedes this node
-
isLeaf
default boolean isLeaf()
Returntrue
ifthis
node has no children.- Returns:
true
ifthis
node has no children,false
otherwise
-
firstLeaf
default T firstLeaf()
Return the first leaf that is a descendant ofthis
node; either this node or its first child's first leaf.this
node is returned if it is a leaf.- Returns:
- the first leaf in the subtree rooted at this node
- See Also:
isLeaf()
,isDescendant(io.jenetics.ext.util.Tree<?, ?>)
-
lastLeaf
default T lastLeaf()
Return the last leaf that is a descendant of this node; eitherthis
node or its last child's last leaf. Returnsthis
node if it is a leaf.- Returns:
- the last leaf in this subtree
- See Also:
isLeaf()
,isDescendant(io.jenetics.ext.util.Tree<?, ?>)
-
nextLeaf
default Optional<T> nextLeaf()
Returns the leaf afterthis
node orOptional.empty()
if this node is the last leaf in the tree.In order to determine the next node, this method first performs a linear search in the parent's child-list in order to find the current node.
That implementation makes the operation suitable for short traversals from a known position. But to traverse all of the leaves in the tree, you should use
depthFirstIterator()
to iterator the nodes in the tree and useisLeaf()
on each node to determine which are leaves.- Returns:
- return the next leaf past this node
- See Also:
depthFirstIterator()
,isLeaf()
-
previousLeaf
default Optional<T> previousLeaf()
Return the leaf beforethis
node ornull
ifthis
node is the first leaf in the tree.In order to determine the previous node, this method first performs a linear search in the parent's child-list in order to find the current node.
That implementation makes the operation suitable for short traversals from a known position. But to traverse all of the leaves in the tree, you should use
depthFirstIterator()
to iterate the nodes in the tree and useisLeaf()
on each node to determine which are leaves.- Returns:
- returns the leaf before
this
node - See Also:
depthFirstIterator()
,isLeaf()
-
leafCount
default int leafCount()
Returns the total number of leaves that are descendants of this node. If this node is a leaf, returns1
. This method isO(n)
, where n is the number of descendants ofthis
node.- Returns:
- the number of leaves beneath this node
- See Also:
isLeaf()
-
breadthFirstIterator
default Iterator<T> breadthFirstIterator()
Return an iterator that traverses the subtree rooted atthis
node in breadth-first order. The first node returned by the iterator isthis
node.Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
- Returns:
- an iterator for traversing the tree in breadth-first order
- See Also:
depthFirstIterator()
-
iterator
default Iterator<T> iterator()
Return an iterator that traverses the subtree rooted atthis
. The first node returned by the iterator isthis
node.Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
- Specified by:
iterator
in interfaceIterable<V>
- Returns:
- an iterator for traversing the tree in breadth-first order
- See Also:
breadthFirstIterator()
-
breadthFirstStream
default Stream<T> breadthFirstStream()
Return a stream that traverses the subtree rooted atthis
node in breadth-first order. The first node returned by the stream isthis
node.- Returns:
- a stream for traversing the tree in breadth-first order
- See Also:
depthFirstIterator()
,stream()
-
stream
default Stream<T> stream()
Return a stream that traverses the subtree rooted atthis
node in breadth-first order. The first node returned by the stream isthis
node.- Returns:
- a stream for traversing the tree in breadth-first order
- See Also:
breadthFirstStream()
-
preorderIterator
default Iterator<T> preorderIterator()
Return an iterator that traverses the subtree rooted atthis
node in pre-order. The first node returned by the iterator isthis
node.Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
- Returns:
- an iterator for traversing the tree in pre-order
- See Also:
postorderIterator()
-
preorderStream
default Stream<T> preorderStream()
Return a stream that traverses the subtree rooted atthis
node in pre-order. The first node returned by the stream isthis
node.Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
- Returns:
- a stream for traversing the tree in pre-order
- See Also:
preorderIterator()
-
postorderIterator
default Iterator<T> postorderIterator()
Return an iterator that traverses the subtree rooted atthis
node in post-order. The first node returned by the iterator is the leftmost leaf. This is the same as a depth-first traversal.- Returns:
- an iterator for traversing the tree in post-order
- See Also:
depthFirstIterator()
,preorderIterator()
-
postorderStream
default Stream<T> postorderStream()
Return a stream that traverses the subtree rooted atthis
node in post-order. The first node returned by the iterator is the leftmost leaf. This is the same as a depth-first traversal.- Returns:
- a stream for traversing the tree in post-order
- See Also:
depthFirstIterator()
,preorderIterator()
-
depthFirstIterator
default Iterator<T> depthFirstIterator()
Return an iterator that traverses the subtree rooted atthis
node in depth-first order. The first node returned by the iterator is the leftmost leaf. This is the same as a postorder traversal.Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
- Returns:
- an iterator for traversing the tree in depth-first order
- See Also:
breadthFirstIterator()
,postorderIterator()
-
depthFirstStream
default Stream<T> depthFirstStream()
Return a stream that traverses the subtree rooted atthis
node in depth-first. The first node returned by the iterator is the leftmost leaf. This is the same as a post-order traversal.- Returns:
- a stream for traversing the tree in post-order
- See Also:
depthFirstIterator()
,preorderIterator()
-
pathFromAncestorIterator
default Iterator<T> pathFromAncestorIterator(Tree<?,?> ancestor)
Return an iterator that follows the path fromancestor
tothis
node. The iterator returnancestor
as first element, The creation of the iterator is O(m), where m is the number of nodes betweenthis
node and theancestor
, inclusive.Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
- Parameters:
ancestor
- the ancestor node- Returns:
- an iterator for following the path from an ancestor of
this
node to this one - Throws:
IllegalArgumentException
- if theancestor
is not an ancestor of this nodeNullPointerException
- if the givenancestor
isnull
- See Also:
isAncestor(io.jenetics.ext.util.Tree<?, ?>)
,isDescendant(io.jenetics.ext.util.Tree<?, ?>)
-
childPath
default Tree.Path childPath()
Return the path ofthis
child node from the root node. You will getthis
node, if you callchildAtPath(Path)
on the root node ofthis
node.final Tree<?, ?> node = ...; final Tree<?, ?> root = node.getRoot(); final int[] path = node.childPath(); assert node == root.childAtPath(path);
- Returns:
- the path of
this
child node from the root node. - Since:
- 4.4
- See Also:
childAtPath(Path)
-
identical
default boolean identical(Tree<?,?> other)
Tests whetherthis
node is the same as theother
node. The default implementation returns the object identity,this == other
, of the two objects, but other implementations may use different criteria for checking the identity.- Parameters:
other
- theother
node- Returns:
true
if theother
node is the same asthis
node.
-
toParenthesesString
default String toParenthesesString(Function<? super V,String> mapper)
Return a compact string representation of the given tree. The treemul ├── div │ ├── cos │ │ └── 1.0 │ └── cos │ └── π └── sin └── mul ├── 1.0 └── z
is printed asmul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
- Parameters:
mapper
- themapper
which converts the tree value to a string- Returns:
- the string representation of the given tree
- Since:
- 4.3
- See Also:
toParenthesesString()
,TreeFormatter.PARENTHESES
-
toParenthesesString
default String toParenthesesString()
Return a compact string representation of the given tree. The treemul ├── div │ ├── cos │ │ └── 1.0 │ └── cos │ └── π └── sin └── mul ├── 1.0 └── z
is printed asmul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
- Returns:
- the string representation of the given tree
- Throws:
NullPointerException
- if themapper
isnull
- Since:
- 4.3
- See Also:
toParenthesesString(Function)
,TreeFormatter.PARENTHESES
-
hashCode
static int hashCode(Tree<?,?> tree)
Calculates the hash code of the given tree.- Parameters:
tree
- the tree where the hash is calculated from- Returns:
- the hash code of the tree
- Throws:
NullPointerException
- if the giventree
isnull
-
equals
static boolean equals(Tree<?,?> a, Tree<?,?> b)
Checks if the two given trees has the same structure with the same values.- Parameters:
a
- the first treeb
- the second tree- Returns:
true
if the two given trees are structurally equals,false
otherwise
-
toString
static String toString(Tree<?,?> tree)
Return a string representation of the given tree, like the following example.mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
This method is intended to be used when override theObject.toString()
method.- Parameters:
tree
- the input tree- Returns:
- the string representation of the given tree
-
-