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