构建订购一棵树在C＃中的列表 [英] Building Ordering a tree as a list in C#

问题描述

我有C＃实体的名单。我的实体定义如下：

I have a list of C# entities. My entity is defined as follows:

public class Item
{
    // the id of an item
    public Guid ID { get; set; }

    // if this is a child item, the ParentID is the ID of the item that
    // this item is a child of
    public Guid? ParentID { get; set; }

    // If this item does not have a parent, this should be 0.
    // Otherwise if it is a child, a level=1
    // If it is a grandchild, level=2, etc.
    public int Level { get; set; }

    // The UTC date the item was created on.
    public DateTime CreateDate { get; set; }
}

我的这些实体的列表是一个随机的顺序。我试图找出如何整理我的实体名单，这样的项目元素由一级（升序）排序，然后CREATEDATE（升序）。从本质上讲名单是这样的：

My list of these entities is in a random order. I'm trying to figure out how to sort my list of entities such that the item elements are sorted by level (ascending) and then createDate (ascending). Essentially a list would look like this:

Item 1 (Level 0)
  Item 2 (Level 1)
    Item 3 (Level 2)
    Item 4 (Level 2)
  Item 5 (Level 1)
Item 6 (Level 0)
  Item 7 (Level 2)
etc.

这似乎很容易。也许我一直在寻找它太长。但是，我似乎可以得到它的工作。有任何想法吗？

This seems easy enough. Maybe I've been looking at it too long. But I can seem to get it to work. Any ideas?

推荐答案

即使你说，你想通过水平（升序）排序的项目，然后CREATEDATE（升序），你的图说除此以外。它看起来像你真正想要的方式，将允许您打印出一棵树，使得每个项目是它的父后其子及亲弟妹之前排序的项目。这是一个拓扑排序这是你问什么显着不同，但并不难：

Even though you said that you wanted the items sorted by level (ascending) and then createDate (ascending), your diagram says otherwise. It looks like you actually want the items sorted in a way that would allow you to print out a tree, such that each item is after its parent and before its children and its parents "younger siblings". This is a topological sort which is substantially different from what you asked for, but not that hard:

class ItemComparer : IComparer<Item>
{
    // allow us to look up parent Items by GUID
    IDictionary<Guid, Item> itemLookup;

    public ItemComparer(IEnumerable<Item> list)
    {
        itemLookup = list.ToDictionary(item => item.ID);
        foreach (var item in list)
            SetLevel(item);
    }

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

    public int Compare(Item x, Item 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)
        {
            x = itemLookup[x.ParentID.Value];
            y = itemLookup[y.ParentID.Value];
        }
        // compare createDate of children of common ancestor
        return x.CreateDate.CompareTo(y.CreateDate);
    }
}

调用它是这样的：

Invoke it like this:

// if List<Item>
items.Sort(new ItemComparer(items));
// if IEnumerable<Item>
var sorted = random.OrderBy(x => x, new ItemComparer(random));

这篇关于构建订购一棵树在C＃中的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！