Context:
Given the following list in an unordered way. You have to return it order as follow: (New lines for presentation.)
{// (ID, Parent_ID);
(1,1), (2,1),(3,1),
(4,3),(5,3),
(6,7), // parent outside, But with Childs
(8,6),(9,6),
(10,11), // Parent outside, no child
(12,null), // No know parent, no child
(13,13) , // itself as parent, no child
}
To be eligible a List, need T to have an ID, parent ID and a way to order the child:
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; }
}
I'm flattenning my tree like :
public class FlatTree<T, TypeId, TypeOrder> where T : Flattenable<TypeId, TypeOrder>
where TypeId : struct, IComparable
where TypeOrder : IComparable
{
ILookup<T, T> mapping;
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)
{
Dictionary<TypeId, T> 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;
}
}
Problem :
It works great with normal and classic tree. But when a root has no childs it doesn't make it to the result.
Test :
Here is the test I use: The correct result is when the ordinal are in the logical order 1<2<3
etc.
public class TreeTest
{
public static void Main()
{
var datas = GetInputData();
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);
}
public static List<Item> GetInputData()
{
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 },
};
}
}
https://dotnetfiddle.net/spJHqD
Expected result is : GetData.OrderBy(x=> X.Ordinal)
Note:
I know that I only add to mapping child. I know about some of the other flattening algo, I use this one because it's readable.
Linking to a wikipedia in the code won't help future maintenance.
I could iterate on itemLookup
and yield the missing element by doing a set substraction with the result of from grouping in mapping ...linq