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