Auto-place items in a CSS grid

Reproduce CSS grid auto-placement for grid-auto-flow: row (sparse, when dense is false) and grid-auto-flow: row dense (when it is true). The grid has columns explicit columns and as many rows as it needs. Each item is [order, col, col_span, row_span]: its CSS order, the 0-based column it is pinned to or null (None in Python) when its column is automatic, and how many columns and rows it spans, each at least 1. No item is pinned to a row. Return each item's top-left cell as [row, col], 0-based, in input order.

1. Width. The grid is widened to fit every item: a pinned item needs col + col_span columns and an automatic one needs col_span.
2. Order. Items are placed one at a time, sorted by order (which may be negative), ties keeping input order.
3. Fit. An item fits at a cell when every cell it would cover lies inside the grid's width and is not covered by an item placed earlier.
4. Sparse. A cursor starts at row 0, column 0, and only ever moves forward:
   • A pinned item sets the cursor's column to its own column, and if that is less than the cursor's previous column, the cursor first moves down one row. Checking the cursor's own row first, the cursor then moves down a row at a time until the item fits.
   • An automatic item is tried at the cursor's own cell first, then the cursor moves right a column at a time until the item fits. Whenever the item would stick out past the last column, the cursor goes to column 0 of the next row.
   • The item is placed at the cursor, and the cursor stays on the item's top-left cell.
5. Dense. There is no cursor. A pinned item takes the first row, counting from 0, where it fits in its column. An automatic item takes the first cell where it fits, scanning rows from 0 and each row from column 0.

Examples:

• grid_place(3, [[0, None, 2, 1], [0, None, 2, 1], [0, None, 1, 1]], False) returns [[0, 0], [1, 0], [1, 2]]: the second wide item does not fit beside the first, and the small item cannot go back to the hole at row 0, column 2.
• The same call with dense true returns [[0, 0], [1, 0], [0, 2]]: dense packing fills that hole.
• grid_place(3, [[0, None, 1, 1], [0, 2, 1, 2], [0, 0, 1, 1], [0, None, 1, 1]], False) returns [[0, 0], [0, 2], [1, 0], [1, 1]]: the item pinned to column 0 comes after one pinned to column 2, so the cursor moves down a row first.