Сортировка списка папок по вложенности

#c_sharp #wpf #сортировка

Есть список директорий (просто строки), которые необходимо отсортировать. Например:
C:\Program Files\Microsoft
C:\Program Files (x86)
C:\Program Files  

Стандартная сортировка:
C:\Program Files
C:\Program Files (x86)
C:\Program Files\Microsoft  

Надо чтобы список сортировался в порядке вложенности папок:
C:\Program Files
C:\Program Files\Microsoft
C:\Program Files (x86)  

В действительности пути хранятся в ObservableCollection Pathes где
AnalyseObject класс:  

public class AnalyseObject
{
    public ObjectType Type { get; set; } //enum: диск / папка / файл
    public string Path { get;  set; } //содержит выше приведенные значения
    public bool IsAnalyzed { get ; set; } //true - анализировать, false - нет
}  


Коллекция привязана к таблице на форме (WPF) с помощью:

xmlns:scm="clr-namespace:System.ComponentModel;assembly=WindowsBase"


    
        
    
  


Каким образом можно добиться такой сортировки?  
    

Ответы

Ответ 1

Пошел по другому пути. Дополнил класс AnalyseObject:  

public class AnalyseObject : IComparable
{
    public ObjectType Type { get; set; } //enum: диск / папка / файл
    public string Path { get;  set; } //содержит выше приведенные значения
    public bool IsAnalyzed { get ; set; } //true - анализировать, false - нет

    public int CompareTo(AnalyseObject other)
    {
        if (this.Path == other.Path)
            return 0;

        int thisPathLength = this.Path.Length;
        int otherPathLength = other.Path.Length;
        int maxIndex = Math.Min(thisPathLength - 1, otherPathLength - 1);
        for (int i = 0; i <= maxIndex; i++)
        {
            if (this.Path[i] == other.Path[i]) continue;
            if (this.Path[i] == '\\') return -1;
            if (other.Path[i] == '\\') return 1;
            return this.Path[i] < other.Path[i] ? -1 : 1;
        }
        return thisPathLength < otherPathLength ? -1 : 1;
    }
}  


Добавил:  

public static class ObservableCollection
{
    public static void Sort(this ObservableCollection source,
Func keySelector, bool byDescending = false)
    {
        if (!byDescending)
        {
            List sortedList = source.OrderBy(keySelector).ToList();
            source.Clear();
            foreach (var sortedItem in sortedList)
            {
                source.Add(sortedItem);
            }
        }
        else
        {
            List sortedList = source.OrderByDescending(keySelector).ToList();
            source.Clear();
            foreach (var sortedItem in sortedList)
            {
                source.Add(sortedItem);
            }
        }
    }
}


Сортировку провожу принудительно:  

Pathes.Sort(p => p);


Наверно далеко не самый оптимальный вариант, но вроде работает как надо. Буду признателен
если кто-то предложит вариант лучше.


Ответ 2

В первом приближении я бы сделал как-то так:

Возьмем отсюда метод EnumerateParts и напишем на его основе компарер:

class PathComparer : IComparer
{
    public int Compare(string x, string y)
    {
        var xParts = EnumerateParts(x).Reverse().ToList();
        var yParts = EnumerateParts(y).Reverse().ToList();
        for (int i = 0; i < xParts.Count && i < yParts.Count; ++i)
        {
            var c = string.Compare(xParts[i], yParts[i]);
            if (c != 0) return c;
        }
        return xParts.Count.CompareTo(yParts.Count);
    }

    IEnumerable EnumerateParts(string path)
    {
        var root = Path.GetPathRoot(path);
        while (path != root)
        {
            yield return Path.GetFileName(path);
            path = Path.GetDirectoryName(path);
        }
        yield return root;
    }
}


Теперь можно пользоваться так:

var source = new[]
{
    @"C:\Program Files\Microsoft",
    @"C:\Program Files (x86)",
    @"C:\Program Files"
};
foreach (var p in source.OrderBy(s => s, new PathComparer()))
    Console.WriteLine(p);


Работает как надо, но если поставить брейкпоинт в EnumerateParts, то можно подсчитать,
что для 3х строк он вызывается аж 10 раз, что может быть очень неэффективно, поэтому
я бы переписал код так, чтобы EnumerateParts вызывался только один раз для каждой строки.
Например:

class PathParts : IComparable
{
    readonly List parts;

    public PathParts(string path)
    {
        parts = EnumerateParts(path).Reverse().ToList();
    }

    public int CompareTo(PathParts other)
    {
        for (int i = 0; i < parts.Count && i < other.parts.Count; ++i)
        {
            var c = string.Compare(parts[i], other.parts[i]);
            if (c != 0) return c;
        }
        return parts.Count.CompareTo(other.parts.Count);
    }

    IEnumerable EnumerateParts(string path)
    {
        var root = Path.GetPathRoot(path);
        while (path != root)
        {
            yield return Path.GetFileName(path);
            path = Path.GetDirectoryName(path);
        }
        yield return root;
    }
}


и теперь:

var source = new[]
{
    @"C:\Program Files\Microsoft",
    @"C:\Program Files (x86)",
    @"C:\Program Files"
};
var ordered = source.Select(s => new { s, pp = new PathParts(s) })
                    .OrderBy(a => a.pp)
                    .Select(a => a.s);
foreach (var p in ordered)
    Console.WriteLine(p);


Ну и теперь можете сделать PathParts вложенным приватным классом в своем AnalyseObject,
также создавать экземпляр PathParts один раз при создании и потом выставить метод:

public int CompareTo(AnalyseObject other) => pathParts.CompareTo(other.pathParts);


Ответ 3

Я буду считать, что вы знаете как получить список директорий (см. вопросы типа такого),
поэтому сосредоточусь только на построении linq-запроса, который отсортирует вашу коллекцию. 

Мои тестовые данные будут такие:

private IEnumerable GetDirectoriesStub()
{
    return new string[]
    {
         @"C:\Documents and Settings"
        ,@"C:\Program Files"
        ,@"C:\Program Files (x86)"
        ,@"C:\Users"
        ,@"C:\Windows"
        ,@"C:\git\gitlab.com"
        ,@"C:\Program Files\Common Files"
        ,@"C:\git\github.com"
        ,@"C:\Program Files\dotnet"
        ,@"C:\Program Files\Git"
        ,@"C:\Program Files\Git\bin"
        ,@"C:\Program Files\Git\dev\shm"
        ,@"C:\git"
        ,@"C:\Program Files\nodejs"
        ,@"C:\Program Files\Git\dev\mqueue"
    };
}   


В первую очередь я посчитаю в каждой строке количество символов \. Чем больше будет
таких символов, тем глубже будет лежать папка, тем больше её level:

var paths = this.GetDirectoriesStub();

paths.Select(x => new { Path = x, Level = x.Count(y => y == '\\')} )
     .Dump();


Получаем следующий набор данных:



Теперь сортируем нужным нам образом. Судя по озвученнм условиям, надо во-первых отсортировать
по уровню вложенности, а во-вторых — по имени папки:

paths.Select(x => new { Path = x, Level = x.Count(y => y == '\\') })
     .OrderBy(x => x.Level)
     .ThenBy(x => x.Path)
     .Dump();


Получается так:



Что-то некрасиво. Попробуем поменять сортировку: сначала по x.Path, потом по x.Level:



Кажется, так гораздо логичнее и понятнее.



Update


  Очень близко, но не совсем то. Обратите внимание на "C:\Program Files
  (x86)", который расположен между "C:\Program Files" и "C:\Program
  Files\Common Files". А по логике он должен выводиться после всех
  вложенных в "C:\Program Files"


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

Добавим немного магии с весовыми коэффициентами:

paths.Select(x => new { 
        Path = x, 
        PathForSorting = (x + '\x01').Replace('\\', '\x02'), 
        Level = x.Count(y => y == '\\') })
     .OrderBy(x => x.PathForSorting)
     .ThenBy(x => x.Path)
     .ThenBy(x => x.Level)
     .Dump();




В принципе, работает и если убрать .Replace('\\', '\x02') - но для надёжности оставил
полный вариант. (В полном варианте можно будет ещё некоторые дополнительные условия
учесть, если понадобится)

paths.Select(x => new { 
        Path = x, 
        PathForSorting = (x + '\x01'),//.Replace('\\', '\x02'), 
        Level = x.Count(y => y == '\\') })
     .OrderBy(x => x.PathForSorting)
     .ThenBy(x => x.Path)
     .ThenBy(x => x.Level)
     .Dump();




Пояснение магии. Зачем был введён первый символ? Чтобы гарантированно различать кто
является родителем, а кто потомком. Если ранее достаточно было считать, что "у кого
длина строки меньше - тот и выше в сортировке / иерархии", то с учётом примера уже
нужно определять точнее.

Второй символ я ввёл исключительно для наглядности, выбрав его больше, чем символ1.
Неявно правило сортировки "\x01 показывать выше \x02" звучит как "родительская папка
(это у нас символ \x01) располагать выше любых вложенных в неё папок (это символ 2)".
Это правило избыточно и введено только для наглядности, чтобы можно было вербализировать
это правило (явное лучше неявного).

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

Причин тут две. 

Во-первых, некоторая неочевидность алгоритма (магия). 

Во-вторых, вполне возможно, что у вас в именах директорий встретятся символы ниже
пробельного (всякие кривые папки) и в реальном приложении лучше избегать таких хаков.
Оно вам надо, чтобы пользователи программы предпочли другое ПО, которое не будет глючить
даже в случае некорректных папок на диске? )