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   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 static vsize
 344 min_page_count (vector<Line_details> const &lines, Real page_height, bool ragged, bool ragged_last)
 345 {
 346   vsize ret = 1;
 347   Real cur_rod_height = 0;
 348
 349   assert (lines.size ());
 350   for (vsize i = lines.size (); i--;)
 351     {
 352       bool rag = ragged || (ragged_last && ret == 1);
 353       Real ext_len = lines[i].extent_.length ();
 354       Real next_height = cur_rod_height + ext_len
 355         + (rag ? lines[i].space_ : 0)
 356         + ((cur_rod_height > 0) ? lines[i].padding_: 0);
 357
 358       if ((next_height > page_height && cur_rod_height > 0)
 359           || (i > 0 && lines[i-1].page_permission_ == ly_symbol2scm ("force")))
 360         {
 361           ret++;
 362           cur_rod_height = ext_len + (rag ? lines[i].space_ : 0);
 363         }
 364       else
 365         cur_rod_height = next_height;
 366     }
 367
 368   return ret;
 369 }
 370
 371 Spacing_result
 372 space_systems_on_min_pages (vector<Line_details> const &lines,
 373                             Real page_height,
 374                             Real odd_pages_penalty,
 375                             bool ragged,
 376                             bool ragged_last)
 377 {
 378   vector<Line_details> compressed_lines = compress_lines (lines);
 379   vsize min_p_count = min_page_count (compressed_lines, page_height, ragged, ragged_last);
 380   Spacing_result ret;
 381
 382   if (min_p_count == 1)
 383     {
 384       Spacing_result candidate1 = space_systems_on_1_page (compressed_lines, page_height, ragged || ragged_last);
 385       candidate1.force_.back () += odd_pages_penalty;
 386       candidate1.demerits_ += odd_pages_penalty;
 387       if (compressed_lines.size () == 1)
 388         ret = candidate1;
 389       else
 390         {
 391           Spacing_result candidate2 = space_systems_on_2_pages (compressed_lines, page_height, ragged, ragged_last);
 392           ret = (candidate1.demerits_ < candidate2.demerits_) ?
 393             candidate1 : candidate2;
 394         }
 395     }
 396   else if (min_p_count == 2)
 397     ret = space_systems_on_2_pages (compressed_lines, page_height, ragged, ragged_last);
 398   else
 399     {
 400       Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
 401       Spacing_result candidate1 = ps.solve (min_p_count);
 402       if (min_p_count % 2 == 0)
 403         ret = candidate1;
 404       else
 405         {
 406           candidate1.force_.back () += odd_pages_penalty;
 407           candidate1.demerits_ += odd_pages_penalty;
 408
 409           if (min_p_count == compressed_lines.size ())
 410             ret = candidate1;
 411           else
 412             {
 413               Spacing_result candidate2 = ps.solve (min_p_count + 1);
 414               ret = (candidate1.demerits_ < candidate2.demerits_) ?
 415                 candidate1 : candidate2;
 416             }
 417         }
 418     }
 419   ret.systems_per_page_ = uncompress_solution (ret.systems_per_page_, compressed_lines);
 420   return ret;
 421 }
 422
 423 Spacing_result
 424 space_systems_on_best_pages (vector<Line_details> const &lines,
 425                              Real page_height,
 426                              Real odd_pages_penalty,
 427                              bool ragged,
 428                              bool ragged_last)
 429 {
 430   vector<Line_details> compressed_lines = compress_lines (lines);
 431   vsize min_p_count = min_page_count (compressed_lines, page_height, ragged, ragged_last);
 432
 433   Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
 434   Spacing_result best = ps.solve (min_p_count);
 435   best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
 436   best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
 437
 438   for (vsize i = min_p_count+1; i <= compressed_lines.size (); i++)
 439     {
 440       Spacing_result cur = ps.solve (i);
 441       cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
 442       if (cur.demerits_ < best.demerits_)
 443         best = cur;
 444     }
 445
 446   best.systems_per_page_ = uncompress_solution (best.systems_per_page_, compressed_lines);
 447   return best;
 448 }