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