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