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