Re: Knuth algorithm problem
Thank you so much for looking into it. From the sound of it I would have continued my search for a long time. On 06.10.2005 11:42:19 Luca Furini wrote: > Luca Furini wrote: > > > I'm going to see what happens ... > > I've found the bug! > > The width, stretch and shrink of the suppressed elements after a break is > taken into account in BreakingAlgorithm.addBreaks(), but this method is > called only if everythings goes well; in your test there is a restart (as > the only created node is too short) and addBreaks() is not called, so the > width (and stretch, and shrink) stored in the node is potentially wrong. > > I'm going to see the best way to fix this without duplicating lines of > code. I think the "for" loop (over the elements that must be ignored) > could be moved into createNode() ... > > In general, the restarting method is quite a critical phase: we are > "resurrecting" a node which was not very good, and maybe not all the > information stored inside it is always correct. > > Regards > Luca Jeremias Maerki
Re: Knuth algorithm problem
Luca Furini wrote: I'm going to see what happens ... I've found the bug! The width, stretch and shrink of the suppressed elements after a break is taken into account in BreakingAlgorithm.addBreaks(), but this method is called only if everythings goes well; in your test there is a restart (as the only created node is too short) and addBreaks() is not called, so the width (and stretch, and shrink) stored in the node is potentially wrong. I'm going to see the best way to fix this without duplicating lines of code. I think the "for" loop (over the elements that must be ignored) could be moved into createNode() ... In general, the restarting method is quite a critical phase: we are "resurrecting" a node which was not very good, and maybe not all the information stored inside it is always correct. Regards Luca
Re: Knuth algorithm problem
Jeremias Maerki wrote: I think I've just stumbled over a problem in the Knuth algorithm. I'm going to see what happens ... Regards Luca
Re: Knuth algorithm problem
The reference I found was in the section about avoiding "psychologically bad" breaks. AFAICS the auxiliary flag is used in line breaking in the hyphenation code, but the breaker algorithm actually doesn't care about it. For page breaking the meaning of the auxiliary flag is undefined, but I've used it to mark elements which are handled in a special way like the elements created by the space resolution. It was simply handy for them to stand out in debug output. There's no logic triggered by the flag and I don't have a problem removing the auxiliary flags if anyone prefers that I should not use them. On 05.10.2005 22:16:11 Simon Pepping wrote: > 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? Jeremias Maerki
Re: Knuth algorithm problem
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=1 > 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=1 > 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=1 > 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=1 > 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=1 > FINE : 28) penalty p=INFINITE w=0 > FINE : 29) glue w=0 stretch=1000 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 3 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 3mpt. 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
Re: Knuth algorithm problem
It's easy after all: http://svn.apache.org/viewcvs?rev=295059&view=rev On 05.10.2005 17:01:23 Jeremias Maerki wrote: > Makes me wonder if it > were very difficult to create JUnit test cases just testing the Knuth > algorithm... Jeremias Maerki
Knuth algorithm problem
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=1 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=1 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=1 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=1 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=1 FINE : 28) penalty p=INFINITE w=0 FINE : 29) glue w=0 stretch=1000 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 3 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 3mpt. 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
