I have never really understood the role of the aux flag on the elements. Is it only for the addAreas phase, or does it also play a role in the breaker algorithm?
Simon On Wed, Oct 05, 2005 at 05:01:23PM +0200, Jeremias Maerki wrote: > 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 > -- Simon Pepping home page: http://www.leverkruid.nl
