[reportlab-users] table row/column spanning

[Robin Becker]

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