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