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.

Answer 2

You should first flatten the structure with level numbers and then order by the levelNo+SeqNo
See the answer for my previous question: Flatten (with level numbers) a hierarchical list

Answer 3

Here is an extended version of your HierarchyTable class that gets you pretty close to what you're looking for. Basically it just adds the following.

• a ToString() method
• a static HierarchicalSort() method that sorts ICollection<HierarchyTable>.
• a static GetNextNode() method that that is used in the creating the HierarchicalSort.

The HierarchicalSort sort method creates both the hierarchy and the sort but only returns the sort. The hierarchy is just left behind so splitting it into two methods might be a good idea. When the function returns, the topNode variable contains the hierarchical data.

There was no real reason to use a custom IComparer because you're only really sorting on SortOrder in your example. You could easily extend it if you need to though.

public class HierarchyTable {
    public HierarchyTable(HierarchyTable parent) {
        Parent = parent;
        Children = new List<HierarchyTable>();
    }

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

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

    public override string ToString() {
        StringBuilder sb = new StringBuilder();

        sb.Append("ID: " + ID).Append('\t');
        sb.Append("Name: " + Name).Append('\t');
        sb.Append("SortOrder: " + SortOrder).Append('\t');
        sb.Append("ParentID: " + ParentID);

        return sb.ToString();
    }

    //-----------------------------------------------------
    // Builds a hierarchical tree out of a List<HierarchyTable>
    // and copies each child row into a different 
    // List<HierarchyTable> as it is being built.
    //-----------------------------------------------------
    public static List<HierarchyTable> HierarchicalSort(ICollection<HierarchyTable> inputlist) {

        HierarchyTable topNode = inputlist.ElementAt(0);
        HierarchyTable current = topNode;
        HierarchyTable child = null;

        inputlist.Remove(topNode);

        List<HierarchyTable> copyList = inputlist.Take(inputlist.Count).ToList();
        List<HierarchyTable> outputList = new List<HierarchyTable>() { topNode };

        foreach (HierarchyTable rec in inputlist) {
            do {                    
                child = GetNextNode(current, copyList);

                if (child != null) {
                    child.Parent = current;
                    current.Children.Add(child);
                    current = child;
                    copyList.Remove(child);
                    outputList.Add(child);
                }

            } while (child != null);

            current = topNode;
        }

        return outputList;
    }

    //-----------------------------------------------------
    // Returns the first child of a sorted match on 
    // ID == ParentID. If you end up needing to sort on 
    // multiple columns or objects that don't already 
    // implement IComparer, then make your own comparer
    // class. The syntax would be:
    //
    // .OrderBy(x => x, new ComparerClass());
    //-----------------------------------------------------
    private static HierarchyTable GetNextNode(HierarchyTable current, ICollection<HierarchyTable> inputlist) {

        List<HierarchyTable> sublist = inputlist
            .Where(
                a => a.ParentID == current.ID
            ).OrderBy(
                x => x.SortOrder
            ).ToList();

        if(sublist.Count > 0)
            return sublist.First();

        return null;
    }
}

Sample Usage:

    List<HierarchyTable> htable = new List<HierarchyTable>(){
        new HierarchyTable() {ID = 1, Name = "A", SortOrder = 0, ParentID = 0},
        new HierarchyTable() {ID = 2, Name = "B", SortOrder = 1, ParentID = 4},
        new HierarchyTable() {ID = 3, Name = "C", SortOrder = 2, ParentID = 1},
        new HierarchyTable() {ID = 4, Name = "D", SortOrder = 1, ParentID = 1},
        new HierarchyTable() {ID = 5, Name = "E", SortOrder = 1, ParentID = 3}
    };

    List<HierarchyTable> sorted = HierarchyTable.HierarchicalSort(htable);

    foreach (HierarchyTable ht in sorted)
        Console.WriteLine(ht);

Console:

---

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

Good luck. I hope this helps.

UPDATE

Another approach would be to go ahead and flatten the hierarchy into a list and then call the sort method using an IComparer similar to this.

public class HierarchyTableComparer : IComparer<HierarchyTable> {
    public int Compare(HierarchyTable a, HierarchyTable b) {
        int comp = 0;

        if ((comp = a.SortOrder.CompareTo(b.SortOrder)) != 0) {
            return comp;
        }
        else if ((comp = a.ID.CompareTo(b.ParentID)) != 0) {
            return comp;
        }
        else {
            return 0;
        }
    }
}

If the framework does the initial job of linking the hierarchical elements, then traditional sorting works because the list will already be sorted by levels.

Sample Usage :

//----------------------------------------------------
// Flattened Hierarchy
//----------------------------------------------------
List<HierarchyTable> htable = new List<HierarchyTable>(){
    new HierarchyTable() {ID = 1, Name = "A", SortOrder = 0, ParentID = 0},
    new HierarchyTable() {ID = 4, Name = "D", SortOrder = 1, ParentID = 1},
    new HierarchyTable() {ID = 2, Name = "B", SortOrder = 1, ParentID = 4},
    new HierarchyTable() {ID = 3, Name = "C", SortOrder = 2, ParentID = 1},
    new HierarchyTable() {ID = 5, Name = "E", SortOrder = 1, ParentID = 3}
};

htable.Sort(new HierarchyTableComparer());

foreach (HierarchyTable ht in htable)
    Console.WriteLine(ht);

Console:

---

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

Answer 4

How about just using a recursive sort inside your HierarchyTable class. This is typically how I would navigate through an abstract syntax tree. If you plan on doing a variety of things with the HierarchyTable and you want minimal modifying of the class, then using the Visitor design pattern is probably your best choice. It is the de facto pattern to use when dealing with hierarchical node structures. Once implemented, it lets you add traversal-dependent functions to a tree node without changing the node's class at all.

I'd be happy to demonstrate how it's implemented if you haven't used it yet, just ask. I don't want to go too far down the wrong path for your question, again. :)

If you're interested, these wikis give a good overview of visitor pattern usage:

• Visitor Pattern
• Hierarchical Visitor Pattern

Essentially the standard pattern is best when you want to interrogate each node and the hierarchical pattern is best when you want to quickly short-circuit some of the nodes instead of wasting time. They both work on hierarchical data so I really don't like the naming distinction.

Anyhow, here is the recursive sort working from within the HierarchyTable class using an IComparer. Using these techniques also lets you start your sort from any level in a hierarchy.

    public List<HierarchyTable> FlatSort(IComparer<HierarchyTable> comparer) {
        List<HierarchyTable> sorted = new List<HierarchyTable>(){
            this   
        };

        if (Children.Count > 0) {
            //------------------------------------------------
            // Create sorted copy of children using IComparer
            //------------------------------------------------
            List<HierarchyTable> children = Children.ToList();
            children.Sort(comparer);

            foreach (HierarchyTable child in children)
                sorted.AddRange(child.FlatSort(comparer));
        }

        return sorted;
    }

    public class HierarchyTableComparer : IComparer<HierarchyTable> {
        public int Compare(HierarchyTable a, HierarchyTable b) {
            int comp = 0;

            if ((comp = a.SortOrder.CompareTo(b.SortOrder)) != 0) {
                return comp;
            }
            else {
                return 0;
            }
        }
    }

Sample Usage :

    List<HierarchyTable> flatsort = hierarchyTableInstance.FlatSort(new HierarchyTableComparer());

    foreach (HierarchyTable item in flatsort)
        Console.WriteLine(item);