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--2008 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                                                vsize configuration,
  40                                                vsize page_number)
  41 {
  42   vsize min_p_count = min_page_count (configuration, page_number);
  43   bool auto_first = to_boolean (book_->paper_->c_variable ("auto-first-page-number"));
  44
  45   /* If [START, END] does not contain an intermediate
  46      breakpoint, we may need to consider solutions that result in a bad turn.
  47      In this case, we won't abort if the min_page_count is too big */
  48   if (start < end - 1 && min_p_count + (auto_first ? 0 : (page_number % 2)) > 2)
  49     return Break_node ();
  50
  51   /* if PAGE-NUMBER is odd, we are starting on a right hand page. That is, we
  52      have the options
  53      PAGE-NUMBER odd:
  54        - even number of pages + a blank page
  55        - odd number of pages
  56      PAGE-NUMBER even:
  57        - odd number of pages + a blank page
  58        - even number of pages
  59
  60      No matter which case PAGE-NUMBER falls into, we take the second choice if
  61      min_p_count has that evenness. (For example, if PAGE-NUMBER is even and
  62      min_p_count is even, we don't even consider the blank page option). */
  63
  64   Page_spacing_result result;
  65   if (start == 0 && auto_first)
  66     {
  67       if (min_p_count % 2)
  68         result = space_systems_on_n_or_one_more_pages (configuration, min_p_count, page_number);
  69       else
  70         result = space_systems_on_n_pages (configuration, min_p_count, page_number);
  71     }
  72   else if (page_number % 2 == min_p_count % 2)
  73     result = space_systems_on_n_pages (configuration, min_p_count, page_number);
  74   else
  75     result = space_systems_on_n_or_one_more_pages (configuration, min_p_count, page_number);
  76
  77   Break_node ret;
  78   ret.prev_ = start - 1;
  79   ret.break_pos_ = end;
  80   ret.page_count_ = result.force_.size ();
  81   ret.first_page_number_ = page_number;
  82   if (auto_first && start == 0)
  83     ret.first_page_number_ += 1 - (ret.page_count_ % 2);
  84
  85   ret.div_ = current_configuration (configuration);
  86   ret.system_count_ = result.systems_per_page_;
  87
  88   ret.too_many_lines_ = all_lines_stretched (configuration);
  89   ret.demerits_ = result.demerits_;
  90   if (start > 0)
  91     ret.demerits_ += state_[start-1].demerits_;
  92
  93   return ret;
  94 }
  95
  96 /* The number of pages taken up by a Break_node, including
  97    the blank page if there is one */
  98 vsize
  99 Page_turn_page_breaking::total_page_count (Break_node const &b)
 100 {
 101   vsize end = b.first_page_number_ + b.page_count_;
 102   return end - 1 + (end % 2) - b.first_page_number_;
 103 }
 104
 105 extern bool debug_page_breaking_scoring;
 106
 107 void
 108 Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint)
 109 {
 110   vsize end = ending_breakpoint + 1;
 111   Break_node best;
 112   Break_node cur;
 113   Break_node this_start_best;
 114   vsize prev_best_system_count = 0;
 115
 116   for (vsize start = end; start--;)
 117     {
 118       if (start < end-1
 119           && breakpoint_property (start+1, "page-turn-permission") == ly_symbol2scm ("force"))
 120         break;
 121
 122       if (start > 0 && best.demerits_ < state_[start-1].demerits_)
 123         continue;
 124
 125       int p_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
 126       if (start > 0)
 127         {
 128           /* except possibly for the first page, enforce the fact that first_page_number_
 129              should always be even (left hand page).
 130              TODO: are there different conventions in right-to-left languages?
 131           */
 132           p_num = state_[start-1].first_page_number_ + state_[start-1].page_count_;
 133           p_num += p_num % 2;
 134         }
 135
 136       Line_division min_division;
 137       Line_division max_division;
 138
 139       vsize min_sys_count = min_system_count (start, end);
 140       vsize max_sys_count = max_system_count (start, end);
 141       this_start_best.demerits_ = infinity_f;
 142
 143       bool ok_page = true;
 144
 145       if (debug_page_breaking_scoring)
 146         message (_f ("page-turn-page-breaking: breaking from %d to %d", (int) start, (int) end));
 147
 148       /* heuristic: we've just added a breakpoint, we'll need at least as
 149          many systems as before */
 150       min_sys_count = max (min_sys_count, prev_best_system_count);
 151       for (vsize sys_count = min_sys_count; sys_count <= max_sys_count && ok_page; sys_count++)
 152         {
 153           set_current_breakpoints (start, end, sys_count, min_division, max_division);
 154           bool found = false;
 155
 156           for (vsize i = 0; i < current_configuration_count (); i++)
 157             {
 158               cur = put_systems_on_pages (start, end, i, p_num);
 159
 160               if (isinf (cur.demerits_)
 161                   || (cur.page_count_  + (p_num % 2) > 2
 162                       && (!isinf (this_start_best.demerits_))
 163                       && total_page_count (cur) > total_page_count (this_start_best)))
 164                 {
 165                   ok_page = false;
 166                   break;
 167                 }
 168
 169               if (cur.demerits_ < this_start_best.demerits_)
 170                 {
 171                   if (debug_page_breaking_scoring)
 172                     print_break_node (cur);
 173
 174                   found = true;
 175                   this_start_best = cur;
 176                   prev_best_system_count = sys_count;
 177
 178                   /* heuristic: if we increase the number of systems, we can bound the
 179                      division from below by our current best division */
 180                   min_division = current_configuration (i);
 181                 }
 182             }
 183           if (!found && this_start_best.too_many_lines_)
 184             break;
 185         }
 186       if (isinf (this_start_best.demerits_))
 187         {
 188           assert (!isinf (best.demerits_) && start < end - 1);
 189           break;
 190         }
 191
 192       if (start == 0 && end == 1
 193           && this_start_best.first_page_number_ == 1
 194           && this_start_best.page_count_ > 1)
 195         warning (_ ("cannot fit the first page turn onto a single page.  "
 196                     "Consider setting first-page-number to an even number."));
 197
 198       if (this_start_best.demerits_ < best.demerits_)
 199         best = this_start_best;
 200     }
 201   state_.push_back (best);
 202 }
 203
 204 SCM
 205 Page_turn_page_breaking::solve ()
 206 {
 207   state_.clear ();
 208   message (_f ("Calculating page and line breaks (%d possible page breaks)...",
 209                (int) last_break_position ()));
 210   for (vsize i = 0; i < last_break_position (); i++)
 211     {
 212       calc_subproblem (i);
 213       progress_indication (string ("[") + to_string (i + 1) + "]");
 214     }
 215   progress_indication ("\n");
 216
 217   vector<Break_node> breaking;
 218   int i = state_.size () - 1;
 219   while (i >= 0)
 220     {
 221       breaking.push_back (state_[i]);
 222       i = state_[i].prev_;
 223     }
 224   reverse (breaking);
 225
 226   message (_ ("Drawing systems..."));
 227   SCM systems = make_lines (&breaking);
 228   return make_pages (breaking, systems);
 229 }
 230
 231 /* do the line breaking in all the scores and return a big list of systems */
 232 SCM
 233 Page_turn_page_breaking::make_lines (vector<Break_node> *psoln)
 234 {
 235   vector<Break_node> &soln = *psoln;
 236   for (vsize n = 0; n < soln.size (); n++)
 237     {
 238       vsize start = n > 0 ? soln[n-1].break_pos_ : 0;
 239       vsize end = soln[n].break_pos_;
 240
 241       break_into_pieces (start, end, soln[n].div_);
 242     }
 243
 244   return systems ();
 245 }
 246
 247 SCM
 248 Page_turn_page_breaking::make_pages (vector<Break_node> const &soln, SCM systems)
 249 {
 250   vector<vsize> lines_per_page;
 251   for (vsize i = 0; i < soln.size (); i++)
 252     {
 253       for (vsize j = 0; j < soln[i].page_count_; j++)
 254         lines_per_page.push_back (soln[i].system_count_[j]);
 255
 256       if (i + 1 < soln.size () && (soln[i].first_page_number_ + soln[i].page_count_) % 2)
 257         /* add a blank page */
 258         lines_per_page.push_back (0);
 259     }
 260
 261   /* this should only actually modify first-page-number if
 262      auto-first-page-number was true. */
 263   book_->paper_->set_variable (ly_symbol2scm ("first-page-number"),
 264                                scm_from_int (soln[0].first_page_number_));
 265   return Page_breaking::make_pages (lines_per_page, systems);
 266 }
 267
 268 void
 269 Page_turn_page_breaking::print_break_node (Break_node const &node)
 270 {
 271   int system_count = 0;
 272   for (vsize i = 0; i < node.system_count_.size (); i++)
 273     system_count += node.system_count_[i];
 274
 275   message (_f ("break starting at page %d", (int) node.first_page_number_));
 276   message (_f ("\tdemerits: %f", node.demerits_));
 277   message (_f ("\tsystem count: %d", system_count));
 278   message (_f ("\tpage count: %d", (int) node.page_count_));
 279   message (_f ("\tprevious break: %d", (int) node.prev_));
 280 }