javascript - 如何使用 rowspans 将树状结构转换为纯 HTML 表格？

Question

给定来自不同数据源的节点结构，其中一个节点依赖于0到n个其他节点，但单个节点只能依赖于一个源的节点

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未排序，顺序是随机的(并且应该无关紧要)。

我想使用行跨度将此结构表示为 HTML 表。我所知道的是列的顺序，其中每个数据源代表一列

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

dataSourceIds 中的第一项( "a") 始终代表根节点组。

首先我尝试“绘制”预期结果

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

<table>
  <thead>
    <tr>
      <th>a</th>
      <th>b</th>
      <th>c</th>
      <th>d</th>
      <th>e</th>
      <th>self-reference</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td rowspan="9">a-1</td>
      <td>b-1</td>
      <td>c-1</td>
      <td><!-- Empty for source d --></td>
      <td>e-1</td>
      <td>a-1</td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td rowspan="6">b-2</td>
      <td>c-2</td>
      <td>d-1</td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-2 rowspan --></td>
      <td rowspan="2">c-3</td>
      <td>d-2</td>
      <td>e-1</td>
      <td><!-- Empty for source a-to-a --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-2 rowspan --></td>
      <td style="display: none"><!-- Covered by c-3 rowspan --></td>
      <td><!-- Empty for source d --></td>
      <td>e-2</td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-2 rowspan --></td>
      <td>c-4</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-2 rowspan --></td>
      <td>c-5</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-2 rowspan --></td>
      <td>c-6</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td rowspan="2">b-3</td>
      <td>c-5</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-3 rowspan --></td>
      <td>c-6</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td rowspan="2">a-2</td>
      <td rowspan="2">b-3</td>
      <td>c-5</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-2 rowspan --></td>
      <td style="display: none"><!-- Covered by b-3 rowspan --></td>
      <td>c-6</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td>a-3</td>
      <td><!-- Empty for source b --></td>
      <td><!-- Empty for source c --></td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
  </tbody>
</table>

这是我迄今为止尝试过的

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);

哪里

• "empty"意味着 <td>元素为空
• coveredByRowIndex意味着它应该使用 style="display: none"

代码效率低下，但现在这不重要，我想稍后优化它。

如您所见 rows尚未包含预期结果。有 2 个节点破坏了算法。我对如何手动完成的想法

• 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

你们有什么想法可以解决这个问题吗？我不认为我需要最终的代码，我只是不知道如何设置算法......所以任何伪代码/算法建议都将受到高度赞赏!

Answer 1

我不是 100% 确信我已经理解您正在使用的完全通用的数据集可能是什么样子，但下面的代码将执行以下操作:

• 解析任意长度和任意依赖关系的节点的任意列表深度。
• 以任意依赖顺序处理任意数量的源。

目前假设:

• 只有根节点可以自引用。这是可以改变的，但是这样做并非易事。
• 依赖源顺序与源排序顺序相同，目前按字母顺序排列。但这可以很容易地设置而不是派生根据数据，例如，根据您上面的已知信息之一。
• 虽然节点之间可以有多条路径，但不能有任何循环，例如“a”依赖于“b”、“c”、“a”。这将导致无限循环。

代码中的做法是:

• 创建节点的结构化链表。
• 获取根节点。
• 递归解析根节点及其后代。

代码中有一些进一步的解释性注释。

如果您需要修复/更改任何内容，请告诉我。

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 += "&nbsp;"
    }
    return text;
}

//  Utility to print a node tree
function printNT(node, depth) {
    var text = "";
    text += '<br>' + 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 = '<tr>' + tableNT(treeRoots[i], "").replaceAll("</tr>", "<td></td></tr>");
        //  Add in a self reference
        if ( selfRefs.indexOf(treeRoots[i][0]) != -1 ) {
            ndx = textRoot.indexOf("</td></tr>");
            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 += '<td>' + '</td>';
        }
    } else if ( parent != child && parent != "" ) {
        for ( var i = 1; i < dataSourceIds.indexOf(child) - dataSourceIds.indexOf(parent); i++ ) {
            text += '<td>' + '</td>';
        }
    }
    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]) + '<td>' + node[0] + '</td>' + tableNTfr(node[2][0], node[1]);
        } else {
            text += sourcePadding(parentSource, node[1]) + '<td>' + node[0] + '</td>' + sourcePadding(node[1], "$") + '</tr>';
        }
    } else {
        text += sourcePadding(parentSource, node[1]) + '<td rowspan="' + node[4] + '">' + node[0] + '</td>' + 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 += '<tr>' + 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]) + '<td>' + node[0] + '</td>' + tableNTfr(node[2][0], node[1]);
        } else {
            text += sourcePadding(parentSource, node[1]) + '<td>' + node[0] + '</td>' + sourcePadding(node[1], "$") + '</tr>';
        }
    } else {
        text += sourcePadding(parentSource, node[1]) + '<td rowspan="' + node[4] + '">' + node[0] + '</td>' + 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 += '<tr>'
                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 += '<th>' + dataSourceIds[i] + '</th>';
    }
    text += '<th>' + 'self-reference' + '</th>';
    return '<tr>' + text + '</tr>';
}

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;
}

<body onload="doStuff()">
<div>
Parsed nodes with calculated row spans and source:
<div id="printerOne">
</div>
</div>
<br>
<div>
Tree converted to table rows:<br>&nbsp;
<div>
<table id="treeTable">
</table>
</div>
</body>