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