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)
 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 (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, Real page_height)
 161 {
 162   /* if there is a forced break, this reduces to 2 1-page problems */
 163   for (vsize i = 0; i < lines.size () - 1; i++)
 164     if (lines[i].page_permission_ == ly_symbol2scm ("force"))
 165       {
 166         vector<Line_details> lines1 (lines.begin (), lines.begin () + i + 1);
 167         vector<Line_details> lines2 (lines.begin () + i + 1, lines.end ());
 168         Spacing_result p1 = space_systems_on_1_page (lines1, page_height);
 169         Spacing_result p2 = space_systems_on_1_page (lines2, page_height);
 170
 171         p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
 172         p1.force_.push_back (p2.force_[0]);
 173         p1.penalty_ += p2.penalty_ - lines[i].turn_penalty_;
 174         p1.demerits_ += p2.demerits_ - lines[i].turn_penalty_;
 175         return p1;
 176       }
 177
 178   vector<Real> page1_force;
 179   vector<Real> page2_force;
 180   Page_spacing page1 (page_height);
 181   Page_spacing page2 (page_height);
 182
 183   page1_force.resize (lines.size () - 1, infinity_f);
 184   page2_force.resize (lines.size () - 1, infinity_f);
 185
 186   for (vsize i = 0; i < page1_force.size (); i++)
 187     {
 188       page1.append_system (lines[i]);
 189       page2.prepend_system (lines[lines.size () - 1 - i]);
 190       page1_force[i] = page1.force_;
 191       page2_force[page2_force.size () - 1 - i] = page2.force_;
 192     }
 193
 194   vsize best_sys_count = 1;
 195   Real best_demerits = infinity_f;
 196   for (vsize i = 0; i < page1_force.size (); i++)
 197     {
 198       Real dem = page1_force[i] * page1_force[i]
 199         + page2_force[i] * page2_force[i]
 200         + lines[i+1].page_penalty_
 201         + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
 202       if (dem < best_demerits)
 203         {
 204           best_demerits = dem;
 205           best_sys_count = i+1;
 206         }
 207     }
 208
 209   Spacing_result ret;
 210   ret.systems_per_page_.push_back (best_sys_count);
 211   ret.systems_per_page_.push_back (lines.size () - best_sys_count);
 212   ret.force_.push_back (page1_force[best_sys_count-1]);
 213   ret.force_.push_back (page2_force[best_sys_count-1]);
 214   ret.penalty_ = lines[best_sys_count-1].page_penalty_
 215     + lines.back ().page_penalty_
 216     + lines.back ().turn_penalty_;
 217   ret.demerits_ = best_demerits;
 218
 219   return ret;
 220 }
 221
 222 /* for page_count > 2, we use a dynamic algorithm similar to
 223    constrained-breaking -- we have a class that stores the intermediate
 224    calculations so they can be reused for querying different page counts.
 225 */
 226
 227 class Page_spacer
 228 {
 229 public:
 230   Page_spacer (vector<Line_details> const &lines, Real page_height);
 231   Spacing_result solve (vsize page_count);
 232
 233 private:
 234   struct Page_spacing_node
 235   {
 236     Page_spacing_node ()
 237     {
 238       demerits_ = infinity_f;
 239       force_ = infinity_f;
 240       penalty_ = infinity_f;
 241       prev_ = VPOS;
 242     }
 243
 244     Real demerits_;
 245     Real force_;
 246     Real penalty_;
 247     vsize prev_;
 248   };
 249
 250   Real page_height_;
 251   vector<Line_details> lines_;
 252   Matrix<Page_spacing_node> state_;
 253   vsize max_page_count_;
 254
 255   void resize (vsize page_count);
 256   bool calc_subproblem (vsize page, vsize lines);
 257 };
 258
 259 Page_spacer::Page_spacer (vector<Line_details> const &lines, Real page_height)
 260   : lines_ (lines)
 261 {
 262   page_height_ = page_height;
 263   max_page_count_ = 0;
 264 }
 265
 266 Spacing_result
 267 Page_spacer::solve (vsize page_count)
 268 {
 269   if (page_count > max_page_count_)
 270     resize (page_count);
 271
 272   Spacing_result ret;
 273   ret.force_.resize (page_count);
 274   ret.systems_per_page_.resize (page_count);
 275
 276   vsize system = lines_.size () - 1;
 277
 278   ret.penalty_ = state_.at (system, page_count-1).penalty_
 279     + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
 280
 281   for (vsize p = page_count; p--;)
 282     {
 283       assert (system != VPOS);
 284
 285       Page_spacing_node const &ps = state_.at (system, p);
 286       ret.force_[p] = ps.force_;
 287       ret.demerits_ += ps.force_ * ps.force_;
 288       if (p == 0)
 289         ret.systems_per_page_[p] = system + 1;
 290       else
 291         ret.systems_per_page_[p] = system - ps.prev_;
 292       system = ps.prev_;
 293     }
 294   ret.demerits_ += ret.penalty_;
 295   return ret;
 296 }
 297
 298 void
 299 Page_spacer::resize (vsize page_count)
 300 {
 301   assert (page_count > 0);
 302
 303   if (max_page_count_ >= page_count)
 304     return;
 305
 306   state_.resize (lines_.size (), page_count, Page_spacing_node ());
 307   for (vsize page = max_page_count_; page < page_count; page++)
 308     for (vsize line = page; line < lines_.size (); line++)
 309       if (!calc_subproblem (page, line))
 310         break;
 311
 312   max_page_count_ = page_count;
 313 }
 314
 315 bool
 316 Page_spacer::calc_subproblem (vsize page, vsize line)
 317 {
 318   Page_spacing space (page_height_);
 319   Page_spacing_node &cur = state_.at (line, page);
 320
 321   for (vsize page_start = line+1; page_start > page && page_start--;)
 322     {
 323       Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
 324
 325       space.prepend_system (lines_[page_start]);
 326       if (isinf (space.force_))
 327         break;
 328
 329       if (page == 0 && page_start > 0)
 330         continue;
 331
 332       Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
 333       Real penalty = 0;
 334       if (page_start > 0)
 335         penalty = lines_[page_start-1].page_penalty_
 336           + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 337
 338       dem += penalty;
 339       if (dem < cur.demerits_)
 340         {
 341           cur.demerits_ = dem;
 342           cur.force_ = space.force_;
 343           cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
 344           cur.prev_ = page_start - 1;
 345         }
 346     }
 347   return !isinf (cur.demerits_);
 348 }
 349
 350 static vsize
 351 min_page_count (vector<Line_details> const &lines, Real page_height)
 352 {
 353   vsize ret = 1;
 354   Real cur_rod_height = 0;
 355
 356   for (vsize i = 0; i < lines.size (); i++)
 357     {
 358       Real next_height = cur_rod_height + lines[i].extent_.length ()
 359         + ((i > 0 && cur_rod_height > 0) ? lines[i-1].padding_: 0);
 360
 361       if ((next_height > page_height && cur_rod_height > 0)
 362           || (i > 0 && lines[i-1].page_permission_ == ly_symbol2scm ("force")))
 363         {
 364           ret++;
 365           cur_rod_height = lines[i].extent_.length ();
 366         }
 367       else
 368         cur_rod_height = next_height;
 369     }
 370   return ret;
 371 }
 372
 373 Spacing_result
 374 space_systems_on_min_pages (vector<Line_details> const &lines,
 375                             Real page_height,
 376                             Real odd_pages_penalty)
 377 {
 378   vector<Line_details> compressed_lines = compress_lines (lines);
 379   vsize min_p_count = min_page_count (compressed_lines, page_height);
 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);
 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);
 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);
 398   else
 399     {
 400       Page_spacer ps (compressed_lines, page_height);
 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 {
 428   vector<Line_details> compressed_lines = compress_lines (lines);
 429   vsize min_p_count = min_page_count (compressed_lines, page_height);
 430
 431   Page_spacer ps (compressed_lines, page_height);
 432   Spacing_result best = ps.solve (min_p_count);
 433   best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
 434
 435   for (vsize i = min_p_count+1; i <= compressed_lines.size (); i++)
 436     {
 437       Spacing_result cur = ps.solve (i);
 438       cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
 439       if (cur.demerits_ < best.demerits_)
 440         best = cur;
 441     }
 442
 443   best.systems_per_page_ = uncompress_solution (best.systems_per_page_, compressed_lines);
 444   return best;
 445 }