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