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 *g)
  22 {
  23   return g->get_property ("page-break-permission") == ly_symbol2scm ("force");
  24 }
  25
  26 Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
  27   : Page_breaking (pb, is_break)
  28 {
  29 }
  30
  31 Optimal_page_breaking::~Optimal_page_breaking ()
  32 {
  33 }
  34
  35 // Solves the subproblem betwen the (END-1)th \pageBreak and the
  36 // ENDth \pageBreak.
  37 // Returns a vector of systems per page for the pages within this chunk.
  38 vector<vsize>
  39 Optimal_page_breaking::solve_chunk (vsize end)
  40 {
  41   vsize max_sys_count = max_system_count (end-1, end);
  42   vsize first_page_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
  43   SCM forced_page_count = book_->paper_->c_variable ("page-count");
  44
  45   set_to_ideal_line_configuration (end-1, end);
  46
  47   Page_spacing_result best;
  48   vsize page_count = robust_scm2int (forced_page_count, 1);
  49   Line_division ideal_line_division = current_configuration (0);
  50   Line_division best_division = ideal_line_division;
  51   vsize min_sys_count = 1;
  52   vsize ideal_sys_count = system_count ();
  53
  54   if (!scm_is_integer (forced_page_count))
  55     {
  56       if (systems_per_page () > 0)
  57         best = space_systems_with_fixed_number_per_page (0, first_page_num);
  58       else
  59         best = space_systems_on_best_pages (0, first_page_num);
  60
  61       page_count = best.systems_per_page_.size ();
  62       ideal_sys_count = best.system_count ();
  63       min_sys_count = ideal_sys_count - best.systems_per_page_.back ();
  64
  65       if (page_count > 1 && best.systems_per_page_[page_count - 2] > 1)
  66         min_sys_count -= best.systems_per_page_[page_count - 2];
  67
  68       min_sys_count = max (min_sys_count, (vsize)1);
  69     }
  70   else
  71     {
  72       /* TODO: the following line will spit out programming errors if the
  73          ideal line spacing doesn't fit on PAGE_COUNT pages */
  74       /* TODO: the interaction between systems_per_page and page_count needs to
  75          be considered. */
  76       best = space_systems_on_n_pages (0, page_count, first_page_num);
  77       min_sys_count = page_count;
  78     }
  79
  80   if (page_count == 1 || scm_is_integer (forced_page_count))
  81     progress_indication (_f ("[%d, %d pages]", (int) end, (int) page_count));
  82   else
  83     progress_indication (_f ("[%d, %d or %d pages]", (int) end, (int) page_count-1, (int)page_count));
  84
  85   /* try a smaller number of systems than the ideal number for line breaking */
  86   Line_division bound = ideal_line_division;
  87   for (vsize sys_count = ideal_sys_count; --sys_count >= min_sys_count;)
  88     {
  89       Page_spacing_result best_for_this_sys_count;
  90       set_current_breakpoints (end-1, end, sys_count, Line_division (), bound);
  91
  92       for (vsize i = 0; i < current_configuration_count (); i++)
  93         {
  94           vsize min_p_count = min_page_count (i, first_page_num);
  95           Page_spacing_result cur;
  96
  97           if (min_p_count == page_count || scm_is_integer (forced_page_count))
  98             cur = space_systems_on_n_pages (i, page_count, first_page_num);
  99           else
 100             cur = space_systems_on_n_or_one_more_pages (i, page_count-1, first_page_num);
 101
 102           if (cur.demerits_ < best_for_this_sys_count.demerits_)
 103             {
 104               best_for_this_sys_count = cur;
 105               bound = current_configuration (i);
 106             }
 107         }
 108
 109       if (best_for_this_sys_count.demerits_ < best.demerits_)
 110         {
 111           best = best_for_this_sys_count;
 112           best_division = bound;
 113         }
 114
 115       /* Check to see if we already have too few systems. There are two ways
 116          we check this: if we are trying one less than the ideal number of pages
 117          and the pages are stretched on average then we have too
 118          few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
 119          have too few systems. In either case, though, we need to continue reducing
 120          the number of systems if max-systems-per-page requires it. */
 121       if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
 122         {
 123           if (best_for_this_sys_count.page_count () < page_count
 124               && best_for_this_sys_count.average_force () > 0)
 125             break;
 126
 127           if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
 128             break;
 129         }
 130     }
 131
 132   /* try a larger number of systems than the ideal line breaking number. This
 133      is more or less C&P, but the loop bounds make it difficult to try something
 134      like do {...} while (flip(&d) != UP). */
 135   bound = ideal_line_division;
 136   for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++)
 137     {
 138       Real best_demerits_for_this_sys_count = infinity_f;
 139       set_current_breakpoints (end-1, end, sys_count, bound);
 140
 141       for (vsize i = 0; i < current_configuration_count (); i++)
 142         {
 143           vsize min_p_count = min_page_count (i, first_page_num);
 144           Page_spacing_result cur;
 145
 146           if (min_p_count > page_count)
 147             continue;
 148           else
 149             cur = space_systems_on_n_pages (i, page_count, first_page_num);
 150
 151           if (cur.demerits_ < best.demerits_)
 152             {
 153               best = cur;
 154               best_division = current_configuration (i);
 155             }
 156
 157           if (cur.demerits_ < best_demerits_for_this_sys_count)
 158             {
 159               best_demerits_for_this_sys_count = cur.demerits_;
 160               bound = current_configuration (i);
 161             }
 162         }
 163       if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
 164         && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
 165         break;
 166     }
 167   break_into_pieces (end-1, end, best_division);
 168
 169   return best.systems_per_page_;
 170 }
 171
 172 SCM
 173 Optimal_page_breaking::solve ()
 174 {
 175   vector<vsize> systems_per_page;
 176
 177   message (_f ("Solving %d page-breaking chunks...", last_break_position ()-1));
 178   for (vsize end = 1; end <= last_break_position (); ++end)
 179     {
 180       vector<vsize> chunk_systems = solve_chunk (end);
 181       systems_per_page.insert (systems_per_page.end (), chunk_systems.begin (), chunk_systems.end ());
 182     }
 183
 184   message (_ ("Drawing systems..."));
 185   SCM lines = systems ();
 186   return make_pages (systems_per_page, lines);
 187 }
 188