*/
#include "page-spacing.hh"
+
#include "matrix.hh"
+#include "warn.hh"
/*
A much simplified rods-and-springs problem.
for (vsize i = 0; i < orig.size (); i++)
{
- if (i < orig.size () - 1 && orig[i].page_permission_ == SCM_EOL)
+ if (ret.size () && ret.back ().page_permission_ == SCM_EOL)
{
- Line_details compressed = orig[i+1];
- compressed.extent_[DOWN] = orig[i].extent_[DOWN];
- compressed.extent_[UP] = orig[i].extent_[UP] + orig[i+1].extent_.length () + orig[i].padding_;
- compressed.space_ += orig[i].space_;
- compressed.inverse_hooke_ += orig[i].inverse_hooke_;
+ Line_details const &old = ret.back ();
+ Line_details compressed = orig[i];
+ compressed.extent_[DOWN] = old.extent_[DOWN];
+ compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
+ compressed.space_ += old.space_;
+ compressed.inverse_hooke_ += old.inverse_hooke_;
/* we don't need the force_ field for the vertical spacing,
- so we use force_ = -1 to signal that the line was compressed
- (and force_ = +1 otherwise).
+ so we use force_ = n to signal that the line was compressed,
+ reducing the number of lines by n (and force_ = 0 otherwise).
This makes uncompression much easier. */
- compressed.force_ = -1;
- ret.push_back (compressed);
- i++;
+ compressed.force_ = old.force_ + 1;
+ ret.back () = compressed;
}
else
{
ret.push_back (orig[i]);
- ret.back ().force_ = 1;
+ ret.back ().force_ = 0;
}
}
return ret;
{
int compressed_count = 0;
for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
- if (compressed[j].force_ < 0)
- compressed_count++;
+ compressed_count += (int)compressed[j].force_;
ret.push_back (systems_per_page[i] + compressed_count);
start_sys += systems_per_page[i];
/* 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 */
static Spacing_result
-space_systems_on_1_page (vector<Line_details> const &lines, Real page_height)
+space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
{
Page_spacing space (page_height);
Spacing_result ret;
space.append_system (lines[i]);
ret.systems_per_page_.push_back (lines.size ());
- ret.force_.push_back (space.force_);
+ ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
ret.demerits_ = ret.force_.back () * ret.force_.back () + ret.penalty_;
}
static Spacing_result
-space_systems_on_2_pages (vector<Line_details> const &lines, Real page_height)
+space_systems_on_2_pages (vector<Line_details> const &lines,
+ Real page_height,
+ bool ragged,
+ bool ragged_last)
{
/* if there is a forced break, this reduces to 2 1-page problems */
for (vsize i = 0; i < lines.size () - 1; i++)
{
vector<Line_details> lines1 (lines.begin (), lines.begin () + i + 1);
vector<Line_details> lines2 (lines.begin () + i + 1, lines.end ());
- Spacing_result p1 = space_systems_on_1_page (lines1, page_height);
- Spacing_result p2 = space_systems_on_1_page (lines2, page_height);
+ Spacing_result p1 = space_systems_on_1_page (lines1, page_height, ragged);
+ Spacing_result p2 = space_systems_on_1_page (lines2, page_height, ragged || ragged_last);
p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
p1.force_.push_back (p2.force_[0]);
{
page1.append_system (lines[i]);
page2.prepend_system (lines[lines.size () - 1 - i]);
- page1_force[i] = page1.force_;
- page2_force[page2_force.size () - 1 - i] = page2.force_;
+ page1_force[i] = (ragged && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
+
+ if (ragged || ragged_last)
+ page2_force[page2_force.size () - 1 - i] =
+ (page2.force_ < 0 && i < page1_force.size () - 1) ? infinity_f : 0;
+ else
+ page2_force[page2_force.size () - 1 - i] = page2.force_;
}
vsize best_sys_count = 1;
return ret;
}
-/* for page_count > 2, we use a dynamic algorithm similar to
- constrained-breaking -- we have a class that stores the intermediate
- calculations so they can be reused for querying different page counts.
-*/
-
-class Page_spacer
-{
-public:
- Page_spacer (vector<Line_details> const &lines, Real page_height);
- Spacing_result solve (vsize page_count);
-
-private:
- struct Page_spacing_node
- {
- Page_spacing_node ()
- {
- demerits_ = infinity_f;
- force_ = infinity_f;
- penalty_ = infinity_f;
- prev_ = VPOS;
- }
-
- Real demerits_;
- Real force_;
- Real penalty_;
- vsize prev_;
- };
-
- Real page_height_;
- vector<Line_details> lines_;
- Matrix<Page_spacing_node> state_;
- vsize max_page_count_;
-
- void resize (vsize page_count);
- bool calc_subproblem (vsize page, vsize lines);
-};
-
-Page_spacer::Page_spacer (vector<Line_details> const &lines, Real page_height)
+Page_spacer::Page_spacer (vector<Line_details> const &lines, Real page_height, bool ragged, bool ragged_last)
: lines_ (lines)
{
page_height_ = page_height;
max_page_count_ = 0;
+ ragged_ = ragged;
+ ragged_last_ = ragged_last;
}
Spacing_result
vsize system = lines_.size () - 1;
+ if (isinf (state_.at (system, page_count-1).demerits_))
+ {
+ programming_error ("tried to space systems on a bad number of pages");
+ return Spacing_result (); /* bad number of pages */
+ }
+
ret.penalty_ = state_.at (system, page_count-1).penalty_
+ lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
+ ret.demerits_ = 0;
for (vsize p = page_count; p--;)
{
assert (system != VPOS);
{
Page_spacing space (page_height_);
Page_spacing_node &cur = state_.at (line, page);
+ bool ragged = ragged_ || (ragged_last_ && line == lines_.size () - 1);
for (vsize page_start = line+1; page_start > page && page_start--;)
{
Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
space.prepend_system (lines_[page_start]);
- if (isinf (space.force_))
+ if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged)))
break;
- if (page == 0 && page_start > 0)
- continue;
+ if (page > 0 || page_start == 0)
+ {
+ if (line == lines_.size () - 1 && ragged_last_ && space.force_ > 0)
+ space.force_ = 0;
- Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
- Real penalty = 0;
- if (page_start > 0)
- penalty = lines_[page_start-1].page_penalty_
- + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
+ /* we may have to deal with single lines that are taller than a page */
+ if (isinf (space.force_) && page_start == line)
+ space.force_ = -200000;
- dem += penalty;
- if (dem < cur.demerits_)
- {
- cur.demerits_ = dem;
- cur.force_ = space.force_;
- cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
- cur.prev_ = page_start - 1;
+ Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
+ Real penalty = 0;
+ if (page_start > 0)
+ penalty = lines_[page_start-1].page_penalty_
+ + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
+
+ dem += penalty;
+ if (dem < cur.demerits_ || page_start == line)
+ {
+ cur.demerits_ = dem;
+ cur.force_ = space.force_;
+ cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
+ cur.prev_ = page_start - 1;
+ }
}
+
+ if (page_start > 0
+ && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
+ break;
}
return !isinf (cur.demerits_);
}
-static vsize
-min_page_count (vector<Line_details> const &lines, Real page_height)
+vsize
+min_page_count (vector<Line_details> const &uncompressed_lines,
+ Real page_height, bool ragged, bool ragged_last)
{
vsize ret = 1;
Real cur_rod_height = 0;
+ vector<Line_details> lines = compress_lines (uncompressed_lines);
- for (vsize i = 0; i < lines.size (); i++)
+ assert (lines.size ());
+ for (vsize i = lines.size (); i--;)
{
- Real next_height = cur_rod_height + lines[i].extent_.length ()
- + ((i > 0 && cur_rod_height > 0) ? lines[i-1].padding_: 0);
+ bool rag = ragged || (ragged_last && ret == 1);
+ Real ext_len = lines[i].extent_.length ();
+ Real next_height = cur_rod_height + ext_len
+ + (rag ? lines[i].space_ : 0)
+ + ((cur_rod_height > 0) ? lines[i].padding_: 0);
if ((next_height > page_height && cur_rod_height > 0)
- || (i > 0 && lines[i-1].page_permission_ == ly_symbol2scm ("force")))
+ || (i < lines.size () - 1 && lines[i].page_permission_ == ly_symbol2scm ("force")))
{
ret++;
- cur_rod_height = lines[i].extent_.length ();
+ cur_rod_height = ext_len + (rag ? lines[i].space_ : 0);
}
else
cur_rod_height = next_height;
}
+
return ret;
}
Spacing_result
-space_systems_on_min_pages (vector<Line_details> const &lines,
- Real page_height,
- Real odd_pages_penalty)
+space_systems_on_n_pages (vector<Line_details> const &lines,
+ vsize n,
+ Real page_height,
+ bool ragged,
+ bool ragged_last)
{
vector<Line_details> compressed_lines = compress_lines (lines);
- vsize min_p_count = min_page_count (compressed_lines, page_height);
Spacing_result ret;
+ assert (n >= min_page_count (lines, page_height, ragged, ragged_last));
- if (min_p_count == 1)
- {
- Spacing_result candidate1 = space_systems_on_1_page (compressed_lines, page_height);
- candidate1.force_.back () += odd_pages_penalty;
- candidate1.demerits_ += odd_pages_penalty;
- if (compressed_lines.size () == 1)
- ret = candidate1;
- else
- {
- Spacing_result candidate2 = space_systems_on_2_pages (compressed_lines, page_height);
- ret = (candidate1.demerits_ < candidate2.demerits_) ?
- candidate1 : candidate2;
- }
- }
- else if (min_p_count == 2)
- ret = space_systems_on_2_pages (compressed_lines, page_height);
- else
- {
- Page_spacer ps (compressed_lines, page_height);
- Spacing_result candidate1 = ps.solve (min_p_count);
- if (min_p_count % 2 == 0)
- ret = candidate1;
- else
- {
- candidate1.force_.back () += odd_pages_penalty;
- candidate1.demerits_ += odd_pages_penalty;
+ if (n > compressed_lines.size ())
+ return Spacing_result ();
+ if (n == 1)
+ ret = space_systems_on_1_page (compressed_lines, page_height, ragged || ragged_last);
+ else if (n == 2)
+ ret = space_systems_on_2_pages (compressed_lines, page_height, ragged, ragged_last);
+
+ Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
+ ret = ps.solve (n);
- if (min_p_count == compressed_lines.size ())
- ret = candidate1;
- else
- {
- Spacing_result candidate2 = ps.solve (min_p_count + 1);
- ret = (candidate1.demerits_ < candidate2.demerits_) ?
- candidate1 : candidate2;
- }
- }
- }
ret.systems_per_page_ = uncompress_solution (ret.systems_per_page_, compressed_lines);
return ret;
}
+Spacing_result
+space_systems_on_n_or_one_more_pages (vector<Line_details> const &lines,
+ vsize n,
+ Real page_height,
+ Real odd_pages_penalty,
+ bool ragged,
+ bool ragged_last)
+{
+ Spacing_result n_res = space_systems_on_n_pages (lines, n, page_height, ragged, ragged_last);
+ Spacing_result m_res = space_systems_on_n_pages (lines, n+1, page_height, ragged, ragged_last);
+ n_res.demerits_ += odd_pages_penalty;
+ n_res.force_.back () += odd_pages_penalty;
+
+ if (n_res.demerits_ < m_res.demerits_)
+ return n_res;
+ return m_res;
+}
+
Spacing_result
space_systems_on_best_pages (vector<Line_details> const &lines,
Real page_height,
- Real odd_pages_penalty)
+ Real odd_pages_penalty,
+ bool ragged,
+ bool ragged_last)
{
vector<Line_details> compressed_lines = compress_lines (lines);
- vsize min_p_count = min_page_count (compressed_lines, page_height);
+ vsize min_p_count = min_page_count (compressed_lines, page_height, ragged, ragged_last);
- Page_spacer ps (compressed_lines, page_height);
+ Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
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 <= compressed_lines.size (); i++)
projects / lilypond.git / blobdiff