source file of the GNU LilyPond music typesetter
- (c) 2006 Joe Neeman <joeneeman@gmail.com>
+ (c) 2006--2007 Joe Neeman <joeneeman@gmail.com>
*/
#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];
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++)
+ for (vsize i = 0; i + 1 < lines.size (); i++)
if (lines[i].page_permission_ == ly_symbol2scm ("force"))
{
vector<Line_details> lines1 (lines.begin (), lines.begin () + i + 1);
if (ragged || ragged_last)
page2_force[page2_force.size () - 1 - i] =
- (page2.force_ < 0 && i < page1_force.size () - 1) ? infinity_f : 0;
+ (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
else
page2_force[page2_force.size () - 1 - i] = page2.force_;
}
vsize system = lines_.size () - 1;
if (isinf (state_.at (system, page_count-1).demerits_))
- return Spacing_result (); /* bad number of pages */
-
- if (isinf (state_.at (system, page_count-1).demerits_))
- return Spacing_result (); /* bad number of pages */
+ {
+ 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);
if (line == lines_.size () - 1 && ragged_last_ && space.force_ > 0)
space.force_ = 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;
+
Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
Real penalty = 0;
if (page_start > 0)
+ (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
dem += penalty;
- if (dem < cur.demerits_)
+ if (dem < cur.demerits_ || page_start == line)
{
cur.demerits_ = dem;
cur.force_ = space.force_;
return !isinf (cur.demerits_);
}
-static vsize
-min_page_count (vector<Line_details> const &lines, Real page_height, bool ragged)
+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--;)
{
+ bool rag = ragged || (ragged_last && ret == 1);
Real ext_len = lines[i].extent_.length ();
- Real next_height = cur_rod_height
- + (ragged ? max (ext_len, lines[i].space_) : ext_len)
- + ((i > 0 && cur_rod_height > 0) ? lines[i-1].padding_: 0);
+ 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 + 1 < lines.size () && lines[i].page_permission_ == ly_symbol2scm ("force")))
{
ret++;
- cur_rod_height = ragged ? max (ext_len, lines[i].space_) : ext_len;
+ 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,
- bool ragged,
- bool ragged_last)
+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, ragged);
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, ragged || ragged_last);
- 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, ragged, ragged_last);
- ret = (candidate1.demerits_ < candidate2.demerits_) ?
- candidate1 : candidate2;
- }
- }
- else if (min_p_count == 2)
+ 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);
- else
- {
- Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
- 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 (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;
- }
- }
- }
+ Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
+ ret = ps.solve (n);
+
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,
bool ragged_last)
{
vector<Line_details> compressed_lines = compress_lines (lines);
- vsize min_p_count = min_page_count (compressed_lines, page_height, ragged);
+ vsize min_p_count = min_page_count (compressed_lines, page_height, ragged, ragged_last);
Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
Spacing_result best = ps.solve (min_p_count);