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

    • 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 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 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 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
      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 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 given node.
      default int siblingCount()
      Return the number of siblings of this node.
      default int size()
      Return the number of nodes of this node (sub-tree).
      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.
    • Method Detail

      • 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<Tparent()
        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<TchildIterator()
        Return an iterator of the children of this Tree node.
        Returns:
        an iterator of the children of this Tree node.
      • childStream

        default Stream<TchildStream()
        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 (sub-tree).
        Returns:
        the number of nodes of this node (sub-tree)
      • childAtPath

        default Optional<TchildAtPath​(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<TchildAtPath​(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<TsharedAncestor​(Tree<?,​?> 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<TpathElements()
        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<TfirstChild()
        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<TlastChild()
        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<TchildAfter​(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<TchildBefore​(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<TnextNode()
        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<TpreviousNode()
        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<TnextSibling()
        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<TpreviousSibling()
        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
      • nextLeaf

        default Optional<TnextLeaf()
        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 of 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<TpreviousLeaf()
        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 of 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()
      • breadthFirstIterator

        default Iterator<TbreadthFirstIterator()
        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<Titerator()
        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<TbreadthFirstStream()
        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<Tstream()
        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<TpreorderIterator()
        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<TpreorderStream()
        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<TpostorderIterator()
        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<TpostorderStream()
        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<TdepthFirstIterator()
        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<TdepthFirstStream()
        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()
      • 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.
      • 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