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