Ordering a self-referencing hierarchy in LINQ

Question

I have a class called NavigationElement that looks like this

public class NavigationElement
{
  public int Id { get; set; }
  public string Title { get; set; }
  public string Link { get; set; }
  public int SortOrder { get; set; }
  public bool Visible { get; set; }
  public int? ParentId { get; set; }

  public virtual ICollection<NavigationElement> Children { get; set; }
  public virtual NavigationElement Parent { get; set; }

  public NavigationElement()
  {
    Children = new List<NavigationElement>();
  }
}

As you can see, the class is self referencing. From that, I am creating a site navigation menu with drop downs (hierarchy in play).

I am struggling in the ordering of the items. I want the top-level items to be ordered by the SortOrder property, but everything underneath, I would like ordered alphabetically by the Title property.

Here is why I have done so far.

var orderedModel = unorderedModel.OrderBy(x => x.SortOrder).ThenBy(x => x.Children.OrderBy(y => y.Title).ThenBy(z => z.Children.OrderBy(a => a.Title))).ToList();

unorderedModel is of type List<NavigationElementModel>.

This is compiling, but I get an error when I run the code. The error says:

At least one object must implement IComparable.

What is `unorderedModel` - list of root elements or flat list with all elements? — Ivan Stoev, Mar 18 '16 at 13:28
You can't use orderby if your class `NavigationElement` doesn't impletemnt IComparable since, well, it can't compare, thus it can't order — Thomas Ayoub, Mar 18 '16 at 13:34
That was kind of obvious. The question was if it contains **all** elements or only **root** elements? — Ivan Stoev, Mar 18 '16 at 13:34
It would contain all, but they'll be in a hierarchy. for example `Service` > `Cleaning` > `Bin Cleaning`. For its `ParentId`, `Cleaning` will have the `Id` of `Service` — J86, Mar 18 '16 at 13:35
@SurfinBird no, `SortOrder` is left as 0 for anything that isn't Top Level. That is why I want those sorted alphabetically. — J86, Mar 18 '16 at 13:38

Maksim Simkin · Accepted Answer · 2017-01-08T09:26:31.120

You should just go recursive through all children elements and sort it.

Somehting like:

var ordered = unorderedModel.OrderBy(x=>x.SortOrder).ToList();
ordered.ForEach(OrderChildren);

public void OrderChildren(NavigationElement el)
{
    el.Children = el.Children.OrderBy(x => x.Title).ToList();
    if (el.Children != null)
    {
        foreach (var c in el.Children)
        {
            OrderChildren(c);
        }
    }
}

score 0 · Answer 2 · answered Mar 18 '16 at 13:49

What about something like this?

public static class LinqExtension {
   public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector) {
       if (source == null) throw new ArgumentNullException("source");

       foreach (var i in source) {
           yield return i;

           var children = childrenSelector(i);
           if (children == null) continue;

           foreach (var child in SelectManyRecursive(children, childrenSelector)) {
               yield return child;
           }
       }
   }
}

var orderedModel = unorderedModel
        .OrderBy(x => x.SortOrder)
        .SelectMany(x => new[] { x }.Union(
                x.Children.SelectManyRecursive(y => y.Children)
                        .OrderBy(y => y.Parent.Title) // considering hierarchy
                        .ThenBy(y => y.Title)
                ))
        .ToList();

score 0 · Answer 3 · edited May 23 '17 at 12:16

I will utilize the approach from Sort hierarchy with path and depth fields using Linq for your case.

First, the general tree traversal helper from my answer to How to flatten tree via LINQ?:

public static partial class TreeUtils
{
    public static IEnumerable<T> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = source.GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var elements = elementSelector(item);
                    if (elements == null) continue;
                    stack.Push(e);
                    e = elements.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }
}

And the solution of your particular problem:

var orderedModel = unorderedModel.Where(item => item.Parent == null).OrderBy(item => item.SortOrder)
    .Expand(item => item.Children != null && item.Children.Any() ? item.Children.OrderBy(child => child.Title) : null)
    .ToList();

Ordering a self-referencing hierarchy in LINQ

3 Answers3

Linked