1

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

Drag and Drop
  • 2,672
  • 3
  • 25
  • 37
  • The issue come from the way I populate the mapping. I only put children with known parent. And classic tree algo https://stackoverflow.com/questions/11830174/how-to-flatten-tree-via-linq , takes a tree. With a known root. Not a list of item with multiple root. – Drag and Drop Dec 23 '21 at 07:43
  • It is unclear what you are asking. Please provide the input and desired output separately. Currently there is a single thing in your answer and it is not clear if it is input or output. Also please elaborate on the parent and child explanations, this is not obvious at the moment – Ivaylo Strandjev Jan 04 '22 at 11:39
  • @IvayloStrandjev, as stated Expected result is : `GetData.OrderBy(x=> X.Ordinal)`. But for the parent thing I don't know who to be more explicit than `Id = 1, Parent_Id = 1 ,`. Will a tree be better? – Drag and Drop Jan 04 '22 at 12:29

0 Answers0