Easiest way to create a nested list from flat data

Question

Assume I have the following information in a flat format, for example a list of objects:

List<Line> lines = new List<Line>
                                   {
                                       new Line{Id = 1, Level = 0},
                                       new Line{Id = 2, Level = 1},
                                       new Line{Id = 3, Level = 1},
                                       new Line{Id = 4, Level = 2},
                                       new Line{Id = 5, Level = 2},
                                       new Line{Id = 6, Level = 1},
                                       new Line{Id = 7, Level = 1},
                                       new Line{Id = 8, Level = 2},
                                       new Line{Id = 9, Level = 1}
                                   };

Each object has an id and a level. What I want to end up with a nested list. For this I have a class which can have a list of children, based on the level.

public class NestedLine
    {
        public int Id;
        public List<NestedLine> Children = new List<NestedLine>();
    }

What's the easiest way to convert that flat list into a nested list?

EDIT: The only information on how to construct the list is the order of the lines and the level. This should be the result:

1
--2
--3
  --4
  --5
--6
--7
  --8
--9

Answer 1

Can you provide a little more information here? This looks to me like you are really dealing with a tree structure:

1
-> 2
-> 3
-> -> 4
-> -> 5
-> 6
-> 7
-> -> 8
-> 9

am i correct? and if so, what is the rule for determining the parent of the lower level nodes?

The first thing that comes to mind is to use a recursive constructor for your NestedLine class:

public NestedLine(List lines)

Answer 2

Here is my attempt.

Calling code

List<Line> lines = new List<Line>
                           {
                               new Line{Id = 1, Level = 0},
                               new Line{Id = 2, Level = 1},
                               new Line{Id = 3, Level = 1},
                               new Line{Id = 4, Level = 2},
                               new Line{Id = 5, Level = 2},
                               new Line{Id = 6, Level = 1},
                               new Line{Id = 7, Level = 1},
                               new Line{Id = 8, Level = 2},
                               new Line{Id = 9, Level = 1}
                           };

NestedLine nestedLine = Recusrsive(lines, 0);

Recursive Method

private NestedLine Recusrsive(List<Line> lines, int listPos)
{
    NestedLine retVal = new NestedLine();
    Line line = lines[listPos];

    retVal.Id = line.Id;

    for (int iItem = listPos + 1; iItem < lines.Count; iItem++)
        if (lines[iItem].Level == line.Level + 1)
            retVal.Children.Add(Recusrsive(lines, iItem));
        else if (lines[iItem].Level <= line.Level) return retVal;

    return retVal;
}

Answer 3

Use a stack to keep track what was the last item added at each level, pushing and popping as you go along:

var stack = new Stack<NestedLine>();
foreach (var line : lines) {
    while (stack.Count > line.Level) {
        // Pop items until the top element is one up from current level
        stack.Pop()
    }
    var child = new NestedLine{Id = line.Id};
    if (stack.Count > 0) {
        // if there is a parent, add the child to its children
        stack.Peek().Children.Add(child);
    }
    // add current line as the deepest item
    stack.Push(child);
}
NestedLine root;
while (stack.Count) {
    root = stack.Pop();
}

Disclaimer: I haven't actually done much C# programming so this might contain some trivial errors.