Package uk.blankaspect.common.tree

Class TreeUtils

java.lang.Object
uk.blankaspect.common.tree.TreeUtils
public class TreeUtils extends Object
This class contains utility methods that relate to trees whose nodes implement the ITreeNode interface.

Calls to methods of this class are forwarded to corresponding methods of the TreeTraversal class along with functions that map a node to its parent or to a list of its children, as required.

  • Method Summary

    Modifier and Type
    Method
    Description
    static <T extends ITreeNode<T>, U>
    T
    findNode(T root, Iterable<U> path, BiPredicate<T,U> matcher)
    Searches a tree of ITreeNodes, starting from the specified node, for a node whose path from the root matches the specified path descriptor.
    static <T extends ITreeNode<T>>
    int
    getDepth(T node)
    Returns the depth of the specified node (ie, the number of levels below the root node of the tree to which the specified node belongs).
    static <T extends ITreeNode<T>>
    int
    getDepth(T root, T node)
    Returns the number of levels of the specified node below the specified root node.
    static <T extends ITreeNode<T>>
    List<Integer>
    getIndices(T node, int baseIndex)
    Returns a list of indices to the specified node from the root of the tree to which it belongs.
    static <T extends ITreeNode<T>>
    List<Integer>
    getIndices(T root, T node, boolean includeRoot, int baseIndex)
    Returns a list of indices of the path from the specified root node to the specified node, which is assumed to be a descendant of the specified root.
    static <T extends ITreeNode<T>>
    List<T>
    getPath(T node)
    Returns the path to the specified node from the root of the tree to which it belongs.
    static <T extends ITreeNode<T>>
    List<T>
    getPath(T root, T node)
    Returns the path from the specified root node to the specified node, which is assumed to be a descendant of the specified root.
    static <T extends ITreeNode<T>>
    T
    getRoot(T node)
    Returns the root node of the tree to which the specified node belongs.
    static <T extends ITreeNode<T>>
    List<T>
    getSiblings(T node)
    Returns a list of the siblings of the specified node.
    static <T extends ITreeNode<T>>
    boolean
    isAncestor(T node, T target)
    Returns true if the specified node is an ancestor of the specified target node.
    static <T extends ITreeNode<T>>
    boolean
    isAncestor(T node, T target, boolean testForIdentity)
    Returns true if the specified node is an ancestor of the specified target node or, optionally, if the node is identical to the target.
    static <T extends ITreeNode<T>>
    T
    searchAscending(T startNode, Predicate<T> test)
    Ascends a tree of ITreeNodes from the specified start node to the root node, applying the specified test to each node that is visited until a node is found that satisfies the test.
    static <T extends ITreeNode<T>>
    T
    searchAscending(T startNode, T endNode, boolean includeEnd, Predicate<T> test)
    Ascends a tree of ITreeNodes from the specified start node to the specified end node, applying the specified test to each node that is visited until a node is found that satisfies the test.
    static <T extends ITreeNode<T>>
    T
    searchBreadthFirst(T root, boolean includeRoot, Predicate<T> test)
    Performs a breadth-first search of a tree of ITreeNodes, starting from the specified root node and applying the specified test to each node that is visited until a node is found that satisfies the test.
    static <T extends ITreeNode<T>>
    T
    searchDepthFirst(T root, boolean preorder, boolean includeRoot, Predicate<T> test)
    Performs a depth-first search of a tree of ITreeNodes, starting from the specified root node and applying the specified test to each node that is visited until a node is found that satisfies the test.
    static <T extends ITreeNode<T>>
    boolean
    testAscending(T startNode, Predicate<T> test)
    Returns true if and only if the specified ITreeNode or one of its ancestors satisfies the specified test.
    static <T extends ITreeNode<T>>
    String
    treeToString(T root, int indentIncrement, Function<T,String> converter)
    Returns a string representation of the tree of ITreeNodes whose root is the specified node.
    static <T extends ITreeNode<T>>
    boolean
    visitAscending(T startNode, Function<T,Boolean> action)
    Ascends a tree of ITreeNodes from the specified node to the root node, applying the specified action to each node that is visited, including the root.
    static <T extends ITreeNode<T>>
    boolean
    visitAscending(T startNode, T endNode, boolean includeEnd, Function<T,Boolean> action)
    Ascends a tree of ITreeNodes from the specified node to the specified end node, applying the specified action to each node that is visited.
    static <T extends ITreeNode<T>>
    boolean
    visitBreadthFirst(T root, boolean includeRoot, Function<T,Boolean> action)
    Performs a breadth-first traversal of a tree of ITreeNodes, starting from the specified root node and applying the specified action to each node that is visited.
    static <T extends ITreeNode<T>>
    boolean
    visitDepthFirst(T root, boolean preorder, boolean includeRoot, Function<T,Boolean> action)
    Performs a depth-first traversal of a tree of ITreeNodes, starting from the specified root node and applying the specified action to each node that is visited.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • getRoot

      public static <T extends ITreeNode<T>> T getRoot(T node)
      Returns the root node of the tree to which the specified node belongs. The root node is assumed to be the first ancestor of the specified node whose parent is null.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      node - the node whose root ancestor is desired.
      Returns:
      the root node of the tree to which node belongs.

    • getSiblings

      public static <T extends ITreeNode<T>> List<T> getSiblings(T node)
      Returns a list of the siblings of the specified node.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      node - the node whose siblings are desired.
      Returns:
      a list of the siblings of node.

    • isAncestor

      public static <T extends ITreeNode<T>> boolean isAncestor(T node, T target)
      Returns true if the specified node is an ancestor of the specified target node.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      node - the node that is a potential ancestor of target.
      target - the node that is a potential descendant of node.
      Returns:
      true if node is an ancestor of target.

    • isAncestor

      public static <T extends ITreeNode<T>> boolean isAncestor(T node, T target, boolean testForIdentity)
      Returns true if the specified node is an ancestor of the specified target node or, optionally, if the node is identical to the target.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      node - the node that is a potential ancestor of target or (if testForIdentity is true) is potentially identical to target.
      target - the node that is a potential descendant of node or (if testForIdentity is true) is potentially identical to node.
      testForIdentity - if true, node and target will be tested for identity as well as for an ancestor–descendant relationship.
      Returns:
      true if
      • node is the ancestor of target, or
      • testForIdentity is true and node is identical to target.

    • getDepth

      public static <T extends ITreeNode<T>> int getDepth(T node)
      Returns the depth of the specified node (ie, the number of levels below the root node of the tree to which the specified node belongs).
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      node - the node whose depth is desired.
      Returns:
      the depth of node.
      See Also:

    • getDepth

      public static <T extends ITreeNode<T>> int getDepth(T root, T node)
      Returns the number of levels of the specified node below the specified root node.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      root - the root of the tree node whose depth is desired.
      node - the node whose depth below root is desired.
      Returns:
      the depth of node below root, or -1 if root is not an ancestor of node.
      See Also:

    • getPath

      public static <T extends ITreeNode<T>> List<T> getPath(T node)
      Returns the path to the specified node from the root of the tree to which it belongs. The path is a list of nodes that includes the root and the target node.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      node - the node whose path is desired.
      Returns:
      a list of nodes that denotes the path to node from the root of the tree to which it belongs.
      See Also:

    • getPath

      public static <T extends ITreeNode<T>> List<T> getPath(T root, T node)
      Returns the path from the specified root node to the specified node, which is assumed to be a descendant of the specified root. The path is a list of nodes that includes the root and the target node.

      If the specified root node is not an ancestor of the target node, the path will be a list of nodes from the root of the tree to which the target node belongs, which will be the first element of the list.

      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      root - the node at which the path will start, unless it is not an ancestor of node.
      node - the node whose path is desired.
      Returns:
      a list of nodes that denotes the path from root to node, or, if root is not an ancestor of node, the path to node from the root of the tree to which it belongs.
      See Also:

    • getIndices

      public static <T extends ITreeNode<T>> List<Integer> getIndices(T node, int baseIndex)
      Returns a list of indices to the specified node from the root of the tree to which it belongs. Each element of the list is the sum of the specified base index and the index of the corresponding node in its parent's list of children, or -1 if the node is not a child of its parent. The first element of the list is a child of the root node. The list is empty if the target node is a root node.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      node - the node whose indices are desired.
      baseIndex - the base index that is added to each valid index in the list of indices.
      Returns:
      a list of nodes that denotes the path to node from the root of the tree to which it belongs.
      See Also:

    • getIndices

      public static <T extends ITreeNode<T>> List<Integer> getIndices(T root, T node, boolean includeRoot, int baseIndex)
      Returns a list of indices of the path from the specified root node to the specified node, which is assumed to be a descendant of the specified root. Each element of the list is the sum of the specified base index and the index of the corresponding node in its parent's list of children, or -1 if the node has no parent or is not a child of its parent. The list of indices may optionally include the index of the root node.

      If the specified root node is not an ancestor of the target node, the list of indices will start at

      • the root of the tree to which the target node belongs, if includeRoot is true, or
      • the ancestor of the target node that is a child of the root of the tree to which the target node belongs, if includeRoot is false.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      root - the node at which the indices will start, unless it is not an ancestor of node.
      node - the node whose indices are desired.
      includeRoot - the index of root will be included in the list of indices.
      baseIndex - the base index that is added to each valid index in the list of indices.
      Returns:
      a list of nodes that denotes the path from root to node.
      See Also:

    • findNode

      public static <T extends ITreeNode<T>, U> T findNode(T root, Iterable<U> path, BiPredicate<T,U> matcher)
      Searches a tree of ITreeNodes, starting from the specified node, for a node whose path from the root matches the specified path descriptor. The first element of the path descriptor is tested against the root node with the specified matcher: if there is no match, the search terminates immediately; otherwise, the root node becomes the current node, and the search proceeds by descending the tree, testing successive elements against the children of the current node until either no children match or the last element of the path descriptor is matched.
      Type Parameters:
      T - the type of the nodes of the tree.
      U - the type of the elements of the path.
      Parameters:
      root - the node at which the search will start.
      path - a path descriptor whose elements are tested sequentially against root and its descendants with matcher.
      matcher - the matcher that tests a node against an element of path.
      Returns:
      the node that matches path, or null if no matching node is found.

    • visitDepthFirst

      public static <T extends ITreeNode<T>> boolean visitDepthFirst(T root, boolean preorder, boolean includeRoot, Function<T,Boolean> action)
      Performs a depth-first traversal of a tree of ITreeNodes, starting from the specified root node and applying the specified action to each node that is visited. The root node may optionally be visited.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      root - the node at the root of a tree of ITreeNodes, each of which will have action applied to it.
      preorder - if true, each node will be visited before its descendants; otherwise, each node will be visited after its descendants.
      includeRoot - if true, root will have action applied to it.
      action - the action that will be applied to each node of the tree that is visited. If the action returns false, the traversal of the tree will be terminated.
      Returns:
      false if the traversal of the tree was terminated by action, possibly before all nodes were visited; true otherwise.

    • visitBreadthFirst

      public static <T extends ITreeNode<T>> boolean visitBreadthFirst(T root, boolean includeRoot, Function<T,Boolean> action)
      Performs a breadth-first traversal of a tree of ITreeNodes, starting from the specified root node and applying the specified action to each node that is visited. The root node may optionally be visited.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      root - the node at the root of a tree of ITreeNodes, each of which will have action applied to it.
      includeRoot - if true, root will have action applied to it.
      action - the action that will be applied to each node of the tree that is visited. If the action returns false, the traversal of the tree will be terminated.
      Returns:
      false if the traversal of the tree was terminated by action, possibly before all nodes were visited; true otherwise.

    • visitAscending

      public static <T extends ITreeNode<T>> boolean visitAscending(T startNode, Function<T,Boolean> action)
      Ascends a tree of ITreeNodes from the specified node to the root node, applying the specified action to each node that is visited, including the root.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      startNode - the node from which the ascent will start.
      action - the action that will be applied to each node of the tree that is visited. If the action returns false, the ascent of the tree will be terminated.
      Returns:
      false if the ascent of the tree was terminated by action, possibly before all nodes were visited; true otherwise.

    • visitAscending

      public static <T extends ITreeNode<T>> boolean visitAscending(T startNode, T endNode, boolean includeEnd, Function<T,Boolean> action)
      Ascends a tree of ITreeNodes from the specified node to the specified end node, applying the specified action to each node that is visited. The end node may optionally be visited.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      startNode - the node from which the ascent will start.
      endNode - the node at which the ascent will end. endNode is visited if includeEnd is true. If endNode is null, startNode and all its ancestors will be visited.
      includeEnd - if true, endNode will have action applied to it.
      action - the action that will be applied to each node of the tree that is visited. If the action returns false, the ascent of the tree will be terminated.
      Returns:
      false if the ascent of the tree was terminated by action, possibly before all nodes were visited; true otherwise.

    • testAscending

      public static <T extends ITreeNode<T>> boolean testAscending(T startNode, Predicate<T> test)
      Returns true if and only if the specified ITreeNode or one of its ancestors satisfies the specified test.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      startNode - the node from which the ascent will start.
      test - the test that will be applied to startNode and its ancestors.
      Returns:
      true if and only if startNode or one of its ancestors satisfies test.

    • searchDepthFirst

      public static <T extends ITreeNode<T>> T searchDepthFirst(T root, boolean preorder, boolean includeRoot, Predicate<T> test)
      Performs a depth-first search of a tree of ITreeNodes, starting from the specified root node and applying the specified test to each node that is visited until a node is found that satisfies the test. If such a node is found, the search terminates immediately and the matching node is returned. The root node may optionally be included in the search.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      root - the node at which the search will start.
      preorder - if true, each node will be visited before its descendants; otherwise, each node will be visited after its descendants.
      includeRoot - if true, root will be included in the search.
      test - the test that will be applied to each node of the tree that is visited until the test succeeds.
      Returns:
      the first node that returns true when test is applied to it, or null if no node satisfies the test.

    • searchBreadthFirst

      public static <T extends ITreeNode<T>> T searchBreadthFirst(T root, boolean includeRoot, Predicate<T> test)
      Performs a breadth-first search of a tree of ITreeNodes, starting from the specified root node and applying the specified test to each node that is visited until a node is found that satisfies the test. If such a node is found, the search terminates immediately and the matching node is returned. The root node may optionally be included in the search.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      root - the node at which the search will start.
      includeRoot - if true, root will be included in the search.
      test - the test that will be applied to each node of the tree that is visited until the test succeeds.
      Returns:
      the first node that returns true when test is applied to it, or null if no node satisfies the test.

    • searchAscending

      public static <T extends ITreeNode<T>> T searchAscending(T startNode, Predicate<T> test)
      Ascends a tree of ITreeNodes from the specified start node to the root node, applying the specified test to each node that is visited until a node is found that satisfies the test. If such a node is found, the search terminates immediately and the matching node is returned. The root is included in the search.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      startNode - the node from which the search will start.
      test - the test that will be applied to each node of the tree that is visited until the test succeeds.
      Returns:
      the first node that returns true when test is applied to it, or null if no node satisfies the test.

    • searchAscending

      public static <T extends ITreeNode<T>> T searchAscending(T startNode, T endNode, boolean includeEnd, Predicate<T> test)
      Ascends a tree of ITreeNodes from the specified start node to the specified end node, applying the specified test to each node that is visited until a node is found that satisfies the test. If such a node is found, the search terminates immediately and the matching node is returned. The end node may optionally be included in the search.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      startNode - the node from which the search will start.
      endNode - the node at which the search will end. endNode is included in the search if includeEnd is true. If endNode is null, startNode and all its ancestors will be included in the search.
      includeEnd - if true, endNode will have test applied to it.
      test - the test that will be applied to each node of the tree that is visited until the test succeeds.
      Returns:
      the first node that returns true when test is applied to it, or null if no node satisfies the test.

    • treeToString

      public static <T extends ITreeNode<T>> String treeToString(T root, int indentIncrement, Function<T,String> converter)
      Returns a string representation of the tree of ITreeNodes whose root is the specified node.
      Type Parameters:
      T - the type of the nodes of the tree.
      Parameters:
      root - the node at the root of the tree.
      indentIncrement - the number of spaces by which the indent of a line of text will be incremented for each level of the tree below root.
      converter - the function that will convert each node to its string representation.
      Returns:
      a string representation of the tree whose root is root.