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:
  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Interface
    Description
    static final class 
    This class represents the path to child within a given tree.
  • Method Summary

    Modifier and Type
    Method
    Description
    default Iterator<T>
    Return an iterator that traverses the subtree rooted at this node in breadth-first order.
    default Stream<T>
    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.
    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>
    Return the child node at the given path.
    default Optional<T>
    childBefore(Tree<?,?> child)
    Return the child which comes immediately before this node.
    int
    Return the number of children this tree node consists of.
    default Iterator<T>
    Return an iterator of the children of this Tree node.
    default Tree.Path
    Return the path of this child node from the root node.
    default Stream<T>
    Return a forward-order stream of this node's children.
    default int
    Returns the depth of the tree rooted at this node.
    default Iterator<T>
    Return an iterator that traverses the subtree rooted at this node in depth-first order.
    default Stream<T>
    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>
    Return the first child of this node, or Optional.empty() if this node has no children.
    default T
    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
    A tree is considered empty if it's value() is null and has no children and parent.
    default boolean
    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
    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>
    Return an iterator that traverses the subtree rooted at this.
    default Optional<T>
    Return the last child of this node, or Optional.empty() if this node has no children.
    default T
    Return the last leaf that is a descendant of this node; either this node or its last child's last leaf.
    default int
    Returns the total number of leaves that are descendants of this node.
    default Stream<T>
    Return a stream of leaves that are descendants of this node.
    default int
    Returns the number of levels above this node.
    default Optional<T>
    Returns the leaf after this node or Optional.empty() if this node is the last leaf in the tree.
    default Optional<T>
    Return the node that follows this node in a pre-order traversal of this tree node.
    default Optional<T>
    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.
    Return the parent node of this tree node.
    default Tree.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>
    Returns the path from the root, to get to this node.
    default Iterator<T>
    Return an iterator that follows the path from ancestor to this node.
    default Iterator<T>
    Return an iterator that traverses the subtree rooted at this node in post-order.
    default Stream<T>
    Return a stream that traverses the subtree rooted at this node in post-order.
    default Iterator<T>
    Return an iterator that traverses the subtree rooted at this node in pre-order.
    default Stream<T>
    Return a stream that traverses the subtree rooted at this node in pre-order.
    default Optional<T>
    Return the leaf before this node or null if this node is the first leaf in the tree.
    default Optional<T>
    Return the node that precedes this node in a pre-order traversal of this tree node.
    default Optional<T>
    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
    Returns the root of the tree that contains this node.
    default Optional<T>
    Returns the nearest common ancestor to this node and the given node.
    default int
    Return the number of siblings of this node.
    default int
    Return the number of nodes of this node (subtree).
    default Stream<T>
    Return a stream that traverses the subtree rooted at this node in breadth-first order.
    default String
    Return a compact string representation of the given tree.
    default String
    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.
    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

      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

      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:
    • 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:
    • 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:
    • 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:
    • 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:
    • 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:
    • 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:
    • 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:
    • 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:
    • 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

      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:
    • 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:
    • 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:
    • 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:
    • 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:
    • 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:
    • 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:
    • 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

      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:
    • 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:
    • 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:
    • 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:
    • 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

      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:
    • 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