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