Building Ordering a tree as a list in 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; }
}

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?

---

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

---

Here's an alternative answer that builds a tree from the input and then traverses it in order. This traversal gives you sorted output.

class FlattenTree
{
    // map each item to its children
    ILookup<Item, Item> mapping;

    public FlattenTree(IEnumerable<Item> list)
    {
        var itemLookup = list.ToDictionary(item => item.ID);
        mapping = list.Where(i => i.ParentID.HasValue)
                      .ToLookup(i => itemLookup[i.ParentID.Value]);
    }

    IEnumerable<Item> YieldItemAndChildren(Item node)
    {
        yield return node;
        foreach (var child in mapping[node].OrderBy(i => i.CreateDate))
            foreach (var grandchild in YieldItemAndChildren(child))
                yield return grandchild;
    }

    public IEnumerable<Item> Sort()
    {
        return from grouping in mapping
               let item = grouping.Key
               where item.ParentID == null
               orderby item.CreateDate
               from child in YieldItemAndChildren(item)
               select child;
    }
}

Invoke it like this:

var sorted = new FlattenTree(random).Sort();

---

Literally, to sort the list, you should use method called Sort. You just need to provide correct comparator, it means you need to define a method which will compare two items as you defined (by level, then createdate). Look at MSDN here: http://msdn.microsoft.com/en-us/library/w56d4y5z.aspx

For example you can use a lambda like this:

mylist.Sort((x,y) => {
  int c = x.Level.CompareTo(y.Level);
  if(c==0) c = x.CreateDate.CompareTo(y.CreateDate);
  return c;
});

Note that I didn't compile and test this code in Visual Studio. Maybe it isn't 100% right but hopefully it showed you where to start.