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--2007 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   ret.force_.resize (page_count);
  96   ret.systems_per_page_.resize (page_count);
  97
  98   vsize system = lines_.size () - 1;
  99   vsize tack_onto_the_end = 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           tack_onto_the_end = system - i;
 116           system = i;
 117         }
 118       else
 119         return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
 120     }
 121
 122   ret.penalty_ = state_.at (system, page_count-1).penalty_
 123     + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
 124
 125   ret.demerits_ = 0;
 126   for (vsize p = page_count; p--;)
 127     {
 128       assert (system != VPOS);
 129
 130       Page_spacing_node const &ps = state_.at (system, p);
 131       ret.force_[p] = ps.force_;
 132       ret.demerits_ += ps.force_ * ps.force_;
 133       if (p == 0)
 134         ret.systems_per_page_[p] = system + 1;
 135       else
 136         ret.systems_per_page_[p] = system - ps.prev_ + tack_onto_the_end;
 137       system = ps.prev_;
 138     }
 139   ret.demerits_ += ret.penalty_;
 140   return ret;
 141 }
 142
 143 void
 144 Page_spacer::resize (vsize page_count)
 145 {
 146   assert (page_count > 0);
 147
 148   if (max_page_count_ >= page_count)
 149     return;
 150
 151   state_.resize (lines_.size (), page_count, Page_spacing_node ());
 152   for (vsize page = max_page_count_; page < page_count; page++)
 153     for (vsize line = page; line < lines_.size (); line++)
 154       if (!calc_subproblem (page, line))
 155         break;
 156
 157   max_page_count_ = page_count;
 158 }
 159
 160 bool
 161 Page_spacer::calc_subproblem (vsize page, vsize line)
 162 {
 163   bool last = line == lines_.size () - 1;
 164   Page_spacing space (breaker_->page_height (page + first_page_num_, last),
 165                       breaker_->page_top_space ());
 166   Page_spacing_node &cur = state_.at (line, page);
 167   bool ragged = ragged_ || (ragged_last_ && last);
 168
 169   for (vsize page_start = line+1; page_start > page && page_start--;)
 170     {
 171       Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
 172
 173       space.prepend_system (lines_[page_start]);
 174       if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged)))
 175         break;
 176
 177       if (page > 0 || page_start == 0)
 178         {
 179           if (line == lines_.size () - 1 && ragged_last_ && space.force_ > 0)
 180             space.force_ = 0;
 181
 182           /* we may have to deal with single lines that are taller than a page */
 183           if (isinf (space.force_) && page_start == line)
 184             space.force_ = -200000;
 185
 186           Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
 187           Real penalty = 0;
 188           if (page_start > 0)
 189             penalty = lines_[page_start-1].page_penalty_
 190               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 191
 192           dem += penalty;
 193           if (dem < cur.demerits_ || page_start == line)
 194             {
 195               cur.demerits_ = dem;
 196               cur.force_ = space.force_;
 197               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 198               cur.prev_ = page_start - 1;
 199             }
 200         }
 201
 202       if (page_start > 0
 203           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
 204         break;
 205     }
 206   return !isinf (cur.demerits_);
 207 }
 208