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