# [reportlab-users] table row/column spanning

Robin Becker robin at reportlab.com
Mon Oct 29 14:20:41 EDT 2007

I'm looking for advice on row/col spanning algorithms. This should be a solved
problem, but I've looked at code for at least two solutions and find it pretty
hard to figure out what's going on. It's clear the same algorithm applies to
rows/columns so we only need to solve it properly. First some assumptions; we
only calculate values that aren't specified. In the code below V0 represents the
initial values of either width/height; if V0[x] is not None it means the value
is fixed. The list V contains the value computed for width/height without
spanning columns/rows. The spanning constraints are specified as inclusive
ranges spanCons[x0,x1]=v means that the cell at x0 that extends upto and
includes x1 requires at least v units to contain its contents. We are not
supposed to have overlaps (but perhaps our current code doesn't exclude them).
I'm trying to address only the non-overlap case. The function below seems to
work, but is fairly complex and probably someone has something simpler.

When given the values

V0=[None,None,None,None] V=[12, 12, 12, 12]
spanCons={(0, 1): 12, (2, 3): 60, (0, 2): 48}
V ends up as [12, 12, 24, 48].

A description of the intent in words is as follows;

m=maximum_constraint_count;
while m:
find a row, r which appears in m constraints
if no such row:
m -= 1
continue
determine the least value constraint(s) containing r
V[r] += v the value required by the least value constraints
remove the least value constraints
decrement all constraints containing r

the actual code; this requires criticism/improvement etc etc etc. Andy says he
remembers looking at a 9 step html table layout mechanism, but has probably
forgotten where it is.
#########################################
def spanFixDim(V0,V,spanCons,FUZZ=rl_config._FUZZ):
'''assign least required space to variable rows
V0 the original value of heights(None here means not fixed)
V the calculated value for height without spanning cell contribs
all values at least 0
spanCons a map (r0,r1) --> requirement for rows r0<=r<=r1

on exit we should have computed the final heights in V
'''
#R is a map row --> list of constraints
#at the same time make the spanCons map to the extra requirement
R = {}
for rr in spanCons.keys():
t = 0
F = []
for r in xrange(rr[0],rr[1]+1):
if V0[r] is None:
F.append(r)
t += V[r]
if not F: continue #no free space
v = spanCons[rr]
if t>=v-FUZZ: continue #not binding
spanCons[rr] = v-t #the differential amount
for f in F:
R.setdefault(f,[]).append(rr)

#find map N mapping constraint count to rows
#this allows us to locate the largest usages easily
N = {}
m = 0
for r,RR in R.iteritems():
n = len(RR)
if n>m: m = n
N.setdefault(n,[]).append(r)

while m:
#find candidate rows appearing in m constraints
S = N.get(m,None)
if not S:
m -= 1
continue
r = S[0] #we are going to remove this row
RR = R[r] #which appears in these constraints
if len(RR)>1:
v = min(spanCons[rr] for rr in RR) #choose all with minimal value
S = [rr for rr in RR if spanCons[rr]<=v+FUZZ]
else:
S = RR[:] #there's only one
v = spanCons[RR[0]]
V[r] += v #this one is now fixed

for rr in S: #constraint rr is now satisfied
#we remove it and adjust data structures
for f in xrange(rr[0],rr[1]+1):
R[f].remove(rr)
n = len(R[f])
N[n+1].remove(f)
if n:
N.setdefault(n,[]).append(f)
spanCons[rr] -= v

for f in R[r]: #larger constraint containing r is decreased
spanCons[f] -= v
#########################################
--
Robin Becker