Эффективное управление данными с помощью иерархической древовидной структуры в .NET C#
programming software-engineering dotnet tree

Эффективное управление данными с помощью иерархической древовидной структуры в .NET C#

3 мая 2023 г.

Иногда вам может понадобиться работать с данными Формы иерархического дерева. Проще говоря, это данные, представленные в узлах родитель-потомок.

В таких ситуациях у вас может возникнуть проблема со сложностью реализации, особенно при работе с большим объемом данных.

В этой статье я предоставлю вам одну из возможных конструкций для таких случаев. Однако следует помнить, что, как обычно, общий дизайн может предлагать абстрактные возможности, но для определенных сценариев в нем могут отсутствовать определенные улучшения.

Поэтому я рекомендую рассматривать дизайн, представленный в этой статье, как открытие разума. Вы должны изучать его, учиться у него, черпать из него идеи и, в конечном счете, адаптировать его к своим потребностям.

Photo by Markus Winkler on Unsplash

Основные цели

Основные цели этого дизайна:

  1. Представить иерархические данные в виде древовидной структуры данных.
  2. Иметь возможность создавать узлы изолированно.
  3. Иметь возможность присоединять и отсоединять узлы.
  4. Иметь возможность поиска узлов с соответствующей производительностью.
  5. Не теряйте преимущества строго типизированных данных.

Поэтому при разработке нашего дизайна мы должны помнить об этих требованиях.

Photo by Med Badr Chemmaoui on Unsplash

Дизайн

Во-первых, нужно иметь в виду, что сами данные могут относиться к любому бизнес-объекту. Однако Иерархическая структура — это нечто иное. Это структура, управляющая отношениями между узлами, как добавлять, как удалять, как искать... и так далее.

Полезная нагрузка

namespace HierarchicalData.Abstractions
{
    public abstract class Payload
    {
    }
}

Что мы можем здесь заметить:

  1. Это основной объект, представляющий бизнес-объект, который должен быть включен в нашу иерархическую структуру.
  2. Мы не добавляли сюда никаких участников, но вы можете добавить их, если считаете, что это является общим для всех ваших бизнес-объектов.

Тип узла

namespace HierarchicalData.Abstractions
{
    public enum NodeType
    {
        Structural = 1,
        Leaf = 2
    }
}

Что мы можем здесь заметить:

  1. Это перечисление, представляющее тип узла.
  2. У нас есть только два типа узлов; Структурный и Конечный.
  3. Структурный узел — это узел, который предоставляет информацию только об иерархической структуре. Проще говоря, это похоже на папку или узел, у которого есть дочерние узлы.
  4. Конечный узел — это узел, который предоставляет только бизнес-данные. Проще говоря, это узел, который упаковывает данные и не имеет дочерних элементов.

Инод

namespace HierarchicalData.Abstractions
{
    public interface INode
    {
        string Id { get; }
        string Name { get; }
        string PathPart { get; }
        NodeType Type { get; }
        IStructuralNode Parent { get; set; }
    }
}

Что мы можем здесь заметить:

  1. Это интерфейс, представляющий общие члены любого узла, независимо от того, является ли он структурным или конечным.
  2. Id – это уникальный идентификатор узла. Это должно быть абсолютно уникальным. Я реализовал его как строку, но вы можете изменить его в соответствии со своими потребностями.
  3. Name — это имя узла. В какой-то момент это должно использоваться для уровня представления.
  4. PathPart – это имя, которое будет использоваться для представления пути к узлу.
  5. Parent — родительский узел. Его тип — IStructuralNode, так как он не может быть Leaf, потому что у Leaf никогда не будет дочернего элемента.

IStructuralNode

using System.Collections.Generic;

namespace HierarchicalData.Abstractions
{
    public delegate void ChildNodeAddedEventHandler(object sender, IStructuralNode node, INode added);

    public delegate void ChildNodeRemovedEventHandler(object sender, IStructuralNode node, INode removed);

    public interface IStructuralNode : INode
    {
        event ChildNodeAddedEventHandler ChildNodeAdded;
        event ChildNodeRemovedEventHandler ChildNodeRemoved;

        IReadOnlyCollection<INode> Children { get; }
        new NodeType Type => NodeType.Structural;

        void AddChild(INode child);
        void RemoveChild(INode child);
        IReadOnlyDictionary<string, INode> GetFlatChildren();
    }
}

Что мы можем здесь заметить:

  1. Мы определили делегат ChildNodeAddedEventHandler для представления обработчика события, которое будет запущено, когда узел добавляется в качестве дочернего под другим узлом.
  2. Мы также определили делегат ChildNodeRemovedEventHandler для представления обработчика события, которое будет запущено, когда узел удаляется из дочерних элементов другого узла.
  3. Мы определили интерфейс IStructuralNode, который расширяет INode.
  4. У него есть два события; ChildNodeAdded и ChildNodeRemoved.
  5. Он имеет доступную только для чтения коллекцию дочерних узлов.
  6. Тип его узла по умолчанию будет Структурный.
  7. У него есть метод добавления дочернего элемента.
  8. Есть метод удаления дочерних элементов.
  9. У него также есть метод для возврата плоской коллекции всех вложенных дочерних узлов.

ILeafNode и ILeafNode

namespace HierarchicalData.Abstractions
{
    public interface ILeafNode : INode
    {
        Payload Payload { get; }
        new NodeType Type => NodeType.Leaf;
    }

    public interface ILeafNode<out TPayload> : ILeafNode where TPayload : Payload
    {
        new TPayload Payload { get; }
    }
}

Что мы можем здесь заметить:

  1. ILeafNode расширяет INode.
  2. У него есть свойство Payload, которое возвращает упакованные данные типа Payload.
  3. Он скрывает родительский Type и по умолчанию использует Leaf.
  4. ILeafNode<out TPayload> скрывает родительский Payload и определяет типизированный.

Узел

using System.Linq;
using HierarchicalData.Abstractions;

namespace HierarchicalData.Implementations
{
    public abstract class Node : INode
    {
        protected Node(
            string id,
            string name,
            string pathPart,
            NodeType type,
            IStructuralNode parent)
        {
            Id = id;
            Name = name;
            PathPart = pathPart;
            Type = type;
            Parent = parent;
        }

        public string Id { get; }
        public string Name { get; }
        public string PathPart { get; }
        public NodeType Type { get; }
        public IStructuralNode Parent
        {
            get => m_Parent;
            set
            {
                if (m_Parent != value)
                {
                    if (value != null && value.Children.All(c => c.Id != Id))
                    {
                        value.AddChild(this);
                    }
                    else if (value == null)
                    {
                        m_Parent.RemoveChild(this);
                    }

                    m_Parent = value;
                }
            }
        }
    }
}

Что мы можем здесь заметить:

  1. Он реализует INode.
  2. Реализация проста.
  3. При желании вы можете расширить его для реализации IEquatable<Node>.
  4. Мы также позволяем пользователю задавать Parent напрямую через свойство Parent. Однако реализация делегируется методам AddChild и RemoveChild.

LeafNode

using HierarchicalData.Abstractions;

namespace HierarchicalData.Implementations
{
    public class LeafNode<TPayload> : Node, ILeafNode<TPayload> where TPayload : Payload
    {
        public LeafNode(
            string id,
            string name,
            string pathPart,
            IStructuralNode parent,
            TPayload payload) : base(id, name, pathPart, NodeType.Leaf, parent)
        {
            Payload = payload;
            parent?.AddChild(this);
        }

        Payload ILeafNode.Payload => Payload;

        public TPayload Payload { get; }
    }
}

Что мы можем здесь заметить:

  1. Он наследуется от Node и реализует ILeafNode<TPayload>.
  2. Здесь стоит упомянуть, что в реализации конструктора, если установлен родитель, мы вызываем AddChild для родителя, передавая this.

Структурный узел

using System.Collections.Generic;
using System.Linq;
using HierarchicalData.Abstractions;

namespace HierarchicalData.Implementations
{
    public class StructuralNode : Node, IStructuralNode
    {
        private readonly List<INode> m_Children;
        private readonly Dictionary<string, INode> m_Catalog;

        public event ChildNodeAddedEventHandler ChildNodeAdded;
        public event ChildNodeRemovedEventHandler ChildNodeRemoved;

        public StructuralNode(
            string id,
            string name,
            string pathPart,
            IStructuralNode parent = null,
            List<INode> children = null) : base(id, name, pathPart, NodeType.Structural, parent)
        {
            m_Children = new List<INode>();
            m_Catalog = new Dictionary<string, INode>();

            if (children != null && children.Any())
            {
                foreach (var child in children)
                {
                    AddChild(child);
                }
            }

            parent?.AddChild(this);
        }

        public IReadOnlyCollection<INode> Children => m_Children;

        public void AddChild(INode child)
        {
            if (child != null && Children.All(c => c.Id != child.Id))
            {
                child.Parent?.RemoveChild(child);

                m_Catalog.Add(child.Id, child);
                m_Children.Add(child);

                OnDirectChildNodeAdded(child);

                if (child.Type == NodeType.Structural && child is IStructuralNode structuralNode)
                {
                    foreach (var keyValuePair in structuralNode.GetFlatChildren())
                    {
                        m_Catalog.Add(keyValuePair.Key, keyValuePair.Value);
                        OnNestedChildNodeAdded(keyValuePair.Value.Parent, keyValuePair.Value);
                    }

                    structuralNode.ChildNodeAdded += AddHandler;
                    structuralNode.ChildNodeRemoved += RemoveHandler;
                }

                child.Parent = this;
            }
        }

        public void RemoveChild(INode child)
        {
            if (child != null && Children.Any(c => c.Id == child.Id))
            {
                m_Catalog.Remove(child.Id);
                m_Children.Remove(child);

                OnDirectChildNodeRemoved(child);

                if (child.Type == NodeType.Structural && child is IStructuralNode structuralNode)
                {
                    foreach (var keyValuePair in structuralNode.GetFlatChildren())
                    {
                        m_Catalog.Remove(keyValuePair.Key);
                        OnNestedChildNodeRemoved(keyValuePair.Value.Parent, keyValuePair.Value);
                    }

                    structuralNode.ChildNodeAdded -= AddHandler;
                    structuralNode.ChildNodeRemoved -= RemoveHandler;
                }

                child.Parent = null;
            }
        }

        public IReadOnlyDictionary<string, INode> GetFlatChildren()
        {
            return m_Catalog;
        }

        protected void OnDirectChildNodeAdded(INode added)
        {
            ChildNodeAdded?.Invoke(this, this, added);
        }

        protected void OnNestedChildNodeAdded(IStructuralNode node, INode added)
        {
            ChildNodeAdded?.Invoke(this, node, added);
        }

        protected void OnDirectChildNodeRemoved(INode removed)
        {
            ChildNodeRemoved?.Invoke(this, this, removed);
        }

        protected void OnNestedChildNodeRemoved(IStructuralNode node, INode removed)
        {
            ChildNodeRemoved?.Invoke(this, node, removed);
        }

        private void AddHandler(object sender, IStructuralNode node, INode added)
        {
            m_Catalog.Add(added.Id, added);
            OnNestedChildNodeAdded(node, added);
        }

        private void RemoveHandler(object sender, IStructuralNode node, INode removed)
        {
            m_Catalog.Remove(removed.Id);
            OnNestedChildNodeRemoved(node, removed);
        }
    }
}

Прежде чем анализировать этот код, нам нужно понять, как он будет работать.

Как мы уже говорили, узлы должны создаваться изолированно. Это означает, что конечный пользователь должен иметь возможность создать узел, не устанавливая никаких родительских или даже дочерних элементов.

Затем он должен иметь возможность присоединить этот узел как дочерний к другому узлу. Кроме того, он должен иметь возможность присоединять другие узлы в качестве дочерних к дочерним элементам этого узла... и так далее.

Для всех этих действий наш код должен сохранять структуру и отношения между узлами нетронутыми.

Кроме того, мы хотим упростить поиск узлов. Особым случаем будет поиск по идентификатору. Это должно быть как можно быстрее.

Поэтому, помня об этом, давайте проанализируем код.

Что мы можем здесь заметить:

  1. В конструкторе, если задана коллекция дочерних элементов, мы вызываем метод AddChild, передавая каждому дочернему элементу дочерние элементы.
  2. Кроме того, если установлен родитель, мы вызываем AddChild для родителя, передавая this.
  3. Чтобы облегчить поиск узла, мы определили Dictionary<string, INode> m_Каталог. Это каталог, в котором мы храним ссылки на все узлы, даже вложенные, ниже текущего узла.
  4. Чтобы этот каталог всегда был синхронизирован, текущий узел подписывается на события ChildNodeAdded и ChildNodeRemoved каждого прямого дочернего узла в момент их добавления.
  5. Следуя тому же правилу, текущий узел отменяет подписку на события ChildNodeAdded и ChildNodeRemoved всех прямых дочерних узлов в момент их удаления.
  6. Кроме того, мы должны иметь в виду, что всякий раз, когда узел добавляется к текущему узлу в качестве прямого потомка, этот узел может иметь другое вложенное поддерево. В этом случае текущий каталог также должен быть обновлен всеми вложенными дочерними элементами поддерева.
  7. Итак, с учетом сказанного, давайте посмотрим на реализацию AddChild(INode child).
  8. child.Parent?.RemoveChild(child); гарантирует, что новый дочерний элемент будет отсоединен от своего старого родителя, прежде чем присоединять его к новому родителю, который является текущим узлом.
  9. m_Catalog.Add(child.Id, child); добавляет новый дочерний элемент в каталог.
  10. m_Children.Add(child); добавляет дочерний элемент в коллекцию Children.
  11. OnDirectChildNodeAdded(child); запускает событие ChildNodeAdded, чтобы уведомить непосредственного родителя о добавлении нового дочернего элемента и, в конечном итоге, к его каталогу должны быть применены новые обновления.
  12. Затем мы проверяем, является ли новый дочерний элемент структурным узлом, потому что в этом случае нам нужно прослушивать изменения, которые могут быть применены к нему.
  13. Итак, если это так, мы зацикливаемся на плоских дочерних элементах нового дочернего элемента, добавляем их один за другим в текущий каталог, а также запускаем событие ChildNodeAdded, но на этот раз с правильными значениями < code>node и добавлены аргументы. Это делается для уведомления прямого родителя о вложенных обновлениях. Обратите внимание, что прямой родитель также сделает то же самое и уведомит своего прямого родителя… и так далее.
  14. Как мы уже говорили, текущий узел должен подписаться на события ChildNodeAdded и ChildNodeRemoved нового дочернего элемента, чтобы он всегда обновлялся. Это то, что мы делаем с structuralNode.ChildNodeAdded += AddHandler; и structuralNode.ChildNodeRemoved += RemoveHandler;.
  15. child.Parent = this; устанавливает родительский элемент дочернего узла в текущий узел.
  16. Теперь давайте посмотрим на реализацию RemoveChild(INode child).
  17. m_Catalog.Remove(child.Id); удаляет дочерний элемент из каталога.
  18. m_Children.Remove(child); удаляет дочерний элемент из коллекции Children.
  19. OnDirectChildNodeRemoved(child); запускает событие ChildNodeRemoved, чтобы уведомить непосредственного родителя об удалении дочернего элемента и, в конечном итоге, к его каталогу должны быть применены новые обновления.
  20. Затем мы проверяем, является ли новый дочерний элемент структурным узлом, потому что в этом случае нам нужно прослушивать изменения, которые могут быть применены к нему.
  21. Итак, если это так, мы зацикливаемся на плоских дочерних элементах дочернего элемента, удаляем их одного за другим из текущего каталога, а также запускаем событие ChildNodeRemoved, но на этот раз с правильными значениями node и добавлены аргументы. Это делается для уведомления прямого родителя о вложенных обновлениях. Обратите внимание, что прямой родитель также сделает то же самое и уведомит своего прямого родителя… и так далее.
  22. Как мы уже говорили, текущий узел должен отказаться от подписки на события ChildNodeAdded и ChildNodeRemoved дочернего узла, подлежащего удалению. Это то, что мы делаем с structuralNode.ChildNodeAdded -= AddHandler; и structuralNode.ChildNodeRemoved -= RemoveHandler;.
  23. child.Parent = null; сбрасывает родительский элемент на null.

Я знаю, что эта часть была сложной, но если вы просто пройдете ее еще раз, вы обнаружите, что это не так сложно.

Навигатор по дереву

using System;
using System.Collections.Generic;
using System.Linq;
using HierarchicalData.Abstractions;

namespace HierarchicalData.Implementations
{
    public class TreeNavigator
    {
        public string[] GetNodeFullPath(INode node)
        {
            var result = new List<string> { node.PathPart };

            var parent = node.Parent;

            while (parent != null)
            {
                result.Insert(0, parent.PathPart);
                parent = parent.Parent;
            }

            return result.ToArray();
        }

        public INode SearchById(IStructuralNode root, string id)
        {
            if (root?.GetFlatChildren().ContainsKey(id) ?? false)
            {
                return root.GetFlatChildren()[id];
            }

            return null;
        }

        public IList<INode> Search(IStructuralNode root, Func<INode, bool> predicate)
        {
            var flat = root?.GetFlatChildren();

            if (flat != null)
            {
                return flat
                       .Where(entry => predicate(entry.Value))
                       .Select(entry => entry.Value)
                       .ToList();
            }

            return new List<INode>();
        }

        public int FindNodeDepth(IStructuralNode root, INode node)
        {
            var foundNode = SearchById(root, node.Id);

            if (foundNode != null)
            {
                var depth = 0;
                var parent = node.Parent;

                while (parent != null)
                {
                    depth++;

                    if (parent.Id == root.Id)
                    {
                        break;
                    }

                    parent = parent.Parent;
                }

                return depth;
            }

            return 0;
        }
    }
}

Это похоже на класс Helper, который предоставляет дополнительные возможности, такие как поиск узлов, оценка полных путей, определение глубины узла и т. д.

Внутри он хорошо использует хорошо определенную и устоявшуюся структуру, которую мы определили для наших классов узлов.

Я не абстрагировал этот класс, но вы наверняка можете это сделать и расширить его, добавив столько возможностей, сколько вам нужно.

Photo by Elisha Terada on Unsplash, adjusted by Ahmed Tarek

Заключительные слова

Я собирался написать пример приложения, чтобы показать вам, насколько эффективен наш дизайн, но, немного подумав, решил оставить это вам в качестве упражнения.

Итак, я знаю, что когда вы смотрите на этот дизайн, вы можете почувствовать, что его слишком сложно понять. Однако в первую очередь нужно помнить о сложности работы.

Как я уже говорил в начале, вам нужно использовать дизайн, описанный в этой статье, как средство для открытия разума, подумать над ним, извлечь из него уроки, отбросить то, что вам не нужно, адаптировать его, улучшить и, наконец, начать его использовать. Это всегда правильный способ учиться и приобретать новые навыки.

Вот и все, надеюсь, вам было так же интересно читать эту статью, как мне было ее писать.

:::информация Также опубликовано здесь.

:::

Оригинал

Recent Post

Categories

PREVIOUS ARTICLE
NEXT ARTICLE