lily/page-spacing.cc

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