TableLayout/KnuthElementsForTables

[Simon Pepping <sp...@leverkruid.nl>]

Jeremias,

I read your TableLayout/KnuthElementsForTables wiki page with
interest. Luca's algorithm is a fine algorithm.

I do have a problem with your last example. Half of the border-after
of the table-header is counted twice, once in the row heights and once
in the header itself. All heights before the page break except the
second one are 2 units too high, and those after the page break are 4
units too high when I compare them with your drawings of the table.

I believe it is better to omit half of the border-after
of the table-header and half of the border-before of the table-footer
from the row height. Then I get the following calculations:

Header is 5 + 8 = 13
Footer is 8 + 5 = 13

row1: 15 + (2/2) => (16,16,16)
row2: 20 + (2/2) => (21,21,21)
row group (37,37,37)

Step 1:
stepw= 10
maxRemainingHeight = 37
addedBoxHeight = 0
penalty = 10 + 37 - 37 = 10
effPenalty: w = 10 (space for block1) + 13 (header) + 4 (border-after-header) + 4 (border-before-footer) + 13 (footer)
box = 10 - 0 - 10 = 0

Step 2:
stepw = 15
maxRemaningHeight = 20
addedBoxHeight = 0
penalty = 15 + 20 - 37 = -2
offPenalty: w = -2 (calc penalty) + 13 + 4 + 4 + 13
box = 15 - 0 - (-2) = 17

Step 3:
stepw = 10 + 10 = 20
maxRemainingHeight = 20
addedBoxHeight = 17
penalty = 20 + 20 - 37 = 3
effPenalty: w = 3 (calc penalty) + 13 + 4 + 4 + 13
box = 20 - 17 - 3 = 0

Step 4:
stepw = 10 + 10 + 10 = 30
maxRemaningHeight = 20
addedBoxHeight = 17
penalty = 30 + 20 - 37 = 13
effPenalty: w = 14 (calc penalty) + 13 + 4 + 4 + 13
box = 30 - 17 - 13 = 0

Step 5:
stepw = 15 + 2 + 20 = 37
maxRemainingHeight = 0
addedBoxHeight = 17
penalty = 37 + 0 - 37 = 0 (last step, omit penalty)
box = 37 - 17 - 0 = 20

box(0)
penalty(10) -> 10/37
box(17)
penalty(-2) -> 15/20
box(0)
penalty(3)  -> 20/20
box(0)
penalty(13) -> 30/20
box(20)
            -> 37

box(0)
penalty(44) //incl. header and footer -> 44/71
box(17)
penalty(32) //incl. header and footer -> 49/54
box(0)
penalty(37) //incl. header and footer -> 54/54
box(0)
penalty(47) //incl. header and footer -> 64/54
box(20)
box(17) //header
box(17) //footer
                                      -> 71

You see I can avoid the subtraction of 2 for the second page break,
which makes the calculation more regular. I do get a negative
penalty. I do not believe that that is a problem, less so because it
is added to the penalty for the header/footer/borders. It expresses
the fact that for this page break the table is shorter than without
page break, due to the merger of the row border with the header and
footer borders.

Regards, Simon

-- 
Simon Pepping
home page: http://www.leverkruid.nl

Re: TableLayout/KnuthElementsForTables

[Jeremias Maerki <de...@greenmail.ch>]

Simon,

thanks for looking into this.

On 09.04.2005 13:31:14 Simon Pepping wrote:
> Jeremias,
> 
> I read your TableLayout/KnuthElementsForTables wiki page with
> interest. Luca's algorithm is a fine algorithm.
> 
> I do have a problem with your last example. Half of the border-after
> of the table-header is counted twice, once in the row heights and once
> in the header itself. All heights before the page break except the
> second one are 2 units too high, and those after the page break are 4
> units too high when I compare them with your drawings of the table.

You're right. I made a mistake there. I should have visually compared
the calculated results.

> I believe it is better to omit half of the border-after
> of the table-header and half of the border-before of the table-footer
> from the row height. Then I get the following calculations:
> 
> Header is 5 + 8 = 13
> Footer is 8 + 5 = 13
> 
> row1: 15 + (2/2) => (16,16,16)
> row2: 20 + (2/2) => (21,21,21)
> row group (37,37,37)
> 
> Step 1:
> stepw= 10
> maxRemainingHeight = 37
> addedBoxHeight = 0
> penalty = 10 + 37 - 37 = 10
> effPenalty: w = 10 (space for block1) + 13 (header) + 4 (border-after-header) + 4 (border-before-footer) + 13 (footer)
> box = 10 - 0 - 10 = 0
> 
> Step 2:
> stepw = 15
> maxRemaningHeight = 20
> addedBoxHeight = 0
> penalty = 15 + 20 - 37 = -2
> offPenalty: w = -2 (calc penalty) + 13 + 4 + 4 + 13
> box = 15 - 0 - (-2) = 17
> 
> Step 3:
> stepw = 10 + 10 = 20
> maxRemainingHeight = 20
> addedBoxHeight = 17
> penalty = 20 + 20 - 37 = 3
> effPenalty: w = 3 (calc penalty) + 13 + 4 + 4 + 13
> box = 20 - 17 - 3 = 0
> 
> Step 4:
> stepw = 10 + 10 + 10 = 30
> maxRemaningHeight = 20
> addedBoxHeight = 17
> penalty = 30 + 20 - 37 = 13
> effPenalty: w = 14 (calc penalty) + 13 + 4 + 4 + 13
> box = 30 - 17 - 13 = 0
> 
> Step 5:
> stepw = 15 + 2 + 20 = 37
> maxRemainingHeight = 0
> addedBoxHeight = 17
> penalty = 37 + 0 - 37 = 0 (last step, omit penalty)
> box = 37 - 17 - 0 = 20
> 
> box(0)
> penalty(10) -> 10/37
> box(17)
> penalty(-2) -> 15/20
> box(0)
> penalty(3)  -> 20/20
> box(0)
> penalty(13) -> 30/20
> box(20)
>             -> 37
> 
> box(0)
> penalty(44) //incl. header and footer -> 44/71
> box(17)
> penalty(32) //incl. header and footer -> 49/54
> box(0)
> penalty(37) //incl. header and footer -> 54/54
> box(0)
> penalty(47) //incl. header and footer -> 64/54
> box(20)
> box(17) //header
> box(17) //footer
>                                       -> 71

Looks good now.

> You see I can avoid the subtraction of 2 for the second page break,
> which makes the calculation more regular. I do get a negative
> penalty. I do not believe that that is a problem, less so because it
> is added to the penalty for the header/footer/borders. It expresses
> the fact that for this page break the table is shorter than without
> page break, due to the merger of the row border with the header and
> footer borders.

I agree.

There's something else: I think your second example [1] is also not
fully correct. The border-before of the table-footer on the first page
in step 1 should be 6 units wide, not 4 because we're still in row 1
there. Also, step 3 may be subject to discussion. Actually, your example
is a very interesting one. Please have a look at the PDF I published [2]
which contains 3 examples: The first is the one you corrected above, the
second is yours and the third I'm describing below. In my visual
interpretation of your example the border-after of the first row
actually intrudes the normal border-before of the table-footer. I
therefore enlarged the row 1 a bit and made block2 part of row 1 while
in my earlier example block2 ends up in both row 1 and 2 due to spanning.

The third example in my PDF is the same as yours, except that I
duplicated the column 2 and modified the two cells to have a
border="solid 8" which makes it dominant over all others but only for
this column. I've only got the non-broken variant right now but I think
it's obvious that the whole thing just got a bit more complicated (even
if the example again is not really a real-world application). I'm taking
the material with me and hope that I'll have time to do more studies. I
have a feeling that this third example might just have another hint
towards the right algorithm.

If anyone wants to take a shot at the table LMs during the next week,
feel free! I haven't started the border stuff, yet, due to the problem
Simon indicated.

[1] http://wiki.apache.org/xmlgraphics-fop/TableLayout/KnuthElementsForTables/RowBorder
[2] http://people.apache.org/~jeremias/fop/KnuthBoxesForTablesWithBorders.pdf


Jeremias Maerki