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 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 Real
  37 Page_turn_page_breaking::calc_demerits (const Break_node &me)
  38 {
  39   Real prev_f = 0;
  40   Real prev_dem = 0;
  41   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 1);
  42   if (me.prev_ != VPOS)
  43     {
  44       prev_f = state_[me.prev_].force_;
  45       prev_dem = state_[me.prev_].demerits_;
  46     }
  47
  48   Real dem = me.force_ * me.force_ * page_weighting
  49            + me.line_force_ * me.line_force_
  50            + fabs (me.force_ - prev_f);
  51   if (isinf (me.line_force_) || isinf (me.force_))
  52     dem = infinity_f;
  53
  54   return dem + prev_dem + me.penalty_ + me.line_penalty_;
  55 }
  56
  57 Page_turn_page_breaking::Break_node
  58 Page_turn_page_breaking::put_systems_on_pages (vsize start,
  59                                                vsize end,
  60                                                vector<Line_details> const &lines,
  61                                                Line_division const &div,
  62                                                int page_number)
  63 {
  64   bool last = end == breaks_.size () - 1;
  65   bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
  66   bool ragged_last = last && to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
  67   Real page_h = page_height (1, false); // FIXME
  68   SCM force_sym = last ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
  69   Real blank_force = robust_scm2double (book_->paper_->lookup_variable (force_sym), 0);
  70   Spacing_result result = space_systems_on_min_pages (lines, page_h, blank_force, ragged_all, ragged_last);
  71
  72   Break_node ret;
  73   ret.prev_ = start - 1;
  74   ret.break_pos_ = end;
  75   ret.first_page_number_ = page_number;
  76   ret.page_count_ = result.force_.size ();
  77   ret.force_ = 0;
  78   for (vsize i = 0; i < result.force_.size (); i++)
  79     ret.force_ += fabs (result.force_[i]);
  80
  81   ret.penalty_ = result.penalty_;
  82   ret.div_ = div;
  83   ret.system_count_ = result.systems_per_page_;
  84
  85   ret.too_many_lines_ = true;
  86   ret.line_force_ = 0;
  87   ret.line_penalty_ = 0;
  88   for (vsize i = 0; i < lines.size (); i++)
  89     {
  90       ret.line_force_ += fabs (lines[i].force_);
  91       ret.line_penalty_ += lines[i].break_penalty_;
  92       if (lines[i].force_ < 0)
  93         ret.too_many_lines_ = false;
  94     }
  95   return ret;
  96 }
  97
  98 void
  99 Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint)
 100 {
 101   vsize end = ending_breakpoint + 1;
 102   Break_node best;
 103   Break_node cur;
 104   Break_node this_start_best;
 105   vsize prev_best_system_count = 0;
 106
 107   for (vsize start = end; start--;)
 108     {
 109       if (start < end-1
 110           && breakpoint_property (start+1, "page-turn-permission") == ly_symbol2scm ("force"))
 111         break;
 112
 113       if (start > 0 && best.demerits_ < state_[start-1].demerits_)
 114         continue;
 115
 116       int p_num = 1;
 117       if (start > 0)
 118         {
 119           /* if the last node has an odd number of pages and is not the first page,
 120              add a blank page */
 121           int p_count = state_[start-1].page_count_;
 122           int f_p_num = state_[start-1].first_page_number_;
 123           p_num = f_p_num + p_count + ((f_p_num > 1) ? p_count % 2 : 0);
 124         }
 125
 126       Line_division min_division;
 127       Line_division max_division;
 128
 129       vsize min_sys_count = min_system_count (start, end);
 130       vsize max_sys_count = max_system_count (start, end);
 131       this_start_best.demerits_ = infinity_f;
 132
 133       bool ok_page = true;
 134
 135       /* heuristic: we've just added a breakpoint, we'll need at least as
 136          many systems as before */
 137       min_sys_count = max (min_sys_count, prev_best_system_count);
 138       for (vsize sys_count = min_sys_count; sys_count <= max_sys_count && ok_page; sys_count++)
 139         {
 140           vector<Line_division> div = line_divisions (start, end, sys_count, min_division, max_division);
 141           bool found = false;
 142
 143           for (vsize d = 0; d < div.size (); d++)
 144             {
 145               vector<Line_details> line = line_details (start, end, div[d]);
 146
 147               cur = put_systems_on_pages (start, end, line, div[d], p_num);
 148
 149               if (cur.page_count_ > 2 &&
 150                   (start < end - 1 || (!isinf (this_start_best.demerits_)
 151                                        && cur.page_count_ + cur.page_count_ % 2
 152                                           > this_start_best.page_count_ + this_start_best.page_count_ % 2)))
 153                 {
 154                   ok_page = false;
 155                   break;
 156                 }
 157               cur.demerits_ = calc_demerits (cur);
 158
 159               if (cur.demerits_ < this_start_best.demerits_)
 160                 {
 161                   found = true;
 162                   this_start_best = cur;
 163                   prev_best_system_count = sys_count;
 164
 165                   /* heuristic: if we increase the number of systems, we can bound the
 166                      division from below by our current best division */
 167                   min_division = div[d];
 168                 }
 169             }
 170           if (!found && this_start_best.too_many_lines_)
 171             break;
 172         }
 173       if (isinf (this_start_best.demerits_))
 174         {
 175           assert (!isinf (best.demerits_) && start < end - 1);
 176           break;
 177         }
 178       if (this_start_best.demerits_ < best.demerits_)
 179         best = this_start_best;
 180     }
 181   state_.push_back (best);
 182 }
 183
 184 SCM
 185 Page_turn_page_breaking::solve ()
 186 {
 187   state_.clear ();
 188   message (_f ("Calculating page and line breaks (%d possible page breaks)...",
 189                (int)breaks_.size () - 1) + " ");
 190   for (vsize i = 0; i < breaks_.size () - 1; i++)
 191     {
 192       calc_subproblem (i);
 193       progress_indication (string ("[") + to_string (i + 1) + "]");
 194     }
 195   progress_indication ("\n");
 196
 197   vector<Break_node> breaking;
 198   int i = state_.size () - 1;
 199   while (i >= 0)
 200     {
 201       breaking.push_back (state_[i]);
 202       i = state_[i].prev_;
 203     }
 204   reverse (breaking);
 205
 206   message (_ ("Drawing systems..."));
 207   SCM systems = make_lines (&breaking);
 208   return make_pages (breaking, systems);
 209 }
 210
 211 /* do the line breaking in all the scores and return a big list of systems */
 212 SCM
 213 Page_turn_page_breaking::make_lines (vector<Break_node> *psoln)
 214 {
 215   vector<Break_node> &soln = *psoln;
 216   for (vsize n = 0; n < soln.size (); n++)
 217     {
 218       vsize start = n > 0 ? soln[n-1].break_pos_ : 0;
 219       vsize end = soln[n].break_pos_;
 220
 221       break_into_pieces (start, end, soln[n].div_);
 222     }
 223
 224   return systems ();
 225 }
 226
 227 SCM
 228 Page_turn_page_breaking::make_pages (vector<Break_node> const &soln, SCM systems)
 229 {
 230   vector<vsize> lines_per_page;
 231   for (vsize i = 0; i < soln.size (); i++)
 232     {
 233       for (vsize j = 0; j < soln[i].page_count_; j++)
 234         lines_per_page.push_back (soln[i].system_count_[j]);
 235
 236       if (i > 0 && i < soln.size () - 1 && soln[i].page_count_ % 2)
 237         /* add a blank page */
 238         lines_per_page.push_back (0);
 239     }
 240   return Page_breaking::make_pages (lines_per_page, systems);
 241 }