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   TODO: should rewrite. See the function in scm/page-layout.scm for
  71   inspiration.
  72
  73  */
  74 Array<Column_x_positions>
  75 Gourlay_breaking::do_solve () const
  76 {
  77   Array<Break_node> optimal_paths;
  78   Link_array<Grob> all =
  79     pscore_->system_->columns ();
  80
  81   Array<int> breaks = find_break_indices ();
  82
  83   Break_node first_node ;
  84   optimal_paths.push (first_node);
  85
  86   bool ragged_right = to_boolean (pscore_->paper_->c_variable ("raggedright"));
  87   bool ragged_last = to_boolean (pscore_->paper_->c_variable ("raggedlast"));
  88
  89   Real worst_force = 0.0;
  90   for (int break_idx = 1; break_idx< breaks.size (); break_idx++)
  91     {
  92       /*
  93         start with a short line, add measures. At some point
  94         the line becomes infeasible. Then we don't try to add more
  95         */
  96       int minimal_start_idx = -1;
  97       Column_x_positions minimal_sol;
  98       Column_x_positions backup_sol;
  99
 100       Real minimal_demerits = infinity_f;
 101
 102       for (int start_idx = break_idx; start_idx--;)
 103         {
 104           Link_array<Grob> line = all.slice (breaks[start_idx], breaks[break_idx]+1);
 105
 106           line[0]     = dynamic_cast<Item*> (line[0])->find_prebroken_piece (RIGHT);
 107           line.top () = dynamic_cast<Item*> (line.top ())->find_prebroken_piece (LEFT);
 108
 109           Column_x_positions cp;
 110           cp.cols_ = line;
 111
 112           Interval line_dims
 113             = line_dimensions_int (pscore_->paper_, optimal_paths[start_idx].line_);
 114           Simple_spacer_wrapper * sp = generate_spacing_problem (line, line_dims);
 115           bool last_line = break_idx == breaks.size ()-1;
 116           bool ragged = ragged_right
 117             || (last_line && ragged_last);
 118
 119           sp->solve (&cp, ragged);
 120
 121           delete sp;
 122
 123           if (ragged && last_line)
 124             cp.force_ = 0.0;
 125
 126           if (fabs (cp.force_) > worst_force)
 127             worst_force = fabs (cp.force_);
 128
 129           /*
 130             We remember this solution as a "should always work
 131             solution", in case everything fucks up.  */
 132           if (start_idx == break_idx - 1)
 133             backup_sol = cp;
 134
 135           Real this_demerits;
 136
 137           if (optimal_paths[start_idx].demerits_ >= infinity_f)
 138             this_demerits = infinity_f;
 139           else
 140             this_demerits = combine_demerits (optimal_paths[start_idx].line_config_, cp)
 141               + optimal_paths[start_idx].demerits_;
 142
 143           if (this_demerits < minimal_demerits)
 144             {
 145               minimal_start_idx = start_idx;
 146               minimal_sol = cp;
 147               minimal_demerits = this_demerits;
 148             }
 149
 150           /*
 151             we couldn't satisfy the constraints, this won't get better
 152             if we add more columns, so we get on with the next one
 153           */
 154           if (!cp.satisfies_constraints_)
 155             break ;
 156         }
 157
 158
 159       Break_node bnod;
 160       if (minimal_start_idx < 0)
 161         {
 162           bnod.demerits_ = infinity_f;
 163           bnod.line_config_ = backup_sol;
 164           bnod.prev_break_ = break_idx - 1;
 165         }
 166       else
 167         {
 168           bnod.prev_break_ = minimal_start_idx;
 169           bnod.demerits_ = minimal_demerits;
 170           bnod.line_config_ = minimal_sol;
 171         }
 172       bnod.line_ = optimal_paths[bnod.prev_break_].line_ + 1;
 173       optimal_paths.push (bnod);
 174
 175       if (! (break_idx % HAPPY_DOTS_I))
 176         progress_indication (String ("[") + to_string (break_idx) + "]");
 177     }
 178
 179   /* do the last one */
 180   if (breaks.size () % HAPPY_DOTS_I)
 181     progress_indication (String ("[") + to_string (breaks.size ()) + "]");
 182
 183   progress_indication ("\n");
 184
 185   Array<int> final_breaks;
 186   Array<Column_x_positions> lines;
 187
 188   /* skip 0-th element, since it is a "dummy" elt*/
 189   for (int i = optimal_paths.size ()-1; i> 0;)
 190     {
 191       final_breaks.push (i);
 192       int prev = optimal_paths[i].prev_break_;
 193       assert (i > prev);
 194       i = prev;
 195     }
 196
 197   if (verbose_global_b)
 198     {
 199       progress_indication (_f ("Optimal demerits: %f",
 200                                optimal_paths.top ().demerits_) + "\n");
 201     }
 202
 203   if (optimal_paths.top ().demerits_ >= infinity_f)
 204     warning (_ ("No feasible line breaking found"));
 205
 206   for (int i= final_breaks.size (); i--;)
 207     {
 208       Column_x_positions cp (optimal_paths[final_breaks[i]].line_config_);
 209
 210       lines.push (cp);
 211       if (!cp.satisfies_constraints_)
 212         warning ("Could not find line breaking that satisfies constraints.");
 213     }
 214   return lines;
 215 }
 216
 217
 218 Gourlay_breaking::Gourlay_breaking ()
 219 {
 220 }
 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_.top ();
 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         {
 242           break_penalties += scm_to_double (pen);
 243         }
 244     }
 245
 246   /*
 247     Q: do we want globally non-cramped lines, or locally equally
 248     cramped lines?
 249
 250     There used to be an example file input/test/uniform-breaking to
 251     demonstrate problems with this approach. When music is gradually
 252     becoming denser, the uniformity requirement makes lines go from
 253     cramped to even more cramped (because going from cramped
 254     3meas/line to relatively loose 2meas/line is such a big step.
 255
 256    */
 257
 258   Real demerit = abs (this_one.force_) +  abs (prev.force_ - this_one.force_)
 259     + break_penalties;
 260
 261   if (!this_one.satisfies_constraints_)
 262      {
 263        /*
 264          If it doesn't satisfy constraints, we make this one
 265          really unattractive.
 266
 267          add 20000 to the demerits, so that a break penalty
 268          of -10000 won't change the result */
 269        demerit = (demerit + 20000) >? 2000;
 270
 271        demerit *= 10;
 272      }
 273
 274    return demerit;
 275 }
 276