Input: a set of regions, each of which takes up a given set of columns region.cols
for a given number of rows region.rows
.
Output: a mapping from regions to their start rows.
Greedy first fit algorithm (sketch):
For each column, keep track of the set of allocated [start, end) intervals so far.
We greedily find a placement for each region in turn (there is no backtracking at the region level):
- Start with the interval of all possible rows. For each column used by this region, recursively narrow the interval in which we could potentially place the region. We do this by intersecting the current interval with the free intervals in each used column. If it won't fit, backtrack to the next free interval.
It is probably easier to explain this just by giving a Python implementation:
#!/usr/bin/env python3
from math import inf
class Region:
def __init__(self, rows, cols):
self.rows = rows
self.cols = cols
def __repr__(self):
return "Region(%d, %r)" % (self.rows, self.cols)
class Column:
def __init__(self, index):
self.index = index
# allocs is an unordered list of [start, end) pairs.
self.allocs = []
def __repr__(self):
return "Column(%d): %r" % (self.index, self.allocs)
def plan(regions):
for reg in regions:
start = first_fit_region(reg, 0, 0, inf)
# Some placement must be possible given infinite rows.
assert start is not None
print("%4r: %r" % (start, reg))
def first_fit_region(reg, col_index, start, end):
assert start + reg.rows <= end
if col_index == len(reg.cols):
return start
c = reg.cols[col_index]
# Iterate over the unallocated nonempty intervals in c that intersect [start, end).
for (c_start, c_end) in free_intervals(c.allocs, start, end):
# Do we have enough room for this column of reg?
if c_start + reg.rows <= c_end:
# Recursively check whether the placement works for all other columns of reg.
row = first_fit_region(reg, col_index+1, c_start, c_end)
if row is not None:
# It works. On the way back out of the recursion, record the placement.
assert row + reg.rows <= c_end
c.allocs.append((row, row + reg.rows))
return row
# No placement worked; the caller will need to try other possibilities.
return None
# allocs is a set of [a_start, a_end) pairs representing disjoint allocated intervals.
# Return all the *unallocated* nonempty intervals intersecting [start, end).
def free_intervals(allocs, start, end):
row = start
for (a_start, a_end) in sorted(allocs):
if a_start >= end:
# further allocated intervals don't intersect
break
if row < a_start:
yield (row, a_start)
row = max(row, a_end) # Edit: fixed bug here.
if row < end:
yield (row, end)
def test():
(c1, c2, c3) = (Column(1), Column(2), Column(3))
reg1 = Region(15, [c1, c2])
reg2 = Region(10, [c3])
reg3 = Region(10, [c3, c1])
plan([reg1, reg2, reg3])
if __name__ == "__main__":
test()
Here's the placement that this algorithm finds for the test case:
0: Block(15, [Column(1): [(0, 15)], Column(2): [(0, 15)]])
0: Block(10, [Column(3): [(0, 10)]])
15: Block(10, [Column(3): [(0, 10), (15, 25)], Column(1): [(0, 15), (15, 25)]])
i.e.
![example](https://user-images.githubusercontent.com/643204/102728344-4413d980-4323-11eb-8262-3e95d46460fb.jpg)