JavaScript recursive function for nested objects in array

Question

I'm trying to implement an algorithm to generate a table with hierarchical headers. These ones can be unlimited nested. An html example of the rendered table markup could be the following:

    <table border=1>
      <thead>
        <tr>
          <th colspan="6">
            Super one
          </th>
          <th colspan="6">
            Super two
          </th>
        </tr>
        <tr>
          <th colspan="3">Head one</th>
          <th colspan="3">Head two</th>
          <th colspan="4">Head three</th>
          <th colspan="2">Head four</th>
        </tr>
        <tr>
          <th>Sub one</th>
          <th>Sub two</th>
          <th>Sub three</th>
          <th>Sub four</th>
          <th>Sub five</th>
          <th>Sub six</th>
          <th>Sub seven</th>
          <th>Sub eight</th>
          <th>Sub nine</th>
          <th>Sub ten</th>
          <th>Sub eleven</th>
          <th>Sub twelve</th>
        </tr>
      </thead>
    </table>  

The configuration of the table should be passed as a JavaScript object in this format:

var columns = [
  {
    label: 'Super one',
    children: [
      {
        label: 'Head one',
        children: [
          {label: 'Sub one'},
          {label: 'Sub two'},
          {label: 'Sub three'}
        ]
      },
      {
        label: 'Head two',
        children: [
          {label: 'Sub four'},
          {label: 'Sub five'},
          {label: 'Sub six'}
        ]
      }
    ]
  },
  {
    label: 'Super two',
    children: [
      {
        label: 'Head three',
        children: [
          {label: 'Sub seven'},
          {label: 'Sub eight'},
          {label: 'Sub nine'},
          {label: 'Sub ten'}
        ]
      },
      {
        label: 'Head four',
        children: [
          {label: 'Sub eleven'},
          {label: 'Sub twelve'}
        ]
      }
    ]
  }
];

Now, let's forget about the html rendering and pay attention only to the algorithm that should iterate over the configuration in order to have a simple 2D array in the format:

var structure = [
  [6, 6],
  [3, 3, 4, 2],
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]; 

where each entry represents a table row (tr) containing its column definition (td) and the number represents the colspan. How can I implement the algorithm?

Currently I created a recursive function which returns the number of total columns based on the configuration:

function getColumnCount(columns) {
  var count = 0;
  for (var i=0; i<columns.length; i++) {
    var col = columns[i];
    if (col.children && col.children.length > 0) {
      count += getColumnCount(col.children);
    }
    else {
      count++;
    }
  }
  return count;
}

it works as expected, but I'm stuck trying to generate the "structure" array... my current (embarrassing) code attempt is this:

function getStructure(columns) {
  var structure = [[]];
  for (var i=0; i<columns.length; i++) {
    var col = columns[i];
    if (col.children && col.children.length > 0) {
      console.log(col.label, '(with children)');
      schema[structure.length - 1].push(getColumnCount(col.children));
      getStructure(col.children, schema);
    }
    else {
      console.log(col.label, '(orphan)');
      schema[structure.length - 1].push(1);
    }
  }
  return structure; 
}

I'm feeling a real dumb, since I know it should be a relatively easy task, but when it comes to recursive functions my brain seems to refuse to collaborate XD

Can you help me?

Answer 1

This should work in any combination:

var columns = [
    {
        label: '1',
        children: [
            {
                label: '1.1',
                children: [
                    {label: '1.1.1'},
                    {
						label: '1.1.2',
						children: [
							{label: '1.1.2.1'},
							{label: '1.1.2.2'},
							{label: '1.1.2.3'},
							{label: '1.1.2.4'},
							{label: '1.1.2.5'}
						]
					},
                    {label: '1.1.3'}
                ]
            },
            {
                label: '1.2',
                children: [
                    {label: '1.2.1'},
                    {label: '1.2.2'},
                    {label: '1.2.3'}
                ]
            }
        ]
    },
    {
        label: '2',
        children: [
            {
                label: '2.1',
                children: [
                    {label: '2.1.1'},
                    {label: '2.1.2'},
                    {label: '2.1.3'},
                    {
						label: '2.1.4',
						children: [
							{label: '2.1.4.1'},
							{label: '2.1.4.2'},
							{
								label: '2.1.4.3',
								children: [
									{label: '2.1.4.3.1'},
									{label: '2.1.4.3.2'},
									{
										label: '2.1.4.3.3',
										children: [
											{label: '2.1.4.3.3.1'},
											{label: '2.1.4.3.3.2'},
											{label: '2.1.4.3.3.3'},
											{label: '2.1.4.3.3.4'}
										]
									},
									{label: '2.1.4.3.4'},
									{label: '2.1.4.3.5'}
								]
							},
						]
					}
                ]
            },
            {
                label: '2.2',
                children: [
                    {label: '2.2.1'},
                    {
						label: '2.2.2',
						children: [
							{label: '2.2.2.1'},
							{label: '2.2.2.2'},
						]
					}
                ]
            }
        ]
    }
];

// table is the table
// cells is the array of cells we're currently processing
// rowIndex is the table row we're on
// colIndex is where the column for the current cell should start
function createTable(table, cells, rowIndex, colIndex)
{
	// get the current row, add if its not there yet
	var tr = table.rows[rowIndex] || table.insertRow();
	
	// how many columns in this group
	var colCount = cells.length;
	
	// iterate through all the columns
	for(var i = 0, numCells = cells.length; i < numCells; ++i)
	{
		// get the current cell
		var currentCell = cells[i];
		
		// we need to see where the last column for the current row is
		// we have to iterate through all the existing cells and add their colSpan value
		var columnEndIndex = 0;
		for(var j = 0, numCellsInThisRow = tr.cells.length; j < numCellsInThisRow; ++j)
		{
			columnEndIndex += tr.cells[j].colSpan || 1;
		}
		
		// now we know the last column in the row
		// we need to see where the column for this cell starts and add fillers in between
		var fillerLength = colIndex - columnEndIndex;
		while(fillerLength-- > 0)
		{
			tr.insertCell();
		}
		
		// now add the cell we want
		var td = tr.insertCell();
		
		// set the value
		td.innerText = currentCell.label;
		
		// if there are children
		if(currentCell.children)
		{
			// before we go to the children row
			// we need to see what the actual column for the current cell is because all the children cells will start here
			// we have to iterate through all the existing cells and add their colSpan value
			var columnEndIndex = 0;
			
			// we don't need the current cell since thats where we want to start the cells in the next row
			for(var j = 0, numCellsInThisRow = tr.cells.length - 1; j < numCellsInThisRow; ++j)
			{
				columnEndIndex += tr.cells[j].colSpan || 1;
			}
			
			// go to the next row and start making the cells
			var childSpanCount = createTable(table, currentCell.children, rowIndex + 1, columnEndIndex);
			
			// we want to add to this recursions total column count
			colCount += childSpanCount - 1;
			
			// set the colspan for this cell
			td.colSpan = childSpanCount;
		}
	}
	
	// return the total column count we have so far so it can be used in the previous recursion
	return colCount;
}

function doIt()
{
	var numCols = createTable(document.getElementById("output"), columns, 0, 0);
	alert("total number of columns: " + numCols);
}

<html>

<body>
  <a href="#" onclick="doIt(); return false">do it</a>
  <br /><br />
  <table id="output" border="1"></table>
</body>

</html>

Answer 2

Here another and a bit smaller approach.

function getStructure(nodes) {
    if (nodes.length == 0) { return [ [ 1 ] ] }
    let level1 = nodes.map(node => getStructure(node.children ? node.children: []))
    let ret = level1.reduce((obj, e) => e.map((a, i) => obj[i].concat(a)))
    let sum = ret[0].reduce((sum, e) => sum + e, 0)
    return [ [ sum ] ].concat(ret)
}

produces

[ [ 12 ],
  [ 6, 6 ],
  [ 3, 3, 4, 2 ],
  [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ]

(I don't know exactly how to deal with the "different height" feature... how should the structure look like?)

Answer 3

The tricky part is to calculate a span, which is the number of leaf nodes under the given node or 1 the node is a leaf itself. This value can be defined recursively as follows:

 numberOfLeaves(node) = if node.children then 
       sum(numberOfLeaves(child) for child in node.children) 
       else 1

The rest is pretty straightforward:

var columns = [
    {
        label: 'Super one',
        children: [
            {
                label: 'Head one',
                children: [
                    {
                        label: 'Sub one',
                        children: [
                            {label: 1},
                            {label: 2},
                        ]
                    },
                    {label: 'Sub two'},
                    {label: 'Sub three'}
                ]
            },
            {
                label: 'Head two',
                children: [
                    {label: 'Sub four'},
                    {label: 'Sub five'},
                    {label: 'Sub six'}
                ]
            }
        ]
    },
    {
        label: 'Super two',
        children: [
            {
                label: 'Head three',
                children: [
                    {label: 'Sub seven'},
                    {label: 'Sub eight'},
                    {label: 'Sub nine'},
                    {label: 'Sub ten'}
                ]
            },
            {
                label: 'Head four',
                children: [
                    {label: 'Sub eleven'},
                    {label: 'Sub twelve'}
                ]
            }
        ]
    }
];

var tab = [];

function calc(nodes, level) {
    tab[level] = tab[level] || [];

    var total = 0;

    nodes.forEach(node => {
        var ccount = 0;
        if ('children' in node) {
            ccount = calc(node.children, level + 1);
        } else {
            ccount = 1;
        }
        tab[level].push({
            label: node.label,
            span: ccount
        });

        total += ccount;
    });

    return total;
}

calc(columns, 0);
console.log(tab);

function makeTable(tab) {
    html = "<table border=1>";
    tab.forEach(row => {
        html += "<tr>";
        row.forEach(cell => {
            html += "<td colspan=" + cell.span + ">" + cell.label + "</td>"
        });
        html += "</tr>"
    })
    return html + "</table>";
}

document.write(makeTable(tab))