lily/page-breaking.cc

   1 /*
   2   page-breaking.cc -- implement a superclass and utility
   3   functions for use by various page-breaking algorithms
   4
   5   source file of the GNU LilyPond music typesetter
   6
   7   (c) 2006 Joe Neeman <joeneeman@gmail.com>
   8 */
   9
  10 #include "page-breaking.hh"
  11
  12 #include "international.hh"
  13 #include "item.hh"
  14 #include "output-def.hh"
  15 #include "page-spacing.hh"
  16 #include "paper-book.hh"
  17 #include "paper-score.hh"
  18 #include "paper-system.hh"
  19 #include "system.hh"
  20 #include "warn.hh"
  21
  22 System_spec::System_spec (Paper_score *ps, int break_count)
  23 {
  24   pscore_ = ps;
  25   prob_ = 0;
  26   score_break_count_ = break_count;
  27 }
  28
  29 System_spec::System_spec (Prob *pb)
  30 {
  31   pscore_ = 0;
  32   prob_ = pb;
  33   score_break_count_ = 0;
  34 }
  35
  36 System_spec::System_spec ()
  37 {
  38   pscore_ = 0;
  39   prob_ = 0;
  40   score_break_count_ = 0;
  41 }
  42
  43 /* for Page_breaking, the start index (when we are dealing with the stuff
  44    between a pair of breakpoints) refers to the break_ index of the end of
  45    the previous page. So the system index of the start of the current page
  46    could either be the same as the end of the previous page or one more than
  47    it. */
  48
  49 /* Turn a break index into the sys index that starts the next page */
  50 vsize Page_breaking::next_system (vsize start) const
  51 {
  52   vsize sys = breaks_[start].sys_;
  53
  54   if (sys == VPOS) /* beginning of the piece */
  55     return 0;
  56   if (all_[sys].pscore_ && all_[sys].score_break_count_ > breaks_[start].score_break_)
  57     return sys; /* the score overflows the previous page */
  58   return sys + 1; /* this page starts with a new sys */
  59 }
  60
  61 Page_breaking::Page_breaking (Paper_book *pb, bool allow_intra_score_breaks)
  62 {
  63   book_ = pb;
  64   create_system_list (allow_intra_score_breaks);
  65 }
  66
  67 Page_breaking::~Page_breaking ()
  68 {
  69 }
  70
  71 /* translate indices into breaks_ into start-end parameters for the line breaker */
  72 void
  73 Page_breaking::line_breaker_args (vsize i, vsize *start, vsize *end)
  74 {
  75   assert (all_[i].pscore_);
  76   assert (next_system (*start) <= i && i <= breaks_[*end].sys_);
  77
  78   vsize start_col = 0;
  79   vsize end_col = VPOS;
  80
  81   if (breaks_[*start].sys_ == i)
  82     start_col = breaks_[*start].score_break_;
  83   if (breaks_[*end].sys_ == i)
  84     end_col = breaks_[*end].score_break_;
  85
  86   assert (end_col && (end_col == VPOS || end_col <= all_[breaks_[*end].sys_].score_break_count_));
  87   *start = start_col;
  88   *end = end_col;
  89 }
  90
  91 vector<Column_x_positions>
  92 Page_breaking::get_line_breaks (vsize i, vsize sys_count, vsize start, vsize end)
  93 {
  94   assert (all_[i].pscore_);
  95   line_breaker_args (i, &start, &end);
  96   return line_breaking_[i].get_solution (start, end, sys_count);
  97 }
  98
  99 vector<Line_details>
 100 Page_breaking::get_line_details (vsize start_break, vsize end_break, vector<vsize> const &div)
 101 {
 102   vector<Line_details> ret;
 103
 104   for (vsize i = next_system (start_break); i <= breaks_[end_break].sys_; i++)
 105     {
 106       if (all_[i].pscore_)
 107         {
 108           vsize div_index = i - next_system (start_break);
 109           vsize start = start_break;
 110           vsize end = end_break;
 111
 112           line_breaker_args (i, &start, &end);
 113           vector<Line_details> l = line_breaking_[i].get_details (start, end, div[div_index]);
 114           ret.insert (ret.end (), l.begin (), l.end ());
 115         }
 116       else
 117         ret.push_back (Line_details (all_[i].prob_));
 118     }
 119   return ret;
 120 }
 121
 122 vsize
 123 Page_breaking::get_min_systems (vsize i, vsize start, vsize end)
 124 {
 125   line_breaker_args (i, &start, &end);
 126   return line_breaking_[i].get_min_systems (start, end);
 127 }
 128
 129 vsize
 130 Page_breaking::get_max_systems (vsize i, vsize start, vsize end)
 131 {
 132   line_breaker_args (i, &start, &end);
 133   return line_breaking_[i].get_max_systems (start, end);
 134 }
 135
 136 Real
 137 Page_breaking::page_height (int page_num, bool last)
 138 {
 139   SCM mod = scm_c_resolve_module ("scm page");
 140   SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
 141   SCM make_page = scm_c_module_lookup (mod, "make-page");
 142
 143   calc_height = scm_variable_ref (calc_height);
 144   make_page = scm_variable_ref (make_page);
 145
 146   SCM page = scm_apply_0 (make_page, scm_list_n (
 147                   book_->self_scm (),
 148                   ly_symbol2scm ("page-number"), scm_from_int (page_num),
 149                   ly_symbol2scm ("is-last"), scm_from_bool (last),
 150                   SCM_UNDEFINED));
 151   SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
 152   return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
 153 }
 154
 155 SCM
 156 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
 157 {
 158   SCM module = scm_c_resolve_module ("scm layout-page-layout");
 159   SCM make_page = scm_c_module_lookup (module, "make-page-from-systems");
 160   make_page = scm_variable_ref (make_page);
 161   SCM book = book_->self_scm ();
 162   bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
 163   bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
 164   SCM ret = SCM_EOL;
 165
 166   for (vsize i = 0; i < lines_per_page.size (); i++)
 167     {
 168       SCM page_num = scm_from_int (i + 1);
 169       SCM last = scm_from_bool (i == lines_per_page.size () - 1);
 170       SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
 171       SCM line_count = scm_from_int (lines_per_page[i]);
 172       SCM lines = scm_list_head (systems, line_count);
 173       SCM page = scm_apply_0 (make_page,
 174                               scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
 175
 176       ret = scm_cons (page, ret);
 177       systems = scm_list_tail (systems, line_count);
 178     }
 179   return scm_reverse (ret);
 180 }
 181
 182 /* if allow_intra_score_breaks is false, that doesn't necessarily mean that there will
 183    be no page turns in the middle of a score, only that we don't give special
 184    consideration to any internal part of a score.
 185
 186    Corollary: if allow_intra_score_breaks is false, any \pageTurn or \noPageTurn commands
 187    in the middle of a score will be ignored.
 188 */
 189 void
 190 Page_breaking::create_system_list (bool allow_intra_score_breaks)
 191 {
 192   breaks_.push_back (Break_position ());
 193
 194   SCM specs = book_->get_system_specs ();
 195   for (SCM s = specs; s != SCM_EOL; s = scm_cdr (s))
 196     {
 197       if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
 198         {
 199           /* add a breakpoint at the end of the last score, if necessary */
 200           if (all_.size () && all_.back ().pscore_)
 201             breaks_.push_back (Break_position (all_.size () - 1,
 202                                                all_.back ().score_break_count_));
 203
 204           vector<vsize> score_brk;
 205           if (allow_intra_score_breaks)
 206             score_brk = find_page_break_indices (ps);
 207
 208           all_.push_back (System_spec (ps, score_brk.size () + 1));
 209
 210           for (vsize i = 0; i < score_brk.size(); i++)
 211             breaks_.push_back (Break_position (all_.size () - 1, i + 1));
 212
 213           /* include a line breaker at the start of the score */
 214           score_brk.insert (score_brk.begin (), 0);
 215           line_breaking_.push_back (Constrained_breaking (score_brk));
 216           line_breaking_.back ().set_pscore (ps);
 217         }
 218       else
 219         {
 220           Prob *pb = unsmob_prob (scm_car (s));
 221           assert (pb);
 222
 223           pb->protect ();
 224           // ignore penalties (from break-before) in favour of using \pageBreak at the
 225           // end of the score
 226           if (all_.size () && all_.back ().pscore_)
 227             breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_));
 228           all_.push_back (System_spec (pb));
 229           line_breaking_.push_back (Constrained_breaking ());
 230         }
 231     }
 232
 233   /* add the ending breakpoint */
 234   if (all_.back ().pscore_)
 235     breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_));
 236   else
 237     breaks_.push_back (Break_position (all_.size () - 1));
 238 }
 239
 240 vector<vsize>
 241 Page_breaking::find_page_break_indices (Paper_score *pscore)
 242 {
 243   vector<Grob*> all = pscore->root_system ()->columns ();
 244   vector<vsize> ret;
 245
 246   /* we don't include breaks at the beginning and end */
 247   for (vsize i = 0; i < all.size () - 1; i++)
 248     if (scm_is_symbol (all[i]->get_property ("page-turn-permission")))
 249       ret.push_back(i);
 250
 251   return ret;
 252 }
 253
 254 void
 255 Page_breaking::calc_system_count_bounds (vsize start, vsize end,
 256                                             vector<vsize> *min,
 257                                             vector<vsize> *max)
 258 {
 259   for (vsize i = next_system (start); i <= breaks_[end].sys_; i++)
 260     {
 261       if (all_[i].pscore_)
 262         {
 263           min->push_back (get_min_systems (i, start, end));
 264           max->push_back (get_max_systems (i, start, end));
 265         }
 266       else
 267         {
 268           min->push_back (1);
 269           max->push_back (1);
 270         }
 271     }
 272 }
 273
 274 /* calculate all possible ways of dividing system_count between the System_specs */
 275 void
 276 Page_breaking::divide_systems (vsize system_count,
 277                                vector<vsize> const &min_sys,
 278                                vector<vsize> const &max_sys,
 279                                vector<vector<vsize> > *result,
 280                                vector<vsize> *cur_division)
 281 {
 282   vsize my_index = cur_division->size ();
 283   vsize others_min = 0;
 284   vsize others_max = 0;
 285
 286   for (vsize i = my_index + 1; i < min_sys.size (); i++)
 287     {
 288       others_min += min_sys[i];
 289       others_max += max_sys[i];
 290     }
 291   others_max = min (others_max, system_count);
 292   vsize real_min = max (min_sys[my_index], system_count - others_max);
 293   vsize real_max = min (max_sys[my_index], system_count - others_min);
 294
 295   if (real_min > real_max || real_min <= 0)
 296     {
 297       /* this should never happen within a recursive call. If it happens
 298          at all, it means that we were called with an unsolvable problem
 299          and we should return an empty result */
 300       assert (my_index == 0);
 301       return;
 302     }
 303
 304   for (vsize i = real_min; i <= real_max; i++)
 305     {
 306       cur_division->push_back (i);
 307       if (my_index == min_sys.size () - 1)
 308         result->push_back (*cur_division);
 309       else
 310         divide_systems (system_count - i, min_sys, max_sys, result, cur_division);
 311       cur_division->pop_back ();
 312     }
 313 }
 314