lily/page-turn-page-breaking.cc

   1 /*
   2   page-turn-page-breaking.cc -- implement Page_turn_page_breaking
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 2006--2007 Joe Neeman <joeneeman@gmail.com>
   7 */
   8
   9 #include "page-turn-page-breaking.hh"
  10
  11 #include "international.hh"
  12 #include "item.hh"
  13 #include "output-def.hh"
  14 #include "page-spacing.hh"
  15 #include "paper-book.hh"
  16 #include "paper-score.hh"
  17 #include "paper-system.hh"
  18 #include "system.hh"
  19 #include "warn.hh"
  20
  21 static bool
  22 is_break (Grob *g)
  23 {
  24   return scm_is_symbol (g->get_property ("page-turn-permission"));
  25 }
  26
  27 Page_turn_page_breaking::Page_turn_page_breaking (Paper_book *pb)
  28   : Page_breaking (pb, is_break)
  29 {
  30 }
  31
  32 Page_turn_page_breaking::~Page_turn_page_breaking ()
  33 {
  34 }
  35
  36 Page_turn_page_breaking::Break_node
  37 Page_turn_page_breaking::put_systems_on_pages (vsize start,
  38                                                vsize end,
  39                                                vector<Line_details> const &lines,
  40                                                Line_division const &div,
  41                                                int page_number)
  42 {
  43   bool last = end == breaks_.size () - 1;
  44   bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
  45   bool ragged_last = last && to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
  46   Real page_h = page_height (1, false); // FIXME
  47   SCM force_sym = last ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
  48   Real blank_force = robust_scm2double (book_->paper_->lookup_variable (force_sym), 0);
  49   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
  50   int min_p_count = min_page_count (lines, page_h, ragged_all, ragged_last);
  51   bool auto_first = to_boolean (book_->paper_->c_variable ("auto-first-page-number"));
  52
  53   /* If [START, END] does not contain an intermediate
  54      breakpoint, we may need to consider solutions that result in a bad turn.
  55      In this case, we won't abort if the min_page_count is too big */
  56   if (start < end - 1 && min_p_count + (auto_first ? 0 : (page_number % 2)) > 2)
  57     return Break_node ();
  58
  59   /* if PAGE-NUMBER is odd, we are starting on a right hand page. That is, we
  60      have the options
  61      PAGE-NUMBER odd:
  62        - even number of pages + a blank page
  63        - odd number of pages
  64      PAGE-NUMBER even:
  65        - odd number of pages + a blank page
  66        - even number of pages
  67
  68      No matter which case PAGE-NUMBER falls into, we take the second choice if
  69      min_p_count has that evenness. (For example, if PAGE-NUMBER is even and
  70      min_p_count is even, we don't even consider the blank page option). */
  71
  72   Spacing_result result;
  73   if (start == 0 && auto_first)
  74     {
  75       if (min_p_count % 2)
  76         result = space_systems_on_n_or_one_more_pages (lines, min_p_count, page_h, 0, ragged_all, ragged_last);
  77       else
  78         result = space_systems_on_n_pages (lines, min_p_count, page_h, ragged_all, ragged_last);
  79     }
  80   else if (page_number % 2 == min_p_count % 2)
  81     result = space_systems_on_n_pages (lines, min_p_count, page_h, ragged_all, ragged_last);
  82   else
  83     result = space_systems_on_n_or_one_more_pages (lines, min_p_count, page_h, blank_force, ragged_all, ragged_last);
  84
  85   Break_node ret;
  86   ret.prev_ = start - 1;
  87   ret.break_pos_ = end;
  88   ret.page_count_ = result.force_.size ();
  89   ret.first_page_number_ = page_number;
  90   if (auto_first && start == 0)
  91     ret.first_page_number_ += 1 - (ret.page_count_ % 2);
  92
  93   ret.div_ = div;
  94   ret.system_count_ = result.systems_per_page_;
  95
  96   ret.too_many_lines_ = true;
  97   ret.demerits_ = result.penalty_;
  98   if (start > 0)
  99     ret.demerits_ += state_[start-1].demerits_;
 100   for (vsize i = 0; i < lines.size (); i++)
 101     {
 102       ret.demerits_ += lines[i].force_ * lines[i].force_;
 103       ret.demerits_ += lines[i].break_penalty_;
 104       if (lines[i].force_ < 0)
 105         ret.too_many_lines_ = false;
 106     }
 107   for (vsize i = 0; i < result.force_.size (); i++)
 108     ret.demerits_ += result.force_[i] * result.force_[i] * page_weighting;
 109   return ret;
 110 }
 111
 112 /* "final page" meaning the number of the final right-hand page,
 113    which always has an odd page number */
 114 vsize
 115 Page_turn_page_breaking::final_page_num (Break_node const &b)
 116 {
 117   vsize end = b.first_page_number_ + b.page_count_;
 118   return end - 1 + (end % 2);
 119 }
 120
 121 extern bool debug_page_breaking_scoring;
 122
 123 void
 124 Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint)
 125 {
 126   vsize end = ending_breakpoint + 1;
 127   Break_node best;
 128   Break_node cur;
 129   Break_node this_start_best;
 130   vsize prev_best_system_count = 0;
 131
 132   for (vsize start = end; start--;)
 133     {
 134       if (start < end-1
 135           && breakpoint_property (start+1, "page-turn-permission") == ly_symbol2scm ("force"))
 136         break;
 137
 138       if (start > 0 && best.demerits_ < state_[start-1].demerits_)
 139         continue;
 140
 141       int p_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
 142       if (start > 0)
 143         {
 144           /* except possibly for the first page, enforce the fact that first_page_number_
 145              should always be even (left hand page).
 146              TODO: are there different conventions in right-to-left languages?
 147           */
 148           p_num = state_[start-1].first_page_number_ + state_[start-1].page_count_;
 149           p_num += p_num % 2;
 150         }
 151
 152       Line_division min_division;
 153       Line_division max_division;
 154
 155       vsize min_sys_count = min_system_count (start, end);
 156       vsize max_sys_count = max_system_count (start, end);
 157       this_start_best.demerits_ = infinity_f;
 158
 159       bool ok_page = true;
 160
 161       if (debug_page_breaking_scoring)
 162         message (_f ("page-turn-page-breaking: breaking from %d to %d", (int) start, (int) end));
 163
 164       /* heuristic: we've just added a breakpoint, we'll need at least as
 165          many systems as before */
 166       min_sys_count = max (min_sys_count, prev_best_system_count);
 167       for (vsize sys_count = min_sys_count; sys_count <= max_sys_count && ok_page; sys_count++)
 168         {
 169           vector<Line_division> div = line_divisions (start, end, sys_count, min_division, max_division);
 170           bool found = false;
 171
 172           for (vsize d = 0; d < div.size (); d++)
 173             {
 174               vector<Line_details> line = line_details (start, end, div[d]);
 175
 176               cur = put_systems_on_pages (start, end, line, div[d], p_num);
 177
 178               if (isinf (cur.demerits_)
 179                   || (cur.page_count_  + (p_num % 2) > 2
 180                       && (!isinf (this_start_best.demerits_))
 181                       && final_page_num (cur) > final_page_num (this_start_best)))
 182                 {
 183                   ok_page = false;
 184                   break;
 185                 }
 186
 187               if (cur.demerits_ < this_start_best.demerits_)
 188                 {
 189                   if (debug_page_breaking_scoring)
 190                     print_break_node (cur);
 191
 192                   found = true;
 193                   this_start_best = cur;
 194                   prev_best_system_count = sys_count;
 195
 196                   /* heuristic: if we increase the number of systems, we can bound the
 197                      division from below by our current best division */
 198                   min_division = div[d];
 199                 }
 200             }
 201           if (!found && this_start_best.too_many_lines_)
 202             break;
 203         }
 204       if (isinf (this_start_best.demerits_))
 205         {
 206           assert (!isinf (best.demerits_) && start < end - 1);
 207           break;
 208         }
 209
 210       if (start == 0 && end == 1
 211           && this_start_best.first_page_number_ == 1
 212           && this_start_best.page_count_ > 1)
 213         warning (_ ("cannot fit the first page turn onto a single page.  "
 214                     "Consider setting first-page-number to an even number."));
 215
 216       if (this_start_best.demerits_ < best.demerits_)
 217         best = this_start_best;
 218     }
 219   state_.push_back (best);
 220 }
 221
 222 SCM
 223 Page_turn_page_breaking::solve ()
 224 {
 225   state_.clear ();
 226   message (_f ("Calculating page and line breaks (%d possible page breaks)...",
 227                (int)breaks_.size () - 1) + " ");
 228   for (vsize i = 0; i + 1 < breaks_.size (); i++)
 229     {
 230       calc_subproblem (i);
 231       progress_indication (string ("[") + to_string (i + 1) + "]");
 232     }
 233   progress_indication ("\n");
 234
 235   vector<Break_node> breaking;
 236   int i = state_.size () - 1;
 237   while (i >= 0)
 238     {
 239       breaking.push_back (state_[i]);
 240       i = state_[i].prev_;
 241     }
 242   reverse (breaking);
 243
 244   message (_ ("Drawing systems..."));
 245   SCM systems = make_lines (&breaking);
 246   return make_pages (breaking, systems);
 247 }
 248
 249 /* do the line breaking in all the scores and return a big list of systems */
 250 SCM
 251 Page_turn_page_breaking::make_lines (vector<Break_node> *psoln)
 252 {
 253   vector<Break_node> &soln = *psoln;
 254   for (vsize n = 0; n < soln.size (); n++)
 255     {
 256       vsize start = n > 0 ? soln[n-1].break_pos_ : 0;
 257       vsize end = soln[n].break_pos_;
 258
 259       break_into_pieces (start, end, soln[n].div_);
 260     }
 261
 262   return systems ();
 263 }
 264
 265 SCM
 266 Page_turn_page_breaking::make_pages (vector<Break_node> const &soln, SCM systems)
 267 {
 268   vector<vsize> lines_per_page;
 269   for (vsize i = 0; i < soln.size (); i++)
 270     {
 271       for (vsize j = 0; j < soln[i].page_count_; j++)
 272         lines_per_page.push_back (soln[i].system_count_[j]);
 273
 274       if (i + 1 < soln.size () && (soln[i].first_page_number_ + soln[i].page_count_) % 2)
 275         /* add a blank page */
 276         lines_per_page.push_back (0);
 277     }
 278
 279   /* this should only actually modify first-page-number if
 280      auto-first-page-number was true. */
 281   book_->paper_->set_variable (ly_symbol2scm ("first-page-number"),
 282                                scm_from_int (soln[0].first_page_number_));
 283   return Page_breaking::make_pages (lines_per_page, systems);
 284 }
 285
 286 void
 287 Page_turn_page_breaking::print_break_node (Break_node const &node)
 288 {
 289   int system_count = 0;
 290   for (vsize i = 0; i < node.system_count_.size (); i++)
 291     system_count += node.system_count_[i];
 292
 293   message (_f ("break starting at page %d", (int) node.first_page_number_));
 294   message (_f ("\tdemerits: %f", node.demerits_));
 295   message (_f ("\tsystem count: %d", system_count));
 296   message (_f ("\tpage count: %d", (int) node.page_count_));
 297   message (_f ("\tprevious break: %d", (int) node.prev_));
 298 }