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 Han-Wen Nienhuys <hanwen@stack.nl>
   7 */
   8
   9 #include "gourlay-breaking.hh"
  10 #include "colhpos.hh"
  11 #include "spring-spacer.hh"
  12 #include "debug.hh"
  13 #include "p-col.hh"
  14 #include "p-score.hh"
  15 #include "paper-def.hh"
  16
  17 const HAPPY_DOTS_I = 3;
  18
  19 /**
  20   Helper to trace back an optimal path
  21  */
  22 struct Break_node {
  23   /** this was the previous. If negative, this break should not be
  24     considered: this path has infinite energy
  25
  26     */
  27   int prev_break_i_;
  28   Real energy_f_;
  29   Col_hpositions line_config_;
  30   Break_node()
  31   {
  32     prev_break_i_ = -1;
  33   }
  34 };
  35
  36 /**
  37   This algorithms is adapted from
  38  */
  39
  40 Array<Col_hpositions>
  41 Gourlay_breaking::do_solve() const
  42 {
  43   Array<Break_node> optimal_paths;
  44   Line_of_cols all = all_cols();
  45   Array<int> breaks = find_break_indices();
  46
  47   optimal_paths.set_size (breaks.size());
  48
  49   Break_node first_node ;
  50   first_node.prev_break_i_ = -1;
  51   first_node.line_config_.energy_f_ = 0;
  52
  53   optimal_paths[0] = first_node;
  54   int break_idx=1;
  55
  56
  57   for (; break_idx< breaks.size(); break_idx++)
  58     {
  59       Array<int> candidates;
  60       Array<Col_hpositions> candidate_lines;
  61       Pointer_list<Line_spacer*> spacer_p_list;
  62
  63       /*
  64         start with a short line, add measures. At some point
  65         the line becomes infeasible. Then we don't try to add more
  66         */
  67       for (int start_idx = break_idx; start_idx--;)
  68         {
  69           if  (break_idx - start_idx > max_measures_i_)
  70             break;
  71
  72           if (optimal_paths[start_idx].prev_break_i_ < 0
  73               && optimal_paths[start_idx].line_config_.energy_f_)
  74
  75             continue;
  76
  77           Line_of_cols line = all.slice (breaks[start_idx], breaks[break_idx]+1);
  78
  79           line[0] = line[0]->postbreak_l();
  80           line.top() = line.top ()->prebreak_l();
  81
  82           if (!feasible (line))
  83             break;
  84
  85           Col_hpositions approx;
  86           approx.cols = line;
  87
  88           approx.spacer_l_ = generate_spacing_problem (line);
  89           spacer_p_list.bottom().add (approx.spacer_l_);
  90
  91           ((Break_algorithm*)this)->approx_stats_.add (approx.cols);
  92           approx.approximate_solve_line();
  93
  94           if  (approx.energy_f_  > energy_bound_f_)
  95             {
  96               continue;
  97             }
  98
  99
 100           // this is a likely candidate. Store it.
 101           candidate_lines.push (approx);
 102           candidates.push (start_idx);
 103         }
 104
 105
 106       int minimal_j = -1;
 107       Real minimal_energy = infinity_f;
 108       for (int j=0; j < candidates.size(); j++)
 109         {
 110           int start = candidates[j];
 111           if (optimal_paths[start].line_config_.energy_f_
 112                + candidate_lines[j].energy_f_  > minimal_energy)
 113
 114             continue;
 115
 116           if (!candidate_lines[j].satisfies_constraints_b_)
 117             {
 118               candidate_lines[j].solve_line();
 119               ((Break_algorithm*)this)->exact_stats_.add (candidate_lines[j].cols);
 120             }
 121
 122           Real this_energy
 123             = optimal_paths[start].line_config_.energy_f_
 124             + candidate_lines[j].energy_f_ ;
 125
 126           if (this_energy < minimal_energy)
 127             {
 128               minimal_j = j;
 129               minimal_energy = this_energy;
 130             }
 131         }
 132
 133       if (minimal_j < 0)
 134         {
 135           optimal_paths[break_idx].prev_break_i_ = -1;
 136           optimal_paths[break_idx].line_config_.energy_f_ = infinity_f;
 137         }
 138       else
 139         {
 140           optimal_paths[break_idx].prev_break_i_ = candidates[minimal_j];
 141           optimal_paths[break_idx].line_config_ = candidate_lines[minimal_j];
 142         }
 143
 144       if (!(break_idx % HAPPY_DOTS_I))
 145         *mlog << "[" << break_idx << "]"<<flush;
 146     }
 147
 148   if  (break_idx % HAPPY_DOTS_I)
 149     *mlog << "[" << break_idx << "]"<<flush;
 150
 151   Array<int> final_breaks;
 152
 153   Array<Col_hpositions> lines;
 154
 155   Real max_energy_f = 0;
 156
 157   /* skip 0-th element, since it is a "dummy" elt*/
 158   for (int i = optimal_paths.size()-1; i> 0;)
 159     {
 160       final_breaks.push (i);
 161       assert (i > optimal_paths[i].prev_break_i_);
 162
 163       // there was no "feasible path"
 164       if (!optimal_paths[i].line_config_.config.size()) {
 165         final_breaks.set_size (0);
 166         break;
 167       }
 168       i = optimal_paths[i].prev_break_i_;
 169     }
 170
 171
 172   for (int i= final_breaks.size(); i--;)
 173     lines.push (optimal_paths[final_breaks[i]].line_config_);
 174
 175   return lines;
 176 }
 177
 178
 179 Gourlay_breaking::Gourlay_breaking()
 180 {
 181   get_line_spacer = Spring_spacer::constructor;
 182   energy_bound_f_ = infinity_f;
 183   max_measures_i_ = INT_MAX;
 184 }
 185
 186 void
 187 Gourlay_breaking::do_set_pscore()
 188 {
 189   energy_bound_f_ = pscore_l_->paper_l_->get_var ("gourlay_energybound");
 190   max_measures_i_ =int (rint (pscore_l_->paper_l_->get_var ("gourlay_maxmeasures")));
 191 }
 192