Difficult hierarchical Sorting

Question

I have run into a very difficult sorting issue and I'm wondering if anyone out there can help me figure this out. Basically I have an SQL table full of the following information:

ID (The comment's Unique Identifier)

Previous ID (The ID of the comment that is being replied to with this comment)

Position (The position of how "deep" the comment is, a post directly on a 
page would be "1" a reply to that "2", etc.

Is it possible with this information to sort using C#/LINQ in such a way that it will be returned in the proper order when called?

An example might be the following:

ID | Position | PreviousID | Message|

1  | 1        | 0          | Hello
2  | 1        | 0          | How
3  | 2        | 1          | There!
4  | 2        | 2          | Are
5  | 3        | 4          | You?

Would be sorted into the following order:

1. Hello
2. There!
3. How
4. Are
5. You?

I am having trouble wrapping my head around how this would be done or if it is even possible, so I would greatly appreciate even just a nudge in the right direction, thanks!

And just for some more info, this is an existing table with plenty of content that cannot be erased, I just need to find a way to sort it in this way.

Answer 1

LINQ can model this with Hierarchical Joins

here is an example of Recursive Hierarchical Joins in C# and LINQ and gives a simple walk through that does what you want.

The keys are slightly different but you should be able to map onto the example.

Answer 2

This is more of a tree traversal problem then a sorting problem.

Here is what I is recommend:

static IEnumerable<T> PreOrderTraverse<T>(IEnumerable<T> nodes, Func<T, IEnumerable<T>> childrenSelector)
{
    foreach (var node in nodes)
    {
        yield return node;

        foreach (var descendant in PreOrderTraverse(childrenSelector(node), childrenSelector))
        {
            yield return descendant;
        }
    }
}

static void Main(string[] args)
{
    /* Some code to load comments*/

    var children = comments.ToLookup(c => c.PreviousID);

    var result = PreOrderTraverse(children[0], c => children[c.ID]);

    foreach (var comment in result)
    {
        Console.WriteLine(comment.Message);
    }
}