LINQ sort a flat list based on childorder

Question

I am currently trying to figure out a good way to sort my elements with LINQ and C#, but I am kinda failing to do so.

For the problem let assume you have the following Table

---TempTable
ID (int)
ParentID (int)
Name (varchar)
SortOrder (int)

The ID and ParentID are related to each other and give me a self hierachical data structure. The root elements have a null in the ID Field. The SortOrder is only a portion of the whole table and based on the ParentID, so the elements that share the same ParentID do have 1, 2, 3 in it.

Lets further assume the following data:

ID = 1
ParentID = null
Name = Test 1
SortOrder = 1

ID = 2
ParentID = 1
Name = Test 2
SortOrder = 1

ID = 3
ParentID = 1
Name = Test 3
SortOrder = 2

ID = 4
ParentID = 2
Name = Test 4
SortOrder = 1

My desired flat list should have the following order:

Test 1 //root element with sort order 1 = very top
Test 2 //child element of root with sort order 1
Test 4 //child element of test 2 with sort order 1
Test 3 //child element of root with sort order 2

Also I like to get the object itself without only getting a portion of information threw the usage of select new ...

This is one of my failed tries:

from x in EntityModel.TempTables //DbSet<TempTable> by EntityFramework - which already holds all elements
   orderby x.SortOrder
   from y in x.TempTableChildren //Navigation Property by EntityFramework
   orderby y.SortOrder
   select y

Thanks in advance for your help.

Edit:

The order with the ParentID maybe helpfull, with the given TestData since the ID, ParentIDs are in perfect order but this isnt the case in a real live application since its data driven, someone could delete a entry create a new one and place it in a certain order under a parent and you would have something like :

ID = 193475037
ParentID = 2
Name = Test 192375937
SortOrder = 25

Now in the application it would be possible to move this one and the ParentID and SortOrder would change randomly to something like:

ID = 193475037
ParentID = 456798424
Name = Test 192375937
SortOrder = 4

To furhter explain the problem here is some code - how I would do it without 1 beautifull Linq Query but with 2 and some yield return:

public class LinqTestDemo
{
    Random rand = new Random();
    List<TempTable> list = new List<TempTable>();

    public List<TempTable> GetFlatData()
    {
        list = GetTestData();

        var rootElement = (from x in list
                            where x.ParentID == null
                            orderby x.SortOrder
                            select x).ToList();

        var flatList = OrderChilds(rootElement).ToList();

        foreach (var tempTable in flatList)
        {
            Console.WriteLine(string.Format("ID = {0} - ParentID = {1} - Name = {2} - SortOrder = {3}", tempTable.ID, tempTable.ParentID, tempTable.Name, tempTable.SortOrder));
        }

        return flatList;
    }

    private IEnumerable<TempTable> OrderChilds(List<TempTable> enumerable)
    {
        foreach (var tempTable in enumerable)
        {
            yield return tempTable;

            TempTable table = tempTable;
            var childs = OrderChilds((from x in list
                                        where x.ParentID == table.ID
                                        orderby x.SortOrder
                                        select x).ToList());

            foreach (var child in childs)
            {
                yield return child;
            }
        }
    }

    public List<TempTable> GetTestData()
    {
        var returnValue = new List<TempTable>();
        for (int i = 0; i < 50; i++)
        {
            var tempTable = new TempTable();
            tempTable.ID = i;
            if (i == 0)
                tempTable.ParentID = null;
            else
                tempTable.ParentID = rand.Next(0, i);

            var maxSortOrder = (from x in returnValue
                                where x.ParentID == tempTable.ParentID
                                select (int?)x.SortOrder).Max();

            if (maxSortOrder.HasValue)
                tempTable.SortOrder = maxSortOrder.Value + 1;
            else
                tempTable.SortOrder = 1;

            tempTable.Name = string.Format("Test {0:00}", i);
            returnValue.Add(tempTable);
        }

        return returnValue;
    }

    public class TempTable
    {
        public int ID { get; set; }
        public int? ParentID { get; set; }
        public string Name { get; set; }
        public int SortOrder { get; set; }
    }
}

@ Breadth-First vs Depth-First Traversal: After some reading I would say my desired result would be Depth-First Traversal, where the elements at the same level depth should be ordered by the property SortOrder.

Answer 1

  public lEnumerable<TempTable> GetList( int? parentID = null){

     foreach ( var item in Context.TempTables
        .Where( x => x.ParentID == parentID )
        .OrderBy( x=> x.SortOrder)
        .ToList() {

        yield return item;

        foreach( var child in GetList( item.ID))
        {
            yield return child;
        }

     }
  }


  var sortedList = GetList();

It is similar to your method but it is smaller & recursive. And works for many depth levels. I prefer calling ToList because it will close resultset before querying next query.

There is no way to do this in single query as of now.

With Single Query as Requested

Entity Framework will automatically fill all children.

 public IEnumerable<TempTable> PrepareList(IEnumerable<TempTable> list){
     list = list.OrderBy( x=> x.SortOrder);
     foreach(var item in list){
         yield return item;
         foreach(var child in PrepareList(item.ChildTempTables)){
             yield return child;
         }
     }
 }

 // since EF will automatically fill each children on fetch
 // all we need is just a top level nodes
 // which we will pass to PrepareList method
 var list = Context.TempTables.ToList().Where(x=> x.ParentID == null);
 var sortedList = PrepareList(list).ToList();

 // it is good to create list at the end if you are going to 
 // iterate it many times and logic will not change.

Answer 2

Here's a non-recursive version. It won't iterate again and again over the initial list. Instead it maintains a dictionary for the parent-to-children relationship and stores the current position of the ongoing pre-order tree traversal in enumerators.

public static IEnumerable<TempTable> PreorderForest(IEnumerable<TempTable> list)
{
    var nodesByParent = list.GroupBy(x => x.ParentID.GetValueOrDefault(-1))
        .ToDictionary(xs => xs.Key, 
                      xs => xs.OrderBy(x => x.SortOrder).GetEnumerator());

    var stack = new Stack<IEnumerator<TempTable>>();
    stack.Push(nodesByParent[-1]);

    while (stack.Count > 0)
    {
        var nodes = stack.Peek();
        if (nodes.MoveNext())
        {
            yield return nodes.Current;
            IEnumerator<TempTable> children;
            if (nodesByParent.TryGetValue(nodes.Current.ID, out children))
                stack.Push(children);
        }
        else
            stack.Pop();
    }
}