How to convert a tree-like structure to a plain HTML table using rowspans?

Question

Given a structure of nodes from different data sources where one node depends on 0 to n other nodes but a single node can only depend on nodes from one source

const nodes = [
    { dataSourceId: "a", id: "a-1", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "a", id: "a-2", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "a", id: "a-3", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "b", id: "b-1", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "b", id: "b-2", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "b", id: "b-3", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1", "a-2"] },
    { dataSourceId: "c", id: "c-1", dependsOnDataSourceId: "b", dependsOnNodes: ["b-1"] },
    { dataSourceId: "c", id: "c-2", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-3", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-4", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-5", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2", "b-3"] },
    { dataSourceId: "c", id: "c-6", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2", "b-3"] },
    { dataSourceId: "e", id: "e-1", dependsOnDataSourceId: "c", dependsOnNodes: ["c-1", "c-3"] },
    { dataSourceId: "e", id: "e-2", dependsOnDataSourceId: "c", dependsOnNodes: ["c-3"] },
    { dataSourceId: "self-reference", id: "a-1", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "d", id: "d-1", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "d", id: "d-2", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
];

nodes is not sorted, the order is random (and should not matter).

I want to represent this structure as a HTML table using rowspans. What I know is the order of columns where each data source represents a column

const dataSourceIds = ["a", "b", "c", "d", "e", "self-reference"];

The first item in dataSourceIds ( "a" ) always represents the group of root nodes.

First I tried to "draw" the expected result

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


  
    
      a
      b
      c
      d
      e
      self-reference
    
  
  
    
      a-1
      b-1
      c-1
      
      e-1
      a-1
    
    
      
      b-2
      c-2
      d-1
      
      
    
    
      
      
      c-3
      d-2
      e-1
      
    
    
      
      
      
      
      e-2
      
    
    
      
      
      c-4
      
      
      
    
    
      
      
      c-5
      
      
      
    
    
      
      
      c-6
      
      
      
    
    
      
      b-3
      c-5
      
      
      
    
    
      
      
      c-6
      
      
      
    
    
      a-2
      b-3
      c-5
      
      
      
    
    
      
      
      c-6
      
      
      
    
    
      a-3

This is what I tried so far

const nodes = [
    { dataSourceId: "a", id: "a-1", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "a", id: "a-2", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "a", id: "a-3", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "b", id: "b-1", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "b", id: "b-2", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "b", id: "b-3", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1", "a-2"] },
    { dataSourceId: "c", id: "c-1", dependsOnDataSourceId: "b", dependsOnNodes: ["b-1"] },
    { dataSourceId: "c", id: "c-2", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-3", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-4", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-5", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2", "b-3"] },
    // breaks here because c-6 must also replace a-2 with a rowspan
    // { dataSourceId: "c", id: "c-6", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2", "b-3"] },
    { dataSourceId: "e", id: "e-1", dependsOnDataSourceId: "c", dependsOnNodes: ["c-1", "c-3"] },
    { dataSourceId: "e", id: "e-2", dependsOnDataSourceId: "c", dependsOnNodes: ["c-3"] },
    { dataSourceId: "self-reference", id: "a-1", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "d", id: "d-1", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    // breaks here because b-2 must be added at c-3 but it tries to add it at c-2
    // { dataSourceId: "d", id: "d-2", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
];

const dataSourceIds = ["a", "b", "c", "d", "e", "self-reference"];

// group the nodes by source so it's easier to inspect them
const groupedNodes = {};

for (const dataSourceId of dataSourceIds) {
    groupedNodes[dataSourceId] = nodes.filter(node => node.dataSourceId === dataSourceId);
}

// extract the root node id so dataSourceIds only contains child sources
const rootNodeId = dataSourceIds.shift();

const rootNodes = groupedNodes[rootNodeId];

let rows = [];

// setup the initial rows with root nodes
for (const rootNode of rootNodes) {
    const row = {
        [rootNodeId]: rootNode
    };

    for (const dataSourceId of dataSourceIds) {
        row[dataSourceId] = "empty";
    }

    rows.push(row);
}

// fill the rows with child nodes
for (let dataSourceIdIndex = 0; dataSourceIdIndex < dataSourceIds.length; dataSourceIdIndex++) {
    const dataSourceId = dataSourceIds[dataSourceIdIndex];
    const childNodes = groupedNodes[dataSourceId];

    for (const childNode of childNodes) {
        const { dependsOnDataSourceId, dependsOnNodes } = childNode;

        for (const parentNodeId of dependsOnNodes) {
            for (let rowIndex = 0; rowIndex < rows.length; rowIndex++) {
                const row = rows[rowIndex];
                const parentNode = row[dependsOnDataSourceId];

                // parent node must exist in this row
                if (parentNode === "empty") {
                    continue;
                }

                // parent node id must match
                if (parentNode.id !== parentNodeId) {
                    continue;
                }

                // what if parent is covered?

                // simply add it if there is no value yet
                if (row[dataSourceId] === "empty") {
                    row[dataSourceId] = childNode;
                    continue;
                }

                // this row already has a value for this data source so we have to duplicate it
                const duplicatedRow = structuredClone(row);

                // replace the parent node with a rowspan
                duplicatedRow[dependsOnDataSourceId] = { coveredByRowIndex: rowIndex };

                // replace the previous child node with the current one
                duplicatedRow[dataSourceId] = childNode;

                // set all data source values between dependsOnDataSourceId ( exclusive ) and dataSourceIdIndex ( exclusive ) to empty because they are siblings with no data
                const dependsOnDataSourceIdIndex = dataSourceIds.findIndex(previousDataSourceId => previousDataSourceId === dependsOnDataSourceId);

                for (let emptyDataSourceIndex = dependsOnDataSourceIdIndex + 1; emptyDataSourceIndex < dataSourceIdIndex; emptyDataSourceIndex++) {
                    const emptyDataSourceId = dataSourceIds[emptyDataSourceIndex];
                    duplicatedRow[emptyDataSourceId] = "empty";
                }

                // check if there already are any covered rows
                const amountOfCoveredRows = rows.filter(rowToInspect => {
                    const dataSourceValue = rowToInspect[dependsOnDataSourceId];

                    if (dataSourceValue.coveredByRowIndex === undefined) {
                        return false;
                    }

                    return dataSourceValue.coveredByRowIndex === rowIndex;
                }).length;

                const insertDuplicatedRowIndex = rowIndex + amountOfCoveredRows + 1;

                // insert the new row after the last covered row
                const previousRows = rows.slice(0, insertDuplicatedRowIndex);
                const nextRows = rows.slice(insertDuplicatedRowIndex, rows.length);

                rows = [
                  ...previousRows,
                  duplicatedRow,
                  ...nextRows
                ];

                // but don't inspect this one in the next run
                rowIndex++;
            }
        }
    }
}

console.log(rows);

where

"empty" means that the element is empty
coveredByRowIndex means that it should use style="display: none"

The code is inefficient but this shouldn't matter for now, I want to optimize it later.

As you can see rows does not contain the expected result yet. There are 2 nodes breaking the algorithm. My thoughts on how I do it manually

group nodes by dataSourceId

for each a, create a new row with empty values ( except for a )

fill b

if there already is a b, duplicate the row and replace the a with a "covered" index

repeat for c

repeat for c-6 but c-6 depends on b-3 and b-3 depends on a-2 so you must set a rowspan for a-2

repeat for d

repeat for d-2 but d-2 depends on b-2. It must not duplicate the row because there is enough space in the c-3 row

repeat for e-1

repeat for e-2 but you must replace d-2 with an "empty" value ( set all sources between parent key and own key to "empty" )

repeat for self-reference

Do you guys have any ideas how to solve this problem? I don't think that I need the final code, I just don't have any idea how to setup the algorithm... so any pseudo code / algorithm suggestions are highly appreciated!

petern0691 · Accepted Answer

I am not 100% confidant that I have understood what the fully generalised data set you are working with might look like, but the code below will do the following:

Parse an arbitrary list of nodes of any length and any dependency depth.
Process any number of sources, in any order of dependency.

It currently assumes:

Only root nodes can be self referencing. This can be changed but it is not trivial to do so.
Dependency source order is the same as a sort order of sources, currently alphabetic. But this can easily be set rather than derived from the data, eg, as per one of your knowns above.
While there can be multiple paths between nodes, there must not be any loops, eg, 'a' depends on 'b' on 'c' on 'a'. This will cause an infinite loop.

The approach in the code is:

Make a structured linked list of the nodes.
Get the root nodes.
Recursively parse the root nodes and their descendants.

There are some further explanatory comments in the code.

Let me know if you need anything fixed/changed.

const nodes = [
    { dataSourceId: "a", id: "a-1", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "a", id: "a-2", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "a", id: "a-3", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "b", id: "b-1", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "b", id: "b-2", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "b", id: "b-3", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1", "a-2"] },
    { dataSourceId: "c", id: "c-1", dependsOnDataSourceId: "b", dependsOnNodes: ["b-1"] },
    { dataSourceId: "c", id: "c-2", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-3", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-4", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-5", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2", "b-3"] },
    { dataSourceId: "c", id: "c-6", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2", "b-3"] },
    { dataSourceId: "e", id: "e-1", dependsOnDataSourceId: "c", dependsOnNodes: ["c-1", "c-3"] },
    { dataSourceId: "e", id: "e-2", dependsOnDataSourceId: "c", dependsOnNodes: ["c-3"] },
    { dataSourceId: "self-reference", id: "a-1", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "d", id: "d-1", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "d", id: "d-2", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "d", id: "d-3", dependsOnDataSourceId: "c", dependsOnNodes: ["c-3"] }
];

//  Build a list of structured nodes
dataSourceIds = [];
list = [];
selfRefs = [];
for ( var i = 0; i < nodes.length; i++ ) {
    if ( nodes[i].dataSourceId == "self-reference" ) {
        selfRefs.push(nodes[i].id);
    } else {
        if ( ! dataSourceIds.includes(nodes[i].dataSourceId) ) dataSourceIds.push(nodes[i].dataSourceId);
        list.push([ nodes[i].id, nodes[i].dataSourceId, [], nodes[i].dependsOnNodes, undefined ]);
    }
}
dataSourceIds.sort()

//  A utility, given a node id return the structured node
function getListNode(id) {
    for ( var i = 0; i < list.length; i++ ) {
        if ( list[i][0] == id ) return list[i];
    }
    return undefined;
}

//  Populate structured nodes with their structured parents
for ( var i = 0; i < list.length; i++ ) {
    var parents = [];
    for ( var j = 0; j < list[i][3].length; j++ ) {
        parents.push(getListNode(list[i][3][j]));
    }
    list[i][3] = parents;
}

//  Populate structured nodes with their structured children
for ( var i = 0; i < list.length; i++ ) {
    for ( var j = 0; j < list[i][3].length; j++ ) {
        list[i][3][j][2].push(list[i]);
    }
}

//  Get the structured nodes with no parents
treeRoots = [];
for ( var i = 0; i < list.length; i++ ) {
    if ( list[i][3].length == 0 ) treeRoots.push(list[i]);
}

function spanner(node) {
    //  Calculate the row span required for a node, by recursively walking the tree for the node
    var span;
    if ( node[2].length == 0 ) {
        span = 1
        node[4] = span;
    } else {
        var span = 0;
        for ( var i = 0; i < node[2].length; i++ ) {
            span += spanner(node[2][i]);
        }
        node[4] = span
    }
    return span
}

//  Utility to print a tree root
function printTR(treeRoots) {
    var text = "";
    for ( var i = 0; i < treeRoots.length; i++ ) {
        text += printNT(treeRoots[i], 0);
    }
    return text;
}

//  Utility to space out fields, indent, etc.
function spacer(n) {
    var N = n * 4;
    var text = "";
    for ( var i = 0; i < N; i++ ) {
        text += " "
    }
    return text;
}

//  Utility to print a node tree
function printNT(node, depth) {
    var text = "";
    text += '
' + spacer(depth) + node[0] + spacer(1) + node[4] + spacer(1) + node[1];
    for ( var j = 0; j < node[2].length; j++ ) {
        text += printNT(node[2][j], depth + 1);
    }
    return text;
}

function tableTR(treeRoots) {
    //  Convert a root tree into a set of rows
    var text = "";
    for ( var i = 0; i < treeRoots.length; i++ ) {
        var textRoot = '' + tableNT(treeRoots[i], "").replaceAll("", "");
        //  Add in a self reference
        if ( selfRefs.indexOf(treeRoots[i][0]) != -1 ) {
            ndx = textRoot.indexOf("");
            text += textRoot.slice(0,ndx) + treeRoots[i][0] + textRoot.slice(ndx);
        } else {
            text += textRoot;
        }
    }
    return text;
}

function sourcePadding(parent, child) {
    //  Generate empty table cells when child source is more than one source away from parent source.
    //  $ is to end of row of sources.
    var text = "";
    if ( child == "$" ) {
        for ( var i = 1; i < dataSourceIds.length - dataSourceIds.indexOf(parent); i++ ) {
            text += '' + '';
        }
    } else if ( parent != child && parent != "" ) {
        for ( var i = 1; i < dataSourceIds.indexOf(child) - dataSourceIds.indexOf(parent); i++ ) {
            text += '' + '';
        }
    }
    return text;
}

function tableNT(node, parentSource) {
    //  Convert a node tree into table rows
    var text = "";
    if ( node[4] == 1 ) {
        if ( node[2].length == 1 ) {
            text += sourcePadding(parentSource, node[1]) + '' + node[0] + '' + tableNTfr(node[2][0], node[1]);
        } else {
            text += sourcePadding(parentSource, node[1]) + '' + node[0] + '' + sourcePadding(node[1], "$") + '';
        }
    } else {
        text += sourcePadding(parentSource, node[1]) + '' + node[0] + '' + tableNTfr(node[2][0], node[1]);
        text += tableNTor(node[2][0], [ [ node[1], node[2][0][1] ] ]);
        for ( var i = 1; i < node[2].length; i++ ) {
            text += '' + tableNT(node[2][i], node[1])
        }
    }
    return text;
}

function tableNTfr(node, parentSource) {
    //  The first row in a row span
    var text = "";
    if ( node[4] == 1 ) {
        if ( node[2].length == 1 ) {
            text += sourcePadding(parentSource, node[1]) + '' + node[0] + '' + tableNTfr(node[2][0], node[1]);
        } else {
            text += sourcePadding(parentSource, node[1]) + '' + node[0] + '' + sourcePadding(node[1], "$") + '';
        }
    } else {
        text += sourcePadding(parentSource, node[1]) + '' + node[0] + '' + tableNTfr(node[2][0], node[1]);
    }
    return text;    
}

function tableNTor(node, skips) {
    //  The other rows in a row span
    var text = "";
    var skipped = [ ...skips ];
    if ( node[2].length != 0 ) {
        if ( node[4] > 1 ) {
            skipped.push([ node[1], node[2][0][1] ]);
            text += tableNTor(node[2][0], skipped)
            for ( var i = 1; i < node[2].length; i++ ) {
                text += ''
                for ( var j = 0; j < skipped.length - 1; j++ ) {
                    text += sourcePadding(skipped[j][0], skipped[j][1], 0);
                }
                text += tableNT(node[2][i], node[1])
            }
        }
    }
    return text;
}

function tableHead(dataSourceIds) {
    text = "";
    for ( var i = 0; i < dataSourceIds.length; i++ ) {
        text += '' + dataSourceIds[i] + '';
    }
    text += '' + 'self-reference' + '';
    return '' + text + '';
}

function doStuff() {
    for ( var i = 0; i < treeRoots.length; i++ ) {
        spanner( treeRoots[i] );
    }
    var printerOne = document.getElementById("printerOne");
    printerOne.innerHTML = printTR( treeRoots );
    var treeTable = document.getElementById("treeTable");
    treeTable.innerHTML = tableHead(dataSourceIds) + tableTR(treeRoots);
}

table {
    border: 1px solid black;
}

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



Parsed nodes with calculated row spans and source:






Tree converted to table rows:

How to convert a tree-like structure to a plain HTML table using rowspans?

Answers (1)

Related Questions