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