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