Re: Page and line penalties
On 4/7/06, Joe Neeman <[EMAIL PROTECTED]> wrote: > I don't think TeX has to deal with this problem because each paragraph is > self-contained. In LilyPond, every line affects every other line. (This is > just an initial reaction. It might change after I read the TeXbook.) > Therefore penalties in TeX cause less instability than penalties in LilyPond. > Or at least they only cause local instability. Paragraphs are self-contained, and TeX chooses doesn't format the whole document before choosing page breaks (as I recall, it looks only a little past optimal page length before choosing a page break). David ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
On Fri, 7 Apr 2006 20:00, Han-Wen Nienhuys wrote: > Joe Neeman wrote: > > On Fri, 7 Apr 2006 16:31, Werner LEMBERG wrote: > >> TeX has exactly the same problem. > > > > Does TeX allow the user to arbitrarily assign penalties for inserting a > > line break at the end of any word? > > Yes, I'm certain. See ch. 14 of the TeXbook (you can download that book, > btw). In fact our use of the value 1 was taken from Knuth's example, > who takes 1 to mean "infinity". Thanks -- Werner has sent me a copy of that chapter. I will read it next week. > > > OK, so the solution will always have a certain level of instability. Just > > to put some idea of scale on my previous example graphs, it's possible > > that LilyPond will be tossing up between using 5 systems and using 10 > > systems. 5 systems provides much better spacing but 10 systems has less > > penalties. The total badness is _slightly_ less for 5 systems so Lily > > goes with that. > > I think this is perfectly reasonable, at least if you're trying to fill > out pages. 5 systems=1 page, 10 systems=2 pages. I wasn't thinking in terms of filling out pages. The point is that, independent of page breaks, you might have a situation where F(5 lines) < F(6 lines) < F(7 lines) < F(8 lines) < F(9 lines) but F(10 lines) is between F(5) and F(6). Just because the line break penalties happen to add up strangely. I don't think TeX has to deal with this problem because each paragraph is self-contained. In LilyPond, every line affects every other line. (This is just an initial reaction. It might change after I read the TeXbook.) Therefore penalties in TeX cause less instability than penalties in LilyPond. Or at least they only cause local instability. ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
On Sat, 8 Apr 2006 00:52, David Feuer wrote: > On 4/7/06, Joe Neeman <[EMAIL PROTECTED]> wrote: > > In constrained-breaking, I use the square of the force rather than its > > absolute value -- I made the change for precisely this reason. > > The sum of absolute values will generally be more stable than the sum > of squares, or so the stat books say. When I said "stable" before, I meant that, starting from the minimum, the weighting function is monotonic in any parameter. Probably "stable" wasn't a good word to use. In any case, I think convexity is important. Particularly since the constrained-breaker has to deal with worse spacing than the gourlay-breaker, I think it makes sense to put large penalties on things that are farther from optimal. ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Print out stencils?
Is there an option I can pass to LilyPond to get it to print out representations of its stencils? I see code for something like that, but I don't see how to activate it. David Feuer ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
Here are three references regarding global page breaking. Maybe you can dig out those books and articles in your library -- unfortuately, only the first one is available in the internet. Most of them handle a slightly different topic, namely how to place floats. Werner == Anne Brüggemann-Klein, Rolf Klein, Stefan Wohlfeil Pagination Reconsidered Technical Report 205, Department of Computer Science, FernUniversität Hagen, Germany, 1996. http://wwwpi6.fernuni-hagen.de/publ/tr205.pdf Michael F. Plass and Donald E. Knuth. Choosing better line breaks. In J. Nievergelt, G. Coray, J.-D. Nicoud, and A. C. Shaw, editors, Document Preparation Systems: A Collection of Survey Articles, pages 221–242. Elsevier North-Holland, Inc., New York, NY, USA, 1982. ISBN 0-444-86493-8. LCCN Z244 .D63 1982. US$46.50 Stefan Wohlfeil. On the Pagination of Complex, Book-Like Documents. Shaker Verlag, Aachen and Maastricht, The Netherlands, 1998. ISBN 3-8265-3304-6. 224 pp. DM 98.00. URL http://www.shaker.de/Online-Gesamtkatalog/Details.idc?ID=24201&CC=59311&IDSRC=1&ISBN=3-8265-3304-6&Reihe=15. ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
On 4/7/06, Joe Neeman <[EMAIL PROTECTED]> wrote: > I think they have to be. In the page-turning case, if G is much smaller than > F, the penalties for a bad turn get ignored. Conversely, if G is too big, we > sacrifice nice spacing. I hadn't actually thought of this before, but it > looks like this might be a main cause of the instability. I don't see a way > around it while keeping penalties, though. Comparing LilyPond to TeX, LilyPond faces a somewhat different challenge. Most of the time, TeX deals with lines that have many words in them. It can move a word from one line to another without changing things too much. It can even hyphenate words to make the change even smaller. Its input is structured into paragraphs, which give fairly frequent mandatory line breaks that are also good page break points. LilyPond doesn't have paragraphs to help it limit the line breaking decisions, and it doesn't have nearly as much flexibility for breaking lines. Lines in LilyPond could be as short as three or four measures, and breaking a measure lies somewhere between extremely bad and unthinkable. LilyPond will need to make compromises. I think one thing that could help would be to allow users to give LilyPond an idea of how fast the music should be played at different points. The penalty for breaking between two notes should probably depend on their real-life length in seconds. A slower piece will end up aesthetically better, while a faster one will bow more to practical concerns. David ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
On 4/7/06, Joe Neeman <[EMAIL PROTECTED]> wrote: > In constrained-breaking, I use the square of the force rather than its > absolute value -- I made the change for precisely this reason. The sum of absolute values will generally be more stable than the sum of squares, or so the stat books say. David ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
On Fri, 7 Apr 2006 22:59, Han-Wen Nienhuys wrote:
> Joe Neeman wrote:
> > On Fri, 7 Apr 2006 20:02, Han-Wen Nienhuys wrote:
> >> ...we should rather
> >> introduce some convexity in the penalties, so one perfect plus two
> >> extremes is much worse than three so-so lines.
> >
> > In constrained-breaking, I use the square of the force rather than its
> > absolute value -- I made the change for precisely this reason.
>
> Hmm, doesn't that introduce scaling/dimension problems?
In what sense? Not within the constrained-breaker -- the demerits calculation
is purely internal so the only possibility of a scaling problem is with
externally introduced penalties.
There is the issue of scaling between the line and page breakers but that will
exist anyway (and the page breaker also uses squares of forces).
> Or does
> everything else also use square(force) as a dimension?
The page breaker does too. Is there anything else?
> It would be
> better if we could figure out a scaling constant, and then introduce an
> arbitrary convex function, which may be set separately. I would guess
> that the scaling should depend on line-width and spacing-increment.
We are talking about the relative importance of page and line breaking, right?
If so, which way would the effect work?
longer line-width => more important line spacing
or the other way around?
>
> FWIW, I used x^{1.1} for a similar problem with cross-staff knee beaming.
x^2 seemed natural to me because when I think of minimising something, I
usually think of it in terms of least-squares. I suspect it wouldn't make a
huge difference, though.
___
lilypond-devel mailing list
lilypond-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
On Fri, 7 Apr 2006 19:55, Han-Wen Nienhuys wrote: > Joe Neeman wrote: > > Suppose we add penalties. Let G(B) be the penalty function for a > > partition into lines. G(B) has no nice structure at all. It will probably > > be zero most of the time, with a few very large spikes. And we want to > > minimize F(B) + G(B). Suppose the user makes a small change: > > I believe most of what you say; however, there are some questions: > > * IIRC, line breaking is not that stable as you suggest. It tends to > have the same problem. Due to uniform density scoring, two consecutive > line breaks may also have global effects. You're right, it isn't very stable. But it certainly has the property that, if I take an optimal solution then a small change in the solution will produce a small change in the badness. For eg, if B is optimal and B' is B but with some breakpoint moved forward one bar and B'' is B but with the same breakpoint moved forward 2 bars, then F(B) < F(B') < F(B''). > > * Did you look at penalties for page-breaking at rests, or did you also > put penalties for line-breaking? I didn't put any penalties for line-breaking. My line-breaking arguments here are mostly speculation, but I have certainly observed instability in the page-breaking when demerits are involved. > > * Isn't it possible to devise a G(B) which has a more regular structure? >What kind of G(B)'s did you try? I can imagine it might be > difficult, but have we thought about all the alternatives? I don't think so -- G(B) is zero unless the user introduces a penalty (and then, currently, it will be either -10001 or 10001). For page breaks, G(B) will be zero if the rest is long enough. The point is that G(B) depends only on the music at one specific point (the line/page break/turn) while F depends on the stretching of an interval of music. If I add an extra bar to the line I'm currently breaking, F will move along a parabola while G will jump up and down unpredictably. > > The problem that you sketch is not caused by F(B) being nice and G(B) > not, but rather because their magnitudes are very similar. I think they have to be. In the page-turning case, if G is much smaller than F, the penalties for a bad turn get ignored. Conversely, if G is too big, we sacrifice nice spacing. I hadn't actually thought of this before, but it looks like this might be a main cause of the instability. I don't see a way around it while keeping penalties, though. > > For example, what if you adjust the penalty of a page-breaks by using > the max distance to the next/previous rest? Then an isolated rest in a > fully filled score will get a huge bonus, but for scores with more > rests, the penalties will be small, relative to the spacing penalties. I don't think an isolated rest needs much of a bonus. If available page turns are widely spaced, the line- and page-breaking force becomes much more significant than penalties because we will be unable to squeeze any more on that particular page. > > * is there any value in removing page-break penalties? Shouldn't we > rather add a forbid/allow property, and otherwise just use normal > penalties? Then we use forbid/force for user tweaks, with automatic > penalties (ie. restrict the domain of possible B). This doesn't change > the shape of the graph, just the parts that we consider. Of course, this > may still cause jumps of the optimum, but they might be more predictable I've been using page-break penalties to break my own scores for some time now and I would ask the opposite question -- is there any value in keeping them? The problem is that we end up with statements like "if this rest is 1/8 longer, we would be willing to accept an extra force of 2.2". These numbers are really pretty arbitrary and they don't have much meaning. Typical use case (for me): 1) Break a score with the default values 2) Decide that the algorithm is skipping a perfectly good page turn because the penalty is too high 3) Tweak context settings so the penalty function is a bit smaller 4) Find that I didn't tweak it enough. Tweak more. 5) Now it's too permissive. I have bad turns all over the place. 6) ... I would prefer just having a threshold -- allow breaks for rests longer than the threshold, forbid them for shorter rests. 1) Break a score with the default values 2) Decide that the algorithm is skipping a perfectly good page turn because the threshold is too high. 3) Manually add \allowBreak. This won't affect any of the other potential breakpoints and I don't have to guess parameters and recompile endlessly. Also, I know that the spacing will /only get better/ because the only thing that has changed is that LilyPond has an extra option in deciding turns. So I don't think (any more) that page turn penalties are valuable. It would be nice if LilyPond could intelligently avoid bad page turns but adding penalties based on rest length just makes things fiddly and hard to override. Now my current algorithm _
Re: Page and line penalties
Joe Neeman wrote:
On Fri, 7 Apr 2006 20:02, Han-Wen Nienhuys wrote:
Juergen Reuter wrote:
Maybe I am totally wrong, but this discussion reminds me of an issue
that I raised on Nov 18, last year; see the thread starting here:
http://lists.gnu.org/archive/html/lilypond-devel/2005-11/msg00088.html
I am mentioning this thread just in case that you are looking for
interesting test examples.
This is really something different. To solve this, we should rather
introduce some convexity in the penalties, so one perfect plus two
extremes is much worse than three so-so lines.
In constrained-breaking, I use the square of the force rather than its
absolute value -- I made the change for precisely this reason.
Hmm, doesn't that introduce scaling/dimension problems? Or does
everything else also use square(force) as a dimension? It would be
better if we could figure out a scaling constant, and then introduce an
arbitrary convex function, which may be set separately. I would guess
that the scaling should depend on line-width and spacing-increment.
FWIW, I used x^{1.1} for a similar problem with cross-staff knee beaming.
--
Han-Wen Nienhuys - [EMAIL PROTECTED] - http://www.xs4all.nl/~hanwen
LilyPond Software Design
-- Code for Music Notation
http://www.lilypond-design.com
___
lilypond-devel mailing list
lilypond-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
On Fri, 7 Apr 2006 20:02, Han-Wen Nienhuys wrote: > Juergen Reuter wrote: > > Maybe I am totally wrong, but this discussion reminds me of an issue > > that I raised on Nov 18, last year; see the thread starting here: > > > > http://lists.gnu.org/archive/html/lilypond-devel/2005-11/msg00088.html > > > > I am mentioning this thread just in case that you are looking for > > interesting test examples. > > This is really something different. To solve this, we should rather > introduce some convexity in the penalties, so one perfect plus two > extremes is much worse than three so-so lines. In constrained-breaking, I use the square of the force rather than its absolute value -- I made the change for precisely this reason. ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
Juergen Reuter wrote: Maybe I am totally wrong, but this discussion reminds me of an issue that I raised on Nov 18, last year; see the thread starting here: http://lists.gnu.org/archive/html/lilypond-devel/2005-11/msg00088.html I am mentioning this thread just in case that you are looking for interesting test examples. This is really something different. To solve this, we should rather introduce some convexity in the penalties, so one perfect plus two extremes is much worse than three so-so lines. -- Han-Wen Nienhuys - [EMAIL PROTECTED] - http://www.xs4all.nl/~hanwen LilyPond Software Design -- Code for Music Notation http://www.lilypond-design.com ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
Joe Neeman wrote: On Fri, 7 Apr 2006 16:31, Werner LEMBERG wrote: TeX has exactly the same problem. Does TeX allow the user to arbitrarily assign penalties for inserting a line break at the end of any word? Yes, I'm certain. See ch. 14 of the TeXbook (you can download that book, btw). In fact our use of the value 1 was taken from Knuth's example, who takes 1 to mean "infinity". OK, so the solution will always have a certain level of instability. Just to put some idea of scale on my previous example graphs, it's possible that LilyPond will be tossing up between using 5 systems and using 10 systems. 5 systems provides much better spacing but 10 systems has less penalties. The total badness is _slightly_ less for 5 systems so Lily goes with that. I think this is perfectly reasonable, at least if you're trying to fill out pages. 5 systems=1 page, 10 systems=2 pages. -- Han-Wen Nienhuys - [EMAIL PROTECTED] - http://www.xs4all.nl/~hanwen LilyPond Software Design -- Code for Music Notation http://www.lilypond-design.com ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
Joe Neeman wrote: Suppose we add penalties. Let G(B) be the penalty function for a partition into lines. G(B) has no nice structure at all. It will probably be zero most of the time, with a few very large spikes. And we want to minimize F(B) + G(B). Suppose the user makes a small change: I believe most of what you say; however, there are some questions: * IIRC, line breaking is not that stable as you suggest. It tends to have the same problem. Due to uniform density scoring, two consecutive line breaks may also have global effects. * Did you look at penalties for page-breaking at rests, or did you also put penalties for line-breaking? * Isn't it possible to devise a G(B) which has a more regular structure? What kind of G(B)'s did you try? I can imagine it might be difficult, but have we thought about all the alternatives? The problem that you sketch is not caused by F(B) being nice and G(B) not, but rather because their magnitudes are very similar. For example, what if you adjust the penalty of a page-breaks by using the max distance to the next/previous rest? Then an isolated rest in a fully filled score will get a huge bonus, but for scores with more rests, the penalties will be small, relative to the spacing penalties. * is there any value in removing page-break penalties? Shouldn't we rather add a forbid/allow property, and otherwise just use normal penalties? Then we use forbid/force for user tweaks, with automatic penalties (ie. restrict the domain of possible B). This doesn't change the shape of the graph, just the parts that we consider. Of course, this may still cause jumps of the optimum, but they might be more predictable LilyPond's algorithm BTW, indeed is very similar to TeX's for line breaking. PS: This also solves the problem that the penalties are arbitrary values. Currently, Lilypond might conceivably ignore a user-forced \break if it causes the forces to work out too badly. I agree that we have to stop using penalties as a kludge for force/forbid. -- Han-Wen Nienhuys - [EMAIL PROTECTED] - http://www.xs4all.nl/~hanwen LilyPond Software Design -- Code for Music Notation http://www.lilypond-design.com ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
On Fri, 7 Apr 2006, Joe Neeman wrote: [...] OK, so the solution will always have a certain level of instability. Just to put some idea of scale on my previous example graphs, it's possible that LilyPond will be tossing up between using 5 systems and using 10 systems. 5 systems provides much better spacing but 10 systems has less penalties. The total badness is _slightly_ less for 5 systems so Lily goes with that. Then the user inserts an extra bar and the number of systems doubles. I think that instability shouldn't occur on this scale. Now, I haven't been playing around with any line penalties, but I have done experiments with page turn penalties and I have seen scores go from 5 to 8 pages with only small changes. Maybe I am totally wrong, but this discussion reminds me of an issue that I raised on Nov 18, last year; see the thread starting here: http://lists.gnu.org/archive/html/lilypond-devel/2005-11/msg00088.html I am mentioning this thread just in case that you are looking for interesting test examples. Greetings, Juergen ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Sorting vectors
Joe Neeman writes: > /* FIXME: the COMPARE functionality is broken? */ > > you are just using the wrong compare function. Thanks for finding this. IWBN if we could drop our own sorting function and use STL. Jan. -- Jan Nieuwenhuizen <[EMAIL PROTECTED]> | GNU LilyPond - The music typesetter http://www.xs4all.nl/~jantien | http://www.lilypond.org ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
On Fri, 7 Apr 2006 16:31, Werner LEMBERG wrote: > TeX has exactly the same problem. Does TeX allow the user to arbitrarily assign penalties for inserting a line break at the end of any word? > Interestingly, Knuth seems to have > accepted this. Isn't it possible to provide default values for the > badness, stretchable and shrinkable space, and other parameters which > ensure a certain layout stableness? I admit to not knowing a great deal about TeX's breaking algorithm. But the description on the wikipedia page on TeX suggests that it is very similar to what ours would be if we got rid of penaties. Lily already does nice things with stretchable/shrinkable space and badness calculations. I'm not proposing changing this. > > > [...] I think the unpredictability and instability of the result > > make it not worthwhile trying to do this automatically. > > I disagree. Dense typesetting (this is, not having much shrinkable > horizontal space) will *always* cause large shifts of system and page > breaks. OK, so the solution will always have a certain level of instability. Just to put some idea of scale on my previous example graphs, it's possible that LilyPond will be tossing up between using 5 systems and using 10 systems. 5 systems provides much better spacing but 10 systems has less penalties. The total badness is _slightly_ less for 5 systems so Lily goes with that. Then the user inserts an extra bar and the number of systems doubles. I think that instability shouldn't occur on this scale. Now, I haven't been playing around with any line penalties, but I have done experiments with page turn penalties and I have seen scores go from 5 to 8 pages with only small changes. I should also be clear that I'm not suggesting changing the _current_ algorithm to make it more stable. Currently we only use _huge_ positive and negative penalties that have a fairly predictable effect -- these would just be replaced (10001 -> FORBID, 0 -> ALLOW, -10001 -> FORCE) so current usage wouldn't change. I only want to restrict it so that the current usage of penalties will be the only usage. Joe ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Page and line penalties
> My current working copy of lilypond does what you just said (using > inverse rest durations for penalties). I've done some testing and > tweaking and I've come to the conclusion that penalties are a bad > idea. I think everything to do with page breaks, line breaks and > page turns should be in terms of ALLOW, FORBID and FORCE. Hmmm. > For example, if incrementing the number of breakpoints in B > increases F(B) then adding 2 to the number of breakpoints in B will > only increase F(B) more. This is good because it means that the > user can change things predictably. If the user decides to forbid > one particular breakpoint, they can be confident that the music > won't suddenly blow up to twice the number of pages. TeX has exactly the same problem. Interestingly, Knuth seems to have accepted this. Isn't it possible to provide default values for the badness, stretchable and shrinkable space, and other parameters which ensure a certain layout stableness? > It's very difficult to find a nice balance that will work for a > large number of cases. I've been playing around with different page > turning penalties and the outputs can very so wildly that it's very > hard to pick one. But this problem is inevitable if you insert more than a system can hold, isn't it? You should probably discuss this problem on comp.text.tex -- there you find most of the TeX gurus who have dealt with TeX's breaking algorithm. > [...] I think the unpredictability and instability of the result > make it not worthwhile trying to do this automatically. I disagree. Dense typesetting (this is, not having much shrinkable horizontal space) will *always* cause large shifts of system and page breaks. Werner ___ lilypond-devel mailing list lilypond-devel@gnu.org http://lists.gnu.org/mailman/listinfo/lilypond-devel
Sorting vectors
flower/include/std-vector.hh contains the comment:
/* FIXME: the COMPARE functionality is broken? */
and the version of vector_sort that makes use of the STL sort algorithm is
commented out. But based on my reading of the SGI STL manual[1], you are just
using the wrong compare function. You use a compare function like
int compare_int (const int &a, const int &b) {return sign (a - b);}
but it expects
bool compare_int (const int &a, const int &b) {return a < b;}
(which is what the STL function less does (if the class that you are
comparing has a "<" operator))
Joe
[1] http://www.sgi.com/tech/stl/table_of_contents.html
___
lilypond-devel mailing list
lilypond-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/lilypond-devel
