Re: setting the number of pages for a score

[Joe Neeman]

Han-Wen Nienhuys wrote:

> Joe Neeman wrote:
>
> > There is a bug in do_solve (it calls get_solution with arguments in 
> > the wrong order). It's supposed to print a programming error and 
> > format it with 4 staves. But the use in paper-score is wrong, too.
>
>
> Can you send a patch for it ?

Sorry, I lied (your usage should have been OK except for my bug). In any 
case, I have changed it slightly so that the number of systems returned 
by solve () will be the same as the last value passed to resize (). I've 
also added more documentation, removed casts, fixed style problems and 
put in some recovery if constraints aren't satisfied.
Index: lily/constrained-breaking.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/constrained-breaking.cc,v
retrieving revision 1.2
diff -u -r1.2 constrained-breaking.cc
--- lily/constrained-breaking.cc        21 Feb 2006 23:26:58 -0000      1.2
+++ lily/constrained-breaking.cc        22 Feb 2006 21:04:32 -0000
@@ -7,36 +7,6 @@
   (c) 2006 Han-Wen Nienhuys <address@hidden>
 */
 
-/*
-  TODO:
-
-  * vsize vs. int: casts should not be necessary. Use VPOS iso -1 as
-  magic signaling value?
-
-  * The specification uses A j, k, n and m as variables.
-  
-  Functions use start,end,sys_count,calc_subproblem as variables. Use the same 
naming
-  for the specification as for the code.
-  
-
-  FURTHER REMARKS:
-
-  *
-  
-   int a;
-   int b;
-
-  iso.
-
-   int a, b;
-
-
-   * no spurious * in <slash><star> <star><slash> comments.
-
-
- */
-
-
 #include "constrained-breaking.hh"
 
 #include "international.hh"
@@ -48,53 +18,71 @@
 #include "system.hh"
 #include "warn.hh"
 
-void
-print_constrained_break_nodes (vector<Constrained_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.
 
-/**
-   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
+
+  Indices in the code:
+
+  The above algorithm makes it easy to end at a point before the end of the
+  score (just find A_{k,m} for some m < breaks_.size () - 1). However, we must
+  add information for starting at a point after the beginning. One constructor
+  allows the specification of a list of starting columns, start_. We then have
+  start_.size () different solution arrays. state_[i] is the array for the
+  solution starting at column number start_[i].
+
+  The indicies "start" and "end" refer to the index in the start_ array of the
+  desired starting and ending columns.
+
+  each solution array looks like
+   a_{1,1,1} a_{2,1,2} a_{3,1,3} . . .
+       X     a_{2,2,2} a_{3,2,3} . . .
+       X         X     a_{3,3,3} . . .
+       .         .         .     .
+       .         .         .       .
+  where the X's mark invalid solutions (can't have more systems than
+  breakpoints). Note that each value is of the form a_{x,n,x}. This is because
+  a breakpoint of the form a_{x,n,x-1} will also be called a_{x-1,m,x-1} for
+  some m < n. Each cell in the array stores the value of its m (ie. the
+  ending breakpoint of the previous line) as "prev_".
 
-   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
+  For finding A_{sys, brk}, let "me" be the (sys_count,brk) cell in our
+  solution array (state_[start][sys * rank + brk]).
 
+  Then A_{sys, brk} = A_{sys - 1, me.prev_} :: me
 */
 
-/* start and sys here are indexed from 0.
-
-max_break is indexed from starting_breakpoints_[start] (for
- max_break, starting_breakpoints_[start] is the beginning of the
- piece; the smallest value we should ever see here is
- starting_breakpoints_[start] + 1) */
+/*
+  start and sys here are indexed from 0.
+  brk is indexed from starting_breakpoints_[start]
+  (for brk, starting_breakpoints_[start] is the beginning
+  of the piece; the smallest value we should ever see here is
+  starting_breakpoints_[start] + 1) */
 bool
-Constrained_breaking::calc_subproblem (int start, int sys, int max_break)
+Constrained_breaking::calc_subproblem (vsize start, vsize sys, vsize brk)
 {
   assert (sys < systems_);
-  assert (start < (int)start_.size ());
-  assert (max_break < (int)breaks_.size ());
+  assert (start < start_.size ());
+  assert (brk < breaks_.size ());
 
   bool found_something = false;
-  int start_col = starting_breakpoints_[start];
+  vsize start_col = starting_breakpoints_[start];
   vector<Constrained_break_node> &st = state_[start];
-  int rank = breaks_.size () - start_col;
-  int max_index = max_break - start_col;
-  for (int j = sys; j < max_index; j++)
+  vsize rank = breaks_.size () - start_col;
+  vsize max_index = brk - start_col;
+  for (vsize j=sys; j < max_index; 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_break];
+      Column_x_positions const &cur = cols_[(j + start_col)*cols_rank_ + brk];
       Column_x_positions prev;
       Real prev_dem = 0;
 
@@ -106,21 +94,18 @@
       if (isinf (prev_dem))
         break;
 
-      Real dem, force, pen;
+      Real dem;
+      Real force;
+      Real pen;
       combine_demerits(prev, cur, &force, &pen, &dem);
       dem += prev_dem;
       if (isinf (dem))
         continue;
 
       int k = sys*rank + max_index;
-      if (isinf (st[k].demerits_)
-          || dem < st[k].demerits_)
+      if (isinf (st[k].demerits_) || dem < st[k].demerits_)
         {
           found_something = true;
-
-         /*
-           TODO:  maybe just copy a Constrained_break_node ? 
-          */
           st[k].demerits_ = dem;
           st[k].force_ = force;
           st[k].penalty_ = pen;
@@ -137,49 +122,59 @@
   if (!systems_)
     {
       programming_error (_f ("no system number set in constrained-breaking"));
-      systems_ = start_.size () / 2;
+      systems_ = breaks_.size () / 4;
     }
 
-  resize ();
-  return get_solution (0, systems_, -1);
+  resize (systems_);
+  return get_solution(0, VPOS, systems_);
+}
+
+Column_x_positions
+Constrained_breaking::space_line (vsize i, vsize j)
+{
+  bool ragged_right = to_boolean (pscore_->layout ()->c_variable 
("ragged-right"));
+  bool ragged_last = to_boolean (pscore_->layout ()->c_variable 
("ragged-last"));
+  Column_x_positions col;
+
+  vector<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);
+
+  col.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);
+
+  bool last = j == breaks_.size () - 1;
+  bool ragged = ragged_right || (last && ragged_last);
+  sp->solve (&col, ragged);
+
+  delete sp;
+  return col;
 }
 
 void
-Constrained_breaking::resize ()
+Constrained_breaking::resize (vsize systems)
 {
-  if (!breaks_.size ())
-    {
-      bool ragged_right = to_boolean (pscore_->layout ()->c_variable 
("ragged-right"));
-      bool ragged_last = to_boolean (pscore_->layout ()->c_variable 
("ragged-last"));
+  systems_ = systems;
 
+  if (!breaks_.size () && pscore_)
+    {
       /* do all the rod/spring problems */
       breaks_ = pscore_->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++)
-         {
-           vector<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);
-
-           bool last = j == breaks_.size () - 1;
-           bool ragged = ragged_right || (last && ragged_last);
-           sp->solve (&cols_[i*cols_rank_ + j], ragged);
-
-           if (!cols_[i*cols_rank_ + j].satisfies_constraints_)
-             break;
-           delete sp;
-         }
+          for (vsize j = i + 1; j < breaks_.size (); j++)
+            {
+              cols_[i*cols_rank_ + j] = space_line (i, j);
+              if (!cols_[i*cols_rank_ + j].satisfies_constraints_)
+                break;
+            }
 
       /* work out all the starting indices */
       for (vsize i = 0; i < start_.size (); i++)
@@ -193,93 +188,113 @@
       state_.resize (start_.size ());
     }
 
-  for (vsize i = 0; i < state_.size (); i++)
-    state_[i].resize((breaks_.size () - starting_breakpoints_[i]) * systems_);
+  if (pscore_ && systems_ > valid_systems_)
+    {
+      for (vsize i = 0; i < state_.size (); i++)
+        state_[i].resize((breaks_.size () - starting_breakpoints_[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 = starting_breakpoints_[i] + j + 1; k < breaks_.size (); 
k++)
-        if (!calc_subproblem (i, j, k))
-          break; /* if we couldn't break this, it is too cramped already */
-  
-  valid_systems_ = systems_;
+      /* fill out the matrices */
+      for (vsize i = 0; i < state_.size (); i++)
+        for (vsize j = valid_systems_; j < systems_; j++)
+          for (vsize k = starting_breakpoints_[i] + j + 1; k < breaks_.size 
(); k++)
+            if (!calc_subproblem (i, j, k))
+              break; /* if we couldn't break this, it is too cramped already */
+      valid_systems_ = systems_;
+    }
 }
 
 vector<Column_x_positions>
-Constrained_breaking::get_solution (int start, int end, int sys_count)
+Constrained_breaking::get_solution (vsize start, vsize end, vsize sys_count)
 {
-  int rank;
-  int brk;
-  prepare_solution (start, end, sys_count, &rank, &brk);
+  vsize rank;
+  vsize end_brk;
+  prepare_solution (start, end, sys_count, &rank, &end_brk);
 
   vector<Constrained_break_node> const &st = state_[start];
   vector<Column_x_positions> ret;
 
-  for (int sys = sys_count-1; sys >= 0; sys--)
+  /* find the first solution that satisfies constraints */
+  for (vsize sys = sys_count-1; sys != VPOS; sys--)
     {
-      assert (brk > 0);
-      ret.push_back (st[sys*rank + brk].line_config_);
-      brk = st[sys*rank + brk].prev_;
+      for (vsize brk = end_brk; brk != VPOS; brk--)
+        {
+          if (!isinf (st[sys*rank + brk].force_))
+            {
+              if (brk != end_brk)
+                {
+                  warning ( _("couldn't find line breaking that satisfies 
constraints" ));
+                  ret.push_back (space_line (brk, end_brk));
+                }
+              /* build up the good solution */
+              for (vsize cur_sys = sys; cur_sys != VPOS; cur_sys--)
+                {
+                  assert (brk != VPOS);
+                  ret.push_back( st[cur_sys*rank + brk].line_config_ );
+                  brk = st[cur_sys*rank + brk].prev_;
+                }
+              reverse (ret);
+              return ret;
+            }
+        }
     }
-  assert (brk == 0);
-
-  reverse (ret);
+  /* if we get to here, just put everything on one line */
+  warning ( _("couldn't find line breaking that satisfies constraints" ));
+  ret.push_back (space_line (0, end_brk));
   return ret;
 }
 
 Real
-Constrained_breaking::get_demerits (int start, int end, int sys_count)
+Constrained_breaking::get_demerits (vsize start, vsize end, vsize sys_count)
 {
-  int rank;
-  int brk;
+  vsize rank;
+  vsize brk;
   prepare_solution (start, end, sys_count, &rank, &brk);
 
   return state_[start][(sys_count-1)*rank + brk].demerits_;
 }
 
 Real
-Constrained_breaking::get_force (int start, int end, int sys_count)
+Constrained_breaking::get_force (vsize start, vsize end, vsize sys_count)
 {
-  int rank;
-  int brk;
+  vsize rank;
+  vsize brk;
   prepare_solution (start, end, sys_count, &rank, &brk);
   vector<Constrained_break_node> const &st = state_[start];
   Real f = 0;
 
-  for (int sys = sys_count-1; sys >= 0 && brk >= 0; sys--)
+  for (int sys = sys_count-1; sys >= 0 && brk != VPOS; sys--)
     {
       f += fabs (st[sys*rank + brk].force_);
       brk = st[sys*rank + brk].prev_;
     }
-  if (brk < 0)
+  if (brk == VPOS)
     f = infinity_f;
 
   return f;
 }
 
 Real
-Constrained_breaking::get_penalty (int start, int end, int sys_count)
+Constrained_breaking::get_penalty (vsize start, vsize end, vsize sys_count)
 {
-  int rank;
-  int brk;
+  vsize rank;
+  vsize brk;
   prepare_solution (start, end, sys_count, &rank, &brk);
 
   return state_[start][(sys_count-1)*rank + brk].penalty_;
 }
 
 Real
-Constrained_breaking::get_page_penalty (int start, int end, int sys_count, int 
sys_num)
+Constrained_breaking::get_page_penalty (vsize start, vsize end, vsize 
sys_count, vsize sys_num)
 {
-  int rank;
-  int brk;
+  vsize rank;
+  vsize brk;
   prepare_solution (start, end, sys_count, &rank, &brk);
 
-  int sys;
+  vsize sys;
   for (sys = sys_count-1; sys > sys_num; sys--)
-    brk = state_[start][sys*rank + brk].prev_;
+      brk = state_[start][sys*rank + brk].prev_;
 
-  if (brk < 0) /* we didn't satisfy constraints */
+  if (brk == VPOS) /* we didn't satisfy constraints */
     return 0;
   vector<Grob*> &cols = state_[start][sys*rank + brk].line_config_.cols_;
   if (cols.empty ())
@@ -296,12 +311,13 @@
 }
 
 int
-Constrained_breaking::get_min_systems (int start, int end)
+Constrained_breaking::get_min_systems (vsize start, vsize end)
 {
-  int rank;
-  int brk;
+  vsize rank;
+  vsize brk;
+  vsize sys_count;
+
   prepare_solution (start, end, 1, &rank, &brk);
-  int sys_count;
   vector<Constrained_break_node> const &st = state_[start];
 
   /* sys_count < rank : rank is the # of breakpoints, we can't have more 
systems */
@@ -309,8 +325,7 @@
     {
       if (sys_count >= valid_systems_)
         {
-          systems_ = sys_count + 3;
-          resize ();
+          resize (sys_count + 3);
         }
       if (!isinf (st[sys_count*rank + brk].force_))
         return sys_count + 1;
@@ -320,29 +335,24 @@
 }
 
 int
-Constrained_breaking::get_max_systems (int start, int end)
+Constrained_breaking::get_max_systems (vsize start, vsize end)
 {
-  int brk = (end < 0 || end >= (int)start_.size ()) ? breaks_.size () - 1 : 
start_[end];
+  vsize brk = (end >= start_.size ()) ? breaks_.size () - 1 : start_[end];
   return brk - starting_breakpoints_[start];
 }
 
 void
-Constrained_breaking::prepare_solution (vsize start, int end, int sys_count, 
int *rank, int *brk)
+Constrained_breaking::prepare_solution (vsize start, vsize end, vsize 
sys_count, vsize *rank, vsize *brk)
 {
-  assert (start < start_.size () && end <= int (start_.size ()));
-  assert (end < 0 || int (start) < end);
-  assert (sys_count > 0);
+  assert (start < start_.size () && (end == VPOS || end <= start_.size ()));
+  assert (start < end);
 
-  if (sys_count >= valid_systems_)
-    {
-      systems_ = sys_count;
-      resize ();
-    }
-  if (end == (int)start_.size ())
-    end = -1;
+  resize (sys_count);
+  if (end == start_.size ())
+    end = VPOS;
 
   *rank = breaks_.size () - starting_breakpoints_[start];
-  *brk = end < 0 ? breaks_.size () - 1 : starting_breakpoints_[end];
+  *brk = end == VPOS ? breaks_.size () - 1 : starting_breakpoints_[end];
   *brk -= starting_breakpoints_[start];
 }
 
Index: lily/paper-score.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/paper-score.cc,v
retrieving revision 1.99
diff -u -r1.99 paper-score.cc
--- lily/paper-score.cc 21 Feb 2006 23:26:58 -0000      1.99
+++ lily/paper-score.cc 22 Feb 2006 21:04:33 -0000
@@ -83,9 +83,9 @@
   int system_count = robust_scm2int (layout ()->c_variable ("system-count"), 
0);
   if (system_count)
     {
-      Constrained_breaking *b = new Constrained_breaking (/* FIXME */);
+      Constrained_breaking *b = new Constrained_breaking;
+      b->resize (system_count);
       algorithm = b;
-      b->systems_ = system_count;
     }
   else
     algorithm = new Gourlay_breaking;
Index: lily/include/constrained-breaking.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/constrained-breaking.hh,v
retrieving revision 1.2
diff -u -r1.2 constrained-breaking.hh
--- lily/include/constrained-breaking.hh        21 Feb 2006 23:26:58 -0000      
1.2
+++ lily/include/constrained-breaking.hh        22 Feb 2006 21:04:38 -0000
@@ -12,16 +12,16 @@
 
 #include "break-algorithm.hh"
 
-/**
+/*
    Helper to trace back an optimal path
 */
 struct Constrained_break_node
 {
-  /** the number of bars in all the systems before this one
-   */
+  /* 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,
+  /* unlike the Gourlay breaker, this is the sum of all demerits up to,
    * and including, this line */
   Real demerits_;
   Real force_;
@@ -44,7 +44,7 @@
   }
 };
 
-/**
+/*
    A dynamic programming solution to breaking scores into lines
 */
 class Constrained_breaking : public Break_algorithm
@@ -54,27 +54,29 @@
   Constrained_breaking ();
   Constrained_breaking (std::vector<int> const &start_col_posns);
 
-  std::vector<Column_x_positions> get_solution(int start, int end, int 
sys_count);
-  Real get_demerits (int start, int end, int sys_count);
-  Real get_force (int start, int end, int sys_count);
-  Real get_penalty (int start, int end, int sys_count);
-  int get_max_systems (int start, int end);
-  int get_min_systems (int start, int end);
+  std::vector<Column_x_positions> get_solution(vsize start, vsize end, vsize 
sys_count);
+  Real get_demerits (vsize start, vsize end, vsize sys_count);
+  Real get_force (vsize start, vsize end, vsize sys_count);
+  Real get_penalty (vsize start, vsize end, vsize sys_count);
+  int get_max_systems (vsize start, vsize end);
+  int get_min_systems (vsize start, vsize end);
 
   /* get the page penalty of system number sys with the given breaking */
-  Real get_page_penalty (int start, int end, int sys_count, int sys);
+  Real get_page_penalty (vsize start, vsize end, vsize sys_count, vsize sys);
+
+  void resize (vsize systems);
 
-  int systems_;
 private:
-  int valid_systems_;
+  vsize valid_systems_;
+  vsize systems_;
 
-  /* the (i,j)th entry is the column configuration for breaking
-  between columns i and j */
+  /* 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_;
+  vsize 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 */
+    first j systems, starting at the i'th allowed starting column */
   std::vector<std::vector<Constrained_break_node> > state_;
 
   vector<int> start_;         /* the columns at which we might be asked to 
start breaking */
@@ -83,12 +85,12 @@
   vector<Grob*> all_;
   std::vector<int> breaks_;
 
-  void prepare_solution (vsize start, int end, int sys_count, int *rank, int 
*brk);
+  Column_x_positions space_line (vsize start_col, vsize end_col);
+  void prepare_solution (vsize start, vsize end, vsize sys_count, vsize *rank, 
vsize *brk);
 
   void combine_demerits (Column_x_positions const &, Column_x_positions const 
&,
-                        Real *force, Real *pen, Real *dem) const;
+                         Real *force, Real *pen, Real *dem) const;
 
-  bool calc_subproblem(int start, int systems, int max_break_index);
-  void resize ();
+  bool calc_subproblem(vsize start, vsize systems, vsize max_break_index);
 };
 #endif /* CONSTRAINED_BREAKING_HH */