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       line_count += lines_[page_start].compressed_nontitle_lines_count_;
 202
 203       space.prepend_system (lines_[page_start]);
 204       // FIXME: The following line doesn't respect min-systems-per-page. More
 205       // generally, what should we do when respecting min-systems-per-page
 206       // would cause a page to be overfull?
 207       if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged)))
 208         break;
 209
 210       if (page > 0 || page_start == 0)
 211         {
 212           if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
 213             space.force_ = 0;
 214
 215           Real demerits = space.force_ * space.force_;
 216           /* If a single line is taller than a page, we need to consider it as
 217              a possible solution (but we give it a very bad score). */
 218           if (isinf (space.force_) && page_start == line)
 219             demerits = BAD_SPACING_PENALTY;
 220           demerits += (prev ? prev->demerits_ : 0);
 221
 222           Real penalty = breaker_->line_count_penalty (line_count);
 223           if (page_start > 0)
 224             penalty = lines_[page_start-1].page_penalty_
 225               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 226
 227           demerits += penalty;
 228           if (demerits < cur.demerits_ || page_start == line)
 229             {
 230               cur.demerits_ = demerits;
 231               cur.force_ = space.force_;
 232               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 233               cur.prev_ = page_start - 1;
 234             }
 235         }
 236
 237       if (page_start > 0
 238           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
 239         break;
 240     }
 241   return !isinf (cur.demerits_);
 242 }
 243