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