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
 118           if (ragged && last_line)
 119             cp.force_ = min (cp.force_, 0.0);
 120
 121           if (fabs (cp.force_) > worst_force)
 122             worst_force = fabs (cp.force_);
 123
 124           /*
 125             We remember this solution as a "should always work
 126             solution", in case everything fucks up.  */
 127           if (start_idx == break_idx - 1)
 128             backup_sol = cp;
 129
 130           Real this_demerits;
 131
 132           if (optimal_paths[start_idx].demerits_ >= infinity_f)
 133             this_demerits = infinity_f;
 134           else
 135             this_demerits = combine_demerits (optimal_paths[start_idx].line_config_, cp)
 136               + optimal_paths[start_idx].demerits_;
 137
 138           if (this_demerits < minimal_demerits)
 139             {
 140               minimal_start_idx = start_idx;
 141               minimal_sol = cp;
 142               minimal_demerits = this_demerits;
 143             }
 144
 145           /*
 146             we couldn't satisfy the constraints, this won't get better
 147             if we add more columns, so we get on with the next one
 148           */
 149           if (!cp.satisfies_constraints_)
 150             break;
 151         }
 152
 153       Break_node bnod;
 154       if (minimal_start_idx < 0)
 155         {
 156           bnod.demerits_ = infinity_f;
 157           bnod.line_config_ = backup_sol;
 158           bnod.prev_break_ = break_idx - 1;
 159         }
 160       else
 161         {
 162           bnod.prev_break_ = minimal_start_idx;
 163           bnod.demerits_ = minimal_demerits;
 164           bnod.line_config_ = minimal_sol;
 165         }
 166       bnod.line_ = optimal_paths[bnod.prev_break_].line_ + 1;
 167       optimal_paths.push_back (bnod);
 168
 169       if (! (break_idx % HAPPY_DOTS))
 170         progress_indication (string ("[") + to_string (break_idx) + "]");
 171     }
 172
 173   /* do the last one */
 174   if (breaks.size () % HAPPY_DOTS)
 175     progress_indication (string ("[") + to_string (breaks.size ()) + "]");
 176
 177   progress_indication ("\n");
 178
 179   vector<int> final_breaks;
 180   vector<Column_x_positions> lines;
 181
 182   /* skip 0-th element, since it is a "dummy" elt*/
 183   for (vsize i = optimal_paths.size () - 1; i > 0;)
 184     {
 185       final_breaks.push_back (i);
 186       vsize prev = optimal_paths[i].prev_break_;
 187       assert (i > prev);
 188       i = prev;
 189     }
 190
 191   if (be_verbose_global)
 192     {
 193       message (_f ("Optimal demerits: %f",
 194                    optimal_paths.back ().demerits_) + "\n");
 195     }
 196
 197   if (optimal_paths.back ().demerits_ >= infinity_f)
 198     warning (_ ("no feasible line breaking found"));
 199
 200   for (vsize i = final_breaks.size (); i--;)
 201     {
 202       Column_x_positions cp (optimal_paths[final_breaks[i]].line_config_);
 203
 204       lines.push_back (cp);
 205       if (!cp.satisfies_constraints_)
 206         warning (_ ("can't find line breaking that satisfies constraints"));
 207     }
 208   return lines;
 209 }
 210
 211 Gourlay_breaking::Gourlay_breaking ()
 212 {
 213 }
 214
 215 /*
 216   TODO: uniformity parameter to control rel. importance of spacing differences.
 217
 218   TODO:
 219
 220   mixing break penalties and constraint-failing solutions is confusing.
 221 */
 222 Real
 223 Gourlay_breaking::combine_demerits (Column_x_positions const &prev,
 224                                     Column_x_positions const &this_one) const
 225 {
 226   Real break_penalties = 0.0;
 227   Grob *pc = this_one.cols_.back ();
 228   if (pc->original ())
 229     {
 230       SCM pen = pc->get_property ("line-break-penalty");
 231       if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
 232         break_penalties += scm_to_double (pen);
 233     }
 234
 235   /*
 236     Q: do we want globally non-cramped lines, or locally equally
 237     cramped lines?
 238
 239     There used to be an example file input/test/uniform-breaking to
 240     demonstrate problems with this approach. When music is gradually
 241     becoming denser, the uniformity requirement makes lines go from
 242     cramped to even more cramped (because going from cramped
 243     3meas/line to relatively loose 2meas/line is such a big step.
 244
 245   */
 246
 247   Real demerit = abs (this_one.force_) + abs (prev.force_ - this_one.force_)
 248     + break_penalties;
 249
 250   if (!this_one.satisfies_constraints_)
 251     {
 252       /*
 253         If it doesn't satisfy constraints, we make this one
 254         really unattractive.
 255
 256         add 20000 to the demerits, so that a break penalty
 257         of -10000 won't change the result */
 258       demerit = max ((demerit + 20000), 2000.0);
 259
 260       demerit *= 10;
 261     }
 262
 263   return demerit;
 264 }
 265