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