Influence of different page sizes on the pagination algorithm to be developed

XSL-FO allows arbitrary sequences of different page specifications. The consequence is that you may have different available IPDs for any page.

Many of the papers we found on pagination don't seem to deal with this fact. They focus mainly on formatting books where each page has the same available IPD. That allows for prefabrication of the vertical box lists and only the page breaking decisions have to be made and the individual boxes distributed over the pages.

An example found in [1], chapter 2.1: "As to the text stream, we assume that the line breaking task has already been completed. Afterwards, each paragraph consists of a sequence of line boxes and vertical glue boxes."

If we consider the possibility of different available IPDs over pages/regions, we can see that for each possible page break a different set of vertical boxes is generated on the subsequent page. This gets worse if a total-fit algorithm is chosen and a whole page-sequence is considered. The number of combinations grows exponentially.

If the available IPD remains equal between pages (which is true for most documents) look-ahead is possible and bearable from the performance POV. If a look-ahead algorithm is chosen, it must be capable of switching off look-ahead if subsequent pages have different available IPD, thus reducing it to a simple best-fit or first-fit algorithm. So if the available IPD remains equal the generated vertical boxes can be reused on a subsequent pages, they only have to be discarded if the IPD changes.

It remains to be determined if side-floats have an impact here. Probably not, since they mostly affect only the present page and there only the line-breaking.

Example of such a document: http://people.apache.org/~jeremias/fop/alternating-page-sizes.fo, http://people.apache.org/~jeremias/fop/alternating-page-sizes.pdf


[1] Br├╝ggemann-Klein, Klein, Wohlfeil: On the Pagination of Complex Documents, http://www.pi6.fernuni-hagen.de/publ/tr234.pdf


Details to consider when implementing "changing available IPD" in FOP Trunk

Here are some points we should look into when we're planning on implementing support for "changing available IPD" in FOP Trunk:

PageLayout/InfluenceOfPageSizesOnAlgorithm (last edited 2009-09-20 23:52:26 by localhost)