Add sequence number for dynamic hierarchy in C#

Question

Suppose I have these records:

Code     |GroupLevel    |Group
-----------------------------------
X0000    |4             |
X1000    |3             |X0000
X2000    |3             |X0000
X3000    |3             |X0000
X1100    |2             |X1000
X1200    |2             |X1000
X1300    |2             |X1000
X2100    |2             |X2000
X2200    |2             |X2000
X2300    |2             |X2000
X1110    |1             |X1100
X1120    |1             |X1100
X1111    |0             |X1110
X1112    |0             |X1110
X1113    |0             |X1110
X1114    |0             |X1110

What I want to acheive is to have this kind of sequence number:

Seq |Code     |GroupLevel    |Group
-------------------------------------
1   |X0000    |4             |
2   |X1000    |3             |X0000
3   |X1100    |2             |X1000
4   |X1110    |1             |X1100
5   |X1111    |0             |X1110
6   |X1112    |0             |X1110
7   |X1113    |0             |X1110
8   |X1114    |0             |X1110
9   |X1120    |1             |X1100
10  |X1200    |2             |X1000
11  |X1300    |2             |X1000
12  |X2000    |3             |X0000
13  |X2100    |2             |X2000
14  |X2200    |2             |X2000
15  |X2300    |2             |X2000
16  |X3000    |3             |X0000

I tried something with fixed group level (3) but not if the group level > 5.

Here's what I did:

List<MySequenceModel> _lstPair = new List<MySequenceModel>();
var _lst = _records.Where(x => x.GroupLevel == 3).ToList();
foreach (var item in _lst)
{
    if (_lstPair.Where(x => x.Code.Equals(item.Code)).FirstOrDefault() == null)
        _lstPair.Add(new MySequenceModel { Code = item.Code, SeqNo = _seqCounter++ });

    var _lst2 = _records.Where(x => x.Group.Equals(item.Code) && !x.Code.Equals(item.Code)).OrderBy(x => x.Code).ToList();
    foreach (var _item2 in _lst2)
    {
        if (_lstPair.Where(x => x.Code.Equals(_item2.Code)).FirstOrDefault() == null)
            _lstPair.Add(new MySequenceModel { Code = _item2.Code, SeqNo = _seqCounter++ });
        var _lst3 = _records.Where(x => x.Group.Equals(_item2.Code) && !x.Code.Equals(_item2.Code)).OrderBy(x => x.Code).ToList();
        foreach (var _item3 in _lst3)
        {
            if (_lstPair.Where(x => x.Code.Equals(_item3.Code)).FirstOrDefault() == null)
                _lstPair.Add(new MySequenceModel { Code = _item3.Code, SeqNo = _seqCounter++ });
            var _lst4 = _records.Where(x => x.Group.Equals(_item3.Code) && !x.Code.Equals(_item3.Code)).OrderBy(x => x.Code).ToList();
            foreach (var _item4 in _lst4)
            {
                if (_lstPair.Where(x => x.Code.Equals(_item4.Code)).FirstOrDefault() == null)
                    _lstPair.Add(new MySequenceModel { Code = _item4.Code, SeqNo = _seqCounter++ });
            }
        }
    }
}

MySequenceModel is a class that has the code and the sequence number which is essentially needed for reporting. A pseudo code will do.

TIA

Please share your code and the community will help you refactor it. — Rajshekar Reddy, Aug 18 '17 at 07:54
The code column should be ordered for the sequence number? And the group level should represent what on the data structure? Could you explain better what you have and what do you want? — Erick Gallani, Aug 18 '17 at 08:09
The structure is that i have a list of records with code and group code but with group level. What I want to achieve is that I have to sort the records based on group level downward and group them according to 'Group' as seen in the example. Like in tree. — Mark, Aug 18 '17 at 08:14

Ivan Stoev · Answer 1 · 2017-08-22T10:33:04.163

I would turn the input list into a tree structure and then simply process it with pre order depth first traversal.

For the first part I would use ToLookup method, for the second part - Expand custom extension method from my answer to How to flatten tree via LINQ?, and finally the Select overload with index for generating the sequence number:

var recordsByGroup = _records
    .OrderBy(r => r.Code)
    .ToLookup(r => r.Group ?? "");

var result = recordsByGroup[""]
    .Expand(r => recordsByGroup[r.Code])
    .Select((r, i) => new MySequenceModel { Code = r.Code, SeqNo = i + 1 })
    .ToList();

Update: I believe the above algorithm is optimal in terms of space and time complexity for the provided input data structure. But for completeness, since the desired transformation is no more than hierarchical sorting, the same can be achieved with sort by the path of the record to the root using the LINQ OrderBy method passing path selector and comparer:

// Helper structure for fast locating the parent records
var recordsByCode = _records.ToDictionary(r => r.Code);
// Path selector (list of records starting from root and icluding the record in question)
Func<MyRecord, IReadOnlyList<MyRecord>> pathSelector = r =>
{
    var path = new List<MyRecord>();
    do path.Add(r); while (recordsByCode.TryGetValue(r.Group, out r));
    path.Reverse();
    return path;
};
// Path comparer
var pathComparer = Comparer<IReadOnlyList<MyRecord>>.Create((path1, path2) =>
{
    int length = Math.Min(path1.Count, path2.Count); // the common path length
    for (int i = 0; i < length; i++)
    {
        int comparison = path1[i].Code.CompareTo(path2[i].Code);
        if (comparison != 0) return comparison;
    }
    // In case the common path is the same, put the shorter path first in the order
    return path1.Count.CompareTo(path2.Count);
});
// Simply sort using the path selector and comparer
var result2 = _records
    .OrderBy(pathSelector, pathComparer)
    .Select((r, i) => new /*MySequenceModel*/ { Code = r.Code, SeqNo = i + 1 })
    .ToList();

This method uses more temporary memory to hold the paths and heavier (hence slower) comparisons inside the record comparer.

This is exactly what I want to do. I'll try this as soon as I get back. Thank you! — Mark, Aug 18 '17 at 09:03
Well, there was extra `;` in code (copy/paste/edit error), but I guess you've fixed it, because otherwise it doesn't compile. But other than that, the code works - https://dotnetfiddle.net/zvRVD2. And Enigmativity is suggesting exactly the same, but with quick and dirty `Expand` implementation. May be you could provide the test fiddle or something which shows how you get zero data result? — Ivan Stoev, Aug 22 '17 at 07:26

score 1 · Answer 2 · answered Aug 22 '17 at 03:27

it's late and this could be better maybe but it work

dotnetfiddler linke

using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        var fun = new List<Data>();
        fun.Add(new Data() { Code ="X0000", GroupLevel=4, Group = null});
        fun.Add(new Data() { Code ="X1000", GroupLevel=3, Group = "X0000"});
        fun.Add(new Data() { Code ="X2000", GroupLevel=3, Group = "X0000"});
        fun.Add(new Data() { Code ="X3000", GroupLevel=3, Group = "X0000"});
        fun.Add(new Data() { Code ="X1100", GroupLevel=2, Group = "X1000"});
        fun.Add(new Data() { Code ="X1200", GroupLevel=2, Group = "X1000"});
        fun.Add(new Data() { Code ="X1300", GroupLevel=2, Group = "X1000"});
        fun.Add(new Data() { Code ="X2100", GroupLevel=2, Group = "X2000"});
        fun.Add(new Data() { Code ="X2200", GroupLevel=2, Group = "X2000"});
        fun.Add(new Data() { Code ="X2300", GroupLevel=2, Group = "X2000"});
        fun.Add(new Data() { Code ="X1110", GroupLevel=1, Group = "X1100"});
        fun.Add(new Data() { Code ="X1120", GroupLevel=1, Group = "X1100"});
        fun.Add(new Data() { Code ="X1111", GroupLevel=0, Group = "X1110"});
        fun.Add(new Data() { Code ="X1112", GroupLevel=0, Group = "X1110"});
        fun.Add(new Data() { Code ="X1113", GroupLevel=0, Group = "X1110"});
        fun.Add(new Data() { Code ="X1114", GroupLevel=0, Group = "X1110"});

        var result = (from f1 in fun
                     join f2 in fun on f1.Code equals (f2.Group ?? f2.Code)
                      orderby f2.Code
                     select f2).Select((v,i) => new Data(v,i)).ToList();

        result.ForEach(x => Console.WriteLine(x));
    }

}

public class Data
{
    public int Seq {get;set;}
    public string Code {get;set;}
    public int GroupLevel {get;set;}
    public string Group {get;set;}

    public Data(){}

    public Data(Data v, int i)
    {
        Seq = i+1;
        Code = v.Code;
        GroupLevel = v.GroupLevel;
        Group = v.Group;
    }

    public override string ToString()
    {
        return string.Format("{3} - {0} - {1} - {2}",Code, GroupLevel,Group, Seq);
    }
}

result;

1 - X0000 - 4 -
2 - X1000 - 3 - X0000
3 - X1100 - 2 - X1000
4 - X1110 - 1 - X1100
5 - X1111 - 0 - X1110
6 - X1112 - 0 - X1110
7 - X1113 - 0 - X1110
8 - X1114 - 0 - X1110
9 - X1120 - 1 - X1100
10 - X1200 - 2 - X1000
11 - X1300 - 2 - X1000
12 - X2000 - 3 - X0000
13 - X2100 - 2 - X2000
14 - X2200 - 2 - X2000
15 - X2300 - 2 - X2000
16 - X3000 - 3 - X0000

This code works for me however, I need to do some tweaking on the Codes without groups. — Mark, Aug 22 '17 at 23:58

score 1 · Accepted Answer · answered Aug 22 '17 at 03:51

Given the following input data (take from the question):

MySequenceModel[] _records = new MySequenceModel[]
{
    new MySequenceModel { Code = "X0000", GroupLevel = 4, Group = "" },
    new MySequenceModel { Code = "X1000", GroupLevel = 3, Group = "X0000" },
    new MySequenceModel { Code = "X2000", GroupLevel = 3, Group = "X0000" },
    new MySequenceModel { Code = "X3000", GroupLevel = 3, Group = "X0000" },
    new MySequenceModel { Code = "X1100", GroupLevel = 2, Group = "X1000" },
    new MySequenceModel { Code = "X1200", GroupLevel = 2, Group = "X1000" },
    new MySequenceModel { Code = "X1300", GroupLevel = 2, Group = "X1000" },
    new MySequenceModel { Code = "X2100", GroupLevel = 2, Group = "X2000" },
    new MySequenceModel { Code = "X2200", GroupLevel = 2, Group = "X2000" },
    new MySequenceModel { Code = "X2300", GroupLevel = 2, Group = "X2000" },
    new MySequenceModel { Code = "X1110", GroupLevel = 1, Group = "X1100" },
    new MySequenceModel { Code = "X1120", GroupLevel = 1, Group = "X1100" },
    new MySequenceModel { Code = "X1111", GroupLevel = 0, Group = "X1110" },
    new MySequenceModel { Code = "X1112", GroupLevel = 0, Group = "X1110" },
    new MySequenceModel { Code = "X1113", GroupLevel = 0, Group = "X1110" },
    new MySequenceModel { Code = "X1114", GroupLevel = 0, Group = "X1110" },
};

Then this works:

var lookup = _records.ToLookup(x => x.Group);
Func<string, IEnumerable<MySequenceModel>> traverse = null;
traverse = grp => lookup[grp].SelectMany(x => new [] { x }.Concat(traverse(x.Code)));

MySequenceModel[] results =
    traverse("")
        .Select((x, n) => new MySequenceModel
        {
            SeqNo = n + 1,
            Code = x.Code,
            GroupLevel = x.GroupLevel,
            Group = x.Group
        })
        .ToArray();

It gives me:

While I simulate this with the real data sets, for some reason, results is returning 0 records. Combining this answer with @Fredou, I came up with a solution. — Mark, Aug 23 '17 at 00:02

Add sequence number for dynamic hierarchy in C#

3 Answers3