lily/page-spacing.cc

   1 /*
   2   page-spacing.cc - implement routines for spacing
   3   systems vertically on pages
   4
   5   source file of the GNU LilyPond music typesetter
   6
   7   (c) 2006--2009 Joe Neeman <joeneeman@gmail.com>
   8 */
   9
  10 #include "page-spacing.hh"
  11
  12 #include "matrix.hh"
  13 #include "page-breaking.hh"
  14 #include "warn.hh"
  15
  16 void
  17 Page_spacing::calc_force ()
  18 {
  19   /* If the first system contains a title, we add back in the page-top-space. */
  20   bool starts_with_title = first_line_.compressed_nontitle_lines_count_ < first_line_.compressed_lines_count_;
  21   Real height = starts_with_title ? page_height_ + page_top_space_ : page_height_;
  22
  23   if (rod_height_ + last_line_.bottom_padding_ >= height)
  24     force_ = infinity_f;
  25   else
  26     force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_)
  27       / max (0.1, inverse_spring_k_);
  28 }
  29
  30 void
  31 Page_spacing::resize (Real new_height)
  32 {
  33   page_height_ = new_height;
  34   calc_force ();
  35 }
  36
  37 void
  38 Page_spacing::append_system (const Line_details &line)
  39 {
  40   if (!rod_height_)
  41     first_line_ = line;
  42
  43   rod_height_ += last_line_.padding_;
  44
  45   rod_height_ += line.extent_.length ();
  46   spring_len_ += line.space_;
  47   inverse_spring_k_ += line.inverse_hooke_;
  48
  49   last_line_ = line;
  50
  51   calc_force ();
  52 }
  53
  54 void
  55 Page_spacing::prepend_system (const Line_details &line)
  56 {
  57   if (rod_height_)
  58     rod_height_ += line.padding_;
  59   else
  60     last_line_ = line;
  61
  62   rod_height_ += line.extent_.length ();
  63   spring_len_ += line.space_;
  64   inverse_spring_k_ += line.inverse_hooke_;
  65
  66   first_line_ = line;
  67
  68   calc_force ();
  69 }
  70
  71 void
  72 Page_spacing::clear ()
  73 {
  74   force_ = rod_height_ = spring_len_ = 0;
  75   inverse_spring_k_ = 0;
  76 }
  77
  78
  79 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
  80   : lines_ (lines)
  81 {
  82   first_page_num_ = first_page_num;
  83   breaker_ = breaker;
  84   max_page_count_ = 0;
  85   ragged_ = breaker->ragged ();
  86   ragged_last_ = breaker->is_last () && breaker->ragged_last ();
  87 }
  88
  89 Page_spacing_result
  90 Page_spacer::solve (vsize page_count)
  91 {
  92   if (page_count > max_page_count_)
  93     resize (page_count);
  94
  95   Page_spacing_result ret;
  96
  97   vsize system = lines_.size () - 1;
  98   vsize extra_systems = 0;
  99   vsize extra_pages = 0;
 100
 101   if (isinf (state_.at (system, page_count-1).demerits_))
 102     {
 103       programming_error ("tried to space systems on a bad number of pages");
 104       /* Usually, this means that we tried to cram too many systems into
 105          to few pages. To avoid crashing, we look for the largest number of
 106          systems that we can fit properly onto the right number of pages.
 107          All the systems that don't fit get tacked onto the last page.
 108       */
 109       vsize i;
 110       for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
 111         ;
 112
 113       if (i)
 114         {
 115           extra_systems = system - i;
 116           system = i;
 117         }
 118       else
 119         {
 120           /* try chopping off pages from the end */
 121           vsize j;
 122           for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
 123             ;
 124
 125           if (j)
 126             {
 127               extra_pages = page_count - j;
 128               page_count = j;
 129             }
 130           else
 131             return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
 132         }
 133     }
 134
 135   ret.force_.resize (page_count);
 136   ret.systems_per_page_.resize (page_count);
 137   ret.penalty_ = state_.at (system, page_count-1).penalty_
 138     + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
 139
 140   ret.demerits_ = 0;
 141   for (vsize p = page_count; p--;)
 142     {
 143       assert (system != VPOS);
 144
 145       Page_spacing_node const &ps = state_.at (system, p);
 146       ret.force_[p] = ps.force_;
 147       ret.demerits_ += ps.force_ * ps.force_;
 148       if (p == 0)
 149         ret.systems_per_page_[p] = system + 1;
 150       else
 151         ret.systems_per_page_[p] = system - ps.prev_;
 152       system = ps.prev_;
 153     }
 154
 155   if (extra_systems)
 156     {
 157       ret.systems_per_page_.back () += extra_systems;
 158       ret.demerits_ += BAD_SPACING_PENALTY;
 159     }
 160   if (extra_pages)
 161     {
 162       ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
 163       ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
 164       ret.demerits_ += BAD_SPACING_PENALTY;
 165     }
 166
 167
 168   ret.demerits_ += ret.penalty_;
 169   return ret;
 170 }
 171
 172 void
 173 Page_spacer::resize (vsize page_count)
 174 {
 175   assert (page_count > 0);
 176
 177   if (max_page_count_ >= page_count)
 178     return;
 179
 180   state_.resize (lines_.size (), page_count, Page_spacing_node ());
 181   for (vsize page = max_page_count_; page < page_count; page++)
 182     for (vsize line = page; line < lines_.size (); line++)
 183       if (!calc_subproblem (page, line))
 184         break;
 185
 186   max_page_count_ = page_count;
 187 }
 188
 189 // Carries out one step in the dynamic programming algorithm for putting systems
 190 // on a fixed number of pages. One call to this routine calculates the best
 191 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
 192 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
 193 //
 194 // This algorithm is similar to the constrained-breaking algorithm.
 195 bool
 196 Page_spacer::calc_subproblem (vsize page, vsize line)
 197 {
 198   bool last = line == lines_.size () - 1;
 199   Page_spacing space (breaker_->page_height (page + first_page_num_, last),
 200                       breaker_->page_top_space ());
 201   Page_spacing_node &cur = state_.at (line, page);
 202   bool ragged = ragged_ || (ragged_last_ && last);
 203   int line_count = 0;
 204
 205   for (vsize page_start = line+1; page_start > page && page_start--;)
 206     {
 207       Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
 208
 209       space.prepend_system (lines_[page_start]);
 210
 211       // This 'if' statement is a little hard to parse. It won't consider this configuration
 212       // if it is overfull unless the current configuration is the first one with this start
 213       // point. We also make an exception (and consider this configuration) if the previous
 214       // configuration we tried had fewer lines than min-systems-per-page.
 215       if (!breaker_->too_few_lines (line_count)
 216           && page_start < line
 217           && (isinf (space.force_) || (space.force_ < 0 && ragged)))
 218         break;
 219
 220       line_count += lines_[page_start].compressed_nontitle_lines_count_;
 221       if (page > 0 || page_start == 0)
 222         {
 223           // If the last page is ragged, set its force to zero. This way, we will leave
 224           // the last page half-empty rather than trying to balance things out
 225           // (which only makes sense in non-ragged situations).
 226           if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
 227             space.force_ = 0;
 228
 229           Real demerits = space.force_ * space.force_;
 230           /* If a single line is taller than a page, we need to consider it as
 231              a possible solution (but we give it a very bad score). */
 232           if (isinf (space.force_) && page_start == line)
 233             demerits = BAD_SPACING_PENALTY;
 234           demerits += (prev ? prev->demerits_ : 0);
 235
 236           Real penalty = breaker_->line_count_penalty (line_count);
 237           if (page_start > 0)
 238             penalty += lines_[page_start-1].page_penalty_
 239               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 240
 241           demerits += penalty;
 242           if (demerits < cur.demerits_ || page_start == line)
 243             {
 244               cur.demerits_ = demerits;
 245               cur.force_ = space.force_;
 246               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 247               cur.system_count_status_ = breaker_->line_count_status (line_count)
 248                 | (prev ? prev->system_count_status_ : 0);
 249               cur.prev_ = page_start - 1;
 250             }
 251         }
 252
 253       if (page_start > 0
 254           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
 255         break;
 256     }
 257   return !isinf (cur.demerits_);
 258 }
 259