lily/page-spacing.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2015 Joe Neeman <joeneeman@gmail.com>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "page-spacing.hh"
  21
  22 #include "international.hh"
  23 #include "matrix.hh"
  24 #include "page-breaking.hh"
  25 #include "warn.hh"
  26
  27 using std::vector;
  28
  29 void
  30 Page_spacing::calc_force ()
  31 {
  32   Real height = page_height_
  33                 - breaker_->min_whitespace_at_top_of_page (first_line_)
  34                 - breaker_->min_whitespace_at_bottom_of_page (last_line_);
  35
  36   if (rod_height_ + last_line_.bottom_padding_ >= height)
  37     force_ = -infinity_f;
  38   else
  39     force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_)
  40              / max (0.1, inverse_spring_k_);
  41 }
  42
  43 void
  44 Page_spacing::resize (Real new_height)
  45 {
  46   page_height_ = new_height;
  47   calc_force ();
  48 }
  49
  50 void
  51 Page_spacing::append_system (const Line_details &line)
  52 {
  53   if (rod_height_)
  54     {
  55       rod_height_ += line.tallness_;
  56       spring_len_ += last_line_.spring_length (line);
  57
  58     }
  59   else
  60     {
  61       rod_height_ += line.full_height ();
  62       first_line_ = line;
  63     }
  64
  65   rod_height_ += account_for_footnotes (line);
  66   inverse_spring_k_ += line.inverse_hooke_;
  67
  68   last_line_ = line;
  69
  70   calc_force ();
  71 }
  72
  73 Real
  74 Page_spacing::account_for_footnotes (Line_details const &line)
  75 {
  76   Real footnote_height = 0.0;
  77   Real in_note_height = 0.0;
  78   bool has_in_notes = false;
  79   for (vsize i = 0; i < line.in_note_heights_.size (); i++)
  80     {
  81       in_note_height += (has_in_notes
  82                          ? 0.0
  83                          : breaker_->in_note_padding ());
  84       has_in_notes = true;
  85       in_note_height += line.in_note_heights_[i];
  86     }
  87
  88   for (vsize i = 0; i < line.footnote_heights_.size (); i++)
  89     {
  90       footnote_height += (has_footnotes_
  91                           ? 0.0
  92                           : (breaker_->footnote_separator_stencil_height ()
  93                              + breaker_->footnote_padding ()
  94                              + breaker_->footnote_number_raise ()));
  95
  96       has_footnotes_ = true;
  97       footnote_height += line.footnote_heights_[i];
  98       footnote_height += breaker_->footnote_padding ();
  99     }
 100
 101   return (in_note_height
 102           - (has_in_notes
 103              ? breaker_->in_note_padding ()
 104              : 0.0))
 105          +
 106          (footnote_height
 107           + (has_footnotes_
 108              ? - breaker_->footnote_padding () + breaker_->footnote_footer_padding ()
 109              : 0.0));
 110 }
 111
 112 void
 113 Page_spacing::prepend_system (const Line_details &line)
 114 {
 115   if (rod_height_)
 116     spring_len_ += line.spring_length (first_line_);
 117   else
 118     last_line_ = line;
 119
 120   rod_height_ -= first_line_.full_height ();
 121   rod_height_ += first_line_.tallness_;
 122   rod_height_ += line.full_height ();
 123   rod_height_ += account_for_footnotes (line);
 124   inverse_spring_k_ += line.inverse_hooke_;
 125
 126   first_line_ = line;
 127
 128   calc_force ();
 129 }
 130
 131 void
 132 Page_spacing::clear ()
 133 {
 134   force_ = rod_height_ = spring_len_ = 0;
 135   inverse_spring_k_ = 0;
 136   has_footnotes_ = false;
 137 }
 138
 139 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
 140   : lines_ (lines)
 141 {
 142   first_page_num_ = first_page_num;
 143   breaker_ = breaker;
 144   max_page_count_ = 0;
 145   ragged_ = breaker->ragged ();
 146   ragged_last_ = breaker->is_last () && breaker->ragged_last ();
 147 }
 148
 149 Page_spacing_result
 150 Page_spacer::solve ()
 151 {
 152   if (simple_state_.empty ())
 153     {
 154       simple_state_.resize (lines_.size ());
 155       for (vsize i = 0; i < lines_.size (); ++i)
 156         calc_subproblem (VPOS, i);
 157     }
 158
 159   Page_spacing_result ret;
 160   if (simple_state_.empty ())
 161     return ret;
 162
 163   ret.penalty_ = simple_state_.back ().penalty_
 164                  + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
 165   ret.system_count_status_ = simple_state_.back ().system_count_status_;
 166
 167   vsize system = lines_.size () - 1;
 168   while (system != VPOS)
 169     {
 170       Page_spacing_node const &cur = simple_state_[system];
 171       vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
 172
 173       ret.force_.push_back (cur.force_);
 174       ret.systems_per_page_.push_back (system_count);
 175       ret.demerits_ += cur.force_ * cur.force_;
 176       system = cur.prev_;
 177     }
 178
 179   reverse (ret.force_);
 180   reverse (ret.systems_per_page_);
 181   return ret;
 182 }
 183
 184 Page_spacing_result
 185 Page_spacer::solve (vsize page_count)
 186 {
 187   if (page_count > max_page_count_)
 188     resize (page_count);
 189
 190   Page_spacing_result ret;
 191
 192   vsize system = lines_.size () - 1;
 193   vsize extra_systems = 0;
 194   vsize extra_pages = 0;
 195
 196   if (isinf (state_.at (system, page_count - 1).demerits_))
 197     {
 198       programming_error ("tried to space systems on a bad number of pages");
 199       /* Usually, this means that we tried to cram too many systems into
 200          to few pages. To avoid crashing, we look for the largest number of
 201          systems that we can fit properly onto the right number of pages.
 202          All the systems that don't fit get tacked onto the last page.
 203       */
 204       vsize i;
 205       for (i = system; isinf (state_.at (i, page_count - 1).demerits_) && i; i--)
 206         ;
 207
 208       if (i)
 209         {
 210           extra_systems = system - i;
 211           system = i;
 212         }
 213       else
 214         {
 215           /* try chopping off pages from the end */
 216           vsize j;
 217           for (j = page_count; j && isinf (state_.at (system, j - 1).demerits_); j--)
 218             ;
 219
 220           if (j)
 221             {
 222               extra_pages = page_count - j;
 223               page_count = j;
 224             }
 225           else
 226             return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
 227         }
 228     }
 229
 230   ret.force_.resize (page_count);
 231   ret.systems_per_page_.resize (page_count);
 232   ret.system_count_status_ = state_.at (system, page_count - 1).system_count_status_;
 233   ret.penalty_ = state_.at (system, page_count - 1).penalty_
 234                  + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
 235
 236   ret.demerits_ = 0;
 237   for (vsize p = page_count; p--;)
 238     {
 239       assert (system != VPOS);
 240
 241       Page_spacing_node const &ps = state_.at (system, p);
 242       ret.force_[p] = ps.force_;
 243       ret.demerits_ += ps.force_ * ps.force_;
 244       if (p == 0)
 245         ret.systems_per_page_[p] = system + 1;
 246       else
 247         ret.systems_per_page_[p] = system - ps.prev_;
 248       system = ps.prev_;
 249     }
 250
 251   if (extra_systems)
 252     {
 253       ret.systems_per_page_.back () += extra_systems;
 254       ret.force_.back () = BAD_SPACING_PENALTY;
 255     }
 256   if (extra_pages)
 257     {
 258       ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
 259       ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
 260     }
 261
 262   return ret;
 263 }
 264
 265 void
 266 Page_spacer::resize (vsize page_count)
 267 {
 268   assert (page_count > 0);
 269
 270   if (max_page_count_ >= page_count)
 271     return;
 272
 273   state_.resize (lines_.size (), page_count, Page_spacing_node ());
 274   for (vsize page = max_page_count_; page < page_count; page++)
 275     for (vsize line = page; line < lines_.size (); line++)
 276       if (!calc_subproblem (page, line))
 277         break;
 278
 279   max_page_count_ = page_count;
 280 }
 281
 282 // Carries out one step in the dynamic programming algorithm for putting systems
 283 // on a fixed number of pages. One call to this routine calculates the best
 284 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
 285 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
 286 //
 287 // This algorithm is similar to the constrained-breaking algorithm.
 288 //
 289 // If page == VPOS, we act on simple_state_ instead of state_.  This is useful if
 290 // we don't want to constrain the number of pages that the solution has.  In this
 291 // case, the algorithm looks more like the page-turn-page-breaking algorithm.  But
 292 // the subproblems look similar for both, so we reuse this method.
 293 bool
 294 Page_spacer::calc_subproblem (vsize page, vsize line)
 295 {
 296   bool last = line == lines_.size () - 1;
 297
 298   // Note: if page == VPOS then we don't actually know yet which page number we're
 299   // working on, so we have to recalculate the page height in the loop.  Therefore
 300   // our early-exit condition from the loop depends on paper_height rather than
 301   // page_height (ie. we break only if we would overfill a page without margins
 302   // or headers/footers).  Otherwise, the algorithm would not be optimal:
 303   // if our page has a very large header then perhaps
 304   // we should look ahead a few systems in order to find the best solution.  A
 305   // good example of this is input/regression/page-spacing-tall-headfoot.ly
 306   vsize page_num = page == VPOS ? 0 : page;
 307   Real paper_height = breaker_->paper_height ();
 308   Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
 309                       breaker_);
 310   Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
 311   bool ragged = ragged_ || (ragged_last_ && last);
 312   int line_count = 0;
 313
 314   for (vsize page_start = line + 1; page_start > page_num && page_start--;)
 315     {
 316       Page_spacing_node const *prev = 0;
 317
 318       if (page == VPOS)
 319         {
 320           if (page_start > 0)
 321             {
 322               prev = &simple_state_[page_start - 1];
 323               space.resize (breaker_->page_height (prev->page_ + 1, last));
 324             }
 325           else
 326             space.resize (breaker_->page_height (first_page_num_, last));
 327         }
 328       else if (page > 0)
 329         prev = &state_.at (page_start - 1, page - 1);
 330
 331       space.prepend_system (lines_[page_start]);
 332
 333       bool overfull = (space.rod_height_ > paper_height
 334                        || (ragged_
 335                            && (space.rod_height_ + space.spring_len_ > paper_height)));
 336       // This 'if' statement is a little hard to parse. It won't consider this configuration
 337       // if it is overfull unless the current configuration is the first one with this start
 338       // point. We also make an exception (and consider this configuration) if the previous
 339       // configuration we tried had fewer lines than min-systems-per-page.
 340       if (!breaker_->too_few_lines (line_count)
 341           && page_start < line
 342           && overfull)
 343         break;
 344
 345       line_count += lines_[page_start].compressed_nontitle_lines_count_;
 346       if (page > 0 || page_start == 0)
 347         {
 348           // If the last page is ragged, set its force to zero. This way, we will leave
 349           // the last page half-empty rather than trying to balance things out
 350           // (which only makes sense in non-ragged situations).
 351           if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
 352             space.force_ = 0;
 353
 354           Real demerits = space.force_ * space.force_;
 355
 356           // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
 357           // is overfull.  This ensures that TERRIBLE_SPACING_PENALTY takes
 358           // precedence over overfull pages.
 359           demerits = min (demerits, BAD_SPACING_PENALTY);
 360           demerits += (prev ? prev->demerits_ : 0);
 361
 362           Real penalty = breaker_->line_count_penalty (line_count);
 363           if (page_start > 0)
 364             penalty += lines_[page_start - 1].page_penalty_
 365                        + (page % 2 == 0) ? lines_[page_start - 1].turn_penalty_ : 0;
 366
 367           /* Deal with widow/orphan lines */
 368           /* Last line of paragraph is first line on the new page */
 369           if ((page_start > 0)
 370               && (page_start < lines_.size ())
 371               && (lines_[page_start].last_markup_line_))
 372             penalty += breaker_->orphan_penalty ();
 373           /* First line of paragraph is last line on the previous page */
 374           if ((page_start > 0)
 375               && (page_start < lines_.size ())
 376               && (lines_[page_start - 1].first_markup_line_))
 377             penalty += breaker_->orphan_penalty ();
 378
 379           demerits += penalty;
 380           if (demerits < cur.demerits_ || page_start == line)
 381             {
 382               cur.demerits_ = demerits;
 383               cur.force_ = space.force_;
 384               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 385               cur.system_count_status_ = breaker_->line_count_status (line_count)
 386                                          | (prev ? prev->system_count_status_ : 0);
 387               cur.prev_ = page_start - 1;
 388               cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
 389             }
 390         }
 391
 392       if (page_start > 0
 393           && scm_is_eq (lines_[page_start - 1].page_permission_,
 394                         ly_symbol2scm ("force")))
 395         break;
 396     }
 397   return !isinf (cur.demerits_);
 398 }
 399