- From: Oriol Brufau via GitHub <sysbot+gh@w3.org>
- Date: Sat, 14 Jul 2018 23:31:03 +0000
- To: public-css-archive@w3.org
I took another look at this and designed an algorithm which works in polynomial time:
1. For each column `col`,
1. Let `max = 0`
2. For each row `row` s.t. there is some element in `(row, col)`,
1. For simplicity I assumed there can only be a single element in that cell (no overlapping), but shouldn't be hard to generalize.
2. If an element starts at the beginning of `col`, you associate its content width with `row`.
2. If an element ends at the end of `col`,
1. Let `v` be the value associated with `row`.
2. Set `max = Math.max(max, v)`
3. The width of the column `col` is set to `max`.
4. For each row `row` s.t. there is a cell in `(row, col)`,
1. Subtract `max` from its associated value, clamping at zero.
It doesn't respect this invariant:
> it doesn't matter the order of how items are processed the result should be the same
but this wasn't either in the LP formulation above.
In particular, the result doesn't look balanced, and the size distribution varies significantly depending on whether you iterate columns left-to-right or right-to-left. But this has an easy fix: first you calculate the column sizes iterating columns left-to-right, then right-to-left, and finally you average both values per each column.
I wrote the algorithm in JS, you can see the result in
<details><summary>Code</summary>
```js
window.addEventListener("load", function() {
document.querySelectorAll(".polyfill").forEach(polyfill);
});
function polyfill(grid) {
grid.style.display = "block";
let itemData = new Map();
let n = 0;
let m = 0;
for (let child of grid.children) {
let cs = getComputedStyle(child);
itemData.set(child, {
colStart: cs.gridColumnStart - 1,
colEnd: cs.gridColumnEnd - 1,
rowStart: cs.gridRowStart - 1,
rowEnd: cs.gridRowEnd - 1,
contentSize: child.offsetWidth,
});
n = Math.max(n, cs.gridRowEnd - 1);
m = Math.max(m, cs.gridColumnEnd - 1);
}
grid.style.display = "";
let gap = parseFloat(getComputedStyle(grid).columnGap) || 0;
let cells = Array(n).fill().map(_ => Array(m));
for (let data of itemData.values()) {
let {rowStart, rowEnd, colStart, colEnd} = data;
for (let i = rowStart; i < rowEnd; ++i) {
for (let j = colStart; j < colEnd; ++j) {
cells[i][j] = data;
}
}
}
function main(reversed) {
let columnSizes = Array(m);
let currentSizes = Array(n);
let col = reversed ? m - 1 : 0;
while (reversed ? col >= 0 : col < m) {
let max = 0;
let rowsWithCells = [];
for (let row = 0; row < n; ++row) {
let cell = cells[row][col];
if (!cell) continue;
let {colStart, colEnd} = cell;
if (reversed) [colStart, colEnd] = [colEnd-1, colStart+1];
rowsWithCells.push(row);
if (colStart === col) {
currentSizes[row] = cell.contentSize;
}
if (colEnd - 1 === col) {
max = Math.max(max, currentSizes[row]);
} else {
currentSizes[row] = Math.max(0, currentSizes[row] - gap);
}
}
columnSizes[col] = max;
for (let row of rowsWithCells) {
currentSizes[row] = Math.max(0, currentSizes[row] - max);
}
col += reversed ? -1 : 1;
}
return columnSizes;
}
let columnSizes1 = main(false);
let columnSizes2 = main(true);
let average = columnSizes1.map((n, i) => (n + columnSizes2[i])/2);
let result = average.map(n => n + "px").join(" ");
grid.style.gridTemplateColumns = result;
let pre = document.createElement("pre");
pre.textContent = "columns: " + result;
grid.parentElement.insertBefore(pre, grid.nextSibling);
}
```
</details>
http://jsbin.com/qazuyucege/edit
http://jsbin.com/juzetolazi/edit
http://jsbin.com/yisedereyo/edit
The output for Florian's example is exactly like the reference (`grid-template-columns: 160px 140px 110px 40px 210px`).
The output for Manuel's 1st example is a bit different (`grid-template-columns: 100px 200px 75px 75px`), but close enough.
The output for Manuel's 2nd example is maybe more unexpected (`grid-template-columns: 25px 275px 0px`), but the size is minimal for sure XD
--
GitHub Notification of comment by Loirooriol
Please view or discuss this issue at https://github.com/w3c/csswg-drafts/issues/2356#issuecomment-405056334 using your GitHub account
Received on Saturday, 14 July 2018 23:31:11 UTC