patch::: 1.5.41.jcn2

[lilypond.git] / lily / gourlay-breaking.cc

diff --git a/lily/gourlay-breaking.cc b/lily/gourlay-breaking.cc
index 192ece0a69c9642c51a56b04fed0b3ad03894f42..b61a750562d3c6718cd8d3ff702a54be32ab9d78 100644 (file)
--- a/lily/gourlay-breaking.cc
+++ b/lily/gourlay-breaking.cc
@@ -3,7 +3,7 @@
 
   source file of the GNU LilyPond music typesetter
 
-  (c)  1997--2000 Han-Wen Nienhuys <hanwen@cs.uu.nl>
+  (c)  1997--2002 Han-Wen Nienhuys <hanwen@cs.uu.nl>
 */
 #include <math.h>              // rint
 
@@ -54,19 +54,17 @@ Array<Column_x_positions>
 Gourlay_breaking::do_solve () const
 {
   Array<Break_node> optimal_paths;
-  Link_array<Score_element> all =
+  Link_array<Grob> all =
     pscore_l_->line_l_->column_l_arr ();
   
   Array<int> breaks = find_break_indices ();
   
-  optimal_paths.set_size (breaks.size ());
-
   Break_node first_node ;
-  
-  optimal_paths[0] = first_node; 
-  int break_idx=1;
+  optimal_paths.push (first_node);
 
-  for (; break_idx< breaks.size (); break_idx++) 
+  Real worst_force = 0.0;
+  
+  for (int break_idx=1; break_idx< breaks.size (); break_idx++) 
     {
       /*
        start with a short line, add measures. At some point 
@@ -80,7 +78,7 @@ Gourlay_breaking::do_solve () const
 
       for (int start_idx = break_idx; start_idx--;)
        {
-         Link_array<Score_element> line = all.slice (breaks[start_idx], breaks[break_idx]+1);
+         Link_array<Grob> line = all.slice (breaks[start_idx], breaks[break_idx]+1);
   
          line[0]     = dynamic_cast<Item*> (line[0])    ->find_prebroken_piece (RIGHT);
          line.top () = dynamic_cast<Item*> (line.top ())->find_prebroken_piece (LEFT);
@@ -94,13 +92,17 @@ Gourlay_breaking::do_solve () const
          sp->solve (&cp);
          delete sp;
 
-         if (start_idx == break_idx - 1)
-           backup_sol = cp;    // in case everything fucks up
-         if (!cp.satisfies_constraints_b_)
-           break;
+         if (fabs (cp.force_f_) > worst_force)
+           worst_force = fabs (cp.force_f_);
 
-         
+         /*
+           We remember this solution as a "should always work
+           solution", in case everything fucks up.  */
+         if (start_idx == break_idx - 1)
+           backup_sol = cp;
+                 
          Real this_demerits;
+
          if (optimal_paths[start_idx].demerits_f_ >= infinity_f)
            this_demerits = infinity_f;
          else
@@ -113,30 +115,39 @@ Gourlay_breaking::do_solve () const
              minimal_sol = cp;
              minimal_demerits = this_demerits;
            }
+
+         /*
+           we couldn't satisfy the constraints, this won't get better
+           if we add more columns, so we get on with the next one
+         */
+         if (!cp.satisfies_constraints_b_)
+           break ; 
        }
 
-      int prev =break_idx - 1;
+
+      Break_node bnod;
       if (minimal_start_idx < 0) 
        {
-         optimal_paths[break_idx].demerits_f_ = infinity_f;
-         optimal_paths[break_idx].line_config_ = backup_sol;     
+         bnod.demerits_f_ = infinity_f;
+         bnod.line_config_ = backup_sol;
+         bnod.prev_break_i_ = break_idx - 1;     
        }
       else 
        {
-         prev = minimal_start_idx;
-         optimal_paths[break_idx].line_config_ = minimal_sol;
-         optimal_paths[break_idx].demerits_f_ = minimal_demerits;
+         bnod.prev_break_i_ = minimal_start_idx;
+         bnod.demerits_f_ = minimal_demerits;
+         bnod.line_config_ = minimal_sol;
        }
-      optimal_paths[break_idx].prev_break_i_ = prev;
-      optimal_paths[break_idx].line_i_ = optimal_paths[prev].line_i_ + 1;
-
+      bnod.line_i_ = optimal_paths[bnod.prev_break_i_].line_i_ + 1;
+      optimal_paths.push (bnod);
+      
       if (! (break_idx % HAPPY_DOTS_I))
        progress_indication (String ("[") + to_str (break_idx) + "]");
     }
 
   /* do the last one */
-  if  (break_idx % HAPPY_DOTS_I)
-       progress_indication (String ("[") + to_str (break_idx) + "]");    
+  if (breaks.size () % HAPPY_DOTS_I)
+    progress_indication (String ("[") + to_str (breaks.size()) + "]");    
 
 
   progress_indication ("\n");
@@ -156,9 +167,14 @@ Gourlay_breaking::do_solve () const
   if (optimal_paths.top ().demerits_f_ >= infinity_f)
     warning (_ ("No feasible line breaking found"));
   
-  for (int i= final_breaks.size (); i--;) 
-    lines.push (optimal_paths[final_breaks[i]].line_config_);
-  
+  for (int i= final_breaks.size (); i--;)
+    {
+      Column_x_positions cp (optimal_paths[final_breaks[i]].line_config_);
+      
+      lines.push (cp);
+      if(!cp.satisfies_constraints_b_)
+       warning ("Could not find line breaking that satisfies constraints.");
+    }
   return lines;
 }
 
@@ -171,23 +187,49 @@ Gourlay_breaking::Gourlay_breaking ()
 
 /*
   TODO: uniformity parameter to control rel. importance of spacing differences.
+
+  TODO:
+
+  mixing break penalties and constraint-failing solutions is confusing.
  */
 Real
 Gourlay_breaking::combine_demerits (Column_x_positions const &prev,
                                    Column_x_positions const &this_one) const
 {
   Real break_penalties = 0.0;
-  Score_element * pc = this_one.cols_.top ();
+  Grob * pc = this_one.cols_.top ();
   if (pc->original_l_)
     {
-      SCM pen = pc->get_elt_property ("penalty");
-      if (gh_number_p (pen))
+      SCM pen = pc->get_grob_property ("penalty");
+      if (gh_number_p (pen) && fabs (gh_scm2double (pen)) < 10000)
        {
          break_penalties += gh_scm2double (pen);
        }
     }
 
-  return abs (this_one.force_f_) + abs (prev.force_f_ - this_one.force_f_)
+#if 1
+  /*
+    Q: do want globally non-cramped lines, or locally equally cramped lines. 
+   */
+  Real demerit = abs (this_one.force_f_) + abs (prev.force_f_ - this_one.force_f_)
     + break_penalties;
+#else
+  Real demerit = abs (this_one.force_f_) + break_penalties;
+#endif
+
+   if (!this_one.satisfies_constraints_b_)
+     {
+       /*
+        If it doesn't satisfy constraints, we make this one
+        really unattractive.
+
+        add 20000 to the demerits, so that a break penalty
+        of -10000 won't change the result */
+       demerit = (demerit + 20000) >? 2000;
+       
+       demerit *= 10;
+     }
+
+   return demerit;
 }