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