Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Algorithmus um tree-like Struktur in HTML Tabelle darstellen zu können

Werbeanzeige

johannestuchel

Frischling

  • »johannestuchel« ist der Autor dieses Themas

Beiträge: 1

  • Private Nachricht senden

1

30.09.2022, 12:37

Algorithmus um tree-like Struktur in HTML Tabelle darstellen zu können

Ich habe eine Liste von Nodes aus unterschiedlichen Datenquellen. Ein einzelnes Node kann von 0 bis n anderen Nodes abhängen, aber es kann nur von Nodes von einer Quelle abhängen.

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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"] },
];


Diese Liste ist nicht sortiert, die Reihenfolge ist zufällig ( und sollte auch nicht wichtig sein )

Ich möchte diese Struktur als HTML Tabelle ausgeben lassen, mithilfe von Rowspans. Was ich weiß, ist die Reihenfolge der Spalten, da jede Datasource eine Spalte repräsentiert.

Quellcode

 
1

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


Das erste Element in diesem Array ist immer die Gruppe der Root Nodes ( in diesem Fall also "a" ).

Nach ich mir das in Excel aufgemalt habe, habe ich erstmal versucht, mein erwartetes Ergebnis in HTML darzustellen ( ihr könnt euch den Output im Snippet anschauen https://jsfiddle.net/671egu24/ )

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

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


Ich dachte, dass man spaltenweise die Tabelle aufziehen kann, indem man erst die Zeilen der Root Nodes erzeugt und dann bei allen weiteren Nodes immer schaut, ob dieses Node noch in die Zeile passt und ggf. die Zeile dupliziert ( damit erhält der Vater einen zustzlichen Rowspan )

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

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


wobei

  • "empty" bedeutet, dass dort später ein leeres td Element erzeugt werden soll ( für diese Zelle gibt es einfach keine Daten )
  • "coveredByRowIndex" bedeutet, dass dort später ein ausgeblendetes td Element ( für den Rowspan ) erzeugt werden soll

Um die Performance möchte ich mich später kümmern, ich weiß, dass dort viele Schleifen laufen. Wichtiger war mir erstmal, ans Ziel zu kommen.

Wer den Code gerne ausprobieren möchte => https://jsfiddle.net/vcpw6hLb/

Die beiden Nodes, die den Algorithmus kaputt gehen lassen, habe ich auskommentiert. Gedanklich gehe ich den Algorithmus wie folgt durch

  • Nodes nach Datasource gruppieren
  • Für jedes a eine neue Reihe erzeugen, mit "empty" Werten ( außer bei dem a )
  • b an passende Stelle setzen
  • wenn der Platz für das b bereits von einem anderen b belegt ist, diese Reihe duplizieren und das a durch ein "covered" ersetzen ( Rowspan )
  • genauso für c anwenden
  • für c-6 auch, aber da c-6 auf b-3 guckt und dieses auf a-2 guckt, muss in diesem Fall auch ein Rowspan für a-2 gesetzt werden
  • genauso für d-1 anwenden
  • für d-2 auch, aber d-2 guckt auf b-2, darf die Reihe aber nicht duplizieren, da es erkennt, dass bei c-3 noch Platz ist
  • genauso für e-1 anwenden
  • für e-2 auch, aber da müsste noch in der neuen Reihe d-2 durch ein "empty" ersetzt werden => alle Keys, die zwischen dem Vater Key und dem eigenen Key liegen auf "empty" setzen
  • self-reference ist wieder "normal"

Habt ihr Ideen, wie man dieses Problem elegant löst?

Schon einmal vielen Dank für Ideen!

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »johannestuchel« (04.10.2022, 10:29)

Ähnliche Themen