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--2002 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8 #include <math.h>               // rint
   9
  10 #include "gourlay-breaking.hh"
  11 #include "column-x-positions.hh"
  12 #include "debug.hh"
  13 #include "paper-column.hh"
  14 #include "paper-score.hh"
  15 #include "paper-def.hh"
  16 #include "simple-spacer.hh"
  17 #include "line-of-score.hh"
  18
  19 /// How often to print operator pacification marks?
  20 const int HAPPY_DOTS_I = 3;
  21
  22 /**
  23   Helper to trace back an optimal path
  24  */
  25 struct Break_node {
  26   /** this was the previous. If negative, this break should not be
  27     considered: this path has infinite energy
  28
  29     */
  30   int prev_break_i_;
  31   /**
  32      Which system number so far?
  33    */
  34   int line_i_;
  35
  36   Real demerits_f_;
  37   Column_x_positions line_config_;
  38
  39   Break_node ()
  40   {
  41     prev_break_i_ = -1;
  42     line_i_ = 0;
  43     demerits_f_ = 0;
  44   }
  45 };
  46
  47 /**
  48   This algorithms is adapted from the OSU Tech report on breaking lines.
  49
  50   this function is longish, but not very complicated.
  51
  52  */
  53 Array<Column_x_positions>
  54 Gourlay_breaking::do_solve () const
  55 {
  56   Array<Break_node> optimal_paths;
  57   Link_array<Grob> all =
  58     pscore_l_->line_l_->column_l_arr ();
  59
  60   Array<int> breaks = find_break_indices ();
  61
  62   Break_node first_node ;
  63   optimal_paths.push (first_node);
  64
  65   Real worst_force = 0.0;
  66
  67   for (int break_idx=1; break_idx< breaks.size (); break_idx++)
  68     {
  69       /*
  70         start with a short line, add measures. At some point
  71         the line becomes infeasible. Then we don't try to add more
  72         */
  73       int minimal_start_idx = -1;
  74       Column_x_positions minimal_sol;
  75       Column_x_positions backup_sol;
  76
  77       Real minimal_demerits = infinity_f;
  78
  79       for (int start_idx = break_idx; start_idx--;)
  80         {
  81           Link_array<Grob> line = all.slice (breaks[start_idx], breaks[break_idx]+1);
  82
  83           line[0]     = dynamic_cast<Item*> (line[0])    ->find_prebroken_piece (RIGHT);
  84           line.top () = dynamic_cast<Item*> (line.top ())->find_prebroken_piece (LEFT);
  85
  86           Column_x_positions cp;
  87           cp.cols_ = line;
  88
  89           Interval line_dims
  90             = pscore_l_->paper_l_->line_dimensions_int (optimal_paths[start_idx].line_i_);
  91           Simple_spacer * sp = generate_spacing_problem (line, line_dims);
  92           sp->solve (&cp);
  93           delete sp;
  94
  95           if (fabs (cp.force_f_) > worst_force)
  96             worst_force = fabs (cp.force_f_);
  97
  98           /*
  99             We remember this solution as a "should always work
 100             solution", in case everything fucks up.  */
 101           if (start_idx == break_idx - 1)
 102             backup_sol = cp;
 103
 104           Real this_demerits;
 105
 106           if (optimal_paths[start_idx].demerits_f_ >= infinity_f)
 107             this_demerits = infinity_f;
 108           else
 109             this_demerits = combine_demerits (optimal_paths[start_idx].line_config_, cp)
 110               + optimal_paths[start_idx].demerits_f_;
 111
 112           if (this_demerits < minimal_demerits)
 113             {
 114               minimal_start_idx = start_idx;
 115               minimal_sol = cp;
 116               minimal_demerits = this_demerits;
 117             }
 118
 119           /*
 120             we couldn't satisfy the constraints, this won't get better
 121             if we add more columns, so we get on with the next one
 122           */
 123           if (!cp.satisfies_constraints_b_)
 124             break ;
 125         }
 126
 127
 128       Break_node bnod;
 129       if (minimal_start_idx < 0)
 130         {
 131           bnod.demerits_f_ = infinity_f;
 132           bnod.line_config_ = backup_sol;
 133           bnod.prev_break_i_ = break_idx - 1;
 134         }
 135       else
 136         {
 137           bnod.prev_break_i_ = minimal_start_idx;
 138           bnod.demerits_f_ = minimal_demerits;
 139           bnod.line_config_ = minimal_sol;
 140         }
 141       bnod.line_i_ = optimal_paths[bnod.prev_break_i_].line_i_ + 1;
 142       optimal_paths.push (bnod);
 143
 144       if (! (break_idx % HAPPY_DOTS_I))
 145         progress_indication (String ("[") + to_str (break_idx) + "]");
 146     }
 147
 148   /* do the last one */
 149   if (breaks.size () % HAPPY_DOTS_I)
 150     progress_indication (String ("[") + to_str (breaks.size()) + "]");
 151
 152
 153   progress_indication ("\n");
 154
 155   Array<int> final_breaks;
 156   Array<Column_x_positions> lines;
 157
 158   /* skip 0-th element, since it is a "dummy" elt*/
 159   for (int i = optimal_paths.size ()-1; i> 0;)
 160     {
 161       final_breaks.push (i);
 162       int prev = optimal_paths[i].prev_break_i_;
 163       assert (i > prev);
 164       i = prev;
 165     }
 166
 167   if (optimal_paths.top ().demerits_f_ >= infinity_f)
 168     warning (_ ("No feasible line breaking found"));
 169
 170   for (int i= final_breaks.size (); i--;)
 171     {
 172       Column_x_positions cp (optimal_paths[final_breaks[i]].line_config_);
 173
 174       lines.push (cp);
 175       if(!cp.satisfies_constraints_b_)
 176         warning ("Could not find line breaking that satisfies constraints.");
 177     }
 178   return lines;
 179 }
 180
 181
 182 Gourlay_breaking::Gourlay_breaking ()
 183 {
 184 }
 185
 186
 187
 188 /*
 189   TODO: uniformity parameter to control rel. importance of spacing differences.
 190
 191   TODO:
 192
 193   mixing break penalties and constraint-failing solutions is confusing.
 194  */
 195 Real
 196 Gourlay_breaking::combine_demerits (Column_x_positions const &prev,
 197                                     Column_x_positions const &this_one) const
 198 {
 199   Real break_penalties = 0.0;
 200   Grob * pc = this_one.cols_.top ();
 201   if (pc->original_l_)
 202     {
 203       SCM pen = pc->get_grob_property ("penalty");
 204       if (gh_number_p (pen) && fabs (gh_scm2double (pen)) < 10000)
 205         {
 206           break_penalties += gh_scm2double (pen);
 207         }
 208     }
 209
 210   Real demerit = abs (this_one.force_f_) + abs (prev.force_f_ - this_one.force_f_)
 211     + break_penalties;
 212
 213
 214    if (!this_one.satisfies_constraints_b_)
 215      {
 216        /*
 217          If it doesn't satisfy constraints, we make this one
 218          really unattractive.
 219
 220          add 20000 to the demerits, so that a break penalty
 221          of -10000 won't change the result */
 222        demerit = (demerit + 20000) >? 2000;
 223
 224        demerit *= 10;
 225      }
 226
 227    return demerit;
 228 }
 229