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
  18 const HAPPY_DOTS_I = 3;
  19
  20 /**
  21   Helper to trace back an optimal path
  22  */
  23 struct Break_node {
  24     /** this was the previous. If negative, this break should not be
  25       considered: this path has infinite energy
  26
  27      */
  28     int prev_break_i_;
  29     Real energy_f_;
  30     Col_hpositions line_config_;
  31     Break_node() {
  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
  44     Array<Break_node> optimal_paths;
  45     Line_of_cols all = all_cols();
  46     Array<int> breaks = find_break_indices();
  47
  48     optimal_paths.set_size (breaks.size());
  49
  50     Break_node first_node ;
  51     first_node.prev_break_i_ = -1;
  52     first_node.line_config_.energy_f_ = 0;
  53
  54     optimal_paths[0] = first_node;
  55     int break_idx=1;
  56
  57
  58     for (; break_idx< breaks.size(); break_idx++) {
  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             if  (break_idx - start_idx > max_measures_i_)
  69                 break;
  70
  71             if (optimal_paths[start_idx].prev_break_i_ < 0
  72                 && optimal_paths[start_idx].line_config_.energy_f_)
  73
  74                 continue;
  75
  76             Line_of_cols line = all.slice (breaks[start_idx], breaks[break_idx]+1);
  77
  78             line[0] = line[0]->postbreak_p_;
  79             line.top() = line.top ()->prebreak_p_;
  80
  81             if (!feasible (line))
  82                 break;
  83
  84             Col_hpositions approx;
  85             approx.cols = line;
  86
  87             approx.spacer_l_ = generate_spacing_problem (line);
  88             spacer_p_list.bottom().add (approx.spacer_l_);
  89
  90             ((Break_algorithm*)this)->approx_stats_.add (approx.cols);
  91             approx.approximate_solve_line();
  92
  93             if  (approx.energy_f_  > energy_bound_f_){
  94                 continue;
  95             }
  96
  97
  98             // this is a likely candidate. Store it.
  99             candidate_lines.push (approx);
 100             candidates.push (start_idx);
 101         }
 102
 103
 104         int minimal_j = -1;
 105         Real minimal_energy = infinity_f;
 106         for (int j=0; j < candidates.size(); j++) {
 107             int start = candidates[j];
 108             if ( optimal_paths[start].line_config_.energy_f_
 109                  + candidate_lines[j].energy_f_  > minimal_energy)
 110
 111                 continue;
 112
 113             if ( !candidate_lines[j].satisfies_constraints_b_) {
 114                  candidate_lines[j].solve_line();
 115                  ((Break_algorithm*)this)->exact_stats_.add ( candidate_lines[j].cols);
 116             }
 117
 118             Real this_energy
 119                 = optimal_paths[start].line_config_.energy_f_
 120                 + candidate_lines[j].energy_f_ ;
 121
 122             if ( this_energy < minimal_energy) {
 123                 minimal_j = j;
 124                 minimal_energy = this_energy;
 125             }
 126         }
 127
 128         if (minimal_j < 0) {
 129             optimal_paths[break_idx].prev_break_i_ = -1;
 130             optimal_paths[break_idx].line_config_.energy_f_ = infinity_f;
 131         } else {
 132             optimal_paths[break_idx].prev_break_i_ = candidates[minimal_j];
 133             optimal_paths[break_idx].line_config_ = candidate_lines[minimal_j];
 134         }
 135
 136         if ( !(break_idx % HAPPY_DOTS_I))
 137             *mlog << "[" << break_idx << "]"<<flush;
 138     }
 139
 140     if  ( break_idx % HAPPY_DOTS_I)
 141         *mlog << "[" << break_idx << "]"<<flush;
 142     print_stats();
 143
 144
 145
 146     Array<int> final_breaks;
 147
 148     Array<Col_hpositions> lines;
 149     /* skip 0-th element, since it is a "dummy" elt*/
 150     for (int i = optimal_paths.size()-1; i> 0;) {
 151         final_breaks.push ( i);
 152         assert ( i > optimal_paths[i].prev_break_i_);
 153
 154         // there was no "feasible path"
 155         if (!optimal_paths[i].line_config_.config.size())
 156            return lines;
 157         i = optimal_paths[i].prev_break_i_;
 158     }
 159
 160     for (int i= final_breaks.size(); i--;)
 161         lines.push ( optimal_paths[final_breaks[i]].line_config_);
 162
 163
 164     return lines;
 165 }
 166
 167
 168 Gourlay_breaking::Gourlay_breaking()
 169 {
 170     get_line_spacer = Spring_spacer::constructor;
 171     energy_bound_f_ = infinity_f;
 172     max_measures_i_ = INT_MAX;
 173 }
 174
 175 void
 176 Gourlay_breaking::do_set_pscore()
 177 {
 178     energy_bound_f_ = pscore_l_->paper_l_->get_var ("gourlay_energybound");
 179     max_measures_i_ =int (rint (pscore_l_->paper_l_->get_var ("gourlay_maxmeasures")));
 180 }
 181