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