On 27 août 2013, at 11:09, d...@gnu.org wrote:
> On 2013/08/27 06:58:05, mike7 wrote:
>> On 27 août 2013, at 09:01, "Keith OHara" <mailto:k-ohara5...@oco.net>
> wrote:
>
>> > How are skylines asked-for, and is it possible to know if they were
> asked for
>> while interpreting the markup ?
>> > {c4-\markup \whiteout \pad-to-box #(-0.5 . 9) #(-0.5 . 1.5) \concat
> {"Clarinet
>> in B" \flat}}
>> >
>
>> class Stencil {
>> private :
>> Scheme expr_;
>> Box dim_;
>> Skyline_pair *vskys_; // set to 0 in the constructor
>> Skyline_pair *hskys_; // set to 0 in the constructor
>
>> public :
>> Skyline_pair* get_vskys () { if (!vskys_) create_vskys (); return
> vskys_; }
>> }
>
>> So, the idea is that we only ever create the skylines if they are
> asked for or
>> if we use something like pad-to-box. Then, if we are going to combine
> two
>> stencils and neither of them have skylines set already, we do not
> calculate
>> their skylines yet.
>
> Either you don't listen or you don't think about your code. Delaying
> skyline calculation until it is needed does _nothing_ whatsoever with
> regard to computational complexity if the skyline is needed eventually,
> which it will almost always be.
I don't see how this system precludes O(n log n) in the majority of cases.
Take :
\header {
title = "foo"
composer "bar"
}
\markup { mit herzlichen foo }
\new Staff \relative c'' { a1^"und bar" }
The skylines for the title, composer, and top-level markup will never be
calculated. For everything in the staff, there are no stencil skyline
overrides, which means a stencil's get_skyline method will not be called before
it is fully formed, which means that the existing divide-and-conquer method
will be used to traverse the stencils' expressions and create the skyline.
This keeps the complexity at O(n log n) instead of O(n^2).
The only cases where O(n^2) behavior would be exhibited is if the stencil's
skyline creation is triggered before a call to translate_axis, translate,
rotate, rotate_degrees_absolute, rotate, scale, add_at_edge, etc. in which case
we'd need to perform these operations on the skylines as well. But the only
time that we would trigger skyline creation is when we want the skyline to
differ from the natural one of the stencil.
Cheers,
MS
_______________________________________________
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
