Комплексная сортировка LINQ с группами

Question

Я пытаюсь отсортировать список элементов в соответствии со следующими (упрощенными) правилами:

У каждого предмета есть следующие свойства:

 Id (int), 
 ParentId (int?), 
 Name (string)

ParentID является самостоятельным присоединением ForeignKey к Id. Если у элемента есть ParentId, родительский объект также будет присутствовать в списке.

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

Так что, если бы у меня было следующее:

 Id: 1, ParentId: null, Name: Pi
 Id: 2, ParentId: null, Name: Gamma
 Id: 11, ParentId: 1, Name: Charlie
 Id: 12, ParentId: 1, Name: Beta
 Id: 21, ParentId: 2, Name: Alpha
 Id: 22, ParentId: 2, Name: Omega

Тогда я бы хотел, чтобы они были отсортированы следующим образом:

Идентификаторы: 2, 21, 22, 1, 12, 11

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

var sortedItems = itemsToSort.OrderBy(x=> x.Name).GroupBy(x=> x.ParentId);

Мой стартовый план был следующим: (в нерабочем коде)

var finalCollection = new List<Item>

var parentGroup = sortedItems.Where(si => si.Key == null);

foreach(parent in parentGroup)
{
   finalCollection.Add(parent);
   foreach(child in sortedItems.Where(si => si.Key == parent.Id)
   {
      finalCollection.Add(child);
   }
}

Однако parentGroup не

 IEnumerable<Item> 

так что это не работает.

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

Answer 1

Как я понимаю ваш вопрос, вы хотите упорядочить результаты по имени родителя (если это родитель), а затем по имени ребенка (если это ребенок), но вы хотите, чтобы все дети появлялись в списке после их соответствующего родителя.

Это должно помочь:

Обновлено для решения проблемы, упомянутой @Martin Liversage.

var query = from item in itemsToSort
            let parent = itemsToSort.Where(i => i.Id == item.ParentId).FirstOrDefault()
            //get the name of the item's parent, or the item itself if it is a parent
            let parentName = (parent != null) ? parent.Name : item.Name
            //get the name of the child (use null if the item isn't a child)
            let childName = (parent != null) ? item.Name : null
            orderby parentName, childName
            select item;

var finalCollection = query.ToList();

Вот вывод:

Answer 2

Если у вас есть только два уровня, вы можете сделать это так:

var lookup = itemsToSort.OrderBy(x => x.Name).ToLookup(x => x.ParentId, x => x);
var parents = lookup[null];
var sortedItems = parents.SelectMany(x => new[] { x }.Concat(lookup[x.Id]));

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

Затем создается таблица поиска, позволяющая искать по ParentId. Затем родители, у которых есть null ParentId, объединяются со своими детьми, используя SelectMany, и таблица поиска используется для поиска детей. Родитель вставляется перед потомками, чтобы получить желаемую последовательность.

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

IEnumerable<Item> GetSubtreeForParent(Item parent, ILookup<Int32?, Item> lookup) {
  yield return parent;
  foreach (var child in lookup[parent.Id])
    foreach (var descendant in GetSubtreeForParent(child, lookup))
      yield return descendant;
}

Код почти такой же, как в простом случае выше:

var lookup = itemsToSort.OrderBy(x => x.Name).ToLookup(x => x.ParentId, x => x);
var parents = lookup[null];
var sortedItems = parents.SelectMany(x => GetSubtreeForParent(x, lookup));

Используя рекурсивную лямбду, вы даже можете делать все это "inline":

var lookup = itemsToSort.OrderBy(x => x.Name).ToLookup(x => x.ParentId, x => x);
// Declare Func to allow recursion.
Func<Int32?, IEnumerable<Item>> getSubTreeForParent = null;
getSubTreeForParent =
  id => lookup[id].SelectMany(x => new[] { x }.Concat(getSubTreeForParent(x.Id)));
var sortedItems = getSubTreeForParent(null);

Answer 3

Я бы пошел с ответом DoctaJonez для 2 уровня.

Он может быть расширен до n уровней, например:

Func<int?,Item> lookup = id => list.Where(i => i.Id == id).FirstOrDefault();

Func<Item,string> makeSortString = null;
makeSortString = i => i.ParentId == null ? i.Name : makeSortString(lookup(i.ParentId)) + i.Name;

list.OrderBy(makeSortString).ToList();

Answer 4

Этого можно добиться, используя:

list.Select(i => 
      new {Parent=list.Where(x => x.Id == i.ParentId).FirstOrDefault(), Item = i})
    .OrderBy(i => i.Parent == null ? i.Item.Name : i.Parent.Name + i.Item.Name)
    .Select(i => i.Item)

Пример в реальном времени: http://rextester.com/rundotnet?code=WMEZ40628

Выход:

2
21
22
1
12
11

Answer 5

Как насчет этого?

var lookup = items.ToLookup(x => x.ParentId);

Func<int?, IEnumerable<Item>> f =  null;
f = ni =>
    from a in lookup[ni].OrderBy(x => x.Name)
    from b in (new [] { a }).Concat(f(a.Id))
    select b;

А затем, чтобы получить отсортированный список, сделайте следующее:

var sorted = f(null);

Simple. : -)

Answer 6

Это

var parentGroup = sortedItems.Where(si => si.Key == null).ToList()

сделает parentGroup IEnumerable<Item>.

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