src/ClothesGraph.Model/Drafting/DraftGraph.cs - main - docNemo/clothes-graph

src/ClothesGraph.Model/Drafting/DraftGraph.cs
353 строки13 KB
docNemo
Запрос на слияние 'interface-to-spec' (#1) из interface-to-spec в main
09 авг 2026, 20:28
09 авг 2026, 20:281bbc436
using System;
using System.Collections.Generic;
using System.Linq;
using ClothesGraph.Geometry;
using ClothesGraph.Model.Formulas;
using ClothesGraph.Model.Measurements;

namespace ClothesGraph.Model.Drafting;

/// <summary>
/// Граф построений чертежа: направленный и ациклический.
/// </summary>
/// <remarks>
/// Цикл здесь — ошибка, и это отличает граф построений от графа швов, где
/// замкнутые цепочки нормальны. Смешивать их в одной структуре нельзя:
/// одна и та же проверка была бы для одного графа обязательной, а для другого
/// ложной тревогой.
/// </remarks>
public sealed class DraftGraph
{
    private readonly Dictionary<NodeId, DraftNode> _nodes = new();
    private readonly Dictionary<string, NodeId> _byName =
        new(StringComparer.CurrentCultureIgnoreCase);

    /// <summary>
    /// Номер правки, при которой построение объявлено требующим пересчёта.
    /// </summary>
    /// <remarks>
    /// Отметки, а не общий набор «грязных». Вычислителей над одним графом
    /// несколько — по одному на размер ряда, — и общий набор доставался тому,
    /// кто пересчитался первым: он снимал пометки, а остальные размеры
    /// оставались с прежней геометрией. Наложенный просмотр показывал правку
    /// только в текущем размере, вывод ряда — старую выкройку.
    /// </remarks>
    private readonly Dictionary<NodeId, long> _invalidatedAt = new();

    private long _epoch;

    public IReadOnlyCollection<DraftNode> Nodes => _nodes.Values;

    public int Count => _nodes.Count;

    /// <summary>Текущий номер правки графа.</summary>
    public long Epoch => _epoch;

    /// <summary>Объявлено ли построение требующим пересчёта после указанной правки.</summary>
    public bool IsInvalidatedSince(NodeId id, long epoch)
        => _invalidatedAt.TryGetValue(id, out var at) && at > epoch;

    public DraftNode Get(NodeId id)
        => _nodes.TryGetValue(id, out var node)
            ? node
            : throw new KeyNotFoundException($"Построение {id} не найдено");

    public bool TryGet(NodeId id, out DraftNode? node) => _nodes.TryGetValue(id, out node);

    public DraftNode? FindByName(string name)
        => !string.IsNullOrWhiteSpace(name) && _byName.TryGetValue(name.Trim(), out var id)
            ? _nodes[id]
            : null;

    public bool Contains(NodeId id) => _nodes.ContainsKey(id);

    /// <summary>Добавляет построение. Ссылки должны существовать, цикл недопустим.</summary>
    public TNode Add<TNode>(TNode node) where TNode : DraftNode
    {
        if (_nodes.ContainsKey(node.Id))
            throw new InvalidOperationException($"Построение {node.Id} уже есть в графе");

        if (_byName.ContainsKey(node.Name))
            throw new InvalidOperationException($"Имя «{node.Name}» уже занято");

        foreach (var dependency in node.Dependencies)
            if (!_nodes.ContainsKey(dependency))
                throw new InvalidOperationException(
                    $"Построение «{node.Name}» ссылается на несуществующее {dependency}");

        _nodes.Add(node.Id, node);
        _byName.Add(node.Name, node.Id);

        // Новый узел не может замкнуть цикл, поскольку на него ещё никто
        // не ссылается, но проверка оставлена: она дешёвая и защищает от
        // ошибок при восстановлении графа из файла.
        if (FindCycle() is { } cycle)
        {
            _nodes.Remove(node.Id);
            _byName.Remove(node.Name);
            throw new DraftCycleException(cycle);
        }

        Invalidate(node.Id);
        return node;
    }

    public void Rename(NodeId id, string newName)
    {
        var node = Get(id);
        var name = DraftNode.Normalize(newName);

        if (_byName.TryGetValue(name, out var existing) && existing != id)
            throw new InvalidOperationException($"Имя «{name}» уже занято");

        _byName.Remove(node.Name);
        node.Name = name;
        _byName[name] = id;
    }

    /// <summary>
    /// Изменяет построение. Если изменение замкнуло цикл или сослалось на
    /// несуществующее построение, оно откатывается целиком, и построение
    /// остаётся ровно таким, каким было.
    /// </summary>
    /// <remarks>
    /// Откат обязателен: ошибка при правке формулы не должна оставлять чертёж
    /// в состоянии, которое пользователь не задавал и не может увидеть.
    /// </remarks>
    public void Update(NodeId id, Action<DraftNode> change)
    {
        var node = Get(id);
        var snapshot = node.Clone();

        change(node);

        try
        {
            foreach (var dependency in node.Dependencies)
                if (!_nodes.ContainsKey(dependency))
                    throw new InvalidOperationException(
                        $"Построение «{node.Name}» ссылается на несуществующее {dependency}");

            if (FindCycle() is { } cycle)
                throw new DraftCycleException(cycle);
        }
        catch
        {
            _nodes[id] = snapshot;
            throw;
        }

        Invalidate(id);
    }

    /// <summary>Снимок построения для отмены операций.</summary>
    public DraftNode Snapshot(NodeId id) => Get(id).Clone();

    /// <summary>Восстанавливает построение из снимка.</summary>
    public void Restore(DraftNode snapshot)
    {
        if (!_nodes.ContainsKey(snapshot.Id))
            throw new KeyNotFoundException($"Построение {snapshot.Id} не найдено");

        _nodes[snapshot.Id] = snapshot;
        Invalidate(snapshot.Id);
    }

    /// <summary>Проверяет, замкнёт ли цикл ссылка одного построения на другое.</summary>
    public bool WouldCreateCycle(NodeId dependent, NodeId dependency)
    {
        if (dependent == dependency)
            return true;

        // Цикл возникнет, если предполагаемая зависимость сама зависит
        // от построения, которое собирается на неё сослаться.
        var visited = new HashSet<NodeId>();
        var stack = new Stack<NodeId>();
        stack.Push(dependency);

        while (stack.Count > 0)
        {
            var current = stack.Pop();

            if (current == dependent)
                return true;

            if (!visited.Add(current) || !_nodes.TryGetValue(current, out var node))
                continue;

            foreach (var next in node.Dependencies)
                stack.Push(next);
        }

        return false;
    }

    /// <summary>Построения, прямо или косвенно зависящие от указанного.</summary>
    public IReadOnlyList<DraftNode> GetDependents(NodeId id)
    {
        var dependents = new List<DraftNode>();
        var affected = new HashSet<NodeId>();
        CollectDependents(id, affected);

        foreach (var affectedId in affected)
            if (affectedId != id && _nodes.TryGetValue(affectedId, out var node))
                dependents.Add(node);

        return dependents;
    }

    /// <summary>
    /// Удаляет построение. При наличии зависящих требует подтверждения:
    /// без <paramref name="force"/> удаление отклоняется с их перечнем.
    /// </summary>
    public void Remove(NodeId id, bool force = false)
    {
        var node = Get(id);
        var dependents = GetDependents(id);

        if (dependents.Count > 0 && !force)
            throw new DraftDependentsException(
                node.Name, dependents.Select(dependent => dependent.Name).ToArray());

        foreach (var dependent in dependents)
        {
            _nodes.Remove(dependent.Id);
            _byName.Remove(dependent.Name);
            _invalidatedAt.Remove(dependent.Id);
        }

        _nodes.Remove(id);
        _byName.Remove(node.Name);
        _invalidatedAt.Remove(id);
    }

    /// <summary>Помечает построение и всё, что от него зависит, требующим пересчёта.</summary>
    public void Invalidate(NodeId id)
    {
        var affected = new HashSet<NodeId>();
        CollectDependents(id, affected);

        _epoch++;

        foreach (var affectedId in affected)
            _invalidatedAt[affectedId] = _epoch;
    }

    /// <summary>Помечает построения, зависящие от мерки, требующими пересчёта.</summary>
    public void InvalidateMeasurement(MeasurementId measurement)
    {
        foreach (var node in _nodes.Values)
            if (node.MeasurementDependencies.Contains(measurement))
                Invalidate(node.Id);
    }

    public void InvalidateAll()
    {
        _epoch++;

        foreach (var id in _nodes.Keys)
            _invalidatedAt[id] = _epoch;
    }

    private void CollectDependents(NodeId id, HashSet<NodeId> affected)
    {
        if (!affected.Add(id))
            return;

        foreach (var node in _nodes.Values)
            if (node.Dependencies.Contains(id))
                CollectDependents(node.Id, affected);
    }

    /// <summary>
    /// Порядок вычисления: каждое построение идёт после всех, от которых зависит.
    /// </summary>
    public IReadOnlyList<DraftNode> TopologicalOrder()
    {
        var order = new List<DraftNode>(_nodes.Count);
        var state = new Dictionary<NodeId, VisitState>();

        foreach (var node in _nodes.Values)
            Visit(node, state, order);

        return order;
    }

    private void Visit(DraftNode node, Dictionary<NodeId, VisitState> state, List<DraftNode> order)
    {
        if (state.TryGetValue(node.Id, out var visited))
        {
            if (visited == VisitState.Done)
                return;

            throw new DraftCycleException([node.Name, node.Name]);
        }

        state[node.Id] = VisitState.InProgress;

        foreach (var dependency in node.Dependencies)
            if (_nodes.TryGetValue(dependency, out var next))
                Visit(next, state, order);

        state[node.Id] = VisitState.Done;
        order.Add(node);
    }

    /// <summary>Ищет цикл и возвращает имена его участников, либо null.</summary>
    public IReadOnlyList<string>? FindCycle()
    {
        var state = new Dictionary<NodeId, VisitState>();
        var path = new List<NodeId>();

        foreach (var node in _nodes.Values)
        {
            var cycle = FindCycle(node.Id, state, path);
            if (cycle is not null)
                return cycle;
        }

        return null;
    }

    private IReadOnlyList<string>? FindCycle(
        NodeId id, Dictionary<NodeId, VisitState> state, List<NodeId> path)
    {
        if (state.TryGetValue(id, out var visited))
        {
            if (visited == VisitState.Done)
                return null;

            // Найдено обратное ребро: путь от места входа в цикл и до текущего
            // построения и есть искомая цепочка.
            var start = path.IndexOf(id);
            var cycle = path.Skip(start).Append(id)
                .Select(step => _nodes.TryGetValue(step, out var node) ? node.Name : step.ToString())
                .ToArray();

            return cycle;
        }

        if (!_nodes.TryGetValue(id, out var current))
            return null;

        state[id] = VisitState.InProgress;
        path.Add(id);

        foreach (var dependency in current.Dependencies)
        {
            var cycle = FindCycle(dependency, state, path);
            if (cycle is not null)
                return cycle;
        }

        path.RemoveAt(path.Count - 1);
        state[id] = VisitState.Done;
        return null;
    }

    private enum VisitState
    {
        InProgress,
        Done
    }
}