lily/optimal-page-breaking.cc

   1 /*
   2   optimal-page-breaking.cc -- implement a page-breaker that
   3   will break pages in such a way that both horizontal and
   4   vertical spacing will be acceptable
   5
   6   source file of the GNU LilyPond music typesetter
   7
   8   (c) 2006--2009 Joe Neeman <joeneeman@gmail.com>
   9 */
  10
  11 #include "international.hh"
  12 #include "optimal-page-breaking.hh"
  13 #include "output-def.hh"
  14 #include "page-spacing.hh"
  15 #include "paper-book.hh"
  16 #include "paper-score.hh"
  17 #include "prob.hh"
  18 #include "system.hh"
  19
  20 static bool
  21 is_break (Grob *)
  22 {
  23   return false;
  24 }
  25
  26 // FIXME: divide the page breaking into subproblems wherever there is a page break.
  27 // This will allow us to tweak line-breaking independently on both sides of a
  28 // page break (currently, we only get to request a number of systems for an entire score
  29 // at a time), which is necessary for min-systems-per-page and \pageBreak to interact
  30 // correctly.
  31 Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
  32   : Page_breaking (pb, is_break)
  33 {
  34 }
  35
  36 Optimal_page_breaking::~Optimal_page_breaking ()
  37 {
  38 }
  39
  40 SCM
  41 Optimal_page_breaking::solve ()
  42 {
  43   vsize end = last_break_position ();
  44   vsize max_sys_count = max_system_count (0, end);
  45   vsize first_page_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
  46   SCM forced_page_count = book_->paper_->c_variable ("page-count");
  47
  48   set_to_ideal_line_configuration (0, end);
  49
  50   Page_spacing_result best;
  51   vsize page_count = robust_scm2int (forced_page_count, 1);
  52   Line_division ideal_line_division = current_configuration (0);
  53   Line_division best_division = ideal_line_division;
  54   vsize min_sys_count = 1;
  55   vsize ideal_sys_count = system_count ();
  56
  57   if (!scm_is_integer (forced_page_count))
  58     {
  59       /* find out the ideal number of pages */
  60       message (_ ("Finding the ideal number of pages..."));
  61
  62       if (systems_per_page () > 0)
  63         best = space_systems_with_fixed_number_per_page (0, first_page_num);
  64       else
  65         best = space_systems_on_best_pages (0, first_page_num);
  66
  67       page_count = best.systems_per_page_.size ();
  68       ideal_sys_count = best.system_count ();
  69       min_sys_count = ideal_sys_count - best.systems_per_page_.back ();
  70
  71       if (page_count > 1 && best.systems_per_page_[page_count - 2] > 1)
  72         min_sys_count -= best.systems_per_page_[page_count - 2];
  73
  74       min_sys_count = max (min_sys_count, (vsize)1);
  75     }
  76   else
  77     {
  78       /* TODO: the following line will spit out programming errors if the
  79          ideal line spacing doesn't fit on PAGE_COUNT pages */
  80       /* TODO: the interaction between systems_per_page and page_count needs to
  81          be considered. */
  82       best = space_systems_on_n_pages (0, page_count, first_page_num);
  83       min_sys_count = page_count;
  84     }
  85
  86   if (page_count == 1)
  87     message (_ ("Fitting music on 1 page..."));
  88   else if (scm_is_integer (forced_page_count))
  89     message (_f ("Fitting music on %d pages...", (int)page_count));
  90   else
  91     message (_f ("Fitting music on %d or %d pages...", (int)page_count-1, (int)page_count));
  92
  93   /* try a smaller number of systems than the ideal number for line breaking */
  94   Line_division bound = ideal_line_division;
  95   for (vsize sys_count = ideal_sys_count; --sys_count >= min_sys_count;)
  96     {
  97       Page_spacing_result best_for_this_sys_count;
  98       set_current_breakpoints (0, end, sys_count, Line_division (), bound);
  99
 100       for (vsize i = 0; i < current_configuration_count (); i++)
 101         {
 102           vsize min_p_count = min_page_count (i, first_page_num);
 103           Page_spacing_result cur;
 104
 105           if (min_p_count == page_count || scm_is_integer (forced_page_count))
 106             cur = space_systems_on_n_pages (i, page_count, first_page_num);
 107           else
 108             cur = space_systems_on_n_or_one_more_pages (i, page_count-1, first_page_num);
 109
 110           if (cur.demerits_ < best_for_this_sys_count.demerits_)
 111             {
 112               best_for_this_sys_count = cur;
 113               bound = current_configuration (i);
 114             }
 115         }
 116
 117       if (best_for_this_sys_count.demerits_ < best.demerits_)
 118         {
 119           best = best_for_this_sys_count;
 120           best_division = bound;
 121         }
 122
 123       /* Check to see if we already have too few systems. There are two ways
 124          we check this: if we are trying one less than the ideal number of pages
 125          and the pages are stretched on average then we have too
 126          few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
 127          have too few systems. In either case, though, we need to continue reducing
 128          the number of systems if max-systems-per-page requires it. */
 129       if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
 130         {
 131           if (best_for_this_sys_count.page_count () < page_count
 132               && best_for_this_sys_count.average_force () > 0)
 133             break;
 134
 135           if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
 136             break;
 137         }
 138     }
 139
 140   /* try a larger number of systems than the ideal line breaking number. This
 141      is more or less C&P, but the loop bounds make it difficult to try something
 142      like do {...} while (flip(&d) != UP). */
 143   bound = ideal_line_division;
 144   for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++)
 145     {
 146       Real best_demerits_for_this_sys_count = infinity_f;
 147       set_current_breakpoints (0, end, sys_count, bound);
 148
 149       for (vsize i = 0; i < current_configuration_count (); i++)
 150         {
 151           vsize min_p_count = min_page_count (i, first_page_num);
 152           Page_spacing_result cur;
 153
 154           if (min_p_count > page_count)
 155             continue;
 156           else
 157             cur = space_systems_on_n_pages (i, page_count, first_page_num);
 158
 159           if (cur.demerits_ < best.demerits_)
 160             {
 161               best = cur;
 162               best_division = current_configuration (i);
 163             }
 164
 165           if (cur.demerits_ < best_demerits_for_this_sys_count)
 166             {
 167               best_demerits_for_this_sys_count = cur.demerits_;
 168               bound = current_configuration (i);
 169             }
 170         }
 171       if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
 172         && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
 173         break;
 174     }
 175
 176   message (_ ("Drawing systems..."));
 177   break_into_pieces (0, end, best_division);
 178   SCM lines = systems ();
 179   return make_pages (best.systems_per_page_, lines);
 180 }
 181