Package uk.blankaspect.common.treetraversal

Class TreeTraversal

java.lang.Object
uk.blankaspect.common.treetraversal.TreeTraversal
public class TreeTraversal extends Object
This class contains utility methods that relate to the traversal of a tree.

  • Method Summary

    Modifier and Type
    Method
    Description
    static <T, U> T
    findNode(T root, Function<T,List<T>> childListMapper, Iterable<U> path, BiPredicate<T,U> matcher)
    Searches a tree, starting from the specified node, for a node whose path from the root matches the specified path descriptor.
    static <T> int
    getDepth(T node, Function<T,T> parentMapper)
    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> int
    getDepth(T root, T node, Function<T,T> parentMapper)
    Returns the number of levels of the specified node below the specified root node.
    static <T> List<Integer>
    getIndices(T node, int baseIndex, Function<T,T> parentMapper, Function<T,List<T>> childListMapper)
    Returns a list of indices to the specified node from the root of the tree to which it belongs.
    static <T> List<Integer>
    getIndices(T root, T node, boolean includeRoot, int baseIndex, Function<T,T> parentMapper, Function<T,List<T>> childListMapper)
    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> List<T>
    getPath(T node, Function<T,T> parentMapper)
    Returns the path to the specified node from the root of the tree to which it belongs.
    static <T> List<T>
    getPath(T root, T node, Function<T,T> parentMapper)
    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> T
    getRoot(T node, Function<T,T> parentMapper)
    Returns the root node of the tree to which the specified node belongs.
    static <T> List<T>
    getSiblings(T node, Function<T,T> parentMapper, Function<T,List<T>> childListMapper)
    Returns a list of the siblings of the specified node.
    static <T> boolean
    isAncestor(T node, T target, boolean testForIdentity, Function<T,T> parentMapper)
    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> boolean
    isAncestor(T node, T target, Function<T,T> parentMapper)
    Returns true if the specified node is an ancestor of the specified target node.
    static <T> T
    searchAscending(T startNode, Function<T,T> parentMapper, Predicate<T> test)
    Ascends a tree 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> T
    searchAscending(T startNode, T endNode, boolean includeEnd, Function<T,T> parentMapper, Predicate<T> test)
    Ascends a tree 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> T
    searchBreadthFirst(T root, boolean includeRoot, Function<T,List<T>> childListMapper, Predicate<T> test)
    Performs a breadth-first search of a tree, 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> T
    searchDepthFirst(T root, boolean preorder, boolean includeRoot, Function<T,List<T>> childListMapper, Predicate<T> test)
    Performs a depth-first search of a tree, 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> String
    treeToString(T root, int indentIncrement, Function<T,T> parentMapper, Function<T,List<T>> childListMapper, Function<T,String> converter)
    Returns a string representation of the tree whose root is the specified node.
    static <T> boolean
    visitAscending(T startNode, Function<T,T> parentMapper, Function<T,Boolean> action)
    Ascends a tree from the specified node to the root node, applying the specified action to each node that is visited, including the root.
    static <T> boolean
    visitAscending(T startNode, T endNode, boolean includeEnd, Function<T,T> parentMapper, Function<T,Boolean> action)
    Ascends a tree from the specified node to the specified end node, applying the specified action to each node that is visited.
    static <T> boolean
    visitBreadthFirst(T root, boolean includeRoot, Function<T,List<T>> childListMapper, Function<T,Boolean> action)
    Performs a breadth-first traversal of a tree, starting from the specified root node and applying the specified action to each node that is visited.
    static <T> boolean
    visitDepthFirst(T root, boolean preorder, boolean includeRoot, Function<T,List<T>> childListMapper, Function<T,Boolean> action)
    Performs a depth-first traversal of a tree, 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> T getRoot(T node, Function<T,T> parentMapper)
      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.
      parentMapper - the function that returns the parent of a given node.
      Returns:
      the root node of the tree to which node belongs.

    • getSiblings

      public static <T> List<T> getSiblings(T node, Function<T,T> parentMapper, Function<T,List<T>> childListMapper)
      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.
      parentMapper - the function that returns the parent of a given node.
      childListMapper - the function that returns a list of the children of a given node.
      Returns:
      a list of the siblings of node.

    • isAncestor

      public static <T> boolean isAncestor(T node, T target, Function<T,T> parentMapper)
      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.
      parentMapper - the function that returns the parent of a given node.
      Returns:
      true if node is an ancestor of target.

    • isAncestor

      public static <T> boolean isAncestor(T node, T target, boolean testForIdentity, Function<T,T> parentMapper)
      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.
      parentMapper - the function that returns the parent of a given node.
      Returns:
      true if
      • node is the ancestor of target, or
      • testForIdentity is true and node is identical to target.

    • getDepth

      public static <T> int getDepth(T node, Function<T,T> parentMapper)
      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.
      parentMapper - the function that returns the parent of a given node.
      Returns:
      the depth of node.
      See Also:

    • getDepth

      public static <T> int getDepth(T root, T node, Function<T,T> parentMapper)
      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.
      parentMapper - the function that returns the parent of a given node.
      Returns:
      the depth of node below root, or -1 if root is not an ancestor of node.
      See Also:

    • getPath

      public static <T> List<T> getPath(T node, Function<T,T> parentMapper)
      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.
      parentMapper - the function that returns the parent of a given node.
      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> List<T> getPath(T root, T node, Function<T,T> parentMapper)
      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.
      parentMapper - the function that returns the parent of a given node.
      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> List<Integer> getIndices(T node, int baseIndex, Function<T,T> parentMapper, Function<T,List<T>> childListMapper)
      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.
      parentMapper - the function that returns the parent of a given node.
      childListMapper - the function that returns a list of the children of a given node.
      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> List<Integer> getIndices(T root, T node, boolean includeRoot, int baseIndex, Function<T,T> parentMapper, Function<T,List<T>> childListMapper)
      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.
      parentMapper - the function that returns the parent of a given node.
      childListMapper - the function that returns a list of the children of a given node.
      Returns:
      a list of nodes that denotes the path from root to node.
      See Also:

    • findNode

      public static <T, U> T findNode(T root, Function<T,List<T>> childListMapper, Iterable<U> path, BiPredicate<T,U> matcher)
      Searches a tree, 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.
      childListMapper - the function that returns a list of the children of a given node.
      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> boolean visitDepthFirst(T root, boolean preorder, boolean includeRoot, Function<T,List<T>> childListMapper, Function<T,Boolean> action)
      Performs a depth-first traversal of a tree, 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, each of whose nodes 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.
      childListMapper - the function that returns a list of the children of a given node.
      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> boolean visitBreadthFirst(T root, boolean includeRoot, Function<T,List<T>> childListMapper, Function<T,Boolean> action)
      Performs a breadth-first traversal of a tree, 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, each of whose nodes will have action applied to it.
      includeRoot - if true, root will have action applied to it.
      childListMapper - the function that returns a list of the children of a given node.
      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> boolean visitAscending(T startNode, Function<T,T> parentMapper, Function<T,Boolean> action)
      Ascends a tree 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.
      parentMapper - the function that returns the parent of a given node.
      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> boolean visitAscending(T startNode, T endNode, boolean includeEnd, Function<T,T> parentMapper, Function<T,Boolean> action)
      Ascends a tree 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.
      parentMapper - the function that returns the parent of a given node.
      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.

    • searchDepthFirst

      public static <T> T searchDepthFirst(T root, boolean preorder, boolean includeRoot, Function<T,List<T>> childListMapper, Predicate<T> test)
      Performs a depth-first search of a tree, 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.
      childListMapper - the function that returns a list of the children of a given node.
      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> T searchBreadthFirst(T root, boolean includeRoot, Function<T,List<T>> childListMapper, Predicate<T> test)
      Performs a breadth-first search of a tree, 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.
      childListMapper - the function that returns a list of the children of a given node.
      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> T searchAscending(T startNode, Function<T,T> parentMapper, Predicate<T> test)
      Ascends a tree 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.
      parentMapper - the function that returns the parent of a given node.
      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> T searchAscending(T startNode, T endNode, boolean includeEnd, Function<T,T> parentMapper, Predicate<T> test)
      Ascends a tree 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.
      parentMapper - the function that returns the parent of a given node.
      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> String treeToString(T root, int indentIncrement, Function<T,T> parentMapper, Function<T,List<T>> childListMapper, Function<T,String> converter)
      Returns a string representation of the tree 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.
      parentMapper - the function that returns the parent of a given node.
      childListMapper - the function that returns a list of the children of a given node.
      converter - the function that will convert each node to its string representation.
      Returns:
      a string representation of the tree whose root is root.