如何使用行跨度将类似树的结构转换为普通的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>元素是empty
• coveredByRowIndex，意味着它应该使用style="display: none"

这段代码效率很低，但这暂时不重要，我想以后再对它进行优化。

如您所见，rows还没有包含预期的结果。有2个节点破坏了该算法。我对我如何手工操作的思考

由dataSourceId

• for各a组成
• 组节点，创建一个具有空值的新行(a除外)，如果已经存在b，则创建一个
• 填充b
• ，复制该行并用c

<代码>H 135重复c-6的“覆盖”索引

• 重复替换a-6，但c-6取决于b-3，而b-3取决于a-2 < nodes >H 236H 137对dH 238H 238对d-2重复，但d-2取决于b-2。它不能重复该行，因为在c-3行中有足够的空间用于e-2的e-1
• 重复，但是必须用“空”值替换d-2 (将父键和自有键之间的所有源设置为“空”)。

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

Answer 1

我并不是百分之百地相信我已经理解您正在使用的全面通用数据集可能是什么样子，但是下面的代码将执行以下操作：

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

它目前假定：

• 只能自引用根节点。这是可以更改的，但这样做并不容易。
• 依赖源顺序与源的排序顺序相同，目前按字母顺序排列。但是，这可以很容易地设置，而不是从数据中导出，例如，根据您上面的一个知识。
• 虽然可以在节点之间有多条路径，但不能有任何循环，例如，a取决于'c‘on 'a’。这将导致无限循环。

守则中的方法是：

nodes.

• Recursively

• 生成节点的结构化链接列表。

• 获取根

• 解析根节点及其descendants.

。

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

如果你需要任何固定的/改变的东西，请告诉我。

​

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>

​