On 29.03.2005 13:56:59 Luca Furini wrote: > Jeremias Maerki wrote: <snip/> > > For those who want to join the mind game, > > here are the expected results from the broken lists: > > > > break at first legal break: > > Part 1 (height -> 15): > > Part 2 (height -> 41): > > > > break at second legal break: > > Part 1 (height -> 30): > > Part 2 (height -> 41): > > > > break at third legal break: > > Part 1 (height -> 33): > > Part 2 (height -> 15): > > > > break at fourth legal break: > > Part 1 (height -> 41): > > Part 2 (height -> 15): > > > > no breaks: > > Part 1 (height -> 45): > > This could be the procedure that creates the combined elements, at least > when there is no stretch nor shrink;
I'm impressed! > with this assumption, the resulting > sequence will contain only boxes and penalties. I guess the sequence will have to be post-processed to add penalties for table-header/footer but that shouldn't be a problem. "before" and "after" cell borders will also be no big problem. Just saying this so we have the whole picture. > First of all, we must know the total height of the row, if it is not split > between pages. > > totalHeight = 0 > for each cell-list > height[i] = compute the total height of each cell-list > if (height[i] > totalHeight) > totalHeight = height[i] > > The sequence we are going to create must be totalHeight long when it is > not divided. > > step = 0 > addedBoxHeight = 0; > while step < totalHeight > step = nextStep() > penaltyHeight = step + maxRemainingHeight() - totalHeight > boxHeight = step - addedBoxHeight - penaltyHeight > addedBoxHeight += boxHeight > sequence.add(new box(boxHeight)) > sequence.add(new penalty(penaltyHeight, 0)) > > For each cell-list, we must know, besides the total height, the height of > the elements already combined into the new ones. > The nextStep() method looks at each cell-list, computing the height of the > first sub-sequence, chooses the smallest increase and updates in each list > the height of the elements already combined; maxRemainingHeight() returns > the greatest difference between the total height of a cell-list and the > height of the elements already combined. > > Using your example, the behaviour of this algorithm is this: > > totalHeight = 45 > > 1st step: step = 15 > maxRemaingHeight = 41 > addedBoxHeight = 0 > penaltyHeight = 15 + 41 - 45 = 11 > boxHeight = 15 - 0 - 11 = 4 > > 2nd step: step = 30 > maxRemaingHeight = 41 > addedBoxHeight = 4 > penaltyHeight = 30 + 41 - 45 = 26 > boxHeight = 30 - 4 - 26 = 0 > > 3rd step: step = 33 > maxRemaingHeight = 15 > addedBoxHeight = 4 > penaltyHeight = 33 + 15 - 45 = 3 > boxHeight = 33 - 4 - 3 = 26 > > 4th step: step = 41 > maxRemaingHeight = 15 > addedBoxHeight = 30 > penaltyHeight = 41 + 15 - 45 = 11 > boxHeight = 41 - 30 - 11 = 0 > > 5th step: step = 45 > maxRemaingHeight = 0 > addedBoxHeight = 30 > penaltyHeight = 45 + 0 - 45 = 0 > boxHeight = 45 - 30 - 0 = 15 > > > combined elements, with their width and what happens if a penalty is used: > > box 4 > penalty 11 ----> 15+41 > box 0 > penalty 26 ----> 30+41 > box 26 > penalty 3 ----> 33+15 > box 0 > penalty 11 ----> 41+15 > box 15 ----> 45 Wow. > I think this procedure could be quite easily extended in order to take > into account stretch and shrink. I'm not so sure. I agree that some degree of stretch and shrink we be no problem for the algorithm, but depending on the amount of shrinkability and stretchability you might get different step constellations you probably can't construct like this. We probably have to play a few scenarios through here. > > An alternative approach might be to do create "combined stretch boxes" > > (actually box+pen(inf)+glue) > > > > Cell1, combined stretch box: w=45000 y=30000 z=0 > > Cell2, combined stretch box: w=30000 y=15000 z=15000 > > Cell2a, combined stretch box: w=41000 y=8000 z=0 > > > > The combined stretch box for the whole row is easily calculated: > > > > row combined stretch box in both cases (2 and 2a) is: > > w=45000 y=30000 z=0 > > > > The LM tries to fit as much as possible into the available area (similar > > to block-container with fixed BPD). The rest that doesn't fit at the end > > is deferred for the next page where a new combined stretch box is > > calculated. The consequence of this is the loss of look-ahead > > possibility, since the combined stretch box doesn't know how much can > > really fit on the previous page, and a new block list needs to be built. > > Yes, I think we should use this approach only if we don't find a better > one ... But still, we have to realize that the "combined list approach" cannot handle auto layout when there's different available IPD between pages or if the auto layout algorithm to be written should calculate new column widths for every page. Maybe sooner or later we may have to implement some kind of back tracking functionality, so we can discard some already generated elements and recreate them using new parameters. If we can do without it for the moment that would be good (80:20 rule). I don't think this will invalidate the work on combined lists. After all, it will only be a way to restart at an earlier point. However, the implementation itself will probably not be so easy (but I may be wrong). You gave me hope that we can use the "combined list" approach which I would me more comfortable with, except that stretch is probably easier with the "stretch box" approach. > > A point I still have to think about for both approaches is how exactly > > to handle row spanning, although I suspect it'll be easier for the first > > approach. > > I did not think about this yet, but I agree with you. I'll try to construct an example based on your algorithm. Jeremias Maerki
