Module io.jenetics.ext

Package io.jenetics.ext.util

Interface Tree<V,T extends Tree<V,T>>

All Superinterfaces:

Iterable<T>, Self<T>

All Known Subinterfaces:

FlatTree<V,T>, TreeGene<A,G>

All Known Implementing Classes:

AbstractTreeGene, FlatTreeNode, ProgramGene, TreeNode

public interface Tree<V,T extends Tree<V,T>>
extends Self<T>, Iterable<T>

General purpose tree structure. The interface only contains tree read methods. For a mutable tree implementation have a look at the TreeNode class.

Since:

3.9

Version:

7.0

See Also:

• TreeNode

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static final class	Tree.Path	This class represents the path to child within a given tree.

Method Summary

Modifier and Type	Method	Description
default Iterator<T>	breadthFirstIterator()	Return an iterator that traverses the subtree rooted at this node in breadth-first order.
default Stream<T>	breadthFirstStream()	Return a stream that traverses the subtree rooted at this node in breadth-first order.
default Optional<T>	childAfter(Tree<?,?> child)	Return the child which comes immediately after this 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 given path.
default Optional<T>	childAtPath(Tree.Path path)	Return the child node at the given path.
default Optional<T>	childBefore(Tree<?,?> child)	Return the child which comes immediately before this node.
int	childCount()	Return the number of children this tree node consists of.
default Iterator<T>	childIterator()	Return an iterator of the children of this Tree node.
default Tree.Path	childPath()	Return the path of this 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 at this node in depth-first order.
default Stream<T>	depthFirstStream()	Return a stream that traverses the subtree rooted at this 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 of this node, or Optional.empty() if this node has no children.
default T	firstLeaf()	Return the first leaf that is a descendant of this 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 whether this node is the same as the other node.
default int	indexOf(Tree<?,?> child)	Returns the index of the specified child in this node's child array, or -1 if this node doesn't contain the given child.
default boolean	isAncestor(Tree<?,?> node)	Return true if the given node is an ancestor of this node.
default boolean	isChild(Tree<?,?> node)	Return true if the given node is a child of this node.
default boolean	isDescendant(Tree<?,?> node)	Return true if the given node is a descendant of this node.
default boolean	isEmpty()	A tree is considered empty if it's value() is null and has no children and parent.
default boolean	isLeaf()	Return true if this node has no children.
default boolean	isRelated(Tree<?,?> node)	Returns true if and only if the given node is in the same tree as this node.
default boolean	isRoot()	Returns true if this node is the root of the tree.
default boolean	isSibling(Tree<?,?> node)	Test if the given node is a sibling of this node.
default Iterator<T>	iterator()	Return an iterator that traverses the subtree rooted at this.
default Optional<T>	lastChild()	Return the last child of this node, or Optional.empty() if this node has no children.
default T	lastLeaf()	Return the last leaf that is a descendant of this node; either this node or its last child's last leaf.
default int	leafCount()	Returns the total number of leaves that are descendants of this node.
default Stream<T>	leaves()	Return a stream 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 after this node or Optional.empty() if this node is the last leaf in the tree.
default Optional<T>	nextNode()	Return the node that follows this node in a pre-order traversal of this tree node.
default Optional<T>	nextSibling()	Return the next sibling of this node in the parent's children array, or null if this 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 the Tree.Path of this tree, such that final Tree<Integer, ?> tree = ...; final Tree.Path path = tree.path(); assert tree == tree.getRoot() .childAtPath(path) .orElse(null);
default 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 from ancestor to this node.
default Iterator<T>	postorderIterator()	Return an iterator that traverses the subtree rooted at this node in post-order.
default Stream<T>	postorderStream()	Return a stream that traverses the subtree rooted at this node in post-order.
default Iterator<T>	preorderIterator()	Return an iterator that traverses the subtree rooted at this node in pre-order.
default Stream<T>	preorderStream()	Return a stream that traverses the subtree rooted at this node in pre-order.
default Optional<T>	previousLeaf()	Return the leaf before this node or null if this node is the first leaf in the tree.
default Optional<T>	previousNode()	Return the node that precedes this node in a pre-order traversal of this tree node.
default Optional<T>	previousSibling()	Return the previous sibling of this node in the parent's children list, or Optional.empty() if this node has no parent or is the parent's first child.
default <U> U	reduce(U[] neutral, BiFunction<? super V,? super U[],? extends U> reducer)	Performs a reduction on the elements of this tree, using an associative reduction function.
default T	root()	Returns the root of the tree that contains this node.
default Optional<T>	sharedAncestor(T node)	Returns the nearest common ancestor to this node and the given node.
default int	siblingCount()	Return the number of siblings of this node.
default int	size()	Return the number of nodes of this node (subtree).
default Stream<T>	stream()	Return a stream that traverses the subtree rooted at this 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 current Tree node.

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface io.jenetics.util.Self

self

Method Details

value

V value()

Return the value of the current Tree node. The value may be null.

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 the index 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 this Tree 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()

Returns true 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 from this node to a leaf. If this node has no children, 0 is returned. This operation is much more expensive than level() because it must effectively traverse the entire tree rooted at this 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 to this node. If this 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 if this node doesn't contain the given child. This method performs a linear search and is O(n) where n 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 given child is null

size

default int size()

Return the number of nodes of this node (subtree).

Returns:

the number of nodes of this node (subtree)

isEmpty

default boolean isEmpty()

A tree is considered empty if it's value() is null and has no children and parent. A newly created tree node with no value is empty.

final Tree<String, ?> tree = TreeNode.of();
assert tree.isEmpty();

Returns:

true if this tree is empty, false otherwise

Since:

7.0

childAtPath

default Optional<T> childAtPath(Tree.Path path)

Return the child node at the given path. 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 of this node, if it exists and tree.childAtPath(Path.of(2, 0)) will return the first child of the third child of this node.

Parameters:

path - the child path

Returns:

the child node at the given path

Throws:

NullPointerException - if the given path array is null

Since:

4.4

See Also:

• childAtPath(int...)

childAtPath

default Optional<T> childAtPath(int... path)

Return the child node at the given path. 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 of this node, if it exists and tree.childAtPath(2, 0) will return the first child of the third child of this node.

Parameters:

path - the child path

Returns:

the child node at the given path

Throws:

NullPointerException - if the given path array is null

IllegalArgumentException - if one of the path elements is smaller than zero

Since:

4.3

See Also:

• childAtPath(Path)

isAncestor

default boolean isAncestor(Tree<?,?> node)

Return true if the given node is an ancestor of this node. This operation is at worst O(h) where h is the distance from the root to this node.

Parameters:

node - the node to test

Returns:

true if the given node is an ancestor of this node, false otherwise

Throws:

NullPointerException - if the given node is null

isDescendant

default boolean isDescendant(Tree<?,?> node)

Return true if the given node is a descendant of this node. If the given node is null, false is returned. This operation is at worst O(h) where h is the distance from the root to this node.

Parameters:

node - the node to test as descendant of this node

Returns:

true if this node is an ancestor of the given node

Throws:

NullPointerException - if the given node is null

sharedAncestor

default Optional<T> sharedAncestor(T node)

Returns the nearest common ancestor to this node and the given node. 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, or Optional.empty() if no common ancestor exists.

Throws:

NullPointerException - if the given node is null

isRelated

default boolean isRelated(Tree<?,?> node)

Returns true if and only if the given node is in the same tree as this node.

Parameters:

node - the other node to check

Returns:

true if the given node is in the same tree as this node, false otherwise.

Throws:

NullPointerException - if the given node is null

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 the Tree.Path of this tree, such that

final 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)

Return true if the given node is a child of this node.

Parameters:

node - the other node to check

Returns:

true if nodeis a child, false otherwise

Throws:

NullPointerException - if the given node is null

firstChild

default Optional<T> firstChild()

Return the first child of this node, or Optional.empty() if this node has no children.

Returns:

the first child of this node

lastChild

default Optional<T> lastChild()

Return the last child of this node, or Optional.empty() if this node has no children.

Returns:

the last child of this node

childAfter

default Optional<T> childAfter(Tree<?,?> child)

Return the child which comes immediately after this node. This method performs a linear search of this node's children for child and is O(n) where n is the number of children.

Parameters:

child - the child node

Returns:

the child of this node that immediately follows the child, or Optional.empty() if the given node is the first node.

Throws:

NullPointerException - if the given child is null

childBefore

default Optional<T> childBefore(Tree<?,?> child)

Return the child which comes immediately before this node. This method performs a linear search of this node's children for child and is O(n) where n is the number of children.

Parameters:

child - the child node

Returns:

the child of this node that immediately precedes the child, or null if the given node is the first node.

Throws:

NullPointerException - if the given child is null

nextNode

default Optional<T> nextNode()

Return the node that follows this node in a pre-order traversal of this tree node. Return Optional.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 of this tree node. Returns Optional.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 given node is a sibling of this node.

Parameters:

node - node to test as sibling of this node

Returns:

true if the node is a sibling of this node

Throws:

NullPointerException - if the given node is null

siblingCount

default int siblingCount()

Return the number of siblings of this node. A node is its own sibling (if it has no parent or no siblings, this method returns 1).

Returns:

the number of siblings of this node

nextSibling

default Optional<T> nextSibling()

Return the next sibling of this node in the parent's children array, or null if this node has no parent, or it is the last child of the paren. This method performs a linear search that is O(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 follows this node

See Also:

• childStream()

previousSibling

default Optional<T> previousSibling()

Return the previous sibling of this node in the parent's children list, or Optional.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()

Return true if this node has no children.

Returns:

true if this node has no children, false otherwise

firstLeaf

default T firstLeaf()

Return the first leaf that is a descendant of this 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; either this node or its last child's last leaf. Returns this 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 after this node or Optional.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 the leaves in the tree, you should use depthFirstIterator() to iterator the nodes in the tree and use isLeaf() 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 before this node or null if this 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 the leaves in the tree, you should use depthFirstIterator() to iterate the nodes in the tree and use isLeaf() 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, returns 1. This method is O(n), where n is the number of descendants of this node.

Returns:

the number of leaves beneath this node

See Also:

• isLeaf()

leaves

default Stream<T> leaves()

Return a stream of leaves that are descendants of this node.

Returns:

a stream of leaves that are descendants of this node

Since:

7.0

breadthFirstIterator

default Iterator<T> breadthFirstIterator()

Return an iterator that traverses the subtree rooted at this node in breadth-first order. The first node returned by the iterator is this 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 at this. The first node returned by the iterator is this node.

Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.

Specified by:

iterator in interface Iterable<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 at this node in breadth-first order. The first node returned by the stream is this 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 at this node in breadth-first order. The first node returned by the stream is this 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 at this node in pre-order. The first node returned by the iterator is this 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 at this node in pre-order. The first node returned by the stream is this 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 at this 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 at this 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 at this 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 at this 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 from ancestor to this node. The iterator return ancestor as a first element, The creation of the iterator is O(m), where m is the number of nodes between this node and the ancestor, 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 the ancestor is not an ancestor of this node

NullPointerException - if the given ancestor is null

See Also:

• isAncestor(io.jenetics.ext.util.Tree<?, ?>)
• isDescendant(io.jenetics.ext.util.Tree<?, ?>)

childPath

default Tree.Path childPath()

Return the path of this child node from the root node. You will get this node, if you call childAtPath(Path) on the root node of this 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 whether this node is the same as the other 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 - the other node

Returns:

true if the other node is the same as this node.

reduce

default <U> U reduce(U[] neutral,
 BiFunction<? super V,? super U[],? extends U> reducer)

Performs a reduction on the elements of this tree, using an associative reduction function. This can be used for evaluating a given expression tree in pre-order.

final Tree<String, ?> formula = TreeNode.parse("add(sub(6,div(230,10)),mul(5,6))");
final double result = formula.reduce(new Double[0], (op, args) ->
    switch (op) {
        case "add" -> args[0] + args[1];
        case "sub" -> args[0] - args[1];
        case "mul" -> args[0] * args[1];
        case "div" -> args[0] / args[1];
        default -> Double.parseDouble(op);
    }
);
assert result == 13.0;

Type Parameters:

U - the result type

Parameters:

neutral - the neutral element of the reduction. In most cases this will be new U[0].

reducer - the reduce function

Returns:

the result of the reduction, or null if this tree is empty (isEmpty() == true)

Since:

7.1

toParenthesesString

default String toParenthesesString(Function<? super V,String> mapper)

Return a compact string representation of the given tree. The tree

  mul
  ├── div
  │   ├── cos
  │   │   └── 1.0
  │   └── cos
  │       └── π
  └── sin
      └── mul
          ├── 1.0
          └── z
  

is printed as

  mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
 

Parameters:

mapper - the mapper 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 tree

  mul
  ├── div
  │   ├── cos
  │   │   └── 1.0
  │   └── cos
  │       └── π
  └── sin
      └── mul
          ├── 1.0
          └── z
  

is printed as

  mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
 

Returns:

the string representation of the given tree

Throws:

NullPointerException - if the mapper is null

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 given tree is null

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 tree

b - 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 the Object.toString() method.

Parameters:

tree - the input tree

Returns:

the string representation of the given tree