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