Class PathFinder

java.lang.Object
cloud.opencode.base.tree.path.PathFinder
public final class PathFinder extends Object
Path Finder 路径查找器

Finds paths in tree structures.

在树结构中查找路径。

Features | 主要功能:

  • Find path to node by ID or predicate - 通过ID或谓词查找节点路径
  • Find all paths to matching nodes - 查找到所有匹配节点的路径
  • Find paths to leaf nodes - 查找到叶子节点的路径
  • Get ancestor IDs and node depth - 获取祖先ID和节点深度
  • Find lowest common ancestor of two nodes - 查找两个节点的最近公共祖先

Usage Examples | 使用示例:

Optional<TreePath<MyNode>> path = PathFinder.findPathById(roots, targetId);
List<ID> ancestors = PathFinder.getAncestorIds(roots, targetId);
int depth = PathFinder.getDepth(roots, targetId);
Optional<MyNode> lca = PathFinder.findLowestCommonAncestor(roots, id1, id2);

Security | 安全性:

  • Thread-safe: No - 否
  • Null-safe: No (roots and targetId must not be null) - 否（根节点和目标ID不能为null）
Since:
JDK 25, opencode-base-tree V1.0.0
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Method Details

    • findPathById

      public static <T extends Treeable<T,ID>, ID> Optional<TreePath<T>> findPathById(List<T> roots, ID targetId)
      Find path to node by ID 通过ID查找到节点的路径
      Type Parameters:
      T - the node type | 节点类型
      ID - the ID type | ID类型
      Parameters:
      roots - the root nodes | 根节点列表
      targetId - the target ID | 目标ID
      Returns:
      the path if found | 如果找到返回路径

    • findPath

      public static <T extends Treeable<T,ID>, ID> Optional<TreePath<T>> findPath(List<T> roots, Predicate<T> predicate)
      Find path to node matching predicate 查找到匹配谓词的节点的路径
      Type Parameters:
      T - the node type | 节点类型
      ID - the ID type | ID类型
      Parameters:
      roots - the root nodes | 根节点列表
      predicate - the target predicate | 目标谓词
      Returns:
      the path if found | 如果找到返回路径

    • findAllPaths

      public static <T extends Treeable<T,ID>, ID> List<TreePath<T>> findAllPaths(List<T> roots, Predicate<T> predicate)
      Find all paths to matching nodes 查找到所有匹配节点的路径
      Type Parameters:
      T - the node type | 节点类型
      ID - the ID type | ID类型
      Parameters:
      roots - the root nodes | 根节点列表
      predicate - the target predicate | 目标谓词
      Returns:
      the paths | 路径列表

    • findAllLeafPaths

      public static <T extends Treeable<T,ID>, ID> List<TreePath<T>> findAllLeafPaths(List<T> roots)
      Find paths to all leaf nodes 查找到所有叶子节点的路径
      Type Parameters:
      T - the node type | 节点类型
      ID - the ID type | ID类型
      Parameters:
      roots - the root nodes | 根节点列表
      Returns:
      the paths to leaves | 到叶子节点的路径

    • getAncestorIds

      public static <T extends Treeable<T,ID>, ID> List<ID> getAncestorIds(List<T> roots, ID targetId)
      Get ancestor IDs for a node 获取节点的祖先ID列表
      Type Parameters:
      T - the node type | 节点类型
      ID - the ID type | ID类型
      Parameters:
      roots - the root nodes | 根节点列表
      targetId - the target ID | 目标ID
      Returns:
      the ancestor IDs | 祖先ID列表

    • getDepth

      public static <T extends Treeable<T,ID>, ID> int getDepth(List<T> roots, ID targetId)
      Get depth of node 获取节点深度
      Type Parameters:
      T - the node type | 节点类型
      ID - the ID type | ID类型
      Parameters:
      roots - the root nodes | 根节点列表
      targetId - the target ID | 目标ID
      Returns:
      the depth (-1 if not found) | 深度（未找到返回-1）

    • findLowestCommonAncestor

      public static <T extends Treeable<T,ID>, ID> Optional<T> findLowestCommonAncestor(List<T> roots, ID id1, ID id2)
      Find lowest common ancestor of two nodes by ID 通过ID查找两个节点的最近公共祖先

      Finds the deepest node that is an ancestor of both target nodes. The algorithm finds paths to both nodes, then walks the paths in parallel to find the last common node.

      查找同时是两个目标节点祖先的最深节点。 算法先分别查找到两个节点的路径，然后并行遍历路径以找到最后一个公共节点。

      Performance | 性能特性:

      • Time complexity: O(n) where n is total node count - 时间复杂度: O(n)，n 为总节点数
      • Space complexity: O(h) where h is tree height - 空间复杂度: O(h)，h 为树高
      Type Parameters:
      T - the node type | 节点类型
      ID - the ID type | ID类型
      Parameters:
      roots - the root nodes | 根节点列表
      id1 - the first node ID | 第一个节点ID
      id2 - the second node ID | 第二个节点ID
      Returns:
      the lowest common ancestor if both nodes exist | 如果两个节点都存在返回最近公共祖先
      Since:
      V1.0.3

    • findLowestCommonAncestor

      public static <T extends Treeable<T,ID>, ID> Optional<T> findLowestCommonAncestor(List<T> roots, Predicate<T> predicate1, Predicate<T> predicate2)
      Find lowest common ancestor of two nodes by predicates 通过谓词查找两个节点的最近公共祖先

      Finds the deepest node that is an ancestor of both target nodes. The algorithm finds paths to both nodes, then walks the paths in parallel to find the last common node.

      查找同时是两个目标节点祖先的最深节点。 算法先分别查找到两个节点的路径，然后并行遍历路径以找到最后一个公共节点。

      Performance | 性能特性:

      • Time complexity: O(n) where n is total node count - 时间复杂度: O(n)，n 为总节点数
      • Space complexity: O(h) where h is tree height - 空间复杂度: O(h)，h 为树高
      Type Parameters:
      T - the node type | 节点类型
      ID - the ID type | ID类型
      Parameters:
      roots - the root nodes | 根节点列表
      predicate1 - the predicate for first node | 第一个节点的谓词
      predicate2 - the predicate for second node | 第二个节点的谓词
      Returns:
      the lowest common ancestor if both nodes exist | 如果两个节点都存在返回最近公共祖先
      Since:
      V1.0.3