How to build an HTML table based on nested Lists of data structure?

Question

I have a nested list structure as follows:

class Person {
   public string Name;
   public List<Person> Children;
   public int RowSpan { 
       get 
       { int childrenCount = 0;
          /* go through children (if any) and update childrenCount */ 
          return childrenCount == 0 ? 1 : childrenCount;
       }
    };
}

EDIT: my real data structure has nothing to do with parents/ children. I just choose a simple data structure to make the question easy to understand. Assume each grandpa can have any number of sons. Each son can have any number of kids. No two grandpas can share the same son. Likewise, sons can't share kids.

Edit2: I don't have issues with getting RowSpan for each cell. That is easy. The issue is: how can I parse the HTML structure of the table while iterating and traversing the data structure.

I populate a sample of this structure as follows:

Person grandpa1  = new Person { Name = "GrandPa1" };
Person grandpa2  = new Person { Name = "GrandPa2" };
Person son1      = new Person { Name = "Son 1" };
Person son2      = new Person { Name = "Son 2" };
Person grandkid1 = new Person { Name = "GrandKid1" };
Person grandkid2 = new Person { Name = "GrandKid2" };
Person grandkid3 = new Person { Name = "GrandKid3" };

grandpa1.Children = new List<Person> { son1, son2 };
son2.Children    = new List<Person> { grandkid1, grandkid2, grandkid3 };

List<Person> family = new List<Person> { grandpa1, grandpa2 } ;

I am trying to represent the family structure in a HTML table, using <td rowspan={number of offsprints}>

For the above family, the output would look like:

.------------------.
|          |       |
|          |  son1 |
|          |-------|-----------.
|          |       | grandkid1 |
| grandpa1 |       |-----------.
|          |       | grandkid2 |
|          |  son2 |-----------.
|          |       | grandkid3 |
|----------|-------.-----------.
| grandpa2 |
.----------.

In the above table, grandpa has a rowspan of 4. son2 has a rowspan of 3.

The equivelant HTML would be something like:

table {
  border-collapse: collapse;
}

td, th {
  border: 1px solid black;
  padding: 4px;
}

th
{
  font-family: monospace;
  background-color: #def;
  padding: 0 2em;
}

<table>
  <thead>
    <tr>
      <th>Grand Parents</th>
      <th>Sons</th>
      <th>Kids</th>
    </tr>
  </thead>
  <tr>
    <td rowspan="4"> grandpa1 </td>
    <td> son1 </td>
  </tr>
  <tr>
    <!-- no cell for grandpa1:in progress -->
    <!-- no cell for son1: fulfilled      -->
    <td rowspan="3"> son2 </td>
    <td> kid1 </td>
  </tr>
  <tr>
    <!-- no cell for grandpa1: in progress -->
    <!-- no cell for son2:     in progress -->
    <td> kid2 </td>
  </tr>
  <tr>
    <!-- no cell for grandpa1: in progress -->
    <!-- no cell for son2:     in progress -->
    <td> kid3</td>
  </tr>
  <tr>
    <!-- no cell for grandpa1: fullfilled -->
    <!-- no cell for son2:     fullfilled -->
    <td> grandpa2 </td>
  </tr>
</table>

I am struggling to write an algorithm that generates the HTML structure described above. I tried a number of ways:

1- I generated a Queue<TagBuilder> for each level of the family and iterate through the highest level and Enqueue a TD with a rowspan of the number of dependants in the lower levels. Then I generated other queues for the other levels. At the end, my plan was to DeQueue from all levels at once and append the TDs into a fresh TR. But that doesn't work because son1 has no children, and dequeuing from level 3 would fetch kids of son2..

2- I tried to iterate though grandparents level and appending a TR for each grandparent with a single TD having the rowspan of his sons/grandsons. Then iterate through sons level and do the same, likewise in grandkids level. However the overall table will be ill-formatted.

I can easily generate the structure in Excel since I have the ability to reference cells and their merge status while iterating the first level, and can comeback to the rows from before and append new cells.

Is there an easy way to generate the family structure table from the data structure above?

Answer 1

My previous answer does not produce the desired result. See the below answer.

Actually, I think it would be easier to "tablefy" the tree into a 2-dimensional array and fill it with the respective values. To determine the row span you need to look in the area below it for null values. The row span will be equal to the number of rows that contain null on all columns up to, and including, the current column.

For instance, Son1 does not have any null directly bellow it meaning its row span is 1. Son2 has 4 null values, but the row span is 3 because on row index 4 and column index 0 there is Grandpa 2. This is why looking directly below the current row (same column) is not enough, you need to check the area below the current cell on each column from start to, and including, current column.

You should be able to expand this to any number of levels and still get a proper table.

class Person
{
    public string Name { get; set; }

    public List<Person> Children { get; set; }
}

void WritePeopleTable(TextWriter textWriter, IEnumerable<Person> people)
{
    var peopleTable = GetPeopleTable(people);

    textWriter.WriteLine("<table>");
    for (var rowIndex = 0; rowIndex < peopleTable.GetLength(0); rowIndex++)
    {
        textWriter.WriteLine("<tr>");
        for (var columnIndex = 0; columnIndex < peopleTable.GetLength(1); columnIndex++)
        {
            var current = peopleTable[rowIndex, columnIndex];
            if (current != null)
            {
                var rowSpan = 1;
                var foundValue = false;
                while (!foundValue && rowIndex + rowSpan < peopleTable.GetLength(0))
                {
                    var searchColumnIndex = 0;
                    while (!foundValue && searchColumnIndex <= columnIndex)
                        if (peopleTable[rowIndex + rowSpan, searchColumnIndex] != null)
                            foundValue = true;
                        else
                            searchColumnIndex++;

                    if (!foundValue)
                        rowSpan++;
                }

                textWriter.Write($"<td rowspan=\"{rowSpan}\">");
                textWriter.Write(current.Name);
                textWriter.WriteLine("</td>");
            }
        }
        textWriter.WriteLine("</tr>");
    }
    textWriter.WriteLine("</table>");
}

struct PersonLevel
{
    public PersonLevel(Person person, int level)
    {
        Person = person;
        Level = level;
    }

    public Person Person { get; }

    public int Level { get; }
}

Person[,] GetPeopleTable(IEnumerable<Person> people)
{
    var rowCount = people.Sum(person => GetLeafCount(person)); // or people.Sum(GetLeafCount);
    var columnCount = people.Max(person => GetTreeHeight(person)); // or people.Max(GetTreeHeight);
    var peopleTable = new Person[rowCount, columnCount];
    var currentRowIndex = 0;
    var previousColumnIndex = -1;
    var toProcess = new Stack<PersonLevel>();
    foreach (var person in people.Reverse())
        toProcess.Push(new PersonLevel(person, 0));

    while (toProcess.Count > 0)
    {
        var current = toProcess.Pop();
        if (current.Person.Children != null)
            foreach (var child in current.Person.Children.AsEnumerable().Reverse())
                toProcess.Push(new PersonLevel(child, current.Level + 1));

        if (current.Level <= previousColumnIndex)
            currentRowIndex++;
        previousColumnIndex = current.Level;

        peopleTable[currentRowIndex, current.Level] = current.Person;
    }

    return peopleTable;
}

int GetLeafCount(Person person)
{
    var leafCount = 0;
    var toVisit = new Queue<Person>();
    toVisit.Enqueue(person);
    do
    {
        var current = toVisit.Dequeue();
        if (current.Children == null || !current.Children.Any())
            leafCount++;
        else
            foreach (var child in current.Children)
                toVisit.Enqueue(child);
    } while (toVisit.Count > 0);

    return leafCount;
}

int GetTreeHeight(Person person)
{
    var height = 0;
    var level = Enumerable.Repeat(person, 1);
    do
    {
        height++;
        level = level.SelectMany(current => current.Children ?? Enumerable.Empty<Person>());
    } while (level.Any());

    return height;
}

---

Previous answer

As I said in the comments, the row span is equal to the number of leaves from the current node (including the current node, row span of 1 is default).

int GetLeafCount(Person person)
{
    var leafCount = 0;
    var toVisit = new Queue<Person>();
    toVisit.Enqueue(person);
    do
    {
        var current = toVisit.Dequeue();
        if (!current.Children.Any())
            leafCount++;
        else
            foreach (var child in current.Children)
                toVisit.Enqueue(child);

    } while (toVisit.Count > 0);

    return leafCount;
}

Something you need to consider when doing this is the scenario when a child provides no grandchildren for the parent, in that case you need to specify a col span as well to fill the space, or fill it with the remaining TD elements. You can get the number of columns by calculating the height of the tree.

int GetTreeHeight(Person person)
{
    var height = 0;
    var level = Enumerable.Repeat(person, 1);
    do
    {
        height++;
        level = level.SelectMany(current => current.Children);
    } while (level.Any());

    return height;
}

You may need to get a collection of people that are on the same level in regards to the parent, i.e.: all people that have the same parent, all people that have the same grand parent and so on.

IEnumerable<IEnumerable<Person>> GetLevels(Person person)
{
    var level = Enumerable.Repeat(person, 1);
    do
    {
        yield return level;
        level = level.SelectMany(current => current.Children);
    } while (level.Any());
}

You can use these methods to generate the table.

void WriteTable(TextWriter textWriter, IEnumerable<Person> people)
{
    textWriter.WriteLine("<table>");
    foreach (var person in people)
        foreach (var rowIndex in Enumerable.Range(0, GetLeafCount(person)))
        {
            textWriter.WriteLine("<tr>");
            foreach (var columnIndex in Enumerable.Range(0, GetTreeHeight(person)))
            {
                var currentPerson = GetLevels(person).ElementAtOrDefault(columnIndex)?.ElementAtOrDefault(rowIndex);

                if (currentPerson != null)
                {
                    textWriter.Write($"<td rowspan=\"{GetLeafCount(currentPerson)}\">");
                    textWriter.Write(currentPerson.Name);
                    textWriter.WriteLine("</td>");
                }
            }
            textWriter.WriteLine("</tr>");
        }
    textWriter.WriteLine("</table>");
}