- breaker_->min_whitespace_at_bottom_of_page (last_line_);
if (rod_height_ + last_line_.bottom_padding_ >= height)
- force_ = infinity_f;
+ force_ = -infinity_f;
else
force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_)
/ max (0.1, inverse_spring_k_);
void
Page_spacing::append_system (const Line_details &line)
{
- if (!rod_height_)
- first_line_ = line;
-
- rod_height_ += line.title_ ? last_line_.title_padding_ : last_line_.padding_;
+ if (rod_height_)
+ {
+ rod_height_ += line.tallness_;
+ }
+ else
+ {
+ rod_height_ += line.full_height ();
+ first_line_ = line;
+ }
- rod_height_ += line.extent_.length ();
- spring_len_ += line.space_;
+ // line.space_ measures the spring which goes from the bottom refpoint
+ // of one system to the top refpoint of the next. spring_len_ measures
+ // how much of that is stretchable.
+ Real refpoint_dist = last_line_.tallness_
+ + last_line_.refpoint_extent_[DOWN]
+ - line.refpoint_extent_[UP];
+ Real space = line.title_ ? last_line_.title_space_ : last_line_.space_;
+ spring_len_ += max (0.0, space - refpoint_dist);
inverse_spring_k_ += line.inverse_hooke_;
last_line_ = line;
void
Page_spacing::prepend_system (const Line_details &line)
{
- if (rod_height_)
- rod_height_ += first_line_.title_ ? line.title_padding_ : line.padding_;
- else
+ if (!rod_height_)
last_line_ = line;
- rod_height_ += line.extent_.length ();
- spring_len_ += line.space_;
+ rod_height_ -= first_line_.full_height ();
+ rod_height_ += first_line_.tallness_;
+ rod_height_ += line.full_height();
+
+ Real refpoint_dist = line.tallness_
+ + line.refpoint_extent_[DOWN]
+ - first_line_.refpoint_extent_[UP];
+ Real space = first_line_.title_ ? line.title_space_ : line.space_;
+ spring_len_ += max (0.0, space - refpoint_dist);
inverse_spring_k_ += line.inverse_hooke_;
first_line_ = line;
ragged_last_ = breaker->is_last () && breaker->ragged_last ();
}
+Page_spacing_result
+Page_spacer::solve ()
+{
+ if (simple_state_.empty ())
+ {
+ simple_state_.resize (lines_.size ());
+ for (vsize i = 0; i < lines_.size (); ++i)
+ calc_subproblem (VPOS, i);
+ }
+
+ Page_spacing_result ret;
+ ret.penalty_ = simple_state_.back ().penalty_
+ + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
+ ret.system_count_status_ = simple_state_.back ().system_count_status_;
+
+ vsize system = lines_.size () - 1;
+ while (system != VPOS)
+ {
+ Page_spacing_node const& cur = simple_state_[system];
+ vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
+
+ ret.force_.push_back (cur.force_);
+ ret.systems_per_page_.push_back (system_count);
+ ret.demerits_ += cur.force_ * cur.force_;
+ system = cur.prev_;
+ }
+
+ reverse (ret.force_);
+ reverse (ret.systems_per_page_);
+ return ret;
+}
+
Page_spacing_result
Page_spacer::solve (vsize page_count)
{
ret.force_.resize (page_count);
ret.systems_per_page_.resize (page_count);
+ ret.system_count_status_ = state_.at (system, page_count-1).system_count_status_;
ret.penalty_ = state_.at (system, page_count-1).penalty_
+ lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
// we have previously called calc_subproblem(page-1, k) for every k < LINE.
//
// This algorithm is similar to the constrained-breaking algorithm.
+//
+// If page == VPOS, we act on simple_state_ instead of state_. This is useful if
+// we don't want to constrain the number of pages that the solution has. In this
+// case, the algorithm looks more like the page-turn-page-breaking algorithm. But
+// the subproblems look similar for both, so we reuse this method.
bool
Page_spacer::calc_subproblem (vsize page, vsize line)
{
bool last = line == lines_.size () - 1;
- Page_spacing space (breaker_->page_height (page + first_page_num_, last),
+
+ // Note: if page == VPOS then we don't actually know yet which page number we're
+ // working on, so we have to recalculate the page height in the loop. Therefore
+ // our early-exit condition from the loop depends on paper_height rather than
+ // page_height (ie. we break only if we would overfill a page without margins
+ // or headers/footers). Otherwise, the algorithm would not be optimal:
+ // if our page has a very large header then perhaps
+ // we should look ahead a few systems in order to find the best solution. A
+ // good example of this is input/regression/page-spacing-tall-headfoot.ly
+ vsize page_num = page == VPOS ? 0 : page;
+ Real paper_height = breaker_->paper_height ();
+ Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
breaker_);
- Page_spacing_node &cur = state_.at (line, page);
+ Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
bool ragged = ragged_ || (ragged_last_ && last);
int line_count = 0;
- for (vsize page_start = line+1; page_start > page && page_start--;)
+ for (vsize page_start = line+1; page_start > page_num && page_start--;)
{
- Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
+ Page_spacing_node const *prev = 0;
+
+ if (page == VPOS)
+ {
+ if (page_start > 0)
+ {
+ prev = &simple_state_[page_start-1];
+ space.resize (breaker_->page_height (prev->page_ + 1, last));
+ }
+ else
+ space.resize (breaker_->page_height (first_page_num_, last));
+ }
+ else if (page > 0)
+ prev = &state_.at (page_start-1, page-1);
space.prepend_system (lines_[page_start]);
+ bool overfull = (space.rod_height_ > paper_height
+ || (ragged
+ && (space.rod_height_ + space.spring_len_ > paper_height)));
// This 'if' statement is a little hard to parse. It won't consider this configuration
// if it is overfull unless the current configuration is the first one with this start
// point. We also make an exception (and consider this configuration) if the previous
// configuration we tried had fewer lines than min-systems-per-page.
if (!breaker_->too_few_lines (line_count)
&& page_start < line
- && (isinf (space.force_) || (space.force_ < 0 && ragged)))
+ && overfull)
break;
line_count += lines_[page_start].compressed_nontitle_lines_count_;
space.force_ = 0;
Real demerits = space.force_ * space.force_;
- /* If a single line is taller than a page, we need to consider it as
- a possible solution (but we give it a very bad score). */
- if (isinf (space.force_) && page_start == line)
- demerits = BAD_SPACING_PENALTY;
+
+ // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
+ // is overfull. This ensures that TERRIBLE_SPACING_PENALTY takes
+ // precedence over overfull pages.
+ demerits = min (demerits, BAD_SPACING_PENALTY);
demerits += (prev ? prev->demerits_ : 0);
Real penalty = breaker_->line_count_penalty (line_count);
cur.system_count_status_ = breaker_->line_count_status (line_count)
| (prev ? prev->system_count_status_ : 0);
cur.prev_ = page_start - 1;
+ cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
}
}
projects / lilypond.git / blobdiff