release: 1.5.29

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

diff --git a/lily/gourlay-breaking.cc b/lily/gourlay-breaking.cc
index 04112971d318513083b415e3f3373c949da1f243..96728b602a9f3d402cbca308663b065e9980ef85 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--2001 Han-Wen Nienhuys <hanwen@cs.uu.nl>
+  (c)  1997--2002 Han-Wen Nienhuys <hanwen@cs.uu.nl>
 */
 #include <math.h>              // rint
 
@@ -59,14 +59,12 @@ Gourlay_breaking::do_solve () const
   
   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 
@@ -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,6 +187,10 @@ 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,
@@ -181,13 +201,29 @@ Gourlay_breaking::combine_demerits (Column_x_positions const &prev,
   if (pc->original_l_)
     {
       SCM pen = pc->get_grob_property ("penalty");
-      if (gh_number_p (pen))
+      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_)
+  Real demerit = abs (this_one.force_f_) + abs (prev.force_f_ - this_one.force_f_)
     + break_penalties;
+
+
+   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;
 }