幅優先探索の実装

[shimodateakira]

WalkPathTreeのBFS版を作る。
基本的にはスタック方式だがシンボリックリンクを処理する場合だけ再帰とする。

[shimodateakira]

とりあえずAIにBFS版を作ってもらった。
これをベースとしてみる。

        /// <summary>
        /// Traverses the path tree starting from the specified path in breadth-first order.
        /// </summary>
        /// <param name="basePath">The base virtual path</param>
        /// <param name="filter">The filter to apply for node types</param>
        /// <param name="recursive">A flag indicating whether to traverse recursively</param>
        /// <param name="followLinks">A flag indicating whether to follow symbolic links</param>
        /// <param name="resolveLinks">A flag indicating whether to resolve symbolic links</param>
        /// <returns>
        /// An enumerable of <see cref="VirtualNodeContext"/> containing
        /// information about the traversed nodes in breadth-first order
        /// </returns>
        /// <remarks>
        /// <para>
        /// This method enumerates nodes in breadth-first order starting from
        /// <paramref name="basePath"/>.
        /// </para>
        /// <para>
        /// When <paramref name="followLinks"/> is <see langword="true"/>,
        /// symbolic links are not returned as nodes. Instead, their target
        /// nodes are traversed using the same semantics as
        /// <see cref="WalkPathTree(VirtualPath, VirtualNodeTypeFilter, bool, bool, bool)"/>,
        /// and the original symbolic link is exposed via
        /// <see cref="VirtualNodeContext.ResolvedLink"/>.
        /// </para>
        /// <para>
        /// When <paramref name="followLinks"/> is <see langword="false"/>,
        /// symbolic links are returned as nodes if allowed by
        /// <paramref name="filter"/>.
        /// </para>
        /// </remarks>
        public IEnumerable<VirtualNodeContext> WalkPathTreeBreadthFirst(
            VirtualPath basePath,
            VirtualNodeTypeFilter filter = VirtualNodeTypeFilter.All,
            bool recursive = true,
            bool followLinks = true,
            bool resolveLinks = true)
        {
            // Normalize the base path
            basePath = ConvertToAbsolutePath(basePath).NormalizePath();
            int baseDepth = basePath.FixedDepth;

            // Get the base node (optionally following links)
            VirtualNode baseNode = GetNode(basePath, followLinks);

            // Resolve traversal and resolved paths (same semantics as WalkPathTree)
            VirtualNodeContext nodeContext = WalkPathToTarget(basePath, null, null, resolveLinks, true);
            VirtualPath traversalBasePath = nodeContext.TraversalPath;
            VirtualPath resolvedBasePath = nodeContext.ResolvedPath!;

            // Parent directory of the resolved base path
            VirtualPath parentDirectoryPath = resolvedBasePath.DirectoryPath;
            VirtualDirectory parentDirectory = GetDirectory(parentDirectoryPath, followLinks);

            // If basePath itself is a symbolic link, keep the link
            VirtualSymbolicLink? link = null;
            if (traversalBasePath != resolvedBasePath)
            {
                link = TryGetSymbolicLink(basePath);
            }

            WalkPathTreeParameters initialParameters = new(
                basePath,
                basePath,
                baseNode,
                parentDirectory,
                baseDepth,
                0,
                0,
                filter,
                recursive,
                followLinks,
                null,
                link);

            Queue<WalkPathTreeParameters> queue = new();
            queue.Enqueue(initialParameters);

            // Clear cycle detection (used when following symbolic links)
            CycleDetectorForTree.Clear();

            while (queue.Count > 0)
            {
                WalkPathTreeParameters p = queue.Dequeue();

                if (p.BaseNode is VirtualDirectory directory)
                {
                    // Notify directory if it matches the filter
                    if (p.Filter.HasFlag(VirtualNodeTypeFilter.Directory))
                    {
                        VirtualPath traversalPath = p.CurrentPath.GetRelativePath(p.BasePath);

                        yield return new VirtualNodeContext(
                            directory,
                            traversalPath,
                            p.ParentDirectory,
                            p.CurrentDepth,
                            p.CurrentIndex,
                            null,
                            false,
                            p.ResolvedLink);
                    }

                    // Enqueue children (respecting recursive flag)
                    if (p.Recursive || p.CurrentDepth == 0)
                    {
                        int index = 0;
                        foreach (VirtualNode node in directory.NodesView)
                        {
                            VirtualPath childPath = p.CurrentPath + node.Name;

                            WalkPathTreeParameters childParameters = new(
                                p.BasePath,
                                childPath,
                                node,
                                directory,
                                p.BaseDepth,
                                p.CurrentDepth + 1,
                                index,
                                p.Filter,
                                p.Recursive,
                                p.FollowLinks,
                                null,
                                null);

                            queue.Enqueue(childParameters);
                            index++;
                        }
                    }
                }
                else if (p.BaseNode is VirtualItem item)
                {
                    // Notify item if it matches the filter
                    if (p.Filter.HasFlag(VirtualNodeTypeFilter.Item))
                    {
                        VirtualPath traversalPath = p.CurrentPath.GetRelativePath(p.BasePath);

                        yield return new VirtualNodeContext(
                            item,
                            traversalPath,
                            p.ParentDirectory,
                            p.CurrentDepth,
                            p.CurrentIndex,
                            null,
                            false,
                            p.ResolvedLink);
                    }
                }
                else if (p.BaseNode is VirtualSymbolicLink symbolicLink)
                {
                    if (p.FollowLinks && symbolicLink.TargetPath != null)
                    {
                        // Follow the link using the existing DFS-based implementation
                        VirtualPath linkTargetPath = symbolicLink.TargetPath;

                        // Convert the symbolic link's target path to an absolute path
                        linkTargetPath = ConvertToAbsolutePath(linkTargetPath, p.CurrentPath).NormalizePath();

                        // Retrieve the target node of the link
                        VirtualNode linkTargetNode = GetNode(linkTargetPath, p.FollowLinks);

                        WalkPathTreeParameters dfsParameters = new(
                            p.BasePath,
                            p.CurrentPath,
                            linkTargetNode,
                            p.ParentDirectory,
                            p.BaseDepth,
                            p.CurrentDepth,
                            p.CurrentIndex,
                            p.Filter,
                            p.Recursive,
                            p.FollowLinks,
                            null,
                            symbolicLink);

                        VirtualPath traversalPath = p.CurrentPath.GetRelativePath(p.BasePath);
                        VirtualPath traversalFullPath = p.BasePath + traversalPath;

                        // Cycle detection check
                        if (CycleDetectorForTree.IsNodeInCycle(symbolicLink))
                        {
                            throw new InvalidOperationException(
                                string.Format(Resources.CircularReferenceDetected, traversalFullPath, symbolicLink));
                        }

                        // Delegate traversal of the link target to the existing DFS implementation
                        foreach (VirtualNodeContext result in WalkPathTreeInternal(dfsParameters))
                        {
                            yield return result;
                        }
                    }
                    else
                    {
                        // Do not follow links: notify the symbolic link itself if allowed by the filter
                        if (p.Filter.HasFlag(VirtualNodeTypeFilter.SymbolicLink))
                        {
                            VirtualPath traversalPath = p.CurrentPath.GetRelativePath(p.BasePath);

                            yield return new VirtualNodeContext(
                                symbolicLink,
                                traversalPath,
                                p.ParentDirectory,
                                p.CurrentDepth,
                                p.CurrentIndex,
                                null,
                                false,
                                p.ResolvedLink);
                        }
                    }
                }
            }
        }