Re: Vertical spacing regression !?

[David Kastrup]

Joe Neeman <address@hidden> writes:

> On Wed, 2010-06-30 at 07:04 +0200, David Kastrup wrote:
>> Joe Neeman <address@hidden> writes:
>> 
>> > On Tue, 2010-06-29 at 20:23 +0200, Arno Waschk wrote:
>> >> can't we have correct heights say for every bar (which must be computed 
>> >> later anyway) with clever caching so we have them ready when the final 
>> >> layout is made?
>> > No. For example, we don't know if a bar will have its clef displayed
>> > until after line-breaking. Also, the vertical collision avoidance means
>> > that in { c1^"long long markup" c1^"long long markup" }, we cannot
>> > calculate the height of the second bar without considering the first bar
>> > too (and the answer will change if they are on different lines).
>> 
>> Maybe I am dull, but we need the line heights (or skyline) for a given
>> line breakpoint sequence, and a given line breakpoint sequence has a
>> given skyline for each line.
>
> No, we don't compute the full skyline for a sequence of breakpoints,
> because doing so would require performing the full horizontal layout
> first. My point is that it isn't possible to get _completely_ accurate
> height estimates unless we do the complete layout for every possible
> line-breaking configuration.

But a lot of line-break configurations share lines.  And even more
configurations share "starting measures", so things that appear only at
the beginning of a line don't need recalculation for every
configuration.

I see an ugly factor (basically O(n l) where l is the maximum line
length in measures, and n the number of measures), but it appears to me
that _if_ one properly shares information (namely using a shortest path
traversal linear programming algorithm), it is, for a fixed value of l,
basically a constant after all.

And that means something that you can hope to wait for.

-- 
David Kastrup