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_ += 200000;
 158     }
 159   if (extra_pages)
 160     {
 161       ret.force_.insert (ret.force_.end (), extra_pages, 200000);
 162       ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
 163       ret.demerits_ += 200000;
 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
 197   for (vsize page_start = line+1; page_start > page && page_start--;)
 198     {
 199       Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
 200
 201       space.prepend_system (lines_[page_start]);
 202       if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged)))
 203         break;
 204
 205       if (page > 0 || page_start == 0)
 206         {
 207           if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
 208             space.force_ = 0;
 209
 210           /* we may have to deal with single lines that are taller than a page */
 211           if (isinf (space.force_) && page_start == line)
 212             space.force_ = -200000;
 213
 214           Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
 215           Real penalty = 0;
 216           if (page_start > 0)
 217             penalty = lines_[page_start-1].page_penalty_
 218               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 219
 220           dem += penalty;
 221           if (dem < cur.demerits_ || page_start == line)
 222             {
 223               cur.demerits_ = dem;
 224               cur.force_ = space.force_;
 225               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 226               cur.prev_ = page_start - 1;
 227             }
 228         }
 229
 230       if (page_start > 0
 231           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
 232         break;
 233     }
 234   return !isinf (cur.demerits_);
 235 }
 236