On Oct 24, 2008, at 17:34, Dario Laera wrote:

Hi Daerio,

(thought I'd finally chime in; I've been following your progress with much interest, but did not feel I could contribute anything...)
<snip />
A really strange thing: is it theoretically possible that the amount of active nodes is greater than the number of knuth elements?

Yes, definitely. In the sense that a 'node' represents a (set of) break-possibilit(y|ies), and without applying any pruning, all such possibilities remain 'possible' the whole time, until the entire set of actual breaks is known (= total-fit).

If I'm guessing correctly, a nice demonstration to see if there are additional benefits to your proposal, would be to try pasting the text of a short to medium-sized book into one single monolithic fo:block. Don't use linefeed preservation, and plain start-alignment. The number of break-possibilities the algorithm has to consider becomes so large, that you easily need +500MB of heap for about 40 pages. (I did this test some time ago, and then I had to give the JVM at least 720MB of heap to render a block with the content of Shakespeare's Hamlet.)

Not a real-life use case, but always a very interesting test to see whether the line-breaking algorithm has scaleability issues.

(in response to your earlier post)
Initially I was setting TD to startLine, but then I noticed that in short line the pruning were activated when startLine was 5 and endLine was 44 (!), so I decided that the mean was a better choice. I can't explain how it's possible that the same text can be laid out in 5 short lines (I'm talking about 2 columns in A4) and in 44 lines...

Yet another extreme case, but in the end, you can always put each word in its own line, no? Or less strongly: there is bound to be a possible layout that distributes the content over much more lines, and still has good demerits, if you consider 'equal distribution of content' to be a determining factor (which, IIC, holds for the current implementation: ideally you will get lines/pages that are all equally full).

I understand that it is strange to see, but if those possibilities are kept 'active' until the definitive set of breaks has been determined, then it would make sense you see something like that. IIUC, it is only in the final phase that, if there are two layouts (sets of break-possibilities) with equal demerits, then the one yielding the least number of breaks is chosen.

(in response to a following post)
The knuth list for a {left|right}-aligned paragraph is about twice the one of a justified paragraph. If you look at the methods addElementsFor* in TextLayoutManager class you can see that in some cases, depending on the alignment, a different number of glues/ penalties can be added. This obviously makes the breaks possibilities growing, as you can see in the graph attached that compare the SAME xsl-fo except for alignment.

Yep, AFAIK, this is intended. Center-alignment should be slightly worse even, since there, each possible line is preceded *and* followed by a stretchable/shrinkable glue.



Reply via email to