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