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   {
  33     prev_break_i_ = -1;
  34   }
  35 };
  36
  37 /**
  38   This algorithms is adapted from
  39  */
  40
  41 Array<Col_hpositions>
  42 Gourlay_breaking::do_solve()const
  43 {
  44
  45   Array<Break_node> optimal_paths;
  46   Line_of_cols all = all_cols();
  47   Array<int> breaks = find_break_indices();
  48
  49   optimal_paths.set_size (breaks.size());
  50
  51   Break_node first_node ;
  52   first_node.prev_break_i_ = -1;
  53   first_node.line_config_.energy_f_ = 0;
  54
  55   optimal_paths[0] = first_node;
  56   int break_idx=1;
  57
  58
  59   for (; break_idx< breaks.size(); break_idx++)
  60     {
  61       Array<int> candidates;
  62       Array<Col_hpositions> candidate_lines;
  63       Pointer_list<Line_spacer*> spacer_p_list;
  64
  65       /*
  66         start with a short line, add measures. At some point
  67         the line becomes infeasible. Then we don't try to add more
  68         */
  69       for (int start_idx = break_idx; start_idx--;)
  70         {
  71           if  (break_idx - start_idx > max_measures_i_)
  72             break;
  73
  74           if (optimal_paths[start_idx].prev_break_i_ < 0
  75               && optimal_paths[start_idx].line_config_.energy_f_)
  76
  77             continue;
  78
  79           Line_of_cols line = all.slice (breaks[start_idx], breaks[break_idx]+1);
  80
  81           line[0] = line[0]->postbreak_p_;
  82           line.top() = line.top ()->prebreak_p_;
  83
  84           if (!feasible (line))
  85             break;
  86
  87           Col_hpositions approx;
  88           approx.cols = line;
  89
  90           approx.spacer_l_ = generate_spacing_problem (line);
  91           spacer_p_list.bottom().add (approx.spacer_l_);
  92
  93           ((Break_algorithm*)this)->approx_stats_.add (approx.cols);
  94           approx.approximate_solve_line();
  95
  96           if  (approx.energy_f_  > energy_bound_f_)
  97             {
  98               continue;
  99             }
 100
 101
 102           // this is a likely candidate. Store it.
 103           candidate_lines.push (approx);
 104           candidates.push (start_idx);
 105         }
 106
 107
 108       int minimal_j = -1;
 109       Real minimal_energy = infinity_f;
 110       for (int j=0; j < candidates.size(); j++)
 111         {
 112           int start = candidates[j];
 113           if ( optimal_paths[start].line_config_.energy_f_
 114                + candidate_lines[j].energy_f_  > minimal_energy)
 115
 116             continue;
 117
 118           if ( !candidate_lines[j].satisfies_constraints_b_)
 119             {
 120               candidate_lines[j].solve_line();
 121               ((Break_algorithm*)this)->exact_stats_.add ( candidate_lines[j].cols);
 122             }
 123
 124           Real this_energy
 125             = optimal_paths[start].line_config_.energy_f_
 126             + candidate_lines[j].energy_f_ ;
 127
 128           if ( this_energy < minimal_energy)
 129             {
 130               minimal_j = j;
 131               minimal_energy = this_energy;
 132             }
 133         }
 134
 135       if (minimal_j < 0)
 136         {
 137           optimal_paths[break_idx].prev_break_i_ = -1;
 138           optimal_paths[break_idx].line_config_.energy_f_ = infinity_f;
 139         }
 140       else
 141         {
 142           optimal_paths[break_idx].prev_break_i_ = candidates[minimal_j];
 143           optimal_paths[break_idx].line_config_ = candidate_lines[minimal_j];
 144         }
 145
 146       if ( !(break_idx % HAPPY_DOTS_I))
 147         *mlog << "[" << break_idx << "]"<<flush;
 148     }
 149
 150   if  ( break_idx % HAPPY_DOTS_I)
 151     *mlog << "[" << break_idx << "]"<<flush;
 152
 153   Array<int> final_breaks;
 154
 155   Array<Col_hpositions> lines;
 156   Real min_energy_f_ = infinity_f;
 157   Real max_energy_f_ = 0;
 158
 159   /* skip 0-th element, since it is a "dummy" elt*/
 160   for (int i = optimal_paths.size()-1; i> 0;)
 161     {
 162       final_breaks.push ( i);
 163       assert ( i > optimal_paths[i].prev_break_i_);
 164
 165       // there was no "feasible path"
 166       if (!optimal_paths[i].line_config_.config.size()) {
 167         final_breaks.set_size (0);
 168         break;
 169       }
 170       i = optimal_paths[i].prev_break_i_;
 171     }
 172
 173   print_stats();
 174   /*
 175     TODO print variation in energy
 176    */
 177   if (max_energy_f_ )
 178     {
 179       ;
 180     }
 181
 182
 183
 184   for (int i= final_breaks.size(); i--;)
 185     lines.push ( optimal_paths[final_breaks[i]].line_config_);
 186
 187
 188   return lines;
 189 }
 190
 191
 192 Gourlay_breaking::Gourlay_breaking()
 193 {
 194   get_line_spacer = Spring_spacer::constructor;
 195   energy_bound_f_ = infinity_f;
 196   max_measures_i_ = INT_MAX;
 197 }
 198
 199 void
 200 Gourlay_breaking::do_set_pscore()
 201 {
 202   energy_bound_f_ = pscore_l_->paper_l_->get_var ("gourlay_energybound");
 203   max_measures_i_ =int (rint (pscore_l_->paper_l_->get_var ("gourlay_maxmeasures")));
 204 }
 205