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