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 /* In order to prevent possible division by zero, we require every line
  17    to have a spring of non-zero length. */
  18 Real
  19 line_space (const Line_details &line)
  20 {
  21   return max (0.1, line.space_);
  22 }
  23
  24 void
  25 Page_spacing::calc_force ()
  26 {
  27   if (rod_height_ + last_line_.bottom_padding_ >= page_height_ || !inverse_spring_k_)
  28     force_ = infinity_f;
  29   else
  30     force_ = (page_height_ - rod_height_ - last_line_.bottom_padding_ - spring_len_) / inverse_spring_k_;
  31 }
  32
  33 void
  34 Page_spacing::append_system (const Line_details &line)
  35 {
  36   rod_height_ += last_line_.padding_;
  37
  38   rod_height_ += line.extent_.length ();
  39   spring_len_ += line_space (line);
  40   inverse_spring_k_ += max (0.1, line.inverse_hooke_);
  41
  42   last_line_ = line;
  43
  44   calc_force ();
  45 }
  46
  47 void
  48 Page_spacing::prepend_system (const Line_details &line)
  49 {
  50   if (rod_height_)
  51     rod_height_ += line.padding_;
  52   else
  53     last_line_ = line;
  54
  55   rod_height_ += line.extent_.length ();
  56   spring_len_ += line_space (line);
  57   inverse_spring_k_ += max (0.1, line.inverse_hooke_);
  58
  59   calc_force ();
  60 }
  61
  62 void
  63 Page_spacing::clear ()
  64 {
  65   force_ = rod_height_ = spring_len_ = 0;
  66   inverse_spring_k_ = 0;
  67 }
  68
  69
  70 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
  71   : lines_ (lines)
  72 {
  73   first_page_num_ = first_page_num;
  74   breaker_ = breaker;
  75   max_page_count_ = 0;
  76   ragged_ = breaker->ragged ();
  77   ragged_last_ = breaker->last () && breaker->ragged_last ();
  78 }
  79
  80 Spacing_result
  81 Page_spacer::solve (vsize page_count)
  82 {
  83   if (page_count > max_page_count_)
  84     resize (page_count);
  85
  86   Spacing_result ret;
  87   ret.force_.resize (page_count);
  88   ret.systems_per_page_.resize (page_count);
  89
  90   vsize system = lines_.size () - 1;
  91   vsize tack_onto_the_end = 0;
  92
  93   if (isinf (state_.at (system, page_count-1).demerits_))
  94     {
  95       programming_error ("tried to space systems on a bad number of pages");
  96       /* Usually, this means that we tried to cram too many systems into
  97          to few pages. To avoid crashing, we look for the largest number of
  98          systems that we can fit properly onto the right number of pages.
  99          All the systems that don't fit get tacked onto the last page.
 100       */
 101       vsize i;
 102       for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i--; )
 103         ;
 104
 105       if (i)
 106         {
 107           tack_onto_the_end = system - i;
 108           system = i;
 109         }
 110       else
 111         return Spacing_result (); /* couldn't salvage it -- probably going to crash */
 112     }
 113
 114   ret.penalty_ = state_.at (system, page_count-1).penalty_
 115     + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
 116
 117   ret.demerits_ = 0;
 118   for (vsize p = page_count; p--;)
 119     {
 120       assert (system != VPOS);
 121
 122       Page_spacing_node const &ps = state_.at (system, p);
 123       ret.force_[p] = ps.force_;
 124       ret.demerits_ += ps.force_ * ps.force_;
 125       if (p == 0)
 126         ret.systems_per_page_[p] = system + 1;
 127       else
 128         ret.systems_per_page_[p] = system - ps.prev_ + tack_onto_the_end;
 129       system = ps.prev_;
 130     }
 131   ret.demerits_ += ret.penalty_;
 132   return ret;
 133 }
 134
 135 void
 136 Page_spacer::resize (vsize page_count)
 137 {
 138   assert (page_count > 0);
 139
 140   if (max_page_count_ >= page_count)
 141     return;
 142
 143   state_.resize (lines_.size (), page_count, Page_spacing_node ());
 144   for (vsize page = max_page_count_; page < page_count; page++)
 145     for (vsize line = page; line < lines_.size (); line++)
 146       if (!calc_subproblem (page, line))
 147         break;
 148
 149   max_page_count_ = page_count;
 150 }
 151
 152 bool
 153 Page_spacer::calc_subproblem (vsize page, vsize line)
 154 {
 155   bool last = line == lines_.size () - 1;
 156   Page_spacing space (breaker_->page_height (page + first_page_num_, last));
 157   Page_spacing_node &cur = state_.at (line, page);
 158   bool ragged = ragged_ || (ragged_last_ && last);
 159
 160   for (vsize page_start = line+1; page_start > page && page_start--;)
 161     {
 162       Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
 163
 164       space.prepend_system (lines_[page_start]);
 165       if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged)))
 166         break;
 167
 168       if (page > 0 || page_start == 0)
 169         {
 170           if (line == lines_.size () - 1 && ragged_last_ && space.force_ > 0)
 171             space.force_ = 0;
 172
 173           /* we may have to deal with single lines that are taller than a page */
 174           if (isinf (space.force_) && page_start == line)
 175             space.force_ = -200000;
 176
 177           Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
 178           Real penalty = 0;
 179           if (page_start > 0)
 180             penalty = lines_[page_start-1].page_penalty_
 181               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 182
 183           dem += penalty;
 184           if (dem < cur.demerits_ || page_start == line)
 185             {
 186               cur.demerits_ = dem;
 187               cur.force_ = space.force_;
 188               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 189               cur.prev_ = page_start - 1;
 190             }
 191         }
 192
 193       if (page_start > 0
 194           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
 195         break;
 196     }
 197   return !isinf (cur.demerits_);
 198 }
 199