Sorting issue within a hierarchy of elements in C#

Question

I've been working on a page in ASP.NET. This page behaves exactly like a forum. A user can reply to entries. A reply is represented as an ItemReply. When a user replys to an item, the ParentID is set to the ID of the ItemReply the user is responding to.

public class ItemReply
{
    public Guid ID { get; set; }    
    public Guid? ParentID { get; set; }
    public int Level { get; set; }    
    public string Remarks { get; set; }    
    public DateTime CreatedOn { get; set; }    
    public string CreatedBy { get; set; }

    public ItemReply(DataRow row)
    {
        ID = GetGuidFromRow(row, "ID", 0);
        ParentID = GetGuidFromRow(row, "ParentID", null);
        Remarks = GetStringFromRow(row, "Remarks", string.Empty);
        Level = 1;

        CreatedOn = GetDateTimeFromRow(row, "CreatedOn", DateTime.UtcNow);
        CreatedBy = GetStringFromRow(row, "CreatedBy", string.Empty);
    }
}

public class ItemComparer : IComparer<ItemReply>
{
    IDictionary<Guid, ItemReply> itemLookup;
    public ReplyComparer(IEnumerable<ItemReply> list)
    {
        itemLookup = list.ToDictionary(item => item.ID);
        foreach (var item in list)
            SetLevel(item);
    }

    public int SetLevel(ItemReplyitem)
    {
        if (item.Level == 0 && item.ParentID.HasValue)
            item.Level = 1 + itemLookup[item.ParentID.Value].Level;
        return item.Level;
    }

    public int Compare(ItemReply x, ItemReply y)
    {
        // see if x is a child of y
        while (x.Level > y.Level)
        {
            if (x.ParentID == y.ID)
                return 1;
            x = itemLookup[x.ParentID.Value];
        }

        // see if y is a child of x
        while (y.Level > x.Level)
        {
            if (y.ParentID == x.ID)
                return -1;
            y = itemLookup[y.ParentID.Value];
        }

        // x and y are not parent-child, so find common ancestor
        while (x.ParentID != y.ParentID)
        {
            if (x.ParentID.HasValue)
                x = itemLookup[x.ParentID.Value];
            if (y.ParentID.HasValue)
                y = itemLookup[y.ParentID.Value];
        }

        // compare createDate of children of common ancestor
        return x.CreatedOn.CompareTo(y.CreatedOn);
    }
}

This code is basically executed via:

List<ItemReply> replies = GetRepliesFromDataSource();
replies.Sort(new ReplyComparer(replies));

The order and hierarchy seems to be working properly. However, The SetLevel method is not working correctly. The purpose of the SetLevel is used to basically determine how far to indent a reply from a UI perspective. To demonstrate, imagine having the following hierarchy:

- Root
-- Child 1
--- Grandchild A
--- Grandchild B
-- Child 2      
--- Grandchild C

For some reason, all of my ItemReply elements have a Level of 1. What am I doing wrong?

Thank you!

Answer 1

For some reason, all of my ItemReply elements have a Level of 1. What am I doing wrong?

Your SetLevel method is not correct since it relies on a particular enumeration order for its correctness - parents must be processed before their children. Unfortunately, there's nothing to suggest that the list you've got there guarantees such an order.

What if an item's parent hasn't had its level set when SetLevel is called on it? Then your method would assign a Level of 1 + 0 instead of 1 + Parent's Actual Level.

This is easily fixed with a recursive call:

public int SetLevel(ItemReply item)
{
    if (item.Level == 0 && item.ParentID.HasValue)
        item.Level = 1 + SetLevel(itemLookup[item.ParentID.Value]);

    return item.Level;
}

This ensures that SetLevel never works with an uninitialized value for its parent's level.