lily/gourlay-breaking.cc

   1 /*
   2   gourlay-breaking.cc -- implement Gourlay_breaking
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1997--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9 #include "gourlay-breaking.hh"
  10
  11 #include <cmath>                // rint
  12 #include <cstdio>
  13 using namespace std;
  14
  15 #include "warn.hh"
  16 #include "main.hh"
  17 #include "paper-column.hh"
  18 #include "paper-score.hh"
  19 #include "output-def.hh"
  20 #include "simple-spacer.hh"
  21 #include "system.hh"
  22
  23 /// How often to print operator pacification marks?
  24 const int HAPPY_DOTS_I = 3;
  25
  26 /**
  27    Helper to trace back an optimal path
  28 */
  29 struct Break_node
  30 {
  31   /** this was the previous. If negative, this break should not be
  32       considered: this path has infinite energy
  33
  34   */
  35   int prev_break_;
  36   /**
  37      Which system number so far?
  38   */
  39   int line_;
  40
  41   Real demerits_;
  42   Column_x_positions line_config_;
  43
  44   Break_node ()
  45   {
  46     prev_break_ = -1;
  47     line_ = 0;
  48     demerits_ = 0;
  49   }
  50
  51   void print () const
  52   {
  53     printf ("prev break %d, line %d, demerits %f\n",
  54             prev_break_, line_, demerits_);
  55   }
  56 };
  57
  58 void
  59 print_break_nodes (Array<Break_node> const &arr)
  60 {
  61   for (int i = 0; i < arr.size (); i++)
  62     {
  63       printf ("node %d: ", i);
  64       arr[i].print ();
  65     }
  66 }
  67
  68 /**
  69    This algorithms is adapted from the OSU Tech report on breaking lines.
  70
  71    this function is longish, but not very complicated.
  72
  73    TODO: should rewrite. See the function in scm/page-layout.scm for
  74    inspiration.
  75 */
  76 Array<Column_x_positions>
  77 Gourlay_breaking::do_solve () const
  78 {
  79   Array<Break_node> optimal_paths;
  80   Link_array<Grob> all
  81     = pscore_->root_system ()->columns ();
  82
  83   Array<int> breaks = find_break_indices ();
  84
  85   Break_node first_node;
  86   optimal_paths.push (first_node);
  87
  88   bool ragged_right = to_boolean (pscore_->layout ()->c_variable ("raggedright"));
  89   bool ragged_last = to_boolean (pscore_->layout ()->c_variable ("raggedlast"));
  90
  91   Real worst_force = 0.0;
  92   for (int break_idx = 1; break_idx < breaks.size (); break_idx++)
  93     {
  94       /*
  95         start with a short line, add measures. At some point
  96         the line becomes infeasible. Then we don't try to add more
  97       */
  98       int minimal_start_idx = -1;
  99       Column_x_positions minimal_sol;
 100       Column_x_positions backup_sol;
 101
 102       Real minimal_demerits = infinity_f;
 103
 104       for (int start_idx = break_idx; start_idx--;)
 105         {
 106           Link_array<Grob> line = all.slice (breaks[start_idx], breaks[break_idx] + 1);
 107
 108           line[0] = dynamic_cast<Item *> (line[0])->find_prebroken_piece (RIGHT);
 109           line.top () = dynamic_cast<Item *> (line.top ())->find_prebroken_piece (LEFT);
 110
 111           Column_x_positions cp;
 112           cp.cols_ = line;
 113
 114           Interval line_dims
 115             = line_dimensions_int (pscore_->layout (), optimal_paths[start_idx].line_);
 116           Simple_spacer_wrapper *sp = generate_spacing_problem (line, line_dims);
 117           bool last_line = break_idx == breaks.size () - 1;
 118           bool ragged = ragged_right
 119             || (last_line && ragged_last);
 120
 121           sp->solve (&cp, ragged);
 122
 123           delete sp;
 124
 125           if (ragged && last_line)
 126             cp.force_ = 0.0;
 127
 128           if (fabs (cp.force_) > worst_force)
 129             worst_force = fabs (cp.force_);
 130
 131           /*
 132             We remember this solution as a "should always work
 133             solution", in case everything fucks up.  */
 134           if (start_idx == break_idx - 1)
 135             backup_sol = cp;
 136
 137           Real this_demerits;
 138
 139           if (optimal_paths[start_idx].demerits_ >= infinity_f)
 140             this_demerits = infinity_f;
 141           else
 142             this_demerits = combine_demerits (optimal_paths[start_idx].line_config_, cp)
 143               + optimal_paths[start_idx].demerits_;
 144
 145           if (this_demerits < minimal_demerits)
 146             {
 147               minimal_start_idx = start_idx;
 148               minimal_sol = cp;
 149               minimal_demerits = this_demerits;
 150             }
 151
 152           /*
 153             we couldn't satisfy the constraints, this won't get better
 154             if we add more columns, so we get on with the next one
 155           */
 156           if (!cp.satisfies_constraints_)
 157             break;
 158         }
 159
 160       Break_node bnod;
 161       if (minimal_start_idx < 0)
 162         {
 163           bnod.demerits_ = infinity_f;
 164           bnod.line_config_ = backup_sol;
 165           bnod.prev_break_ = break_idx - 1;
 166         }
 167       else
 168         {
 169           bnod.prev_break_ = minimal_start_idx;
 170           bnod.demerits_ = minimal_demerits;
 171           bnod.line_config_ = minimal_sol;
 172         }
 173       bnod.line_ = optimal_paths[bnod.prev_break_].line_ + 1;
 174       optimal_paths.push (bnod);
 175
 176       if (! (break_idx % HAPPY_DOTS_I))
 177         progress_indication (String ("[") + to_string (break_idx) + "]");
 178     }
 179
 180   /* do the last one */
 181   if (breaks.size () % HAPPY_DOTS_I)
 182     progress_indication (String ("[") + to_string (breaks.size ()) + "]");
 183
 184   progress_indication ("\n");
 185
 186   Array<int> final_breaks;
 187   Array<Column_x_positions> lines;
 188
 189   /* skip 0-th element, since it is a "dummy" elt*/
 190   for (int i = optimal_paths.size () - 1; i > 0;)
 191     {
 192       final_breaks.push (i);
 193       int prev = optimal_paths[i].prev_break_;
 194       assert (i > prev);
 195       i = prev;
 196     }
 197
 198   if (be_verbose_global)
 199     {
 200       message (_f ("Optimal demerits: %f",
 201                    optimal_paths.top ().demerits_) + "\n");
 202     }
 203
 204   if (optimal_paths.top ().demerits_ >= infinity_f)
 205     warning (_ ("no feasible line breaking found"));
 206
 207   for (int i = final_breaks.size (); i--;)
 208     {
 209       Column_x_positions cp (optimal_paths[final_breaks[i]].line_config_);
 210
 211       lines.push (cp);
 212       if (!cp.satisfies_constraints_)
 213         warning (_ ("can't find line breaking that satisfies constraints"));
 214     }
 215   return lines;
 216 }
 217
 218 Gourlay_breaking::Gourlay_breaking ()
 219 {
 220 }
 221
 222 /*
 223   TODO: uniformity parameter to control rel. importance of spacing differences.
 224
 225   TODO:
 226
 227   mixing break penalties and constraint-failing solutions is confusing.
 228 */
 229 Real
 230 Gourlay_breaking::combine_demerits (Column_x_positions const &prev,
 231                                     Column_x_positions const &this_one) const
 232 {
 233   Real break_penalties = 0.0;
 234   Grob *pc = this_one.cols_.top ();
 235   if (pc->original ())
 236     {
 237       SCM pen = pc->get_property ("penalty");
 238       if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
 239         break_penalties += scm_to_double (pen);
 240     }
 241
 242   /*
 243     Q: do we want globally non-cramped lines, or locally equally
 244     cramped lines?
 245
 246     There used to be an example file input/test/uniform-breaking to
 247     demonstrate problems with this approach. When music is gradually
 248     becoming denser, the uniformity requirement makes lines go from
 249     cramped to even more cramped (because going from cramped
 250     3meas/line to relatively loose 2meas/line is such a big step.
 251
 252   */
 253
 254   Real demerit = abs (this_one.force_) + abs (prev.force_ - this_one.force_)
 255     + break_penalties;
 256
 257   if (!this_one.satisfies_constraints_)
 258     {
 259       /*
 260         If it doesn't satisfy constraints, we make this one
 261         really unattractive.
 262
 263         add 20000 to the demerits, so that a break penalty
 264         of -10000 won't change the result */
 265       demerit = max ((demerit + 20000), 2000.0);
 266
 267       demerit *= 10;
 268     }
 269
 270   return demerit;
 271 }
 272