Sounds to me like 2) is the way to go right now. This would mean minimal recreation of vertical boxes in case of changing available IPD. Sure, this is an exotic case but XSL-FO makes it possible, therefore we must be prepared for it.
Thanks for the hints and the helpful example. On 08.03.2005 19:43:57 Luca Furini wrote: > 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: > box > box > penalty(not infinite) > box > penalty(not infinite) > box > box > 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 > recreated. > 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 > cases. > > Regards > Luca > > Jeremias Maerki
