lily/page-spacing.cc

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