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 Page_turn_page_breaking::Page_turn_page_breaking (Paper_book *pb)
  22   : Page_breaking (pb, true)
  23 {
  24 }
  25
  26 Page_turn_page_breaking::~Page_turn_page_breaking ()
  27 {
  28 }
  29
  30 Real
  31 Page_turn_page_breaking::calc_demerits (const Break_node &me)
  32 {
  33   Real prev_f = 0;
  34   Real prev_dem = 0;
  35   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 1);
  36   if (me.prev_ != VPOS)
  37     {
  38       prev_f = state_[me.prev_].force_;
  39       prev_dem = state_[me.prev_].demerits_;
  40     }
  41
  42   Real dem = me.force_ * me.force_ * page_weighting
  43            + me.line_force_ * me.line_force_
  44            + fabs (me.force_ - prev_f);
  45   if (isinf (me.line_force_) || isinf (me.force_))
  46     dem = infinity_f;
  47
  48   return dem + prev_dem + me.penalty_ + me.line_penalty_;
  49 }
  50
  51 Page_turn_page_breaking::Break_node
  52 Page_turn_page_breaking::put_systems_on_pages (vsize start,
  53                                                vsize end,
  54                                                vector<Line_details> const &lines,
  55                                                vector<vsize> const &div,
  56                                                int page_number)
  57 {
  58   bool last = end == breaks_.size () - 1;
  59   Real page_h = page_height (1, false); // FIXME
  60   SCM force_sym = last ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
  61   Real blank_force = robust_scm2double (book_->paper_->lookup_variable (force_sym), 0);
  62   Spacing_result result = space_systems_on_min_pages (lines, page_h, blank_force);
  63
  64   Break_node ret;
  65   ret.prev_ = start - 1;
  66   ret.break_pos_ = end;
  67   ret.first_page_number_ = page_number;
  68   ret.page_count_ = result.force_.size ();
  69   ret.force_ = 0;
  70   for (vsize i = 0; i < result.force_.size (); i++)
  71     ret.force_ += fabs (result.force_[i]);
  72
  73   ret.penalty_ = result.penalty_;
  74   ret.div_ = div;
  75   ret.system_count_ = result.systems_per_page_;
  76
  77   ret.too_many_lines_ = true;
  78   ret.line_force_ = 0;
  79   ret.line_penalty_ = 0;
  80   for (vsize i = 0; i < lines.size (); i++)
  81     {
  82       ret.line_force_ += fabs (lines[i].force_);
  83       ret.line_penalty_ += lines[i].break_penalty_;
  84       if (lines[i].force_ < 0)
  85         ret.too_many_lines_ = false;
  86     }
  87   return ret;
  88 }
  89
  90 void
  91 Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint)
  92 {
  93   vsize end = ending_breakpoint + 1;
  94   Break_node best;
  95   Break_node cur;
  96   Break_node this_start_best;
  97   vsize prev_best_system_count = 0;
  98
  99   for (vsize start = end; start--;)
 100     {
 101       if (start > 0 && best.demerits_ < state_[start-1].demerits_)
 102         continue;
 103
 104       int p_num = 1;
 105       if (start > 0)
 106         {
 107           /* if the last node has an odd number of pages and is not the first page,
 108              add a blank page */
 109           int p_count = state_[start-1].page_count_;
 110           int f_p_num = state_[start-1].first_page_number_;
 111           p_num = f_p_num + p_count + ((f_p_num > 1) ? p_count % 2 : 0);
 112         }
 113
 114       vector<vsize> min_systems;
 115       vector<vsize> max_systems;
 116       vsize min_system_count = 0;
 117       vsize max_system_count = 0;
 118       this_start_best.demerits_ = infinity_f;
 119       calc_system_count_bounds (start, end, &min_systems, &max_systems);
 120
 121       /* heuristic: we've prepended some music, only the first system is allowed
 122          to get more lines */
 123       if (this_start_best.page_count_ == 2 && this_start_best.div_.size ())
 124         {
 125           vsize ds = max_systems.size () - this_start_best.div_.size ();
 126           for (vsize i = ds + 1; i < max_systems.size (); i++)
 127             {
 128               assert (this_start_best.div_[i - ds] <= max_systems[i]);
 129               max_systems[i] = this_start_best.div_[i - ds];
 130             }
 131         }
 132
 133       for (vsize i = 0; i < min_systems.size (); i++)
 134         {
 135           min_system_count += min_systems[i];
 136           max_system_count += max_systems[i];
 137         }
 138
 139       bool ok_page = true;
 140
 141       /* heuristic: we've just added a breakpoint, we'll need at least as
 142          many systems as before */
 143       min_system_count = max (min_system_count, prev_best_system_count);
 144       for (vsize sys_count = min_system_count; sys_count <= max_system_count && ok_page; sys_count++)
 145         {
 146           vector<vector<vsize> > div;
 147           vector<vsize> blank;
 148           bool found = false;
 149           divide_systems (sys_count, min_systems, max_systems, &div, &blank);
 150
 151           for (vsize d = 0; d < div.size (); d++)
 152             {
 153               vector<Line_details> line = get_line_details (start, end, div[d]);
 154
 155               cur = put_systems_on_pages (start, end, line, div[d], p_num);
 156
 157               if (cur.page_count_ > 2 &&
 158                   (start < end - 1 || (!isinf (this_start_best.demerits_)
 159                                        && cur.page_count_ + cur.page_count_ % 2
 160                                           > this_start_best.page_count_ + this_start_best.page_count_ % 2)))
 161                 {
 162                   ok_page = false;
 163                   break;
 164                 }
 165               cur.demerits_ = calc_demerits (cur);
 166
 167               if (cur.demerits_ < this_start_best.demerits_)
 168                 {
 169                   found = true;
 170                   this_start_best = cur;
 171                   prev_best_system_count = sys_count;
 172                 }
 173             }
 174           if (!found && this_start_best.too_many_lines_)
 175             break;
 176         }
 177       if (isinf (this_start_best.demerits_))
 178         {
 179           assert (!isinf (best.demerits_) && start < end - 1);
 180           break;
 181         }
 182       if (this_start_best.demerits_ < best.demerits_)
 183         best = this_start_best;
 184     }
 185   state_.push_back (best);
 186 }
 187
 188 SCM
 189 Page_turn_page_breaking::solve ()
 190 {
 191   state_.clear ();
 192   message (_f ("Calculating page and line breaks (%d possible page breaks)...",
 193                (int)breaks_.size () - 1) + " ");
 194   for (vsize i = 0; i < breaks_.size () - 1; i++)
 195     {
 196       calc_subproblem (i);
 197       progress_indication (string ("[") + to_string (i + 1) + "]");
 198     }
 199   progress_indication ("\n");
 200
 201   vector<Break_node> breaking;
 202   int i = state_.size () - 1;
 203   while (i >= 0)
 204     {
 205       breaking.push_back (state_[i]);
 206       i = state_[i].prev_;
 207     }
 208   reverse (breaking);
 209
 210   message (_ ("Drawing systems..."));
 211   SCM systems = make_lines (&breaking);
 212   return make_pages (breaking, systems);
 213 }
 214
 215 /* do the line breaking in all the scores and return a big list of systems */
 216 SCM
 217 Page_turn_page_breaking::make_lines (vector<Break_node> *psoln)
 218 {
 219   vector<Break_node> &soln = *psoln;
 220   for (vsize n = 0; n < soln.size (); n++)
 221     {
 222       vsize start = n > 0 ? soln[n-1].break_pos_ : 0;
 223       vsize end = soln[n].break_pos_;
 224
 225       /* break each score into pieces */
 226       for (vsize i = next_system (start); i <= breaks_[end].sys_; i++)
 227         {
 228           vsize d = i - next_system (start);
 229           if (all_[i].pscore_)
 230             {
 231               vector<Column_x_positions> line_brk;
 232
 233               line_brk = get_line_breaks (i, soln[n].div_[d], start, end);
 234               all_[i].pscore_->root_system ()->break_into_pieces (line_brk);
 235               assert (line_brk.size () == soln[n].div_[d]);
 236             }
 237         }
 238     }
 239   SCM ret = SCM_EOL;
 240   SCM *tail = &ret;
 241   for (vsize i = 0; i < all_.size (); i++)
 242     {
 243       if (all_[i].pscore_)
 244         for (SCM s = scm_vector_to_list (all_[i].pscore_->root_system ()->get_paper_systems ());
 245               scm_is_pair (s); s = scm_cdr (s))
 246           {
 247             *tail = scm_cons (scm_car (s), SCM_EOL);
 248             tail = SCM_CDRLOC (*tail);
 249           }
 250       else
 251         {
 252           *tail = scm_cons (all_[i].prob_->self_scm (), SCM_EOL);
 253           all_[i].prob_->unprotect ();
 254           tail = SCM_CDRLOC (*tail);
 255         }
 256     }
 257   return ret;
 258 }
 259
 260 SCM
 261 Page_turn_page_breaking::make_pages (vector<Break_node> const &soln, SCM systems)
 262 {
 263   vector<vsize> lines_per_page;
 264   for (vsize i = 0; i < soln.size (); i++)
 265     {
 266       for (vsize j = 0; j < soln[i].page_count_; j++)
 267         lines_per_page.push_back (soln[i].system_count_[j]);
 268
 269       if (i > 0 && i < soln.size () - 1 && soln[i].page_count_ % 2)
 270         /* add a blank page */
 271         lines_per_page.push_back (0);
 272     }
 273   return Page_breaking::make_pages (lines_per_page, systems);
 274 }