Jeremias Maerki wrote:

> 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?

I think that a first fit algorithm could be implemented in two different ways:
1) wait until the list of elements representing a whole page-sequence is
   collected, and call findBreakingPoints(); this method will call a
   different considerLegalBreak() method, much simpler and faster than
   the knuth's one.
2) start building pages little by little: the FlowLM returns elements to
   the PageLM as soon as one of its own child returns them

Alternative 1) is much like the total fit algorithm: breaks are computed
at the end of each page-sequence; even if the evaluation method is much
faster than Knuth's one, there could still be a long wait in order to get
the whole list.

With alternative 2) the PageLM would behave much the same as it now does:
as soon as a page is filled, it is possible to call addAreas. Note that
the last elements in the partial sequence cannot be considered as feasible
break. For example, if there is a block which creates 6 lines, the
sequence will be something like:
 penalty(not infinite)
 penalty(not infinite)
and the evaluation must stop at the second penalty; only when some
following elements are known it will be possible to decide whether the
last two lines could be at the end of a page.

If the IPD is always the same, I think the two alternatives are
equivalent, and the first one is "better" because it just needs a
different considerLegalBreak() method; as the output file cannot be
printed until the end of the process, the only advantage of 2) could be
memory usage.

> 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.

If the IPD changes, I fear 2) must be necessarily used: if a block is
split between pages with different ipd, only a few lines need to be
Using 1), the LineLM should know how wide the lines are, but this cannot
be known as page breaking has not yet started.

The check could be done before starting the layout phase: if there is a
change, 2) is used, otherwise 1).
Maybe, the check could be even more sophisticated: for example, if the
first page is different, but the following are equally wide, we could use
2) to create the first page and then switch to 1).

> A remaining question
> mark is with side-floats as they influence the available IPD on a
> line-to-line basis.

This is a question mark for me 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 have created and implemented a new property right about this! :-)

> 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.

If changing ipd is really important and not just a theorical possibility,
we could start implementing 2, and later add the check and the algorithm
1: the getNextKnuthElements() in the block-level LM could be used in both


Reply via email to