Как сравнить два дерева каталогов?

Question

[Николай Богданов]

Есть дерево вот таких объектов, подскажите, как сравнить два таких дерева, чтобы получить два списка: добавленные файлы и каталоги и удаленные файлы и каталоги? Хотя бы идею какую-то, что-то сильно туплю.

public class Folder
{
    public string Path { get; set; }
    public DateTime LWT { get; set; }
    public int Depth { get; set; }
    public List<FileSystemInfo> Files { get; set; } = new List<FileSystemInfo>();
    public List<Folder> SubFolders { get; set; } = new List<Folder>();
}

Answer 1

[Wataru]

Рекурсия. Функции передаются 2 каталога. Она сравнивает файлы в них и добавляет новые/пропавшие файлы в списки. Также смотрит на директории. Если какая-то директория новая, то другая рекурсивная функции добавляеет все файлы и каталоги в ней в список новых. Также удаленные директории добавляются в список. Если какая-то директория есть и там и там, то рекурсивно вызывйтесь от них.

Comments

[Николай Богданов]

Получилось вроде бы, посмотрите. Единственное, чего я не понял, как обойтись без общего состояния (глобальной переменной _res), или в рекурсивных функциях это неизбежно?

private void DiffBetween(Folder exist, Folder other)
{
    if (exist.Path != other.Path) return;

    foreach (var oldFolder in exist.SubFolders)
    {
        if (other[oldFolder.Path] == null) 
        { 
            _res.RemovedFolders.Add(oldFolder.Path);
            RemoveSubFolders(oldFolder);
        }
    }

    foreach (var newFolder in other.SubFolders)
    {
        if (exist[newFolder.Path] == null)
        {
            _res.AddedFolders.Add(newFolder.Path);
            AddSubFolders(newFolder);
        }
        else
        {
            var oldFolder = exist[newFolder.Path];
            DiffBetween(oldFolder, newFolder);
        }
    }
}

private void AddSubFolders(Folder folder) 
{
    AddFiles(folder);
    
    foreach (Folder item in folder.SubFolders)
    {
        _res.AddedFolders.Add(item.Path);
       AddSubFolders(item);
    }
}

private void RemoveSubFolders(Folder folder)
{
    RemoveFiles(folder);
    
    foreach (Folder item in folder.SubFolders)
    {
        _res.RemovedFolders.Add(item.Path);
        RemoveSubFolders(item);
    }
}

private void AddFiles(Folder folder)
{
    foreach (var file in folder.Files)
    {
        _res.AddedFiles.Add(file.FullName);
    }
}

private void RemoveFiles(Folder folder)
{
    foreach (var file in folder.Files)
    {
        _res.RemovedFiles.Add(file.FullName);
    }
}

[Wataru]

Николай Богданов, вы не обрабатываете файлы в текущей директории в DiffBetween. Можно избавиться от глобального состояния, если просто передавать его по ссылке в функцию. Или сделать функции возвращающими списки удаленных и новых файлов. Соответсвенно после рекурсивного вызова надо будет накапливать возвращенные данные и возвращать итог. Но это будет медленнее чем с параметром.

Но вообще, у вас функции члены класса похоже - это нормально иметь какое-то состояние. Можно сделать у класса конструктор, который получает 2 каталога и обрабатывает их. И методы для получения всяких уже подсчитанных данных.

[Николай Богданов]

Wataru, спасибо, написал подходящий тест и поправил, надеюсь что получилось)

private void DiffBetween(Folder exist, Folder other)
{
    if (exist.Path != other.Path) return;

    foreach (var oldFile in exist.Files)
    {
        if (other.FindFile(oldFile.FullName) == null) _res.RemovedFiles.Add(oldFile.FullName);
    }

    foreach (var newFile in other.Files)
    {
        if (exist.FindFile(newFile.FullName) == null) _res.AddedFiles.Add(newFile.FullName);
    }

    foreach (var oldFolder in exist.SubFolders)
    {
        if (other[oldFolder.Path] == null)
        {
            _res.RemovedFolders.Add(oldFolder.Path);
            RemoveSubFolders(oldFolder);
        }
    }

    foreach (var newFolder in other.SubFolders)
    {
        if (exist[newFolder.Path] == null)
        {
            _res.AddedFolders.Add(newFolder.Path);
            AddSubFolders(newFolder);
        }
        else
        {
            var oldFolder = exist[newFolder.Path];
            DiffBetween(oldFolder, newFolder);
        }
    }
}

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

Assert.IsTrue(result.AddedFiles.Contains(_files[4]));
Assert.IsTrue(result.AddedFiles.Contains(_files[5]));
Assert.IsTrue(result.AddedFiles.Contains(_files[6]));
Assert.IsTrue(result.AddedFiles.Contains(_files[7]));

Assert.IsTrue(result.RemovedFiles.Contains(_files[0]));
Assert.IsTrue(result.RemovedFiles.Contains(_files[1]));
Assert.IsTrue(result.RemovedFiles.Contains(_files[2]));
Assert.IsTrue(result.RemovedFiles.Contains(_files[8]));

Assert.IsTrue(result.AddedFolders.Contains(_folders[4]));
Assert.IsTrue(result.AddedFolders.Contains(_folders[5]));
Assert.IsTrue(result.AddedFolders.Contains(_folders[6]));

Assert.IsTrue(result.RemovedFolders.Contains(_folders[0]));
Assert.IsTrue(result.RemovedFolders.Contains(_folders[1]));
Assert.IsTrue(result.RemovedFolders.Contains(_folders[2]));

[Николай Богданов]

Wataru, да, все это члены класса (даже двух, один собирает дерево из файловой системы, сохраняет и восстанавливает, а другой — собственно класс Folder из изначального вопроса, в котором теперь вся логика по поиску и сравнению).

Предполагается такой сценарий — собираем дерево, сохраняем в файл, через некотрое время собираем новое дерево, читаем старое из файла и сравниваем, по результатам что-то делаем с добавленными и удаленными позициями.

Answer 2

[Виталий Качан]

Ну для меня алгоритм выглядит следующим:
- если рутовые Folder.Path не совпадают, то выбирается одно из деревьев и по все Subfolders ищется Folder.path другого дерева, если не найдено - меняются местами. Если по итогу не найдено - это разные не совпадающие деревья
- Если найден общий root - разница это добавленнные/удаленные папки и деревья.
- далее от общего рута сравниваются списки папок и файлов и рекурсивно (либо циклично) как обход дерева происходит сравнение все SubFolders

Comments

[Николай Богданов]

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