+
+vsize
+Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
+{
+ vsize ret = 1;
+ Real cur_rod_height = 0;
+ Real cur_spring_height = 0;
+ Real cur_page_height = page_height (first_page_num, false);
+
+ cache_line_details (configuration);
+ for (vsize i = 0; i < cached_line_details_.size (); i++)
+ {
+ Real ext_len = cached_line_details_[i].extent_.length ();
+ Real next_rod_height = cur_rod_height + ext_len
+ + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
+ Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
+ Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
+
+
+ if ((next_height > cur_page_height && cur_rod_height > 0)
+ || (i > 0
+ && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
+ {
+ cur_rod_height = ext_len;
+ cur_spring_height = cached_line_details_[i].space_;
+ cur_page_height = page_height (first_page_num + ret, false);
+ ret++;
+ }
+ else
+ {
+ cur_rod_height = next_rod_height;
+ cur_spring_height = next_spring_height;
+ }
+ }
+
+ /* there are two potential problems with the last page (because we didn't know
+ it was the last page until after we managed to fit all the systems to it):
+ - we are ragged-last but the last page has a compressed spring
+ - the value returned by page_height (num, true) is smaller than the
+ value returned by page_height (num, false) and it causes the page not to
+ fit.
+
+ In either case, we just need to add one more page. This is because the last
+ line will always fit on the extra page and by adding one more page to the
+ end, the previous page is no longer the last page, so our previous
+ calculations that treated it as a non-last page were ok.
+ */
+
+ cur_page_height = page_height (first_page_num + ret - 1, true);
+ Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
+ if (cur_height > cur_page_height
+ /* don't increase the page count if the last page had only one system */
+ && cur_rod_height > cached_line_details_.back ().extent_.length ())
+ ret++;
+
+ assert (ret <= cached_line_details_.size ());
+ return ret;
+}
+
+Page_spacing_result
+Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
+{
+ Page_spacing_result ret;
+
+ cache_line_details (configuration);
+ bool valid_n = (n >= min_page_count (configuration, first_page_num)
+ && n <= cached_line_details_.size ());
+
+ if (!valid_n)
+ programming_error ("number of pages is out of bounds");
+
+ if (n == 1 && valid_n)
+ ret = space_systems_on_1_page (cached_line_details_,
+ page_height (first_page_num, is_last ()),
+ ragged () || (is_last () && ragged_last ()));
+ else if (n == 2 && valid_n)
+ ret = space_systems_on_2_pages (configuration, first_page_num);
+ else
+ {
+ Page_spacer ps (cached_line_details_, first_page_num, this);
+ ret = ps.solve (n);
+ }
+
+ return finalize_spacing_result (configuration, ret);
+}
+
+Real
+Page_breaking::blank_page_penalty () const
+{
+ SCM penalty_sym = is_last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
+ return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
+}
+
+Page_spacing_result
+Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
+{
+ Page_spacing_result n_res;
+ Page_spacing_result m_res;
+
+ cache_line_details (configuration);
+ vsize min_p_count = min_page_count (configuration, first_page_num);
+ bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
+
+ if (!valid_n)
+ programming_error ("both page counts are out of bounds");
+
+ if (n == 1 && valid_n)
+ {
+ bool rag = ragged () || (is_last () && ragged_last ());
+ Real height = page_height (first_page_num, is_last ());
+
+ if (1 >= min_p_count)
+ n_res = space_systems_on_1_page (cached_line_details_, height, rag);
+ if (1 < cached_line_details_.size ())
+ m_res = space_systems_on_2_pages (configuration, first_page_num);
+ }
+ else
+ {
+ Page_spacer ps (cached_line_details_, first_page_num, this);
+
+ if (n >= min_p_count || !valid_n)
+ n_res = ps.solve (n);
+ if (n < cached_line_details_.size () || !valid_n)
+ m_res = ps.solve (n+1);
+ }
+
+ m_res = finalize_spacing_result (configuration, m_res);
+ n_res = finalize_spacing_result (configuration, n_res);
+
+ Real penalty = blank_page_penalty ();
+ n_res.demerits_ += penalty;
+
+ if (n_res.force_.size ())
+ n_res.force_.back () += penalty;
+
+ return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
+}
+
+Page_spacing_result
+Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
+{
+ vsize min_p_count = min_page_count (configuration, first_page_num);
+ Real odd_pages_penalty = blank_page_penalty ();
+
+ cache_line_details (configuration);
+ Page_spacer ps (cached_line_details_, first_page_num, this);
+ Page_spacing_result best = ps.solve (min_p_count);
+ best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
+ best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
+
+ for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
+ {
+ Page_spacing_result cur = ps.solve (i);
+ cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
+ if (cur.demerits_ < best.demerits_)
+ best = cur;
+ }
+
+ return finalize_spacing_result (configuration, best);
+}
+
+Page_spacing_result
+Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
+{
+ Page_spacing_result res;
+ vsize page = 0;
+ vsize page_first_line = 0;
+ Page_spacing space (page_height (first_page_num, false), page_top_space_);
+
+ cache_line_details (configuration);
+ for (vsize line = 0; line < cached_line_details_.size (); line++)
+ {
+ Real prev_force = space.force_;
+ space.append_system (cached_line_details_[line]);
+ if ((line > page_first_line)
+ && (isinf (space.force_)
+ || ((line > 0)
+ && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
+ {
+ res.systems_per_page_.push_back (line - page_first_line);
+ res.force_.push_back (prev_force);
+ res.penalty_ += cached_line_details_[line-1].page_penalty_;
+ page++;
+ space.resize (page_height (first_page_num + page, false));
+ space.clear ();
+ space.append_system (cached_line_details_[line]);
+ page_first_line = line;
+ }
+
+ if (line == cached_line_details_.size () - 1)
+ {
+ /* This is the last line */
+ /* When the last page height was computed, we did not know yet that it
+ * was the last one. If the systems put on it don't fit anymore, the last
+ * system is moved to a new page */
+ space.resize (page_height (first_page_num + page, true));
+ if ((line > page_first_line) && (isinf (space.force_)))
+ {
+ res.systems_per_page_.push_back (line - page_first_line);
+ res.force_.push_back (prev_force);
+ /* the last page containing the last line */
+ space.resize (page_height (first_page_num + page + 1, true));
+ space.clear ();
+ space.append_system (cached_line_details_[line]);
+ res.systems_per_page_.push_back (1);
+ res.force_.push_back (space.force_);
+ res.penalty_ += cached_line_details_[line-1].page_penalty_;
+ res.penalty_ += cached_line_details_[line].page_penalty_;
+ }
+ else
+ {
+ res.systems_per_page_.push_back (line + 1 - page_first_line);
+ res.force_.push_back (space.force_);
+ res.penalty_ += cached_line_details_[line].page_penalty_;
+ }
+ }
+ }
+ return finalize_spacing_result (configuration, res);
+}
+
+/* Calculate demerits and fix res.systems_per_page_ so that
+ it refers to the original line numbers, not the ones given by compress_lines (). */
+Page_spacing_result
+Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
+{
+ if (res.force_.empty ())
+ return res;
+
+ cache_line_details (configuration);
+ res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
+
+ Real line_force = 0;
+ Real line_penalty = 0;
+ Real page_force = 0;
+ Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
+
+ for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
+ {
+ line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
+ line_penalty += uncompressed_line_details_[i].break_penalty_;
+ }
+
+ for (vsize i = 0; i < res.force_.size (); i++)
+ {
+ Real f = res.force_[i];
+ if (isinf (f) && res.systems_per_page_[i] == 1)
+ f = 20000;
+
+ page_force += f * f;
+ }
+
+ /* for a while we tried averaging page and line forces across pages instead
+ of summing them, but it caused a problem: if there is a single page
+ with a very bad page force (for example because of a forced page break),
+ the page breaker will put in a _lot_ of pages so that the bad force
+ becomes averaged out over many pages. */
+ res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
+ return res;
+
+}
+
+/* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
+ are by far the most common cases, we have special functions for them.
+
+ space_systems_on_1_page has a different calling convention than most of the
+ space_systems functions. This is because space_systems_on_1_page is (unlike
+ the other space_systems functions) sometimes called on subsets of a full
+ configuration. */
+Page_spacing_result
+Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
+{
+ Page_spacing space (page_height, page_top_space_);
+ Page_spacing_result ret;
+
+ for (vsize i = 0; i < lines.size (); i++)
+ space.append_system (lines[i]);
+
+ ret.systems_per_page_.push_back (lines.size ());
+ ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
+ ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
+
+ /* don't do finalize_spacing_result () because we are only an internal function */
+ return ret;
+}
+
+Page_spacing_result
+Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
+{
+ Real page1_height = page_height (first_page_num, false);
+ Real page2_height = page_height (first_page_num + 1, is_last ());
+ bool ragged1 = ragged ();
+ bool ragged2 = ragged () || (is_last () && ragged_last ());
+
+ /* if there is a forced break, this reduces to 2 1-page problems */
+ cache_line_details (configuration);
+ for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
+ if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
+ {
+ vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
+ vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
+ Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
+ Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
+
+ p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
+ p1.force_.push_back (p2.force_[0]);
+ p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
+ return p1;
+ }
+
+ vector<Real> page1_force;
+ vector<Real> page2_force;
+ Page_spacing page1 (page1_height, page_top_space_);
+ Page_spacing page2 (page2_height, page_top_space_);
+
+ page1_force.resize (cached_line_details_.size () - 1, infinity_f);
+ page2_force.resize (cached_line_details_.size () - 1, infinity_f);
+
+ /* find the page 1 and page 2 forces for each page-breaking position */
+ for (vsize i = 0; i < page1_force.size (); i++)
+ {
+ page1.append_system (cached_line_details_[i]);
+ page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
+ page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
+
+ if (ragged2)
+ page2_force[page2_force.size () - 1 - i] =
+ (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
+ else
+ page2_force[page2_force.size () - 1 - i] = page2.force_;
+ }
+
+ /* find the position that minimises the sum of the page forces */
+ vsize best_sys_count = 1;
+ Real best_demerits = infinity_f;
+ for (vsize i = 0; i < page1_force.size (); i++)
+ {
+ Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
+ Real uneven = 2 * (page1_force[i] - page2_force[i]);
+ Real dem = uneven * uneven + f
+ + cached_line_details_[i+1].page_penalty_
+ + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
+ if (dem < best_demerits)
+ {
+ best_demerits = dem;
+ best_sys_count = i+1;
+ }
+ }
+
+ Page_spacing_result ret;
+ ret.systems_per_page_.push_back (best_sys_count);
+ ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
+ ret.force_.push_back (page1_force[best_sys_count-1]);
+ ret.force_.push_back (page2_force[best_sys_count-1]);
+ ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
+ + cached_line_details_.back ().page_penalty_
+ + cached_line_details_.back ().turn_penalty_;
+
+ /* don't do finalize_spacing_result () because we are only an internal function */
+ return ret;
+}
+
+bool
+Page_breaking::all_lines_stretched (vsize configuration)
+{
+ cache_line_details (configuration);
+ for (vsize i = 0; i < cached_line_details_.size (); i++)
+ if (cached_line_details_[i].force_ < 0)
+ return false;
+
+ return true;
+}
+
+Page_breaking::Line_division
+Page_breaking::current_configuration (vsize configuration_index) const
+{
+ return current_configurations_[configuration_index];
+}
+
+bool
+Page_breaking::is_last () const
+{
+ return current_end_breakpoint_ == last_break_position ();
+}
+
+vsize
+Page_breaking::last_break_position () const
+{
+ return breaks_.size () - 1;
+}