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