hrynco-common/HrynCo.Common/Tree/TreeUtils.cs

namespace HrynCo.Common.Tree;

public static class TreeUtils
{
    public static HashSet<TKey> CollectDescendants<TNode, TKey>(
        TKey rootId,
        IEnumerable<TNode> nodes,
        TKey rootMarker)
        where TNode : ITreeNode<TKey>
        where TKey : struct
    {
        var map = nodes
            .GroupBy(x => x.ParentId ?? rootMarker)
            .ToDictionary(g => g.Key, g => g.ToList());

        var result = new HashSet<TKey>
        {
            rootId
        };
        var queue = new Queue<TKey>();
        queue.Enqueue(rootId);

        while (queue.Count > 0)
        {
            TKey current = queue.Dequeue();
            if (!map.TryGetValue(current, out var children))
            {
                continue;
            }

            foreach (TNode child in children.Where(child => result.Add(child.Id)))
            {
                queue.Enqueue(child.Id);
            }
        }

        return result;
    }

    public static List<BreadcrumbNode<TKey>> BuildBreadcrumb<TNode, TKey>(
        TKey currentId,
        IReadOnlyDictionary<TKey, TNode> map)
        where TNode : class, ITreeNode<TKey>, INameNode
        where TKey : struct
    {
        var path = new List<BreadcrumbNode<TKey>>();
        TNode? current = map.GetValueOrDefault(currentId);

        while (current != null)
        {
            path.Add(new BreadcrumbNode<TKey>(current.Id, current.Name));
            current = current.ParentId is { } parentId
                ? map.GetValueOrDefault(parentId)
                : null;
        }

        path.Reverse();
        return path;
    }
}