Rowspan "clearing" the algorithm
I have a structure similar to the colspan / rowspan HTML table:
[
[1,4], [4,1]
[2,2], [2,2]
[1,1], [1,1], [1,1], [1,1]
]
looks like
<tr>
<td rowspan=4></td>
<td colspan=4></td>
</tr>
<tr>
<td rowspan=2 colspan=2></td>
<td colspan=2 rowspan=2></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
----------------
| | |
| |-----------|
| | | |
| |-----------|
| | | | | |
----------------
The second row (and the first cell from the first row that spans all 4 rows) in
[
[1,3], [4,1]
[2,1], [2,1]
[1,1], [1,1], [1,1], [1,1]
]
and the "topology" of the table remains the same
However a table like
[
[1,4], [4,1]
[2,2], [2,1]
[2,1],
[1,1], [1,1], [1,1], [1,1]
]
----------------
| | |
| |-----------|
| | | |
| | |-----|
| | | |
| |-----------|
| | | | | |
----------------
does not "shrink"
What is an efficient algorithm to perform this transformation or leave the table as it is? Any programming language will work.
Suppose the structure is valid (missing cells, table is rectangular) if it makes things easy
source to share
Convert cell extents to coordinates.
0 1 2 3 4 5
0 ----------------
| | |
1 | |-----------|
| | | |
| | | |
| | | |
3 | |-----------|
| | | | | |
4 ----------------
Compute a sorted set of y-coordinates ( 0, 1, 3, 4
). Match each coordinate with its index in the set ( 0: 0, 1: 1, 3: 2, 4: 3
).
Compute a sorted set of x-coordinates ( 0, 1, 2, 3, 4, 5
). Map each coordinate to its index in the set (identity mapping).
0 1 2 3 4 5
0 ----------------
| | |
1 | |-----------|
| | | |
| | | |
| | | |
2 | |-----------|
| | | | | |
3 ----------------
Convert cell coordinates back to extents.
source to share