Re: Applying Finn Bock's patch (again) :-)
(I'm currently not getting all the posts from the mailing lists. The ISP started filtering spam 2005-05-01 and is doing a poor job. Sorry if I miss anything. For example, I didn't get Luca's first mail, only Glen's answer.) Glen, the branch uses Knuth's algorithms for both line and page breaking. Thankfully, we even have a lot of code sharing between the two aspects. Michael Plass who wrote that research paper was Knuth's student. His work is also based on Knuth's work on line breaking. So far I haven't been able to get a lot out of his paper, although he writes about footnotes for example, which will eventually come in handy. I get the impressions that, in certain areas, we're going farther than what was described in the papers I could find. So far the most helpful resource for understanding the whole story was Digital Typography by Donald Knuth (chapter 3 only): http://www.amazon.com/exec/obidos/tg/detail/-/1575860104 Plass' paper on the other side is the only paper that sheds some more light on page breaking studd, but not much IMO. I've also found stuff that criticized some of Plass' statements. Anyway, we have to find out everything the hard way. :-) (comments on Luca's message below) On 03.05.2005 05:29:44 Glen Mazza wrote: BTW, is the page breaking also using Knuth's algorithms, or is it from the research paper* that Jeremias ordered a few months back and was mentioning to us? I have been generically calling both the line- and page-breaking the Knuth code--I don't know how correct that is. Thanks, Glen * Also, would it help me to order that research paper--how helpful would it be in understanding our code? Luca Furini wrote: I realized just a few days ago that the breaking algorithm (in the BreakingAlgorithm class) is not fully patched with Finn's great refactoring of the Knuth code (bug 32612). I must admit that this is due to my laziness: when I was playing with Knuth's algorithm for page breaking I applied to my local copy of the code only the new restarting strategy, so, although Jeremias applied the patch before the branch, most benefits in performance and readability got lost in the merge. So it's more my fault than yours. I mostly didn't understand the code back then and still have troubles understanding it to the last corner. Anyway, thank you for fixing this! I have now applied the patch to the branch code: it needed some change in order to fit in the new classes, and I hope I did not introduce errors. :-) I'll see how the code holds up now. I'm still in the middle of implementing tables. Smoking head the whole time. :-) A few doubts / questions / comments: - the value BestRecord.INFINITE_DEMERITS: I'm not sure it must be +infinity; if it is a finite value it acts like a threshold, reducing the number of active nodes. On the other hand, the finite value should be carefully chosen, otherwise breakpoints with an allowed adjustment ratio could be later discarded because it has more than finite infinity demerits (this is something that Finn pointed out some time ago). What about a finite value computed according to the adjustment threshold and the line width? Some experimenting here certainly can't hurt. - in addition to Finn's restarting strategy, lastTooShort is resetted to null after the creation of new nodes: the newly created nodes are surely better than it, and a lastTooShort solution will be found later; it will most likely have more demerits (demerits always increase, when a new line / page is created), but it will be better anyway. - as now KnuthSequence extends ArrayList instead of LinkedList, a few more optimizations could be done here and there: using get() instead of ListIterators, for example. Regards Luca Jeremias Maerki
Collapsing border model
I've just realized I probably made a big mistake interpreting collapsing border model. While going through the specs to reread everything about the outer table border I carefully reread the following passages: XSL-FO 1.0, 6.7.2, Trait Derivation: If the value of the border-collapse property is collapse or collapse-with-precedence the border is determined, for each segment, at the cell level. So far I've based everything on being determined, for each segment, at the segment level as it seems. I even had the part about cell level highlighted in my print-out and still got it wrong. Damn me! But I think I know why I got it wrong: XSL-FO 1.0, 6.7.10, Trait Derivation: If the value of the border-collapse trait is collapse, the border for each side of the cell is determined by, for each segment of a border, selecting, from all border specifications for that segment, the border that has the most eye catching border style... Obviously sounded too much like a per-segment thing. Under the new light, this means a totally different thing. Looking at my (buggy) example [1] this means that the segment where the arrow points should actually be the same broad red border as the one next to it on the right side. That also means that it's making the whole border resolution a lot more complicated. If you started with the upper left cell and tried to determine the after border you can end up taking the after border specification from the cell on the right side of the cell. I'll have to think about how to implement this in an efficient way, first. But before I turn everything upside-down again, can please someone confirm that I was really wrong before and got it right now? Thanks a lot. [1] http://wiki.apache.org/xmlgraphics-fop/CollapsingBorderModel Jeremias Maerki PS: Can someone please beat me?
RE: Collapsing border model
-Original Message- From: Jeremias Maerki [mailto:[EMAIL PROTECTED] Hi, snip / BTW: Am I the only one who has trouble viewing the pictures on the wiki page? (It seems to be the only one with which I have problems. The other table-related pages show up nicely...) That also means that it's making the whole border resolution a lot more complicated. If you started with the upper left cell and tried to determine the after border you can end up taking the after border specification from the cell on the right side of the cell. Are you talking about what our current implementation *would* end up taking as after border, or what *should* be taken as after border according to the spec? In the latter case, if you mean 'start/end', I'm game, but I don't see how the 'after' border of the first cell to the right of a given cell could influence the 'after' border of that cell... If the border is determined, for each segment, at the cell level that seems to mean a decision at the cell level between: - table - body (header / footer) - column - row - neighbouring cells * start ~ border-end of first cell to the left * end ~ border-start of first cell to the right * before ~ border-after of first cell above * after ~ border-before of first cell below - the cell itself for each of the border segments: start - before - end - after One optimistic note: all of the above options can't be an option at the same time for one and the same cell... and the decision between row borders and table borders, for instance, could already be resolved at row level, such that, when the borders are determined at cell level, the cell only needs to query the row, column and neighbouring cells (not reach back up to the body and table). But before I turn everything upside-down again, can please someone confirm that I was really wrong before and got it right now? Thanks a lot. If I could only see the images... Cheers, Andreas
Re: Collapsing border model
I've attached the picture and an FO file I wrote today to mimic that picture. BTW, the pictures worked fine for me the whole day. They are all here: http://people.apache.org/~jeremias/fop/ Alternatively, if you log into cvs.apache.org you can cd into /x1/home/jeremias/public_html/fop to get them. On 03.05.2005 19:40:39 Andreas L. Delmelle wrote: -Original Message- From: Jeremias Maerki [mailto:[EMAIL PROTECTED] Hi, snip / BTW: Am I the only one who has trouble viewing the pictures on the wiki page? (It seems to be the only one with which I have problems. The other table-related pages show up nicely...) That also means that it's making the whole border resolution a lot more complicated. If you started with the upper left cell and tried to determine the after border you can end up taking the after border specification from the cell on the right side of the cell. Are you talking about what our current implementation *would* end up taking as after border, or what *should* be taken as after border according to the spec? *should* :-( In the latter case, if you mean 'start/end', I'm game, but I don't see how the 'after' border of the first cell to the right of a given cell could influence the 'after' border of that cell... If the border is determined, for each segment, at the cell level that seems to mean a decision at the cell level between: - table - body (header / footer) - column - row - neighbouring cells * start ~ border-end of first cell to the left * end ~ border-start of first cell to the right * before ~ border-after of first cell above * after ~ border-before of first cell below - the cell itself for each of the border segments: start - before - end - after One optimistic note: all of the above options can't be an option at the same time for one and the same cell... and the decision between row borders and table borders, for instance, could already be resolved at row level, such that, when the borders are determined at cell level, the cell only needs to query the row, column and neighbouring cells (not reach back up to the body and table). Got to think that through first. It might speed things up a little. But before I turn everything upside-down again, can please someone confirm that I was really wrong before and got it right now? Thanks a lot. If I could only see the images... Cheers, Andreas Jeremias Maerki attachment: border-collapse5.png table-border-special2.fo Description: Binary data
Re: Collapsing border model
I am afraid I just followed your interpretation. I will try to read the spec more independently and more critically. Regards, Simon On Tue, May 03, 2005 at 03:14:50PM +0200, Jeremias Maerki wrote: I've just realized I probably made a big mistake interpreting collapsing border model. While going through the specs to reread everything about the outer table border I carefully reread the following passages: XSL-FO 1.0, 6.7.2, Trait Derivation: If the value of the border-collapse property is collapse or collapse-with-precedence the border is determined, for each segment, at the cell level. So far I've based everything on being determined, for each segment, at the segment level as it seems. I even had the part about cell level highlighted in my print-out and still got it wrong. Damn me! But I think I know why I got it wrong: XSL-FO 1.0, 6.7.10, Trait Derivation: If the value of the border-collapse trait is collapse, the border for each side of the cell is determined by, for each segment of a border, selecting, from all border specifications for that segment, the border that has the most eye catching border style... Obviously sounded too much like a per-segment thing. Under the new light, this means a totally different thing. Looking at my (buggy) example [1] this means that the segment where the arrow points should actually be the same broad red border as the one next to it on the right side. That also means that it's making the whole border resolution a lot more complicated. If you started with the upper left cell and tried to determine the after border you can end up taking the after border specification from the cell on the right side of the cell. I'll have to think about how to implement this in an efficient way, first. But before I turn everything upside-down again, can please someone confirm that I was really wrong before and got it right now? Thanks a lot. [1] http://wiki.apache.org/xmlgraphics-fop/CollapsingBorderModel Jeremias Maerki PS: Can someone please beat me? -- Simon Pepping home page: http://www.leverkruid.nl
Re: Applying Finn Bock's patch (again) :-)
Jeremias Maerki wrote: So far the most helpful resource for understanding the whole story was Digital Typography by Donald Knuth (chapter 3 only): http://www.amazon.com/exec/obidos/tg/detail/-/1575860104 The chapter in question (Breaking Paragraphs Into Lines) was originally published by Knuth and Plass in Software - Practice and Experience 11 (1981), 1119-1184. Anyone who is interested may be able to obtain a copy of the ogiginal paper more cheaply than the book. Peter -- Peter B. West http://cv.pbw.id.au/ Folio http://defoe.sourceforge.net/folio/ http://folio.bkbits.net/
Re: Collapsing border model
Jeremias Maerki wrote: PS: Can someone please beat me? Stick, riding crop, whip, rope, chain or plain old bare knuckles? Peter -- Peter B. West http://cv.pbw.id.au/ Folio http://defoe.sourceforge.net/folio/ http://folio.bkbits.net/
Re: Collapsing border model
Whatever helps. Thanks! On 04.05.2005 04:14:51 Peter B. West wrote: Jeremias Maerki wrote: PS: Can someone please beat me? Stick, riding crop, whip, rope, chain or plain old bare knuckles? Peter -- Peter B. West http://cv.pbw.id.au/ Folio http://defoe.sourceforge.net/folio/ http://folio.bkbits.net/ Jeremias Maerki
