+
+void
+Page_breaking::compute_line_heights ()
+{
+ Real prev_hanging = 0;
+ Real prev_hanging_begin = 0;
+ Real prev_hanging_rest = 0;
+
+ // refpoint_hanging is the y coordinate of the origin of this system.
+ // It may not be the same as refpoint_extent[UP], which is the
+ // refpoint of the first spaceable staff in this system.
+ Real prev_refpoint_hanging = 0;
+ for (vsize i = 0; i < cached_line_details_.size (); i++)
+ {
+ Line_details &cur = cached_line_details_[i];
+ Line_shape shape = cur.shape_;
+ Real a = shape.begin_[UP];
+ Real b = shape.rest_[UP];
+ bool title = cur.title_;
+ Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
+
+ if (i > 0)
+ {
+ Real padding = 0;
+ Line_details const &prev = cached_line_details_[i - 1];
+ if (!cur.tight_spacing_)
+ padding = title
+ ? prev.title_padding_
+ : prev.padding_;
+ Real min_dist = title
+ ? prev.title_min_distance_
+ : prev.min_distance_;
+ refpoint_hanging = max (refpoint_hanging + padding,
+ prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
+ + cur.refpoint_extent_[UP] + min_dist);
+ }
+
+ Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
+ Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
+ Real hanging = max (hanging_begin, hanging_rest);
+ cur.tallness_ = hanging - prev_hanging;
+ prev_hanging = hanging;
+ prev_hanging_begin = hanging_begin;
+ prev_hanging_rest = hanging_rest;
+ prev_refpoint_hanging = refpoint_hanging;
+ }
+}
+
+vsize
+Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
+{
+ vsize ret = 1;
+ vsize page_starter = 0;
+ Real cur_rod_height = 0;
+ Real cur_spring_height = 0;
+ Real cur_page_height = page_height (first_page_num, false);
+ int line_count = 0;
+
+ cache_line_details (configuration);
+
+ if (cached_line_details_.size ())
+ cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
+
+ for (vsize i = 0; i < cached_line_details_.size (); i++)
+ {
+ Line_details const &cur = cached_line_details_[i];
+ Line_details const *const prev = (i > 0) ? &cached_line_details_[i - 1] : 0;
+ Real ext_len;
+ if (cur_rod_height > 0)
+ ext_len = cur.tallness_;
+ else
+ ext_len = cur.full_height ();
+
+ Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
+ Real next_rod_height = cur_rod_height + ext_len;
+ Real next_spring_height = cur_spring_height + spring_len;
+ Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
+ + min_whitespace_at_bottom_of_page (cur);
+ int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
+
+ if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
+ || too_many_lines (next_line_count)
+ || (prev && scm_is_eq (prev->page_permission_, ly_symbol2scm ("force"))))
+ {
+ line_count = cur.compressed_nontitle_lines_count_;
+ cur_rod_height = cur.full_height ();
+ cur_spring_height = 0;
+ page_starter = i;
+
+ cur_page_height = page_height (first_page_num + ret, false);
+ cur_page_height -= min_whitespace_at_top_of_page (cur);
+
+ ret++;
+ }
+ else
+ {
+ cur_rod_height = next_rod_height;
+ cur_spring_height = next_spring_height;
+ line_count = next_line_count;
+ }
+ }
+
+ /* 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.
+ */
+
+ if (is_last ())
+ {
+ cur_page_height = page_height (first_page_num + ret - 1, true);
+ cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
+ cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
+
+ if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
+ && cur_rod_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 ().full_height ())
+ ret++;
+ assert (ret <= cached_line_details_.size ());
+ }
+
+ return ret;
+}
+
+// If systems_per_page_ is positive, we don't really try to space on N pages;
+// we just put the requested number of systems on each page and penalize
+// if the result doesn't have N pages.
+Page_spacing_result
+Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
+{
+ Page_spacing_result ret;
+
+ if (systems_per_page_ > 0)
+ {
+ Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
+ ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
+ return 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;
+
+ if (is_last ())
+ penalty_sym = ly_symbol2scm ("blank-last-page-penalty");
+ else if (ends_score ())
+ penalty_sym = ly_symbol2scm ("blank-after-score-page-penalty");
+ else
+ penalty_sym = ly_symbol2scm ("blank-page-penalty");
+
+ Break_position const &pos = breaks_[current_end_breakpoint_];
+ if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
+ return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
+
+ return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
+}
+
+// If systems_per_page_ is positive, we don't really try to space on N
+// or N+1 pages; see the comment to space_systems_on_n_pages.
+Page_spacing_result
+Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
+ Real penalty_for_fewer_pages)
+{
+ Page_spacing_result n_res;
+ Page_spacing_result m_res;
+
+ if (systems_per_page_ > 0)
+ {
+ Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
+ ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n - 1)) ? 0 : BAD_SPACING_PENALTY;
+ return ret;
+ }
+
+ 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 page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
+ n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
+
+ if (n_res.force_.size ())
+ n_res.force_.back () += penalty_for_fewer_pages;
+
+ 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)
+{
+ if (systems_per_page_ > 0)
+ return space_systems_with_fixed_number_per_page (configuration, first_page_num);
+
+ cache_line_details (configuration);
+ Page_spacer ps (cached_line_details_, first_page_num, this);
+
+ return finalize_spacing_result (configuration, ps.solve ());
+}
+
+Page_spacing_result
+Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
+ vsize first_page_num)
+{
+ Page_spacing_result res;
+ Page_spacing space (page_height (first_page_num, false), this);
+ vsize line = 0;
+ vsize page = 0;
+ vsize page_first_line = 0;
+
+ cache_line_details (configuration);
+ while (line < cached_line_details_.size ())
+ {
+ page++;
+ space.clear ();
+ space.resize (page_height (first_page_num + page, false));
+
+ int system_count_on_this_page = 0;
+ while (system_count_on_this_page < systems_per_page_
+ && line < cached_line_details_.size ())
+ {
+ Line_details const &cur_line = cached_line_details_[line];
+ space.append_system (cur_line);
+ system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
+ line++;
+
+ if (scm_is_eq (cur_line.page_permission_, ly_symbol2scm ("force")))
+ break;
+ }
+
+ res.systems_per_page_.push_back (line - page_first_line);
+
+ res.force_.push_back (space.force_);
+ res.penalty_ += cached_line_details_[line - 1].page_penalty_;
+ if (system_count_on_this_page != systems_per_page_)
+ {
+ res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
+ res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
+ ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
+ }
+
+ page_first_line = line;
+ }
+
+ /* Recalculate forces for the last page because we know now that is
+ really the last page. */
+ space.resize (page_height (first_page_num + page, true));
+ res.force_.back () = space.force_;
+ return finalize_spacing_result (configuration, res);
+}
+
+Page_spacing_result
+Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
+{
+ // TODO: add support for min/max-systems-per-page.
+ Page_spacing_result res;
+ vsize page = 0;
+ vsize page_first_line = 0;
+ Page_spacing space (page_height (first_page_num, false), this);
+
+ 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)
+ && scm_is_eq (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_demerits = res.penalty_;
+ 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 = ragged () ? res.force_.size () - 1 : 0;
+ i < res.force_.size () - (is_last () && ragged_last ());
+ i++)
+ {
+ Real f = res.force_[i];
+
+ page_demerits += min (f * f, BAD_SPACING_PENALTY);
+ }
+
+ /* 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_demerits * 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, this);
+ Page_spacing_result ret;
+ int line_count = 0;
+
+ for (vsize i = 0; i < lines.size (); i++)
+ {
+ space.append_system (lines[i]);
+ line_count += lines[i].compressed_nontitle_lines_count_;
+ }
+
+ ret.systems_per_page_.push_back (lines.size ());
+ ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
+ ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
+ ret.system_count_status_ |= line_count_status (line_count);
+
+ /* 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 (scm_is_eq (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_;
+ p1.system_count_status_ |= p2.system_count_status_;
+ return p1;
+ }
+
+ vector<Real> page1_force;
+ vector<Real> page2_force;
+
+ // page1_penalty and page2_penalty store the penalties based
+ // on min-systems-per-page and max-systems-per-page.
+ vector<Real> page1_penalty;
+ vector<Real> page2_penalty;
+
+ // page1_status and page2_status keep track of whether the min-systems-per-page
+ // and max-systems-per-page constraints are satisfied.
+ vector<int> page1_status;
+ vector<int> page2_status;
+
+ Page_spacing page1 (page1_height, this);
+ Page_spacing page2 (page2_height, this);
+ int page1_line_count = 0;
+ int page2_line_count = 0;
+
+ page1_force.resize (cached_line_details_.size () - 1, infinity_f);
+ page2_force.resize (cached_line_details_.size () - 1, infinity_f);
+ page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
+ page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
+ page1_status.resize (cached_line_details_.size () - 1, 0);
+ page2_status.resize (cached_line_details_.size () - 1, 0);
+
+ /* 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_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
+ page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
+
+ page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
+ page1_penalty[i] = line_count_penalty (page1_line_count);
+ page1_status[i] = line_count_status (page1_line_count);
+
+ if (ragged1)
+ page2_force[page2_force.size () - 1 - i]
+ = (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
+ else if (ragged2 && page2.force_ > 0)
+ page2_force[page2_force.size () - 1 - i] = 0.0;
+ else
+ page2_force[page2_force.size () - 1 - i] = page2.force_;
+ page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
+ page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
+ }
+
+ /* 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];
+
+ // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
+ // constraints. That is, we penalize harshly when they don't happen
+ // but we don't completely reject.
+ Real dem = f
+ + page1_penalty[i] + page2_penalty[i]
+ + 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.system_count_status_ = page1_status[best_sys_count - 1] | page2_status[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_
+ + page1_penalty[best_sys_count - 1] + page2_penalty[best_sys_count - 1];
+
+ /* 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 ();
+}
+
+bool
+Page_breaking::ends_score () const
+{
+ return breaks_[current_end_breakpoint_].score_ender_;
+}
+
+vsize
+Page_breaking::last_break_position () const
+{
+ return breaks_.size () - 1;
+}
+
+// This gives the minimum distance between the top of the
+// printable area (ie. the bottom of the top-margin) and
+// the extent box of the topmost system.
+Real
+Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
+{
+ SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
+ if (line.title_)
+ first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
+
+ Real min_distance = -infinity_f;
+ Real padding = 0;
+
+ Page_layout_problem::read_spacing_spec (first_system_spacing,
+ &min_distance,
+ ly_symbol2scm ("minimum-distance"));
+ Page_layout_problem::read_spacing_spec (first_system_spacing,
+ &padding,
+ ly_symbol2scm ("padding"));
+
+ // FIXME: take into account the height of the header
+ Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
+ return max (0.0, max (padding, min_distance - translate));
+}
+
+Real
+Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
+{
+ SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
+ Real min_distance = -infinity_f;
+ Real padding = 0;
+
+ Page_layout_problem::read_spacing_spec (last_system_spacing,
+ &min_distance,
+ ly_symbol2scm ("minimum-distance"));
+ Page_layout_problem::read_spacing_spec (last_system_spacing,
+ &padding,
+ ly_symbol2scm ("padding"));
+
+ // FIXME: take into account the height of the footer
+ Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
+ return max (0.0, max (padding, min_distance + translate));
+}
+
+int
+Page_breaking::orphan_penalty () const
+{
+ return orphan_penalty_;
+}