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