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 "warn.hh"
  14
  15 /*
  16   A much simplified rods-and-springs problem.
  17  */
  18 struct Page_spacing
  19 {
  20   Real force_;
  21   Real page_height_;
  22   Real rod_height_;
  23   Real spring_len_;
  24   Real inverse_spring_k_;
  25
  26   Line_details last_line_;
  27
  28   Page_spacing (Real page_height)
  29   {
  30     page_height_ = page_height;
  31     clear ();
  32   }
  33
  34   void calc_force ();
  35
  36   void append_system (const Line_details &line);
  37   void prepend_system (const Line_details &line);
  38   void clear ();
  39 };
  40
  41 /* In order to prevent possible division by zero, we require every line
  42    to have a spring of non-zero length. */
  43 static Real
  44 line_space (const Line_details &line)
  45 {
  46   return max (0.1, line.space_);
  47 }
  48
  49 void
  50 Page_spacing::calc_force ()
  51 {
  52   if (rod_height_ + last_line_.bottom_padding_ >= page_height_ || !inverse_spring_k_)
  53     force_ = infinity_f;
  54   else
  55     force_ = (page_height_ - rod_height_ - last_line_.bottom_padding_ - spring_len_) / inverse_spring_k_;
  56 }
  57
  58 void
  59 Page_spacing::append_system (const Line_details &line)
  60 {
  61   rod_height_ += last_line_.padding_;
  62
  63   rod_height_ += line.extent_.length ();
  64   spring_len_ += line_space (line);
  65   inverse_spring_k_ += max (0.1, line.inverse_hooke_);
  66
  67   last_line_ = line;
  68
  69   calc_force ();
  70 }
  71
  72 void
  73 Page_spacing::prepend_system (const Line_details &line)
  74 {
  75   if (rod_height_)
  76     rod_height_ += line.padding_;
  77   else
  78     last_line_ = line;
  79
  80   rod_height_ += line.extent_.length ();
  81   spring_len_ += line_space (line);
  82   inverse_spring_k_ += max (0.1, line.inverse_hooke_);
  83
  84   calc_force ();
  85 }
  86
  87 void
  88 Page_spacing::clear ()
  89 {
  90   force_ = rod_height_ = spring_len_ = 0;
  91   inverse_spring_k_ = 0;
  92 }
  93
  94 /* for each forbidden page break, merge the systems around it into one system. */
  95 static vector<Line_details>
  96 compress_lines (const vector<Line_details> &orig)
  97 {
  98   vector<Line_details> ret;
  99
 100   for (vsize i = 0; i < orig.size (); i++)
 101     {
 102       if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
 103         {
 104           Line_details const &old = ret.back ();
 105           Line_details compressed = orig[i];
 106           compressed.extent_[DOWN] = old.extent_[DOWN];
 107           compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
 108           compressed.space_ += old.space_;
 109           compressed.inverse_hooke_ += old.inverse_hooke_;
 110
 111           /* we don't need the force_ field for the vertical spacing,
 112              so we use force_ = n to signal that the line was compressed,
 113              reducing the number of lines by n (and force_ = 0 otherwise).
 114              This makes uncompression much easier. */
 115           compressed.force_ = old.force_ + 1;
 116           ret.back () = compressed;
 117         }
 118       else
 119         {
 120           ret.push_back (orig[i]);
 121           ret.back ().force_ = 0;
 122         }
 123     }
 124   return ret;
 125 }
 126
 127 /* translate the number of systems-per-page into something meaningful for
 128    the uncompressed lines.
 129 */
 130 static vector<vsize>
 131 uncompress_solution (vector<vsize> const &systems_per_page,
 132                      vector<Line_details> const &compressed)
 133 {
 134   vector<vsize> ret;
 135   vsize start_sys = 0;
 136
 137   for (vsize i = 0; i < systems_per_page.size (); i++)
 138     {
 139       int compressed_count = 0;
 140       for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
 141         compressed_count += (int)compressed[j].force_;
 142
 143       ret.push_back (systems_per_page[i] + compressed_count);
 144       start_sys += systems_per_page[i];
 145     }
 146   return ret;
 147 }
 148
 149 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
 150    are by far the most common cases, we have special functions for them */
 151 static Spacing_result
 152 space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
 153 {
 154   Page_spacing space (page_height);
 155   Spacing_result ret;
 156
 157   for (vsize i = 0; i < lines.size (); i++)
 158     space.append_system (lines[i]);
 159
 160   ret.systems_per_page_.push_back (lines.size ());
 161   ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
 162   ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
 163   ret.demerits_ = ret.force_.back () * ret.force_.back () + ret.penalty_;
 164
 165   return ret;
 166 }
 167
 168 static Spacing_result
 169 space_systems_on_2_pages (vector<Line_details> const &lines,
 170                           Real page_height,
 171                           bool ragged,
 172                           bool ragged_last)
 173 {
 174   /* if there is a forced break, this reduces to 2 1-page problems */
 175   for (vsize i = 0; i + 1 < lines.size (); i++)
 176     if (lines[i].page_permission_ == ly_symbol2scm ("force"))
 177       {
 178         vector<Line_details> lines1 (lines.begin (), lines.begin () + i + 1);
 179         vector<Line_details> lines2 (lines.begin () + i + 1, lines.end ());
 180         Spacing_result p1 = space_systems_on_1_page (lines1, page_height, ragged);
 181         Spacing_result p2 = space_systems_on_1_page (lines2, page_height, ragged || ragged_last);
 182
 183         p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
 184         p1.force_.push_back (p2.force_[0]);
 185         p1.penalty_ += p2.penalty_ - lines[i].turn_penalty_;
 186         p1.demerits_ += p2.demerits_ - lines[i].turn_penalty_;
 187         return p1;
 188       }
 189
 190   vector<Real> page1_force;
 191   vector<Real> page2_force;
 192   Page_spacing page1 (page_height);
 193   Page_spacing page2 (page_height);
 194
 195   page1_force.resize (lines.size () - 1, infinity_f);
 196   page2_force.resize (lines.size () - 1, infinity_f);
 197
 198   for (vsize i = 0; i < page1_force.size (); i++)
 199     {
 200       page1.append_system (lines[i]);
 201       page2.prepend_system (lines[lines.size () - 1 - i]);
 202       page1_force[i] = (ragged && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
 203
 204       if (ragged || ragged_last)
 205         page2_force[page2_force.size () - 1 - i] =
 206           (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
 207       else
 208         page2_force[page2_force.size () - 1 - i] = page2.force_;
 209     }
 210
 211   vsize best_sys_count = 1;
 212   Real best_demerits = infinity_f;
 213   for (vsize i = 0; i < page1_force.size (); i++)
 214     {
 215       Real dem = page1_force[i] * page1_force[i]
 216         + page2_force[i] * page2_force[i]
 217         + lines[i+1].page_penalty_
 218         + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
 219       if (dem < best_demerits)
 220         {
 221           best_demerits = dem;
 222           best_sys_count = i+1;
 223         }
 224     }
 225
 226   Spacing_result ret;
 227   ret.systems_per_page_.push_back (best_sys_count);
 228   ret.systems_per_page_.push_back (lines.size () - best_sys_count);
 229   ret.force_.push_back (page1_force[best_sys_count-1]);
 230   ret.force_.push_back (page2_force[best_sys_count-1]);
 231   ret.penalty_ = lines[best_sys_count-1].page_penalty_
 232     + lines.back ().page_penalty_
 233     + lines.back ().turn_penalty_;
 234   ret.demerits_ = best_demerits;
 235
 236   return ret;
 237 }
 238
 239 Page_spacer::Page_spacer (vector<Line_details> const &lines, Real page_height, bool ragged, bool ragged_last)
 240   : lines_ (lines)
 241 {
 242   page_height_ = page_height;
 243   max_page_count_ = 0;
 244   ragged_ = ragged;
 245   ragged_last_ = ragged_last;
 246 }
 247
 248 Spacing_result
 249 Page_spacer::solve (vsize page_count)
 250 {
 251   if (page_count > max_page_count_)
 252     resize (page_count);
 253
 254   Spacing_result ret;
 255   ret.force_.resize (page_count);
 256   ret.systems_per_page_.resize (page_count);
 257
 258   vsize system = lines_.size () - 1;
 259   vsize tack_onto_the_end = 0;
 260
 261   if (isinf (state_.at (system, page_count-1).demerits_))
 262     {
 263       programming_error ("tried to space systems on a bad number of pages");
 264       /* Usually, this means that we tried to cram too many systems into
 265          to few pages. To avoid crashing, we look for the largest number of
 266          systems that we can fit properly onto the right number of pages.
 267          All the systems that don't fit get tacked onto the last page.
 268       */
 269       vsize i;
 270       for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i--; )
 271         ;
 272
 273       if (i)
 274         {
 275           tack_onto_the_end = system - i;
 276           system = i;
 277         }
 278       else
 279         return Spacing_result (); /* couldn't salvage it -- probably going to crash */
 280     }
 281
 282   ret.penalty_ = state_.at (system, page_count-1).penalty_
 283     + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
 284
 285   ret.demerits_ = 0;
 286   for (vsize p = page_count; p--;)
 287     {
 288       assert (system != VPOS);
 289
 290       Page_spacing_node const &ps = state_.at (system, p);
 291       ret.force_[p] = ps.force_;
 292       ret.demerits_ += ps.force_ * ps.force_;
 293       if (p == 0)
 294         ret.systems_per_page_[p] = system + 1;
 295       else
 296         ret.systems_per_page_[p] = system - ps.prev_ + tack_onto_the_end;
 297       system = ps.prev_;
 298     }
 299   ret.demerits_ += ret.penalty_;
 300   return ret;
 301 }
 302
 303 void
 304 Page_spacer::resize (vsize page_count)
 305 {
 306   assert (page_count > 0);
 307
 308   if (max_page_count_ >= page_count)
 309     return;
 310
 311   state_.resize (lines_.size (), page_count, Page_spacing_node ());
 312   for (vsize page = max_page_count_; page < page_count; page++)
 313     for (vsize line = page; line < lines_.size (); line++)
 314       if (!calc_subproblem (page, line))
 315         break;
 316
 317   max_page_count_ = page_count;
 318 }
 319
 320 bool
 321 Page_spacer::calc_subproblem (vsize page, vsize line)
 322 {
 323   Page_spacing space (page_height_);
 324   Page_spacing_node &cur = state_.at (line, page);
 325   bool ragged = ragged_ || (ragged_last_ && line == lines_.size () - 1);
 326
 327   for (vsize page_start = line+1; page_start > page && page_start--;)
 328     {
 329       Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
 330
 331       space.prepend_system (lines_[page_start]);
 332       if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged)))
 333         break;
 334
 335       if (page > 0 || page_start == 0)
 336         {
 337           if (line == lines_.size () - 1 && ragged_last_ && space.force_ > 0)
 338             space.force_ = 0;
 339
 340           /* we may have to deal with single lines that are taller than a page */
 341           if (isinf (space.force_) && page_start == line)
 342             space.force_ = -200000;
 343
 344           Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
 345           Real penalty = 0;
 346           if (page_start > 0)
 347             penalty = lines_[page_start-1].page_penalty_
 348               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 349
 350           dem += penalty;
 351           if (dem < cur.demerits_ || page_start == line)
 352             {
 353               cur.demerits_ = dem;
 354               cur.force_ = space.force_;
 355               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 356               cur.prev_ = page_start - 1;
 357             }
 358         }
 359
 360       if (page_start > 0
 361           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
 362         break;
 363     }
 364   return !isinf (cur.demerits_);
 365 }
 366
 367 vsize
 368 min_page_count (vector<Line_details> const &uncompressed_lines,
 369                 Real page_height, bool ragged, bool ragged_last)
 370 {
 371   vsize ret = 1;
 372   Real cur_rod_height = 0;
 373   vector<Line_details> lines = compress_lines (uncompressed_lines);
 374
 375   assert (lines.size ());
 376   for (vsize i = lines.size (); i--;)
 377     {
 378       bool rag = ragged || (ragged_last && ret == 1);
 379       Real ext_len = lines[i].extent_.length ();
 380       Real next_height = cur_rod_height + ext_len
 381         + (rag ? line_space (lines[i]) : 0)
 382         + ((cur_rod_height > 0) ? lines[i].padding_: 0);
 383
 384       if ((next_height > page_height && cur_rod_height > 0)
 385           || (i + 1 < lines.size () && lines[i].page_permission_ == ly_symbol2scm ("force")))
 386         {
 387           ret++;
 388           cur_rod_height = ext_len + (rag ? line_space (lines[i]) : 0);
 389         }
 390       else
 391         cur_rod_height = next_height;
 392     }
 393
 394   return ret;
 395 }
 396
 397 Spacing_result
 398 space_systems_on_n_pages (vector<Line_details> const &lines,
 399                           vsize n,
 400                           Real page_height,
 401                           bool ragged,
 402                           bool ragged_last)
 403 {
 404   vector<Line_details> compressed_lines = compress_lines (lines);
 405   Spacing_result ret;
 406   assert (n >= min_page_count (lines, page_height, ragged, ragged_last));
 407
 408   if (n > compressed_lines.size ())
 409     return Spacing_result ();
 410   if (n == 1)
 411     ret = space_systems_on_1_page (compressed_lines, page_height, ragged || ragged_last);
 412   else if (n == 2)
 413     ret = space_systems_on_2_pages (compressed_lines, page_height, ragged, ragged_last);
 414
 415   Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
 416   ret = ps.solve (n);
 417
 418   ret.systems_per_page_ = uncompress_solution (ret.systems_per_page_, compressed_lines);
 419   return ret;
 420 }
 421
 422 Spacing_result
 423 space_systems_on_n_or_one_more_pages (vector<Line_details> const &lines,
 424                                       vsize n,
 425                                       Real page_height,
 426                                       Real odd_pages_penalty,
 427                                       bool ragged,
 428                                       bool ragged_last)
 429 {
 430   Spacing_result n_res = space_systems_on_n_pages (lines, n, page_height, ragged, ragged_last);
 431   Spacing_result m_res = space_systems_on_n_pages (lines, n+1, page_height, ragged, ragged_last);
 432   n_res.demerits_ += odd_pages_penalty;
 433   n_res.force_.back () += odd_pages_penalty;
 434
 435   if (n_res.demerits_ < m_res.demerits_)
 436     return n_res;
 437   return m_res;
 438 }
 439
 440 Spacing_result
 441 space_systems_on_best_pages (vector<Line_details> const &lines,
 442                              Real page_height,
 443                              Real odd_pages_penalty,
 444                              bool ragged,
 445                              bool ragged_last)
 446 {
 447   vector<Line_details> compressed_lines = compress_lines (lines);
 448   vsize min_p_count = min_page_count (compressed_lines, page_height, ragged, ragged_last);
 449
 450   Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
 451   Spacing_result best = ps.solve (min_p_count);
 452   best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
 453   best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
 454
 455   for (vsize i = min_p_count+1; i <= compressed_lines.size (); i++)
 456     {
 457       Spacing_result cur = ps.solve (i);
 458       cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
 459       if (cur.demerits_ < best.demerits_)
 460         best = cur;
 461     }
 462
 463   best.systems_per_page_ = uncompress_solution (best.systems_per_page_, compressed_lines);
 464   return best;
 465 }