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