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