May I make so bold as to intrude on what is clearly a private 
conversation?  Comments below.

Keiron Liddle wrote:
> Hi Arved, Joerg,
> It seems you have a different view of how keeps work than what I was
> thinking.
> Section 4.8 of the spec seems to be the only real description, last
> paragraph.
> In your example with blocks a, b and c. If you have a+b together and
> break after b this means that you have not satisfied a 5 keep but kept a
> 3 keep. The spec suggests this when talking about the maximal subsets of
> keeps.
> It says (ignoring breaks):
> - each keep must be satisfied
> - except where it would cause a stronger keep to fail
> - if breaking at equal strength then maximise satisfying these keeps
> (along with all strong keeps)
> - maximise subsets of stronger keeps
> On Thu, 2002-08-15 at 05:00, Arved Sandstrom wrote:
>>I don't see how some form of lookahead can be avoided. Let's assume that
>>blocks 1-4 can be laid out on page 1, and we do so. Block 5 has a
>>keep-with-previous; to satisfy that block 4 should be on page 2 (assuming
>>that none of block 5 fits on page 1, and none of block 4 originally is laid
>>out into page 2).
> This should be done like so:
> - continue to find best breaks in the first four blocks
> - the current best break will be before the second last line of the 4th
> block
> - for next break: block 5 has a keep prev so we cannot break after 4.
> - block 5 can break after 2nd line, this becomes new best break
> - page full so go back to last best break (2nd last line of block 4)
> So whatever you call it, it finds a future best break.
> Obviously if a block sees that it is going over the bpd it will return
> the next break regardless.

I call it lookahead with backtracking.  Lookahead effectively occurs 
when you layout anything which does not end up on the page currently 
being laid out.  Your original point was that a finished page should not 
be redone; that the problems should be solved during the layout of a 
page only, not considering future pages.  In a sense, that's what 
lookahead achieves.  Layout which will eventually be on a future page is 
done in order that the decisions about this page may be sensible.  And 
that is what you are proposing.

> For a brief description of the current idea (more ideas below to handle
> extra things).
> Each layout manager can find a break inside its own data/children. The
> flow manager gets best breaks until the last which is worst than the
> current best break. It could be worse because it is past the page end or
> further away from the optimal spacing or has a higher keep.
> So all the blocks have returned their best breaks, the flow has sorted
> these breaks out considering keeps, page bpd etc.
> The best break is then known for that page.
> The page manager then says to addAreas until the best break. Each child
> manager then adds the areas up to that break.
> This would mean that it only considers the keeps for the current page
> and not future pages. (another idea below)

In the sense that it is applying those keeps to the current page.  But 
they may end up being realised on another page.

>>My current belief is that lookahead is primarily motivated by keeps. Other
>>things like floats or footnotes can be handled without this, and so can
>>forward references like page citations if we allocate fixed space for a page
>>number, to be filled in later. As Keiron said.
>>Keeps, especially near-pathological combinations, I don't see how one can
>>avoid lookahead. I don't view this as entailing any backtracking, per se;
>>it's more a galley model. Once a page is cut or committed then it doesn't
>>get revisited. Whole point is that we have a sliding window, in the presence
>>of keeps, of partially laid-out stuff.

What happens when the next page has a different page master with, say, a 
different region-width?

>>RenderX XEP (I believe) has a configurable lookahead size...IOW, one might
>>say that we will only do lookahead for 2 pages, or 4 pages. It's this
>>lookahead limit that makes the problem deterministic, which it has to be in
>>order for it to be coded. What are we expecting to do otherwise - handwave,
>>and sort of expect the keeps problem to solve itself at implementation time?
>>:-) There needs to be an algorithm, pseudocode or otherwise, that clearly
>>explains how layout will occur in the presence of keeps.

Arved, this is unkind.  The look-ahead limit does not make the *problem* 
deterministic, it makes the *solution* deterministic for pathological 
cases.  And it is one possible deterministic solution.  Yes, 
pathological cases do require some kind of limiter, some point at which 
a deadlock-breaking heuristic cuts in, but I would like to see a 
structure which supports the refinement of heuristics, and eventually 
allows layout decisions based on aesthetic grounds, rather than strict 
keep rules, for example.  I would also like to see the possibility of 
looking ahead from page 1 to page 1000 to resolve page numbers as a 
tunable parameter in a later version.

Simple examples of aesthetic rules would be the case where a page ends 
up with a single line.  It should be possible to backtrack and inform 
the layout components that <space> components should be tweaked to 
squeeze more text onto the page.  Such a decision must obviously be 
taken at a page level, even though it must be implemented recursively 
throughout the page component structures.  This may be hand-waving, but 
it is *realizable* hand-waving.

I don't want these things now.  But neither do I want A solution that 
places severe limitations on the possibility of development in the area 
of layout refinement.  We have A solution that does that.  The only way 
to achieve that is to think about these issues now, and try to come up 
with software models that leave possibilities open, rather than closing 
them off.

>>If there is something I am missing here I would dearly love to hear about
>>it. :-)
> Sounds like:
> - if the best break on a page has a keep (level 1)
> - more can fit on the page but with higher keep (level 2)
> - break at higher keep first then try next page to see if it satisfies a
> higher keep or more equal keeps (level 2)
> - continue to the end of all contiguous keeps
> - count up maximal subsets of all keep level satisfied
> - try again breaking at the original level 1 keep
> - compare subsets
> - use best result
> If there are more higher levels then repeat for each keep level.
> It has to find the breaks for all pages, count the keeps that are
> satisfied and the keeps that are not.
> Because the LayoutManagers find the break positions and compare breaks
> this could be possible to implement from what we have.
> The flow manager could handle this.
> I will maintain the following point: the layout managers concept allows
> us to explore how to do this sort of thing.

I happen to agree.  Layout driven from below has to be instructed to go 
in certain directions by some processes capable of judging the results 
at higher levels.  That's a layout manager *function*, whether it occurs 
on the page-builder or on an individual block builder.

Not drowning, waving.

"Lord, to whom shall we go?"

To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, email: [EMAIL PROTECTED]

Reply via email to