using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

​

public class TreeTest

{

    public static void Main()

    {

        var datas = GetData();

        var test = new FlatTree<Item, int, int>(datas).Sort().ToList();

        var Six = test.Any(x => x.ID == 6);

        var Ten = test.Any(x => x.ID == 10);

        var Twe = test.Any(x => x.ID == 12);

        var Thi = test.Any(x => x.ID == 13);

​

        test.Select(x=> x.Order).Dump();

    }

    public static List<Item> GetData()

    {

        return new List<Item> {

            new Item { Id = 6, Parent_Id = 7 , Ordinal = 6 },

            new Item { Id = 10, Parent_Id = 11 , Ordinal = 9 },

            new Item { Id = 12, Parent_Id = null , Ordinal = 10 },

            new Item { Id = 13, Parent_Id = 13, Ordinal = 11 },

​

​

            new Item { Id = 1, Parent_Id = 1 , Ordinal = 1 },

            new Item { Id = 2, Parent_Id = 1 , Ordinal = 2 },

            new Item { Id = 3, Parent_Id = 1 , Ordinal = 3 },

            new Item { Id = 4, Parent_Id = 3 , Ordinal = 4 },

            new Item { Id = 5, Parent_Id = 3 , Ordinal = 5 },

            new Item { Id = 8, Parent_Id = 6 , Ordinal = 7 },

            new Item { Id = 9, Parent_Id = 6 , Ordinal = 8 },

        };

    }

​

}

​

public partial class Item

{

    public int Id { get; set; }

    public int? Parent_Id { get; set; }

    public int Ordinal { get; set; }

}

public partial class Item : Flattenable<int, int>

{

    public override int ID => this.Id;

    public override int? Parent_ID => this.Parent_Id;

    public override int Order => this.Ordinal;

}

​

public abstract class Flattenable<T_Id, T_Order> where T_Id : struct, IComparable

                                                 where T_Order : IComparable

{

    public abstract T_Id ID { get; }

    public abstract Nullable<T_Id> Parent_ID { get; }

    public abstract T_Order Order { get; }

}

​

public class FlatTree<T, TypeId, TypeOrder> where T : Flattenable<TypeId, TypeOrder>

                                        where TypeId : struct, IComparable

                                        where TypeOrder : IComparable

{

    ILookup<T, T> mapping;

    Dictionary<TypeId, T> itemLookup;

​

    private bool IsRootElement(T item)

    {

        // Doesnt has a Parent. Has Itself as Parent. Parent is outside of the List, is eligible for emmancipation.

        return !item.Parent_ID.HasValue

                        || EqualityComparer<TypeId>.Default.Equals((TypeId)item.Parent_ID, item.ID)

                        || !itemLookup.ContainsKey(item.Parent_ID.Value);

    } 

    public FlatTree(IEnumerable<T> list)

    {

        itemLookup = list.ToDictionary(item => item.ID);

​

        mapping = list.Where(i => !IsRootElement(i))

                        .ToLookup(i => itemLookup[i.Parent_ID.Value]);

    }

​

    IEnumerable<T> YieldSelfAndChildren(T node)

    {

        yield return node;

        foreach (var child in mapping[node].OrderBy(i => i.Order))

            foreach (var grandchild in YieldSelfAndChildren(child))

                yield return grandchild;

    }

​

    public IEnumerable<T> Sort()

    {

        return

                from grouping in mapping

                let item = grouping.Key

                where IsRootElement(item)

                orderby item.Order

                from child in YieldSelfAndChildren(item)

                select child;

    }

}

​

​

​