C# 中元素层次结构内的排序问题

Question

我一直在 ASP.NET 中开发一个页面。该页面的行为与论坛完全相同。用户可以回复条目。回复表示为 ItemReply。当用户回复某个项目时，ParentID 将设置为用户正在回复的 ItemReply 的 ID。

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);
    }
}

该代码基本上是通过以下方式执行的：

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

顺序和层次结构似乎工作正常。但是，SetLevel 方法无法正常工作。 SetLevel 的目的主要是用于从 UI 角度确定回复缩进多远。为了进行演示，想象一下具有以下层次结构：

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

出于某种原因，我的所有 ItemReply 元素的级别均为 1。我做错了什么？

谢谢你！

Answer 1

由于某种原因，我的所有 ItemReply 元素的级别均为 1。什么
我做错了吗？

您的 SetLevel 方法不正确，因为它依赖于特定的枚举顺序来保证其正确性 - 必须在子级之前处理父级。不幸的是，没有任何迹象表明您那里的列表可以保证这样的顺序。

如果在调用 SetLevel 时，某个项目的父项尚未设置其级别，该怎么办？然后，您的方法将分配 Level 为 1 + 0，而不是 1 + Parent's Actual Level。

通过递归调用可以轻松修复此问题：

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

    return item.Level;
}

这可确保 SetLevel 永远不会使用其父级级别的未初始化值。