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 bool
 189 Page_spacer::calc_subproblem (vsize page, vsize line)
 190 {
 191   bool last = line == lines_.size () - 1;
 192   Page_spacing space (breaker_->page_height (page + first_page_num_, last),
 193                       breaker_->page_top_space ());
 194   Page_spacing_node &cur = state_.at (line, page);
 195   bool ragged = ragged_ || (ragged_last_ && last);
 196   int line_count = 0;
 197
 198   for (vsize page_start = line+1; page_start > page && page_start--;)
 199     {
 200       Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
 201
 202       space.prepend_system (lines_[page_start]);
 203
 204       // This 'if' statement is a little hard to parse. It won't consider this configuration
 205       // if it is overfull unless the current configuration is the first one with this start
 206       // point. We also make an exception (and consider this configuration) if the previous
 207       // configuration we tried had fewer lines than min-systems-per-page.
 208       if (!breaker_->too_few_lines (line_count)
 209           && page_start < line
 210           && (isinf (space.force_) || (space.force_ < 0 && ragged)))
 211         break;
 212
 213       line_count += lines_[page_start].compressed_nontitle_lines_count_;
 214       if (page > 0 || page_start == 0)
 215         {
 216           if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
 217             space.force_ = 0;
 218
 219           Real demerits = space.force_ * space.force_;
 220           /* If a single line is taller than a page, we need to consider it as
 221              a possible solution (but we give it a very bad score). */
 222           if (isinf (space.force_) && page_start == line)
 223             demerits = BAD_SPACING_PENALTY;
 224           demerits += (prev ? prev->demerits_ : 0);
 225
 226           Real penalty = breaker_->line_count_penalty (line_count);
 227           if (page_start > 0)
 228             penalty += lines_[page_start-1].page_penalty_
 229               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 230
 231           demerits += penalty;
 232           if (demerits < cur.demerits_ || page_start == line)
 233             {
 234               cur.demerits_ = demerits;
 235               cur.force_ = space.force_;
 236               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 237               cur.system_count_status_ = breaker_->line_count_status (line_count)
 238                 | (prev ? prev->system_count_status_ : 0);
 239               cur.prev_ = page_start - 1;
 240             }
 241         }
 242
 243       if (page_start > 0
 244           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
 245         break;
 246     }
 247   return !isinf (cur.demerits_);
 248 }
 249