IComparer logic sort of hierachy structure to a flat list

Question

I am currently developing a IComparer and its working fine for simple properties that are int and string, also the asending and descending is working, but I am facing a problem with a datastructure thats hierarchical.

Lets assume you have the following table in your database:

HierarchyTable
    ID, int
    Name, string
    SortOrder, int
    ParentID, int

The HierarchyTable is has a relation between ID and ParentID to build up a self referencing relation, that builds our hierarchy.

Now the problem starts with my SortOrder. The SortOrder isnt a unique int that is representing the sortorder for the whole level, instead it only stores the sortorder of the current level you are in.

Lets assume the following data:

ID --- Name --- SortOrder --- ParentID
1  --- A    --- 0         --- null
2  --- B    --- 1         --- 4
3  --- C    --- 2         --- 1
4  --- D    --- 1         --- 1
5  --- E    --- 1         --- 3

This would result in the following hierarchy:

ID --- Name --- SortOrder --- ParentID
1  --- A    --- 0         --- null
    4  --- D    --- 1         --- 1
        2  --- B    --- 1         --- 4
    3  --- C    --- 2         --- 1
        5  --- E    --- 1         --- 3

Now I wish to have this hierarchy in a flat list, with the help of an IComparer and a List that just calls the Sort method and voila here is a correct sorted flat list.

This table structure is in my Entity Framework application and represenst one of entities, so if I need to I could extend this with other properties.

The Entity for this simple example would look something like this:

public class HierarchyTable
{
    public int ID { get; set; }
    public string Name { get; set; }
    public int SortOrder { get; set; }
    public in ParentID { get; set; }

    //Navigation Properties created by Entity Framework
    public virtual HierarchyTable Parent { get; set; }
    public virtual ICollection<HierarchyTable> Children { get; set; }
}

Answer 1

Your comparer needs lists of SortOrders, following the entire ancestor chain for each record (parent, child, grandchild...). Like this:

ID --- Name --- SortOrder --- ParentID --- HierarchicalSortOrder
1  --- A    --- 0         --- null     --- 0
2  --- B    --- 1         --- 4        --- 0,1,1
3  --- C    --- 2         --- 1        --- 0,2
4  --- D    --- 1         --- 1        --- 0,1
5  --- E    --- 1         --- 3        --- 0,2,1

Then you can simply sort on HierarchicalSortOrder:

1 --- 0
4 --- 0,1
2 --- 0,1,1
3 --- 0,2
5 --- 0,2,1

The following function constructs this HierarchicalSortOrder:

public string GetHierarchicalSortOrder(HierarchyTable element)
{
   List<int> sortOrders = new List<int>() {element.SortOrder};

   while (element.Parent != null)
   {
      element = element.Parent;
      sortOrders.Insert(0, element);
   }
   return String.Join(",", sortOrders);
}

For simplicity, I assumed there are no ties in the sort order; if there are, you should also include element.ID in the list, otherwise children will become attached to the wrong parents.