I think I've just stumbled over a problem in the Knuth algorithm. Assume the following element list:
FINE : ElementList: category=breaker, id= FINE : 0) aux. box w=0 FINE : 1) aux. penalty p=INFINITE w=0 FINE : 2) aux. glue w=5000 stretch=0 shrink=0 FINE : 3) box w=10000 FINE : 4) penalty p=0 w=0 FINE : 5) aux. glue w=-5000 stretch=0 shrink=0 FINE : 6) aux. box w=0 FINE : 7) aux. penalty p=INFINITE w=0 FINE : 8) aux. glue w=5000 stretch=0 shrink=0 FINE : 9) box w=10000 FINE : 10) penalty p=0 w=0 FINE : 11) aux. glue w=-5000 stretch=0 shrink=0 FINE : 12) aux. box w=0 FINE : 13) aux. penalty p=INFINITE w=0 FINE : 14) aux. glue w=5000 stretch=0 shrink=0 FINE : 15) box w=10000 FINE : 16) penalty p=0 w=0 FINE : 17) aux. glue w=-5000 stretch=0 shrink=0 FINE : 18) aux. box w=0 FINE : 19) aux. penalty p=INFINITE w=0 FINE : 20) aux. glue w=5000 stretch=0 shrink=0 FINE : 21) box w=10000 FINE : 22) penalty p=0 w=0 FINE : 23) aux. glue w=-5000 stretch=0 shrink=0 FINE : 24) aux. box w=0 FINE : 25) aux. penalty p=INFINITE w=0 FINE : 26) aux. glue w=5000 stretch=0 shrink=0 FINE : 27) box w=10000 FINE : 28) penalty p=INFINITE w=0 FINE : 29) glue w=0 stretch=10000000 shrink=0 FINE : 30) penalty p=-INFINITE w=0 (forced break) Note the negative glue after each page break penalty here. Further assume a page height of 30000 mpt. The first break point is on element 10 (difference=5000). The algorithm currently doesn't create a second break point at element 22 because it thinks it can fit the last 3 boxes into the 30000mpt. I believe now that the -5000mpt from the glue are not taken into account when creating the active nodes, or rather that the -5000 is not eliminated when calculating the difference, and therefore the algorithm falls 5000mpt short of the target. I'm still debuggging to see if I can locate the problem point but since I'm still not fully at home here I thought I should make you aware of this in case someone has a quick answer here. I'm not comfortable with uploading my space resolution code. Therefore, I'm afraid I can't provide a testcase for you to easily reproduce. Makes me wonder if it were very difficult to create JUnit test cases just testing the Knuth algorithm....... Jeremias Maerki
