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   Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
 251                       breaker_);
 252   Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
 253   bool ragged = ragged_ || (ragged_last_ && last);
 254   int line_count = 0;
 255
 256   for (vsize page_start = line+1; page_start > page_num && page_start--;)
 257     {
 258       Page_spacing_node const *prev = 0;
 259
 260       if (page == VPOS)
 261         {
 262           if (page_start > 0)
 263             {
 264               prev = &simple_state_[page_start-1];
 265               space.resize (breaker_->page_height (prev->page_ + 1, last));
 266             }
 267           else
 268             space.resize (breaker_->page_height (first_page_num_, last));
 269         }
 270       else if (page > 0)
 271         prev = &state_.at (page_start-1, page-1);
 272
 273       space.prepend_system (lines_[page_start]);
 274
 275       // This 'if' statement is a little hard to parse. It won't consider this configuration
 276       // if it is overfull unless the current configuration is the first one with this start
 277       // point. We also make an exception (and consider this configuration) if the previous
 278       // configuration we tried had fewer lines than min-systems-per-page.
 279       if (!breaker_->too_few_lines (line_count)
 280           && page_start < line
 281           && (isinf (space.force_) || (space.force_ < 0 && ragged)))
 282         break;
 283
 284       line_count += lines_[page_start].compressed_nontitle_lines_count_;
 285       if (page > 0 || page_start == 0)
 286         {
 287           // If the last page is ragged, set its force to zero. This way, we will leave
 288           // the last page half-empty rather than trying to balance things out
 289           // (which only makes sense in non-ragged situations).
 290           if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
 291             space.force_ = 0;
 292
 293           Real demerits = space.force_ * space.force_;
 294           /* If a single line is taller than a page, we need to consider it as
 295              a possible solution (but we give it a very bad score). */
 296           if (isinf (space.force_) && page_start == line)
 297             demerits = BAD_SPACING_PENALTY;
 298           demerits += (prev ? prev->demerits_ : 0);
 299
 300           Real penalty = breaker_->line_count_penalty (line_count);
 301           if (page_start > 0)
 302             penalty += lines_[page_start-1].page_penalty_
 303               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 304
 305           /* Deal with widow/orphan lines */
 306           /* Last line of paragraph is first line on the new page */
 307           if ((page_start > 0) &&
 308               (page_start < lines_.size ()) &&
 309               (lines_[page_start].last_markup_line_))
 310                   penalty += breaker_->orphan_penalty ();
 311           /* First line of paragraph is last line on the previous page */
 312           if ((page_start > 0) &&
 313               (page_start < lines_.size ()) &&
 314               (lines_[page_start-1].first_markup_line_))
 315                   penalty += breaker_->orphan_penalty ();
 316
 317           demerits += penalty;
 318           if (demerits < cur.demerits_ || page_start == line)
 319             {
 320               cur.demerits_ = demerits;
 321               cur.force_ = space.force_;
 322               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 323               cur.system_count_status_ = breaker_->line_count_status (line_count)
 324                 | (prev ? prev->system_count_status_ : 0);
 325               cur.prev_ = page_start - 1;
 326               cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
 327             }
 328         }
 329
 330       if (page_start > 0
 331           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
 332         break;
 333     }
 334   return !isinf (cur.demerits_);
 335 }
 336