Re: setting the number of pages for a score

[Joe Neeman]

Jose-Luc Hopital wrote:

> I'm used to work this way: once a score is completely
> keyed , i estimate the ideal number of pages for legibility,
> turns , occupation of pages. Next i try different values
> with set-global-staff-size until I obtain this number.
>  
First of all, i recommend playing with
\override Score.SpacingSpanner #'shortest-duration-space
instead of global-staff-size. If you do many pieces with different 
global-staff-sizes, then put them all together they look strange because 
they all have different font sizes!

> This method is long : new value for global-staff-size,
> recompilation, test ...
> I'm searching a better way : I think to a variable giving the wished
> number of pages , lilypond being free to choose 
> global-staff-size to obtain this number.
>  
Once again, I think changing the spacing instead of the font size is 
better. But as it happens, I have been working on something like this 
for some time now. I am still having some problems, but I thought I'd 
share what I have so far (this is my first time hacking the lily source, 
so be gentle!).

I am writing a combined page/line breaker that aims to break pages in a 
page-turnable way. The idea is that the user will add \allowPageBreak in 
certain places, then lilypond will break the pages optimally with page 
turns only at those allowed places. The actual page-breaking part is 
currently a mess, but I think the line breaker is mostly OK, so I am 
enclosing a patch for my new line breaker.

Rather than simply breaking lines optimally like the Gourlay_breaker, 
the line breaker allows specification of
- the number of lines to break things into
- the starting point
- the ending point
It also stores intermediate calculations to ensure that each 
recalculation (with different parameters maybe) is short. It is 
currently slower than the Gourlay_breaker (it makes lily about 20% 
slower) but I haven't done much optimisation and in any case it does a 
lot more work.

The idea for the page breaker is that, using a similar algorithm to the 
current Gourlay line breaker, it will try out different numbers of 
systems on each page until it finds the solution with the least combined 
line and page demerits. The starting/ending point specification in the 
line breaker allows the page breaker to only line break the segment of 
music between 2 possible page breaks.

As I said previously, the page breaker is still a mess. It's mostly 
related to the fact that lilypond assumes that, once the line breaking 
is done, it can throw away unneeded grobs. Since I need to try many 
different line breakings, this is causing problems.

If there is enough interest in the page breaker (and people think the 
design is acceptable) then I will keep going on this.

Joe

PS: this is probably a stupid question, but how do I get CVS to give me 
a diff including new files? I tried the -N option, but that didn't work. 
As a result, I attach a patch for my changes to existing files and my 
new files in full (I know this is discouraged, sorry).
Index: lily/break-algorithm.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/break-algorithm.cc,v
retrieving revision 1.53
diff -u -r1.53 break-algorithm.cc
--- lily/break-algorithm.cc     6 Feb 2006 01:13:58 -0000       1.53
+++ lily/break-algorithm.cc     9 Feb 2006 23:05:24 -0000
@@ -89,7 +89,7 @@
 }
 
 std::vector<Column_x_positions>
-Break_algorithm::solve () const
+Break_algorithm::solve ()
 {
   std::vector<Column_x_positions> h= do_solve ();
 
Index: lily/gourlay-breaking.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/gourlay-breaking.cc,v
retrieving revision 1.92
diff -u -r1.92 gourlay-breaking.cc
--- lily/gourlay-breaking.cc    6 Feb 2006 01:13:58 -0000       1.92
+++ lily/gourlay-breaking.cc    9 Feb 2006 23:05:24 -0000
@@ -75,7 +75,7 @@
    inspiration.
 */
 std::vector<Column_x_positions>
-Gourlay_breaking::do_solve () const
+Gourlay_breaking::do_solve ()
 {
   std::vector<Break_node> optimal_paths;
   Link_array__Grob_ all
Index: lily/include/break-algorithm.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/break-algorithm.hh,v
retrieving revision 1.30
diff -u -r1.30 break-algorithm.hh
--- lily/include/break-algorithm.hh     3 Feb 2006 01:32:16 -0000       1.30
+++ lily/include/break-algorithm.hh     9 Feb 2006 23:05:26 -0000
@@ -30,14 +30,14 @@
 
   Simple_spacer_wrapper *generate_spacing_problem (Link_array__Grob_ const &,
                                                   Interval) const;
-  virtual std::vector<Column_x_positions> do_solve () const = 0;
+  virtual std::vector<Column_x_positions> do_solve () = 0;
 
 public:
   virtual ~Break_algorithm ();
   Simple_spacer *(*get_line_spacer) ();
   Break_algorithm ();
   void set_pscore (Paper_score *);
-  std::vector<Column_x_positions> solve () const;
+  std::vector<Column_x_positions> solve ();
 };
 
 #endif // BREAK_HH
Index: lily/include/gourlay-breaking.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/gourlay-breaking.hh,v
retrieving revision 1.20
diff -u -r1.20 gourlay-breaking.hh
--- lily/include/gourlay-breaking.hh    31 Jan 2006 00:30:42 -0000      1.20
+++ lily/include/gourlay-breaking.hh    9 Feb 2006 23:05:26 -0000
@@ -16,7 +16,7 @@
 */
 struct Gourlay_breaking : public Break_algorithm
 {
-  std::vector<Column_x_positions> do_solve () const;
+  std::vector<Column_x_positions> do_solve ();
   Gourlay_breaking ();
   Real combine_demerits (Column_x_positions const &, Column_x_positions const 
&) const;
 };

/*
  restrained-breaking.hh -- declare a line breaker that
  supports limits on the number of systems

  source file of the GNU LilyPond music typesetter

  (c) 1997--2005 Han-Wen Nienhuys <address@hidden>
*/

#ifndef RESTRAINED_BREAKING_HH
#define RESTRAINED_BREAKING_HH

#include "break-algorithm.hh"

/**
   Helper to trace back an optimal path
*/
struct Restrained_break_node
{
  /** the number of bars in all the systems before this one
  */
  int prev_;

  /** unlike the Gourlay breaker, this is the sum of all demerits up to,
   * and including, this line */
  Real demerits_;
  Column_x_positions line_config_;

  Restrained_break_node ()
  {
    prev_ = -1;
    demerits_ = infinity_f;
  }

  void print () const
  {
    printf ("prev break %d, demerits %f\n",
            prev_, demerits_);
  }
};

/**
   A dynamic programming solution to breaking scores into lines
*/
class Restrained_breaking : public Break_algorithm
{
  public:
    std::vector<Column_x_positions> do_solve ();
    Restrained_breaking ();
    Restrained_breaking (std::vector<int> const &start_col_posns);
    Real combine_demerits (Column_x_positions const &, Column_x_positions const 
&) const;

    // return an optimal solution with n_sys systems
    // (n_sys must be less than systems_) and with
    // max column index no greater than max_col
    std::vector<Column_x_positions> get_soln(int start_idx, int n_sys, int 
max_col);
    Real get_demerits (int start_idx, int n_sys, int max_col);

  private:
    int valid_systems_;
    int systems_;

    // the (i,j)th entry is the column configuration for breaking between
    // columns i and j
    std::vector<Column_x_positions> cols_;
    int cols_rank_;

    // the [i](j,k)th entry is the score for fitting the first k bars onto the
    // first j systems, starting at the i'th allowed starting column
    std::vector<std::vector<Restrained_break_node> > state_;

    vector<int> start_;         // the columns at which we might be asked to 
start breaking
    vector<int> start_brk_idx_; // the corresponding index in breaks_

    Link_array__Grob_ all_;
    std::vector<int> breaks_;

    void calc_subproblem(int start_idx, int systems, int max_brk);
    void resize ();
};
#endif // RESTRAINED_BREAKING_HH

/*
  restrained-breaking.cc -- implement a line breaker that
  support limits on the number of systems

  source file of the GNU LilyPond music typesetter

  (c) 1997--2005 Han-Wen Nienhuys <address@hidden>
*/

#include "restrained-breaking.hh"

#include <cmath>                // rint
#include <cstdio>
using namespace std;

#include "warn.hh"
#include "main.hh"
#include "paper-column.hh"
#include "paper-score.hh"
#include "output-def.hh"
#include "simple-spacer.hh"
#include "system.hh"

#include "international.hh"

/// How often to print operator pacification marks?
const int HAPPY_DOTS_I = 3;

void
print_restrained_break_nodes (std::vector<Restrained_break_node> const &arr)
{
  for (vsize i = 0; i < arr.size (); i++)
    {
      printf ("node %d: ", (int)i);
      arr[i].print ();
    }
}

/**
   We use the following optimal substructure. Let W(A) be our weight function.

   Let A_{k,n} = (a_{k,n,1}, ... a_{k,n,k}) be the optimal set of line breaks
   for k systems and n potential breakpoints. a_{k,n,k} = n (it is the end of
   the piece)

   Then A_{k+1, m} is contructed from
                        min_ {k <= j < m} ( W(A_{k,j} :: m) )
   where by A::m we denote appending m to the list A
*/

/* start_idx and sys here are indexed from 0.
 * max_brk is indexed from start_brk_idx_[start_idx]
 * (for max_brk, start_brk_idx_[start_idx] is the beginning
 * of the piece; the smallest value we should ever see here is
 * start_brk_idx_[start_idx] + 1) */
void Restrained_breaking::calc_subproblem (int start_idx, int sys, int max_brk)
{
  assert (sys < systems_);
  assert (start_idx < start_.size ());
  assert (max_brk < breaks_.size ());

  int start_col = start_brk_idx_[start_idx];
  std::vector<Restrained_break_node> &st = state_[start_idx];
  int rank = breaks_.size () - start_col;
  int max_idx = max_brk - start_col;
  for (int j=sys; j < max_idx; j++)
    {
      if (0 == sys && j > 0)
        break; // the first line cannot have its first break after the beginning

      Column_x_positions const &cur = cols_[(j + start_col)*cols_rank_ + 
max_brk];
      Column_x_positions prev;
      Real prev_dem = 0;

      if (sys > 0) {
        prev = st[(sys-1) * rank + j].line_config_;
        prev_dem = st[(sys-1) * rank + j].demerits_;
      }
      Real dem = combine_demerits(prev, cur) + prev_dem;

      if (isinf (st[sys*rank + max_idx].demerits_)
          || dem < st[sys*rank + max_idx].demerits_) {
        st[sys*rank + max_idx].demerits_ = dem;
        st[sys*rank + max_idx].prev_ = j;
        st[sys*rank + max_idx].line_config_ = cur;
      }
    }
}

std::vector<Column_x_positions>
Restrained_breaking::do_solve ()
{
  resize ();
  return get_soln(0, systems_, -1);
}

void
Restrained_breaking::resize ()
{
  if (!breaks_.size ())
    {
      // do all the rod/spring problems
      breaks_ = find_break_indices ();
      cols_rank_ = breaks_.size ();
      all_ = pscore_->root_system ()->columns ();
      cols_.resize (breaks_.size () * breaks_.size ());
      for (vsize i = 0; i < breaks_.size () - 1; i++)
          for (vsize j = i + 1; j < breaks_.size (); j++)
            {
              Link_array__Grob_ line (all_.begin () + breaks_[i],
                                      all_.begin() + breaks_[j] + 1);

              line[0] = dynamic_cast<Item *> (line[0])->find_prebroken_piece 
(RIGHT);
              line.back () = dynamic_cast<Item *> (line.back 
())->find_prebroken_piece (LEFT);

              cols_[i*cols_rank_ + j].cols_ = line;

              // we have no idea what line this will be -- only whether it is 
the first
              Interval line_dims = line_dimensions_int (pscore_->layout (), i);
              Simple_spacer_wrapper *sp = generate_spacing_problem (line, 
line_dims);

              // TODO: support raggedness
              sp->solve (&cols_[i*cols_rank_ + j], false);
              delete sp;
            }
      // work out all the starting indices
      for (vsize i = 0; i < start_.size (); i++)
        {
          vsize j;
          for (j = 0; breaks_[j] < start_[i]; j++)
            ;
          start_brk_idx_.push_back (j);
        }
      state_.resize (start_.size ());
    }

  if (!systems_) systems_ = 4; // just to make this compatible with Gourlay

  for (vsize i = 0; i < state_.size (); i++)
    state_[i].resize((breaks_.size () - start_brk_idx_[i]) * systems_);

  // fill out the matrices
  for (vsize i = 0; i < state_.size (); i++)
    for (int j = valid_systems_; j < systems_; j++)
      for (vsize k = start_brk_idx_[i] + 1; k < breaks_.size (); k++)
          calc_subproblem(i, j, k);
  valid_systems_ = systems_;
}

std::vector<Column_x_positions>
Restrained_breaking::get_soln (int start_idx, int nsys, int max_col)
{
  if (nsys > valid_systems_)
    {
      systems_ = nsys;
      resize ();
    }
  assert (start_idx < start_.size ());

  std::vector<Restrained_break_node> const &st = state_[start_idx];
  int rank = breaks_.size () - start_brk_idx_[start_idx];
  std::vector<Column_x_positions> ret;
  int brk = breaks_.size () - 1;

  if (max_col > 0)
    while (breaks_[brk] > max_col)
      brk--;
  brk -= start_brk_idx_[start_idx];

  for (int sys = nsys-1; sys >= 0; sys--) {
    assert (brk > 0);
    //::message (_f ("system %d, breaking at %d has demerits %f", sys, brk, 
st[sys*rank + brk].demerits_));
    ret.push_back( st[sys*rank + brk].line_config_ );
    brk = st[sys*rank + brk].prev_;
  }
  assert (brk == 0);
  reverse (ret);
  return ret;
}

Real
Restrained_breaking::get_demerits (int start_idx, int nsys, int max_col)
{
  assert (start_idx < start_.size ());
  int brk = breaks_.size () - 1;
  int rank = breaks_.size () - start_brk_idx_[start_idx];
  if (max_col > 0)
    while (breaks_[brk] > max_col)
      brk--;
  brk -= start_brk_idx_[start_idx];
  return state_[start_idx][nsys*rank + brk].demerits_;
}

Restrained_breaking::Restrained_breaking ()
{
  valid_systems_ = systems_ = 0;
  start_.push_back (0);
}

Restrained_breaking::Restrained_breaking (vector<int> const &start):
  start_ (start)
{
  valid_systems_ = systems_ = 0;
}

Real
Restrained_breaking::combine_demerits (Column_x_positions const &prev,
                                       Column_x_positions const &col) const
{
  Real break_penalties = 0.0;
  Grob *pc = col.cols_.back ();
  if (pc->original ())
    {
      SCM pen = pc->get_property ("penalty");
      if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
        break_penalties += scm_to_double (pen);
    }

  Real demerit = abs (col.force_) + abs (prev.force_ - col.force_) + 
break_penalties;

  if (!col.satisfies_constraints_)
    {
      /*
        If it doesn't satisfy constraints, we make this one
        really unattractive.

        add 20000 to the demerits, so that a break penalty
        of -10000 won't change the result */
      demerit = max ((demerit + 20000), 2000.0);

      demerit *= 10;
    }

  return demerit;
}