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   Real height = page_height_
  20     - breaker_->min_whitespace_at_top_of_page (first_line_)
  21     - breaker_->min_whitespace_at_bottom_of_page (last_line_);
  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.force_.back () = 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     }
 165
 166   return ret;
 167 }
 168
 169 void
 170 Page_spacer::resize (vsize page_count)
 171 {
 172   assert (page_count > 0);
 173
 174   if (max_page_count_ >= page_count)
 175     return;
 176
 177   state_.resize (lines_.size (), page_count, Page_spacing_node ());
 178   for (vsize page = max_page_count_; page < page_count; page++)
 179     for (vsize line = page; line < lines_.size (); line++)
 180       if (!calc_subproblem (page, line))
 181         break;
 182
 183   max_page_count_ = page_count;
 184 }
 185
 186 // Carries out one step in the dynamic programming algorithm for putting systems
 187 // on a fixed number of pages. One call to this routine calculates the best
 188 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
 189 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
 190 //
 191 // This algorithm is similar to the constrained-breaking algorithm.
 192 bool
 193 Page_spacer::calc_subproblem (vsize page, vsize line)
 194 {
 195   bool last = line == lines_.size () - 1;
 196   Page_spacing space (breaker_->page_height (page + first_page_num_, last),
 197                       breaker_);
 198   Page_spacing_node &cur = state_.at (line, page);
 199   bool ragged = ragged_ || (ragged_last_ && last);
 200   int line_count = 0;
 201
 202   for (vsize page_start = line+1; page_start > page && page_start--;)
 203     {
 204       Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
 205
 206       space.prepend_system (lines_[page_start]);
 207
 208       // This 'if' statement is a little hard to parse. It won't consider this configuration
 209       // if it is overfull unless the current configuration is the first one with this start
 210       // point. We also make an exception (and consider this configuration) if the previous
 211       // configuration we tried had fewer lines than min-systems-per-page.
 212       if (!breaker_->too_few_lines (line_count)
 213           && page_start < line
 214           && (isinf (space.force_) || (space.force_ < 0 && ragged)))
 215         break;
 216
 217       line_count += lines_[page_start].compressed_nontitle_lines_count_;
 218       if (page > 0 || page_start == 0)
 219         {
 220           // If the last page is ragged, set its force to zero. This way, we will leave
 221           // the last page half-empty rather than trying to balance things out
 222           // (which only makes sense in non-ragged situations).
 223           if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
 224             space.force_ = 0;
 225
 226           Real demerits = space.force_ * space.force_;
 227           /* If a single line is taller than a page, we need to consider it as
 228              a possible solution (but we give it a very bad score). */
 229           if (isinf (space.force_) && page_start == line)
 230             demerits = BAD_SPACING_PENALTY;
 231           demerits += (prev ? prev->demerits_ : 0);
 232
 233           Real penalty = breaker_->line_count_penalty (line_count);
 234           if (page_start > 0)
 235             penalty += lines_[page_start-1].page_penalty_
 236               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 237
 238           demerits += penalty;
 239           if (demerits < cur.demerits_ || page_start == line)
 240             {
 241               cur.demerits_ = demerits;
 242               cur.force_ = space.force_;
 243               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 244               cur.system_count_status_ = breaker_->line_count_status (line_count)
 245                 | (prev ? prev->system_count_status_ : 0);
 246               cur.prev_ = page_start - 1;
 247             }
 248         }
 249
 250       if (page_start > 0
 251           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
 252         break;
 253     }
 254   return !isinf (cur.demerits_);
 255 }
 256