Определите самые маленькие изменения в Treeview

Question

У меня есть древовидная структура, в которой пользователь может перемещать, удалять поддеревья, узлы и создавать узлы.

Я не хочу сохранять каждое действие сразу, но пользователь может сказать «применить мои изменения».Поэтому мне нужно сравнить новое дерево со старым деревом и - самое главное - определить наименьший набор операций для построения нового дерева.Какой подход к этой проблеме?

Я использую ASP.NET/C#, но вопрос не совсем связан с этой технологией.

Спасибо

Answer 1

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

Если вы хотите заменить действия пользователя оптимальным набором действий, который дает тот же результат (для некоторого определения «оптимального»), этоВ общем, очень сложная проблема для решения.Я полагаю, что самый известный алгоритм основан на так называемом «расстоянии редактирования между деревьями» и описан в техническом отчете Чжана и Шаша .Имейте в виду, что это очень плотное чтение.Здесь есть гораздо более читаемая статья здесь для поиска оптимального сценария редактирования для преобразования одного XML-документа в другой.Он основан на первом преобразовании XML в деревья и работе с ними, поэтому основные алгоритмы могут быть непосредственно применимы к вашей проблеме.Он даже поставляется с псевдокодом.

Answer 2

Ну, я думаю, что консолидация операций - лучший доступный вариант, и в моем случае я не мог придумать сценарий, в котором было бы создано неоптимальное решение.Если кому-то действительно интересно, я поделился своим кодом консолидации здесь:

 public class TreeOperationConsolidator : ITreeOperationConsolidator
{
    public IEnumerable<ITreeOperation> ConsolidateOperations(IEnumerable<ITreeOperation> operations)
    {
        List<ITreeOperation> result = new List<ITreeOperation>();
        foreach (var op in operations)
        {
            if (op.Operation == OperationType.Move)
            {
                ConsolidateMoveOperation(op, operations, result);
            }
            else if (op.Operation == OperationType.Rename)
            {
                ConsolidateRenameOperation(op, operations, result);
            }
            else if (op.Operation == OperationType.Create)
            {
                ConsolidateCreateOperation(op, operations, result);
            }
            else if (op.Operation == OperationType.Delete)
            {
                ConsolidateDeleteOperation(op, operations, result);
            }
        }
        return result;
    }

    private void ConsolidateDeleteOperation(ITreeOperation op, IEnumerable<ITreeOperation> operations, List<ITreeOperation> result)
    {
        bool newlyCreated = result.Any(o => o.SourceId == op.SourceId && o.Operation == OperationType.Create);

        result.RemoveAll(o => o.SourceId == op.SourceId);

        var children = (from o in result
                        where
                            (o.Operation == OperationType.Move && o.DestId == op.SourceId)
                            || (o.Operation == OperationType.Create && o.DestId == op.SourceId)
                        select o).ToList();

        foreach (var child in children)
        {
            result.Remove(child);
            ConsolidateDeleteOperation(new TreeOperation { Operation = OperationType.Temp, SourceId = child.SourceId }, operations, result);
        }

        if (newlyCreated == false && op.Operation != OperationType.Temp)
            result.Add(op);
    }

    private void ConsolidateCreateOperation(ITreeOperation op, IEnumerable<ITreeOperation> operations, List<ITreeOperation> result)
    {
        result.Add(op);
    }

    private void ConsolidateRenameOperation(ITreeOperation op, IEnumerable<ITreeOperation> operations, List<ITreeOperation> result)
    {
        var createOperation = result.FirstOrDefault(o => o.SourceId == op.SourceId && o.Operation == OperationType.Create);
        if (createOperation == null)
        {
            var renameOp = result.FirstOrDefault(o => o.SourceId == op.SourceId && o.Operation == op.Operation);
            if (renameOp != null)
            {
                result.Remove(renameOp);
            }
            result.Add(op);
        }
        else
        {
            createOperation.Argument = op.Argument;
        }
    }

    protected void ConsolidateMoveOperation(ITreeOperation op, IEnumerable<ITreeOperation> operations, List<ITreeOperation> result)
    {
        var createOperation = result.FirstOrDefault(o => o.SourceId == op.SourceId && o.Operation == OperationType.Create);
        if (createOperation == null)
        {
            var moveOp = result.FirstOrDefault(o => o.SourceId == op.SourceId && o.Operation == op.Operation);
            if (moveOp != null)
            {
                result.Remove(moveOp);
            }
            result.Add(op);
        }
        else
        {
            createOperation.DestId = op.DestId;
        }
    }
}

public class TreeOperation : ITreeOperation
{
    public string Argument { get; set; }

    public OperationType Operation { get; set; }

    public string SourceId { get; set; }

    public string DestId { get; set; }
}

public enum OperationType
{
    Move,
    Rename,
    Create,
    Delete,
    Temp
}

public interface ITreeOperationConsolidator
{
    IEnumerable<ITreeOperation> ConsolidateOperations(IEnumerable<ITreeOperation> operations);
}

public interface ITreeOperation
{
    string Argument { get; set; }

    OperationType Operation { get; set; }

    string SourceId { get; set; }

    string DestId { get; set; }
}

Так что вам нужно отслеживать все действия пользователя в дереве (т.е. сохранять экземпляры ITreeOperation в сеансе (или где-то еще). Перед применением всех изменений обязательно позвоните IEnumerable<ITreeOperation> ConsolidateOperations(IEnumerable<ITreeOperation> operations).

Answer 3

Как говорит svick, лучший вариант - записывать все изменения и применять их, когда пользователь нажимает кнопку «Применить».

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

• перемещение узла во второй раз сводит на нет первое движение
• , удаление недавно созданного узла и наоборот.В этом случае новую запись также следует удалить.
• удаление узла и создание другого узла (или поддеревьев одинакового размера) можно заменить движением

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