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.  Therefore
 251   // our early-exit condition from the loop depends on paper_height rather than
 252   // page_height (ie. we break only if we would overfill a page without margins
 253   // or headers/footers).  Otherwise, the algorithm would not be optimal:
 254   // if our page has a very large header then perhaps
 255   // we should look ahead a few systems in order to find the best solution.  A
 256   // good example of this is input/regression/page-spacing-tall-headfoot.ly
 257   vsize page_num = page == VPOS ? 0 : page;
 258   Real paper_height = breaker_->paper_height ();
 259   Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
 260                       breaker_);
 261   Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
 262   bool ragged = ragged_ || (ragged_last_ && last);
 263   int line_count = 0;
 264
 265   for (vsize page_start = line+1; page_start > page_num && page_start--;)
 266     {
 267       Page_spacing_node const *prev = 0;
 268
 269       if (page == VPOS)
 270         {
 271           if (page_start > 0)
 272             {
 273               prev = &simple_state_[page_start-1];
 274               space.resize (breaker_->page_height (prev->page_ + 1, last));
 275             }
 276           else
 277             space.resize (breaker_->page_height (first_page_num_, last));
 278         }
 279       else if (page > 0)
 280         prev = &state_.at (page_start-1, page-1);
 281
 282       space.prepend_system (lines_[page_start]);
 283
 284       bool overfull = (space.rod_height_ > paper_height
 285                        || (ragged
 286                            && (space.rod_height_ + space.spring_len_ > paper_height)));
 287       // This 'if' statement is a little hard to parse. It won't consider this configuration
 288       // if it is overfull unless the current configuration is the first one with this start
 289       // point. We also make an exception (and consider this configuration) if the previous
 290       // configuration we tried had fewer lines than min-systems-per-page.
 291       if (!breaker_->too_few_lines (line_count)
 292           && page_start < line
 293           && overfull)
 294         break;
 295
 296       line_count += lines_[page_start].compressed_nontitle_lines_count_;
 297       if (page > 0 || page_start == 0)
 298         {
 299           // If the last page is ragged, set its force to zero. This way, we will leave
 300           // the last page half-empty rather than trying to balance things out
 301           // (which only makes sense in non-ragged situations).
 302           if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
 303             space.force_ = 0;
 304
 305           Real demerits = space.force_ * space.force_;
 306
 307           // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
 308           // is overfull.  This ensures that TERRIBLE_SPACING_PENALTY takes
 309           // precedence over overfull pages.
 310           demerits = min (demerits, BAD_SPACING_PENALTY);
 311           demerits += (prev ? prev->demerits_ : 0);
 312
 313           Real penalty = breaker_->line_count_penalty (line_count);
 314           if (page_start > 0)
 315             penalty += lines_[page_start-1].page_penalty_
 316               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 317
 318           /* Deal with widow/orphan lines */
 319           /* Last line of paragraph is first line on the new page */
 320           if ((page_start > 0) &&
 321               (page_start < lines_.size ()) &&
 322               (lines_[page_start].last_markup_line_))
 323                   penalty += breaker_->orphan_penalty ();
 324           /* First line of paragraph is last line on the previous page */
 325           if ((page_start > 0) &&
 326               (page_start < lines_.size ()) &&
 327               (lines_[page_start-1].first_markup_line_))
 328                   penalty += breaker_->orphan_penalty ();
 329
 330           demerits += penalty;
 331           if (demerits < cur.demerits_ || page_start == line)
 332             {
 333               cur.demerits_ = demerits;
 334               cur.force_ = space.force_;
 335               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 336               cur.system_count_status_ = breaker_->line_count_status (line_count)
 337                 | (prev ? prev->system_count_status_ : 0);
 338               cur.prev_ = page_start - 1;
 339               cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
 340             }
 341         }
 342
 343       if (page_start > 0
 344           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
 345         break;
 346     }
 347   return !isinf (cur.demerits_);
 348 }
 349