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   rod_height_ += line.title_ ? last_line_.title_padding_ : last_line_.padding_;
  60   spring_len_ += line.space_;
  61   inverse_spring_k_ += line.inverse_hooke_;
  62
  63   last_line_ = line;
  64
  65   calc_force ();
  66 }
  67
  68 void
  69 Page_spacing::prepend_system (const Line_details &line)
  70 {
  71   if (rod_height_)
  72     rod_height_ += first_line_.title_ ? line.title_padding_ : line.padding_;
  73   else
  74     last_line_ = line;
  75
  76   rod_height_ -= first_line_.full_height ();
  77   rod_height_ += first_line_.tallness_;
  78   rod_height_ += line.full_height();
  79   spring_len_ += line.space_;
  80   inverse_spring_k_ += line.inverse_hooke_;
  81
  82   first_line_ = line;
  83
  84   calc_force ();
  85 }
  86
  87 void
  88 Page_spacing::clear ()
  89 {
  90   force_ = rod_height_ = spring_len_ = 0;
  91   inverse_spring_k_ = 0;
  92 }
  93
  94
  95 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
  96   : lines_ (lines)
  97 {
  98   first_page_num_ = first_page_num;
  99   breaker_ = breaker;
 100   max_page_count_ = 0;
 101   ragged_ = breaker->ragged ();
 102   ragged_last_ = breaker->is_last () && breaker->ragged_last ();
 103 }
 104
 105 Page_spacing_result
 106 Page_spacer::solve (vsize page_count)
 107 {
 108   if (page_count > max_page_count_)
 109     resize (page_count);
 110
 111   Page_spacing_result ret;
 112
 113   vsize system = lines_.size () - 1;
 114   vsize extra_systems = 0;
 115   vsize extra_pages = 0;
 116
 117   if (isinf (state_.at (system, page_count-1).demerits_))
 118     {
 119       programming_error ("tried to space systems on a bad number of pages");
 120       /* Usually, this means that we tried to cram too many systems into
 121          to few pages. To avoid crashing, we look for the largest number of
 122          systems that we can fit properly onto the right number of pages.
 123          All the systems that don't fit get tacked onto the last page.
 124       */
 125       vsize i;
 126       for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
 127         ;
 128
 129       if (i)
 130         {
 131           extra_systems = system - i;
 132           system = i;
 133         }
 134       else
 135         {
 136           /* try chopping off pages from the end */
 137           vsize j;
 138           for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
 139             ;
 140
 141           if (j)
 142             {
 143               extra_pages = page_count - j;
 144               page_count = j;
 145             }
 146           else
 147             return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
 148         }
 149     }
 150
 151   ret.force_.resize (page_count);
 152   ret.systems_per_page_.resize (page_count);
 153   ret.penalty_ = state_.at (system, page_count-1).penalty_
 154     + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
 155
 156   ret.demerits_ = 0;
 157   for (vsize p = page_count; p--;)
 158     {
 159       assert (system != VPOS);
 160
 161       Page_spacing_node const &ps = state_.at (system, p);
 162       ret.force_[p] = ps.force_;
 163       ret.demerits_ += ps.force_ * ps.force_;
 164       if (p == 0)
 165         ret.systems_per_page_[p] = system + 1;
 166       else
 167         ret.systems_per_page_[p] = system - ps.prev_;
 168       system = ps.prev_;
 169     }
 170
 171   if (extra_systems)
 172     {
 173       ret.systems_per_page_.back () += extra_systems;
 174       ret.force_.back () = BAD_SPACING_PENALTY;
 175     }
 176   if (extra_pages)
 177     {
 178       ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
 179       ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
 180     }
 181
 182   return ret;
 183 }
 184
 185 void
 186 Page_spacer::resize (vsize page_count)
 187 {
 188   assert (page_count > 0);
 189
 190   if (max_page_count_ >= page_count)
 191     return;
 192
 193   state_.resize (lines_.size (), page_count, Page_spacing_node ());
 194   for (vsize page = max_page_count_; page < page_count; page++)
 195     for (vsize line = page; line < lines_.size (); line++)
 196       if (!calc_subproblem (page, line))
 197         break;
 198
 199   max_page_count_ = page_count;
 200 }
 201
 202 // Carries out one step in the dynamic programming algorithm for putting systems
 203 // on a fixed number of pages. One call to this routine calculates the best
 204 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
 205 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
 206 //
 207 // This algorithm is similar to the constrained-breaking algorithm.
 208 bool
 209 Page_spacer::calc_subproblem (vsize page, vsize line)
 210 {
 211   bool last = line == lines_.size () - 1;
 212   Page_spacing space (breaker_->page_height (page + first_page_num_, last),
 213                       breaker_);
 214   Page_spacing_node &cur = state_.at (line, page);
 215   bool ragged = ragged_ || (ragged_last_ && last);
 216   int line_count = 0;
 217
 218   for (vsize page_start = line+1; page_start > page && page_start--;)
 219     {
 220       Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
 221
 222       space.prepend_system (lines_[page_start]);
 223
 224       // This 'if' statement is a little hard to parse. It won't consider this configuration
 225       // if it is overfull unless the current configuration is the first one with this start
 226       // point. We also make an exception (and consider this configuration) if the previous
 227       // configuration we tried had fewer lines than min-systems-per-page.
 228       if (!breaker_->too_few_lines (line_count)
 229           && page_start < line
 230           && (isinf (space.force_) || (space.force_ < 0 && ragged)))
 231         break;
 232
 233       line_count += lines_[page_start].compressed_nontitle_lines_count_;
 234       if (page > 0 || page_start == 0)
 235         {
 236           // If the last page is ragged, set its force to zero. This way, we will leave
 237           // the last page half-empty rather than trying to balance things out
 238           // (which only makes sense in non-ragged situations).
 239           if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
 240             space.force_ = 0;
 241
 242           Real demerits = space.force_ * space.force_;
 243           /* If a single line is taller than a page, we need to consider it as
 244              a possible solution (but we give it a very bad score). */
 245           if (isinf (space.force_) && page_start == line)
 246             demerits = BAD_SPACING_PENALTY;
 247           demerits += (prev ? prev->demerits_ : 0);
 248
 249           Real penalty = breaker_->line_count_penalty (line_count);
 250           if (page_start > 0)
 251             penalty += lines_[page_start-1].page_penalty_
 252               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 253
 254           /* Deal with widow/orphan lines */
 255           /* Last line of paragraph is first line on the new page */
 256           if ((page_start > 0) &&
 257               (page_start < lines_.size ()) &&
 258               (lines_[page_start].last_markup_line_))
 259                   penalty += breaker_->orphan_penalty ();
 260           /* First line of paragraph is last line on the previous page */
 261           if ((page_start > 0) &&
 262               (page_start < lines_.size ()) &&
 263               (lines_[page_start-1].first_markup_line_))
 264                   penalty += breaker_->orphan_penalty ();
 265
 266           demerits += penalty;
 267           if (demerits < cur.demerits_ || page_start == line)
 268             {
 269               cur.demerits_ = demerits;
 270               cur.force_ = space.force_;
 271               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 272               cur.system_count_status_ = breaker_->line_count_status (line_count)
 273                 | (prev ? prev->system_count_status_ : 0);
 274               cur.prev_ = page_start - 1;
 275             }
 276         }
 277
 278       if (page_start > 0
 279           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
 280         break;
 281     }
 282   return !isinf (cur.demerits_);
 283 }
 284