Thanks, Luca.

I've had a nice casual talk on the phone with Simon, yesterday.
Essentially, we only talked about very high-level stuff, especially the
decision for a certain strategy (or two). You know I came up with the
idea to create a simpler best-fit strategy with no look-ahead for
invoice-style documents but maybe it would be possible to design your
obvious total-fit strategy in a way that it could be used as a best-fit
without look-ahead. The problem, like I mentioned already, is the
possible change of available IPD within a page-sequence which results in
a possible back-tracking and recalculation of vertical boxes.

Of course, if it's possible to stay with one page-breaking algorithm for
all use cases that would be best (because of the reduced effort), but
only if the algorithm is reasonably fast for invoice-style documents.
I'm repeatedly confronted with certain speed requirements in this case.
Since modern high-volume single-feed printers handle about 180 pages per
minute (continuous feed systems handle over 4 times that speed, but I
think that's neither relevant, nor realistic here) FOP should be able to
operate close to these 180 pages per minute for not too complex
documents on a modern server. That means 330ms per page. Not much. Of
course, in such an environment it is possible to distribute the
formatting process over several blade servers but I had to realize that
certain companies tend to prefer spending 100'000 dollars on a big
server than spending a lot less for a much faster CPU-power-oriented
setup. It seems to be hard to say good-bye to the old host systems. Well,
that's just like the reality looks like in my environment.

Simon, for example, is much more interested in book-style documents
where there are other requirements. Speed is not a big issue, but
quality is.

In the end, I think we need to rate the chosen approach in these two
points of view. These are very contradicting requirements and it's
something that seems quite important to me not to forget here.

Luca, do you think your total-fit approach may be written in a way to
handle changing available IPDs and that look-ahead can be disabled to
improve processing speed at the cost of optimal break decisions? If it's
ok for you (and feasible) I'd like to integrate what you already have
(in code) into that branch I was talking about. I would like to avoid
recreating something you've already started, even if it doesn't work
with the changes that happened in the last weeks. Even if we may create
two different strategies I'm sure that certain parts will be shared by
both approaches, like the creation of Knuth-style elements for the

Some more comments inline:

On 04.03.2005 13:23:01 Luca Furini wrote:
> Jeremias Maerki wrote:
> >Would you consider sharing what you already
> >have? This may help us in the general discussion and may be a good
> >starting point.
> Ok, I'll try to.
> The main change in the LineLM is that the line breaking algorithm does not
> select only the node in activeList with fewest demerits: all the nodes
> whose demerits are <= a threshold are used to create LineBreakPositions,
> so for each paragraph there is a set of layout options (for example, a
> paragraph could create 8 to 10 lines, 9 being the layout with fewest
> demerits).

Hmm, that's a feature that I would say is something that only book-style
documents will need. Invoice-style documents could live without it.

> According to the value of widows and orphans, the LineLM creates a
> sequence of elements: besides "normal" lines, represented by a box, there
> are "optional lines", represented by
>   box(0) penalty(inf,0) glue(0,1,0) box(0)
> and "removable lines"
>   box(0) penalty(inf,0) glue(1,0,1) box(0)
> A few complications arise if not every possible layout allows breaks
> between lines, but they all can be solved using boxes, glues and
> penalties (for example, if a paragraph needs 3 or 4 lines, if it uses 3
> it cannot be parted).

Also something that's not all too important for invoice-style documents,
although it can't hurt to have it.

> The BlockLM, and a block stacking LM in general, adds elements
> representing its children's spaces and keep condition, for example
> adding a 0 penalty or an infinite penalty according to
> child1.mustKeepWithNext(), child2.mustKeepWithPrevious() and
> this.mustKeepTogether().

That's certainly a must-have in any case.

> The PageLM, once it has the list of elements representing a whole
> page-sequence (or the content before a forced page break), calls the same
> breaking algorithm, using only a different selection method which leaves
> only one node in activeList.

That's the part where I have a big question mark about changing
available IPD. We may have to have a check that figures out if the
available IPD changes within a page-sequence by inspecting the
page-masters. That would allow us to switch automatically between
total-fit and best-fit or maybe even first-fit. A remaining question
mark is with side-floats as they influence the available IPD on a
line-to-line basis.

> It has now a rough sequence of pages: each one may may have a positive or
> negative difference (with respect to the page height); the glue elements
> representing adjustable lines or adjustable spaces in a page are collected
> in different lists and they are used to "negotiate" a block progression
> adjustment with the LM which created them. In this phase each LineLM
> knows how many lines it will finally create.
> Then, a new sequence of elements is created, and this time each element
> has a fixed width (as the adjustments have already been decided).
> This sequence is used to create the final pages; note that if the
> adjustments have been enough to perfectly fill the pages, a first fit
> algorithm would be enough to recreate the right page breaks.
> This phase is needed, at the moment, because the Positions that the
> LineLMs store in their elements are not LineBreakPosition (as they still
> don't know how many lines they have to create), but maybe it could be
> avoided in some way ...
> Don't hesitate to ask for further details, I'll try to answer as clearly
> as possible!
> As per the columns, I did not think about them yet, but if they are
> equally wide it shouldn't be terribly hard to handle them ...

Yes, I think so, too. One thing for a deluxe strategy for book-style
documents is certainly alignment of lines between facing pages. But
that's something that's not important at the moment.

I'd be very interested to hear what you think about the difficulty of
changing available IPD. The more I think about it, however, the more I
think the total-fit model gets too complicated for what we/I need right
now. But I'm unsure here.

Jeremias Maerki

Reply via email to