This introduces an algorithmic improvement and many cleanups in the page
breaking code. The algorithmic improvement is that we are able to adjust
line-counts on either side of a forced page break independently. This
code is contained in the Page_breaking class and abstracted nicely so
all subclasses can benefit.
"make web" works and output-distance.py doesn't find any changed files.
2006-08-17 Joe Neeman <[EMAIL PROTECTED]>
* lily/paper-column-engraver.cc (finalize): make the end of a score
breakable by default. This is to balance out a change in behaviour
of the page-turn-breaker which no longer makes the end of a score
breakable.
* lily/paper-book.cc (pages): set the systems_ once the pages are
broken
* lily/page-turn-page-breaking.cc (calc_subproblem): use the new
Page_breaking interface.
* lily/page-breaking.cc (class Page_breaking): make the interface
more consistent and provide abstractions for dealing with
Line_divisions.
* lily/optimal-page-breaking.cc (solve): use a more straightforward
algorithm. Use the new interface to Page_breaking.
Index: ChangeLog
===================================================================
RCS file: /sources/lilypond/lilypond/ChangeLog,v
retrieving revision 1.5241
diff -u -r1.5241 ChangeLog
--- ChangeLog 14 Aug 2006 08:30:20 -0000 1.5241
+++ ChangeLog 16 Aug 2006 21:35:04 -0000
@@ -1,3 +1,23 @@
+2006-08-17 Joe Neeman <[EMAIL PROTECTED]>
+
+ * lily/paper-column-engraver.cc (finalize): make the end of a score
+ breakable by default. This is to balance out a change in behaviour
+ of the page-turn-breaker which no longer makes the end of a score
+ breakable.
+
+ * lily/paper-book.cc (pages): set the systems_ once the pages are
+ broken
+
+ * lily/page-turn-page-breaking.cc (calc_subproblem): use the new
+ Page_breaking interface.
+
+ * lily/page-breaking.cc (class Page_breaking): make the interface
+ more consistent and provide abstractions for dealing with
+ Line_divisions.
+
+ * lily/optimal-page-breaking.cc (solve): use a more straightforward
+ algorithm. Use the new interface to Page_breaking.
+
2006-08-14 Mats Bengtsson <[EMAIL PROTECTED]>
* scripts/lilypond-book.py (output): Remove obsolete(!?)
Index: lily/optimal-page-breaking.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/optimal-page-breaking.cc,v
retrieving revision 1.1
diff -u -r1.1 optimal-page-breaking.cc
--- lily/optimal-page-breaking.cc 8 Aug 2006 10:01:22 -0000 1.1
+++ lily/optimal-page-breaking.cc 16 Aug 2006 21:35:04 -0000
@@ -1,5 +1,5 @@
/*
- optimal-page-breaking.hh -- implement a page-breaker that
+ optimal-page-breaking.cc -- implement a page-breaker that
will break pages in such a way that both horizontal and
vertical spacing will be acceptable
@@ -16,8 +16,15 @@
#include "prob.hh"
#include "system.hh"
+static bool
+break_p (Grob *g)
+{
+ (void) g; /* shutup warning */
+ return false;
+}
+
Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
- : Page_breaking (pb, false)
+ : Page_breaking (pb, break_p)
{
}
@@ -26,9 +33,9 @@
}
Spacing_result
-Optimal_page_breaking::try_page_spacing (vector<vsize> line_count)
+Optimal_page_breaking::try_page_spacing (Line_division const &line_count)
{
- vector<Line_details> lines = get_line_details (0, breaks_.size () - 1, line_count);
+ vector<Line_details> lines = line_details (0, breaks_.size () - 1, line_count);
Real page_h = page_height (1, false); // FIXME
SCM force_sym = ly_symbol2scm ("blank-last-page-force");
Real blank_force = robust_scm2double (book_->paper_->lookup_variable (force_sym), 0);
@@ -65,108 +72,60 @@
return ret;
}
-/* The algorithm is as follows:
- 1) break everything into its preferred number of lines
- 2) decrease the number of lines until we've decreased
- the number of pages
- 3) increase the number of lines until we've increased
- the number of pages
- Take the best score we've found
-*/
SCM
Optimal_page_breaking::solve ()
{
- vector<vsize> ideal_line_count;
- vector<vsize> max_line_count;
- vector<vsize> min_line_count;
- vector<vsize> last_best_line_count;
- vector<vsize> best_line_count;
- vsize last_line_total = 0;
-
- calc_system_count_bounds (0, breaks_.size () - 1, &min_line_count, &max_line_count);
- ideal_line_count.resize (all_.size (), 1);
- for (vsize i = 0; i < all_.size (); i++)
+ vsize end = breaks_.size () - 1;
+ vsize min_sys_count = min_system_count (0, end);
+ vsize max_sys_count = max_system_count (0, end);
+ vsize max_page_count = INT_MAX;
+ vsize cur_page_count = 0;
+ Spacing_result best;
+ Line_division best_division;
+ Line_division lower_bound;
+
+ for (vsize sys_count = min_sys_count;
+ cur_page_count <= max_page_count && sys_count <= max_sys_count;
+ sys_count++)
{
- if (all_[i].pscore_)
- ideal_line_count[i] = line_breaking_[i].get_best_solution (0, VPOS).size ();
- last_line_total += ideal_line_count[i];
- }
-
- Spacing_result best_result = try_page_spacing (ideal_line_count);
- vsize original_page_count = best_result.systems_per_page_.size ();
- best_line_count = ideal_line_count;
- last_best_line_count = ideal_line_count;
-
- Direction d = original_page_count > 1 ? DOWN : UP;
- vector<vector<vsize> > div;
- Spacing_result this_best_result;
- do {
- do {
- vector<vsize> blank;
-
- vector<vsize> this_best_line_count;
- this_best_result.demerits_ = infinity_f;
-
- last_line_total += d;
- div.clear ();
- divide_systems (last_line_total,
- d == DOWN ? min_line_count : last_best_line_count,
- d == DOWN ? last_best_line_count : max_line_count,
- &div, &blank);
-
- for (vsize i = 0; i < div.size (); i++)
+ Real this_best_demerits = infinity_f;
+ vector<Line_division> div = line_divisions (0, end, sys_count, lower_bound);
+ for (vsize d = 0; d < div.size (); d++)
{
- Spacing_result cur = try_page_spacing (div[i]);
- if (cur.demerits_ < this_best_result.demerits_)
+ Spacing_result cur = try_page_spacing (div[d]);
+ cur_page_count = cur.systems_per_page_.size ();
+ if (cur.demerits_ < best.demerits_)
{
- this_best_result = cur;
- this_best_line_count = div[i];
+ best = cur;
+ best_division = div[d];
}
- }
- last_best_line_count = this_best_line_count;
- if (this_best_result.demerits_ < best_result.demerits_)
- {
- best_line_count = this_best_line_count;
- best_result = this_best_result;
+ if (cur.demerits_ < this_best_demerits)
+ {
+ this_best_demerits = cur.demerits_;
+ lower_bound = div[d];
+ }
+
+ vector<Line_details> det = line_details (0, end, div[d]);
+ bool all_lines_stretched = true;
+ for (vsize i = 0; i < det.size (); i++)
+ if (det[i].force_ < 0)
+ all_lines_stretched = false;
+
+ if (all_lines_stretched)
+ max_page_count = cur_page_count + 1;
}
- } while (div.size () && this_best_result.systems_per_page_.size () == original_page_count);
+ }
- /* we're finished decreasing system count, let's try raising it */
- last_best_line_count = ideal_line_count;
- last_line_total = 0;
- for (vsize i = 0; i < ideal_line_count.size (); i++)
- last_line_total += ideal_line_count[i];
+ break_into_pieces (0, end, best_division);
+ vector<SCM> lines = systems ();
+ SCM lines_scm = SCM_EOL;
- } while (flip (&d) != DOWN);
+ for (vsize i = 0; i < lines.size (); i++)
+ lines_scm = scm_cons (lines[i], lines_scm);
+ lines_scm = scm_reverse (lines_scm);
- SCM lines = make_lines (best_line_count);
- SCM pages = make_pages (best_result.systems_per_page_, lines);
+ SCM pages = make_pages (best.systems_per_page_, lines_scm);
return pages;
}
-SCM
-Optimal_page_breaking::make_lines (vector<vsize> line_count)
-{
- assert (line_count.size () == all_.size ());
-
- SCM ret = SCM_EOL;
- for (vsize i = 0; i < all_.size (); i++)
- {
- if (all_[i].pscore_)
- {
- vector<Column_x_positions> line_brk = line_breaking_[i].get_solution (0, VPOS, line_count[i]);
- System *sys = all_[i].pscore_->root_system ();
-
- sys->break_into_pieces (line_brk);
- ret = scm_append (scm_list_2 (ret, scm_vector_to_list (sys->get_paper_systems ())));
- }
- else
- {
- SCM l = scm_cons (all_[i].prob_->self_scm (), SCM_EOL);
- ret = scm_append (scm_list_2 (ret, l));
- all_[i].prob_->unprotect ();
- }
- }
- return ret;
-}
Index: lily/page-breaking-scheme.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/page-breaking-scheme.cc,v
retrieving revision 1.1
diff -u -r1.1 page-breaking-scheme.cc
--- lily/page-breaking-scheme.cc 8 Aug 2006 10:01:22 -0000 1.1
+++ lily/page-breaking-scheme.cc 16 Aug 2006 21:35:04 -0000
@@ -28,3 +28,4 @@
Optimal_page_breaking b (unsmob_paper_book (pb));
return b.solve ();
}
+
Index: lily/page-breaking.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/page-breaking.cc,v
retrieving revision 1.1
diff -u -r1.1 page-breaking.cc
--- lily/page-breaking.cc 8 Aug 2006 10:01:22 -0000 1.1
+++ lily/page-breaking.cc 16 Aug 2006 21:35:05 -0000
@@ -1,6 +1,6 @@
/*
page-breaking.cc -- implement a superclass and utility
- functions for use by various page-breaking algorithms
+ functions shared by various page-breaking algorithms
source file of the GNU LilyPond music typesetter
@@ -19,27 +19,6 @@
#include "system.hh"
#include "warn.hh"
-System_spec::System_spec (Paper_score *ps, int break_count)
-{
- pscore_ = ps;
- prob_ = 0;
- score_break_count_ = break_count;
-}
-
-System_spec::System_spec (Prob *pb)
-{
- pscore_ = 0;
- prob_ = pb;
- score_break_count_ = 0;
-}
-
-System_spec::System_spec ()
-{
- pscore_ = 0;
- prob_ = 0;
- score_break_count_ = 0;
-}
-
/* for Page_breaking, the start index (when we are dealing with the stuff
between a pair of breakpoints) refers to the break_ index of the end of
the previous page. So the system index of the start of the current page
@@ -47,21 +26,22 @@
it. */
/* Turn a break index into the sys index that starts the next page */
-vsize Page_breaking::next_system (vsize start) const
+vsize Page_breaking::next_system (Break_position const &break_pos) const
{
- vsize sys = breaks_[start].sys_;
+ vsize sys = break_pos.sys_;
- if (sys == VPOS) /* beginning of the piece */
+ if (sys == VPOS) /* beginning of the book */
return 0;
- if (all_[sys].pscore_ && all_[sys].score_break_count_ > breaks_[start].score_break_)
+ if (all_[sys].pscore_ && !break_pos.score_ender_)
return sys; /* the score overflows the previous page */
return sys + 1; /* this page starts with a new sys */
}
-Page_breaking::Page_breaking (Paper_book *pb, bool allow_intra_score_breaks)
+Page_breaking::Page_breaking (Paper_book *pb, Break_p break_p)
{
book_ = pb;
- create_system_list (allow_intra_score_breaks);
+ create_system_list ();
+ find_chunks_and_breaks (break_p);
}
Page_breaking::~Page_breaking ()
@@ -70,67 +50,96 @@
/* translate indices into breaks_ into start-end parameters for the line breaker */
void
-Page_breaking::line_breaker_args (vsize i, vsize *start, vsize *end)
+Page_breaking::line_breaker_args (vsize sys,
+ Break_position const &start,
+ Break_position const &end,
+ vsize *line_breaker_start,
+ vsize *line_breaker_end)
{
- assert (all_[i].pscore_);
- assert (next_system (*start) <= i && i <= breaks_[*end].sys_);
+ assert (all_[sys].pscore_);
+ assert (next_system (start) <= sys && sys <= end.sys_);
- vsize start_col = 0;
- vsize end_col = VPOS;
-
- if (breaks_[*start].sys_ == i)
- start_col = breaks_[*start].score_break_;
- if (breaks_[*end].sys_ == i)
- end_col = breaks_[*end].score_break_;
+ if (start.sys_ == sys)
+ *line_breaker_start = start.score_break_;
+ else
+ *line_breaker_start = 0;
- assert (end_col && (end_col == VPOS || end_col <= all_[breaks_[*end].sys_].score_break_count_));
- *start = start_col;
- *end = end_col;
+ if (end.sys_ == sys)
+ *line_breaker_end = end.score_break_;
+ else
+ *line_breaker_end = VPOS;
}
-vector<Column_x_positions>
-Page_breaking::get_line_breaks (vsize i, vsize sys_count, vsize start, vsize end)
+void
+Page_breaking::break_into_pieces (vsize start_break, vsize end_break, Line_division const &div)
{
- assert (all_[i].pscore_);
- line_breaker_args (i, &start, &end);
- return line_breaking_[i].get_solution (start, end, sys_count);
+ vector<Break_position> chunks = chunk_list (start_break, end_break);
+ assert (chunks.size () == div.size () + 1);
+
+ for (vsize i = 0; i < chunks.size () - 1; i++)
+ {
+ vsize sys = next_system (chunks[i]);
+ if (all_[sys].pscore_)
+ {
+ vsize start;
+ vsize end;
+ line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
+
+ vector<Column_x_positions> pos = line_breaking_[sys].get_solution (start, end, div[i]);
+ all_[sys].pscore_->root_system ()->break_into_pieces (pos);
+ }
+ }
}
-vector<Line_details>
-Page_breaking::get_line_details (vsize start_break, vsize end_break, vector<vsize> const &div)
+vector<SCM>
+Page_breaking::systems ()
{
- vector<Line_details> ret;
-
- for (vsize i = next_system (start_break); i <= breaks_[end_break].sys_; i++)
+ vector<SCM> ret;
+ for (vsize sys = 0; sys < all_.size (); sys++)
{
- if (all_[i].pscore_)
+ if (all_[sys].pscore_)
{
- vsize div_index = i - next_system (start_break);
- vsize start = start_break;
- vsize end = end_break;
-
- line_breaker_args (i, &start, &end);
- vector<Line_details> l = line_breaking_[i].get_details (start, end, div[div_index]);
- ret.insert (ret.end (), l.begin (), l.end ());
+ SCM lines = all_[sys].pscore_->root_system ()->get_paper_systems ();
+ vsize line_count = scm_c_vector_length (lines);
+
+ for (vsize i = 0; i < line_count; i++)
+ ret.push_back (scm_c_vector_ref (lines, i));
}
else
- ret.push_back (Line_details (all_[i].prob_));
+ {
+ ret.push_back (all_[sys].prob_->self_scm ());
+ all_[sys].prob_->unprotect ();
+ }
}
return ret;
}
-vsize
-Page_breaking::get_min_systems (vsize i, vsize start, vsize end)
+vector<Line_details>
+Page_breaking::line_details (vsize start_break, vsize end_break, Line_division const &div)
{
- line_breaker_args (i, &start, &end);
- return line_breaking_[i].get_min_systems (start, end);
-}
+ vector<Break_position> chunks = chunk_list (start_break, end_break);
+ vector<Line_details> ret;
+ assert (chunks.size () == div.size () + 1);
-vsize
-Page_breaking::get_max_systems (vsize i, vsize start, vsize end)
-{
- line_breaker_args (i, &start, &end);
- return line_breaking_[i].get_max_systems (start, end);
+ for (vsize i = 0; i < chunks.size () - 1; i++)
+ {
+ vsize sys = next_system (chunks[i]);
+ if (all_[sys].pscore_)
+ {
+ vsize start;
+ vsize end;
+ line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
+
+ vector<Line_details> details = line_breaking_[sys].get_details (start, end, div[i]);
+ ret.insert (ret.end (), details.begin (), details.end ());
+ }
+ else
+ {
+ assert (div[i] == 1);
+ ret.push_back (Line_details (all_[sys].prob_));
+ }
+ }
+ return ret;
}
Real
@@ -179,105 +188,181 @@
return scm_reverse (ret);
}
-/* if allow_intra_score_breaks is false, that doesn't necessarily mean that there will
- be no page turns in the middle of a score, only that we don't give special
- consideration to any internal part of a score.
+/* The page-turn-page-breaker needs to have a line-breaker between any two
+ columns with non-NULL page-turn-permission.
+
+ The optimal-breaker needs to have a line-breaker between any two columns
+ with page-break-permission = 'force.
- Corollary: if allow_intra_score_breaks is false, any \pageTurn or \noPageTurn commands
- in the middle of a score will be ignored.
+ By using a grob predicate, we can accommodate both of these uses.
*/
void
-Page_breaking::create_system_list (bool allow_intra_score_breaks)
+Page_breaking::create_system_list ()
{
- breaks_.push_back (Break_position ());
-
SCM specs = book_->get_system_specs ();
for (SCM s = specs; s != SCM_EOL; s = scm_cdr (s))
{
if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
- {
- /* add a breakpoint at the end of the last score, if necessary */
- if (all_.size () && all_.back ().pscore_)
- breaks_.push_back (Break_position (all_.size () - 1,
- all_.back ().score_break_count_));
-
- vector<vsize> score_brk;
- if (allow_intra_score_breaks)
- score_brk = find_page_break_indices (ps);
-
- all_.push_back (System_spec (ps, score_brk.size () + 1));
-
- for (vsize i = 0; i < score_brk.size(); i++)
- breaks_.push_back (Break_position (all_.size () - 1, i + 1));
-
- /* include a line breaker at the start of the score */
- score_brk.insert (score_brk.begin (), 0);
- line_breaking_.push_back (Constrained_breaking (score_brk));
- line_breaking_.back ().set_pscore (ps);
- }
+ all_.push_back (System_spec (ps));
else
{
Prob *pb = unsmob_prob (scm_car (s));
assert (pb);
pb->protect ();
- // ignore penalties (from break-before) in favour of using \pageBreak at the
- // end of the score
- if (all_.size () && all_.back ().pscore_)
- breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_));
all_.push_back (System_spec (pb));
- line_breaking_.push_back (Constrained_breaking ());
}
}
+}
- /* add the ending breakpoint */
- if (all_.back ().pscore_)
- breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_));
- else
- breaks_.push_back (Break_position (all_.size () - 1));
+void Page_breaking::find_chunks_and_breaks (Break_p break_p)
+{
+ SCM force_sym = ly_symbol2scm ("force");
+
+ chunks_.push_back (Break_position ());
+ breaks_.push_back (Break_position ());
+
+ for (vsize i = 0; i < all_.size (); i++)
+ {
+ if (all_[i].pscore_)
+ {
+ vector<Grob*> cols = all_[i].pscore_->root_system ()->columns ();
+ vector<vsize> line_breaker_columns;
+ line_breaker_columns.push_back (0);
+
+ for (vsize j = 0; j < cols.size (); j++)
+ {
+ bool last = j == cols.size () - 1;
+ bool break_point = break_p (cols[j]);
+ bool chunk_end = cols[i]->get_property ("page-break-permission") == force_sym;
+ Break_position cur_pos = Break_position (i,
+ line_breaker_columns.size (),
+ last);
+
+ if (break_point || (i == all_.size () - 1 && last))
+ breaks_.push_back (cur_pos);
+ if (chunk_end || last)
+ chunks_.push_back (cur_pos);
+
+ if ((break_point || chunk_end) && !last)
+ line_breaker_columns.push_back (j);
+ }
+ line_breaking_.push_back (Constrained_breaking (line_breaker_columns));
+ line_breaking_.back ().set_pscore (all_[i].pscore_);
+ }
+ else
+ {
+ /* TODO: we want some way of applying Break_p to a prob? */
+ if (i == all_.size () - 1)
+ breaks_.push_back (Break_position (i));
+
+ chunks_.push_back (Break_position (i));
+ line_breaking_.push_back (Constrained_breaking ());
+ }
+ }
}
-vector<vsize>
-Page_breaking::find_page_break_indices (Paper_score *pscore)
+vector<Break_position>
+Page_breaking::chunk_list (vsize start_index, vsize end_index)
{
- vector<Grob*> all = pscore->root_system ()->columns ();
- vector<vsize> ret;
+ Break_position start = breaks_[start_index];
+ Break_position end = breaks_[end_index];
- /* we don't include breaks at the beginning and end */
- for (vsize i = 0; i < all.size () - 1; i++)
- if (scm_is_symbol (all[i]->get_property ("page-turn-permission")))
- ret.push_back(i);
+ vsize i;
+ for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
+ ;
+
+ vector<Break_position> ret;
+ ret.push_back (start);
+ for (; i < chunks_.size () && chunks_[i] < end; i++)
+ ret.push_back (chunks_[i]);
+ ret.push_back (end);
+ return ret;
+}
+vsize
+Page_breaking::min_system_count (vsize start, vsize end)
+{
+ vector<Break_position> chunks = chunk_list (start, end);
+ Line_division div = system_count_bounds (chunks, true);
+ vsize ret = 0;
+
+ for (vsize i = 0; i < div.size (); i++)
+ ret += div[i];
return ret;
}
-void
-Page_breaking::calc_system_count_bounds (vsize start, vsize end,
- vector<vsize> *min,
- vector<vsize> *max)
+vsize
+Page_breaking::max_system_count (vsize start, vsize end)
+{
+ vector<Break_position> chunks = chunk_list (start, end);
+ Line_division div = system_count_bounds (chunks, false);
+ vsize ret = 0;
+
+ for (vsize i = 0; i < div.size (); i++)
+ ret += div[i];
+ return ret;
+}
+
+Page_breaking::Line_division
+Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
{
- for (vsize i = next_system (start); i <= breaks_[end].sys_; i++)
+ assert (chunks.size () >= 2);
+
+ Line_division ret;
+ ret.resize (chunks.size () - 1, 1);
+
+ for (vsize i = 0; i < chunks.size () - 1; i++)
{
- if (all_[i].pscore_)
- {
- min->push_back (get_min_systems (i, start, end));
- max->push_back (get_max_systems (i, start, end));
- }
- else
- {
- min->push_back (1);
- max->push_back (1);
- }
+ vsize sys = next_system (chunks[i]);
+ if (all_[sys].pscore_)
+ {
+ vsize start;
+ vsize end;
+ line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
+ ret[i] = min
+ ? line_breaking_[sys].get_min_systems (start, end)
+ : line_breaking_[sys].get_max_systems (start, end);
+ }
}
+
+ return ret;
+}
+
+vector<Page_breaking::Line_division>
+Page_breaking::line_divisions (vsize start,
+ vsize end,
+ vsize system_count,
+ Line_division lower_bound,
+ Line_division upper_bound)
+{
+ vector<Break_position> chunks = chunk_list (start, end);
+
+ if (!lower_bound.size ())
+ lower_bound = system_count_bounds (chunks, true);
+ if (!upper_bound.size ())
+ upper_bound = system_count_bounds (chunks, false);
+
+ assert (lower_bound.size () == chunks.size () - 1);
+ assert (upper_bound.size () == chunks.size () - 1);
+
+ vector<Line_division> ret;
+ Line_division work_in_progress;
+
+ line_divisions_rec (system_count,
+ lower_bound,
+ upper_bound,
+ &ret,
+ &work_in_progress);
+ return ret;
}
-/* calculate all possible ways of dividing system_count between the System_specs */
void
-Page_breaking::divide_systems (vsize system_count,
- vector<vsize> const &min_sys,
- vector<vsize> const &max_sys,
- vector<vector<vsize> > *result,
- vector<vsize> *cur_division)
+Page_breaking::line_divisions_rec (vsize system_count,
+ Line_division const &min_sys,
+ Line_division const &max_sys,
+ vector<Line_division > *result,
+ Line_division *cur_division)
{
vsize my_index = cur_division->size ();
vsize others_min = 0;
@@ -307,8 +392,7 @@
if (my_index == min_sys.size () - 1)
result->push_back (*cur_division);
else
- divide_systems (system_count - i, min_sys, max_sys, result, cur_division);
+ line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
cur_division->pop_back ();
}
}
-
Index: lily/page-spacing.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/page-spacing.cc,v
retrieving revision 1.1
diff -u -r1.1 page-spacing.cc
--- lily/page-spacing.cc 8 Aug 2006 10:01:22 -0000 1.1
+++ lily/page-spacing.cc 16 Aug 2006 21:35:05 -0000
@@ -219,43 +219,6 @@
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)
: lines_ (lines)
{
@@ -275,6 +238,9 @@
vsize system = lines_.size () - 1;
+ if (isinf (state_.at (system, page_count-1).demerits_))
+ return Spacing_result (); /* bad number of pages */
+
ret.penalty_ = state_.at (system, page_count-1).penalty_
+ lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
@@ -430,6 +396,7 @@
Page_spacer ps (compressed_lines, page_height);
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++)
Index: lily/page-turn-page-breaking.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/page-turn-page-breaking.cc,v
retrieving revision 1.1
diff -u -r1.1 page-turn-page-breaking.cc
--- lily/page-turn-page-breaking.cc 8 Aug 2006 10:01:22 -0000 1.1
+++ lily/page-turn-page-breaking.cc 16 Aug 2006 21:35:05 -0000
@@ -18,8 +18,14 @@
#include "system.hh"
#include "warn.hh"
+static bool
+break_p (Grob *g)
+{
+ return scm_is_symbol (g->get_property ("page-turn-permission"));
+}
+
Page_turn_page_breaking::Page_turn_page_breaking (Paper_book *pb)
- : Page_breaking (pb, true)
+ : Page_breaking (pb, break_p)
{
}
@@ -52,7 +58,7 @@
Page_turn_page_breaking::put_systems_on_pages (vsize start,
vsize end,
vector<Line_details> const &lines,
- vector<vsize> const &div,
+ Line_division const &div,
int page_number)
{
bool last = end == breaks_.size () - 1;
@@ -111,46 +117,26 @@
p_num = f_p_num + p_count + ((f_p_num > 1) ? p_count % 2 : 0);
}
- vector<vsize> min_systems;
- vector<vsize> max_systems;
- vsize min_system_count = 0;
- vsize max_system_count = 0;
- this_start_best.demerits_ = infinity_f;
- calc_system_count_bounds (start, end, &min_systems, &max_systems);
+ Line_division min_division;
+ Line_division max_division;
- /* heuristic: we've prepended some music, only the first system is allowed
- to get more lines */
- if (this_start_best.page_count_ == 2 && this_start_best.div_.size ())
- {
- vsize ds = max_systems.size () - this_start_best.div_.size ();
- for (vsize i = ds + 1; i < max_systems.size (); i++)
- {
- assert (this_start_best.div_[i - ds] <= max_systems[i]);
- max_systems[i] = this_start_best.div_[i - ds];
- }
- }
-
- for (vsize i = 0; i < min_systems.size (); i++)
- {
- min_system_count += min_systems[i];
- max_system_count += max_systems[i];
- }
+ vsize min_sys_count = min_system_count (start, end);
+ vsize max_sys_count = max_system_count (start, end);
+ this_start_best.demerits_ = infinity_f;
bool ok_page = true;
/* heuristic: we've just added a breakpoint, we'll need at least as
many systems as before */
- min_system_count = max (min_system_count, prev_best_system_count);
- for (vsize sys_count = min_system_count; sys_count <= max_system_count && ok_page; sys_count++)
+ min_sys_count = max (min_sys_count, prev_best_system_count);
+ for (vsize sys_count = min_sys_count; sys_count <= max_sys_count && ok_page; sys_count++)
{
- vector<vector<vsize> > div;
- vector<vsize> blank;
+ vector<Line_division> div = line_divisions (start, end, sys_count, min_division, max_division);
bool found = false;
- divide_systems (sys_count, min_systems, max_systems, &div, &blank);
for (vsize d = 0; d < div.size (); d++)
{
- vector<Line_details> line = get_line_details (start, end, div[d]);
+ vector<Line_details> line = line_details (start, end, div[d]);
cur = put_systems_on_pages (start, end, line, div[d], p_num);
@@ -169,6 +155,10 @@
found = true;
this_start_best = cur;
prev_best_system_count = sys_count;
+
+ /* heuristic: if we increase the number of systems, we can bound the
+ division from below by our current best division */
+ min_division = div[d];
}
}
if (!found && this_start_best.too_many_lines_)
@@ -222,39 +212,15 @@
vsize start = n > 0 ? soln[n-1].break_pos_ : 0;
vsize end = soln[n].break_pos_;
- /* break each score into pieces */
- for (vsize i = next_system (start); i <= breaks_[end].sys_; i++)
- {
- vsize d = i - next_system (start);
- if (all_[i].pscore_)
- {
- vector<Column_x_positions> line_brk;
-
- line_brk = get_line_breaks (i, soln[n].div_[d], start, end);
- all_[i].pscore_->root_system ()->break_into_pieces (line_brk);
- assert (line_brk.size () == soln[n].div_[d]);
- }
- }
+ break_into_pieces (start, end, soln[n].div_);
}
+
+ vector<SCM> lines = systems ();
SCM ret = SCM_EOL;
- SCM *tail = &ret;
- for (vsize i = 0; i < all_.size (); i++)
- {
- if (all_[i].pscore_)
- for (SCM s = scm_vector_to_list (all_[i].pscore_->root_system ()->get_paper_systems ());
- scm_is_pair (s); s = scm_cdr (s))
- {
- *tail = scm_cons (scm_car (s), SCM_EOL);
- tail = SCM_CDRLOC (*tail);
- }
- else
- {
- *tail = scm_cons (all_[i].prob_->self_scm (), SCM_EOL);
- all_[i].prob_->unprotect ();
- tail = SCM_CDRLOC (*tail);
- }
- }
- return ret;
+ for (vsize i = 0; i < lines.size (); i++)
+ ret = scm_cons (lines[i], ret);
+
+ return scm_reverse (ret);
}
SCM
Index: lily/paper-book.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/paper-book.cc,v
retrieving revision 1.133
diff -u -r1.133 paper-book.cc
--- lily/paper-book.cc 8 Aug 2006 10:01:22 -0000 1.133
+++ lily/paper-book.cc 16 Aug 2006 21:35:05 -0000
@@ -382,6 +382,20 @@
pages_ = SCM_EOL;
SCM proc = paper_->c_variable ("page-breaking");
pages_ = scm_apply_0 (proc, scm_list_1(self_scm ()));
+
+ /* set systems_ from the pages */
+ if (systems_ == SCM_BOOL_F)
+ {
+ systems_ = SCM_EOL;
+ for (SCM p = pages_; p != SCM_EOL; p = scm_cdr (p))
+ {
+ Prob *page = unsmob_prob (scm_car (p));
+ SCM systems = page->get_property ("lines");
+
+ systems_ = scm_append (scm_list_2 (systems_, systems));
+ }
+ }
+
return pages_;
}
Index: lily/paper-column-engraver.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/paper-column-engraver.cc,v
retrieving revision 1.21
diff -u -r1.21 paper-column-engraver.cc
--- lily/paper-column-engraver.cc 8 Aug 2006 10:01:22 -0000 1.21
+++ lily/paper-column-engraver.cc 16 Aug 2006 21:35:05 -0000
@@ -43,6 +43,11 @@
{
command_column_->set_property ("line-break-permission", ly_symbol2scm ("allow"));
system_->set_bound (RIGHT, command_column_);
+
+ /* FIXME: for now, we just make the end of any score page-turnable.
+ There needs to be a better policy...
+ */
+ command_column_->set_property ("page-turn-permission", ly_symbol2scm ("allow"));
}
}
Index: lily/include/optimal-page-breaking.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/optimal-page-breaking.hh,v
retrieving revision 1.1
diff -u -r1.1 optimal-page-breaking.hh
--- lily/include/optimal-page-breaking.hh 8 Aug 2006 10:01:22 -0000 1.1
+++ lily/include/optimal-page-breaking.hh 16 Aug 2006 21:35:06 -0000
@@ -23,8 +23,7 @@
virtual ~Optimal_page_breaking ();
private:
- SCM make_lines (vector<vsize> line_count);
- Spacing_result try_page_spacing (vector<vsize> line_count);
+ Spacing_result try_page_spacing (Line_division const&);
};
#endif /* OPTIMAL_PAGE_BREAKING_HH */
Index: lily/include/page-breaking.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/page-breaking.hh,v
retrieving revision 1.1
diff -u -r1.1 page-breaking.hh
--- lily/include/page-breaking.hh 8 Aug 2006 10:01:22 -0000 1.1
+++ lily/include/page-breaking.hh 16 Aug 2006 21:35:06 -0000
@@ -17,66 +17,112 @@
*/
struct System_spec
{
- System_spec (Paper_score*, int);
- System_spec (Prob*);
- System_spec ();
+ System_spec (Paper_score *ps)
+ {
+ pscore_ = ps;
+ prob_ = NULL;
+ }
+
+ System_spec (Prob *pb)
+ {
+ prob_ = pb;
+ pscore_ = NULL;
+ }
+
+ System_spec ()
+ {
+ pscore_ = NULL;
+ prob_ = NULL;
+ }
Paper_score *pscore_;
Prob *prob_;
-
- vsize score_break_count_; /* for scores, this is the number of start-points our line-
- breaker has */
};
struct Break_position
{
- vsize sys_; /* the index in our all_ list */
+ vsize sys_; /* our index in the all_ list */
vsize score_break_; /* if sys_ is a score, then we start at the score_brk_'th
possible page-break in the score */
+ bool score_ender_;
- Break_position (vsize s=VPOS, vsize brk=VPOS)
+ Break_position (vsize s=VPOS, vsize brk=VPOS, bool end=false)
{
sys_ = s;
score_break_ = brk;
+ score_ender_ = end;
+ }
+
+ bool operator< (const Break_position &other)
+ {
+ return (sys_ == VPOS && other.sys_ != VPOS)
+ || (sys_ < other.sys_)
+ || (sys_ == other.sys_ && score_break_ < other.score_break_);
+ }
+
+ bool operator<= (const Break_position &other)
+ {
+ return (sys_ == VPOS)
+ || (sys_ < other.sys_ && other.sys_ != VPOS)
+ || (sys_ == other.sys_ && score_break_ <= other.score_break_);
}
};
class Page_breaking
{
public:
+ typedef bool (*Break_p) (Grob *);
+ typedef vector<vsize> Line_division;
virtual SCM solve () = 0;
- Page_breaking (Paper_book *pb, bool allow_intra_score_breaks);
+ Page_breaking (Paper_book *pb, Break_p);
virtual ~Page_breaking ();
protected:
- std::vector<Break_position> breaks_;
- std::vector<System_spec> all_;
- std::vector<Constrained_breaking> line_breaking_;
-
Paper_book *book_;
Real page_height (int page_number, bool last);
vsize next_system (vsize starting_break_index) const;
-
- void create_system_list (bool allow_intra_score_breaks);
- std::vector<vsize> find_page_break_indices (Paper_score *pscore);
+ vsize next_system (Break_position const &break_pos) const;
SCM make_pages (vector<vsize> lines_per_page, SCM lines);
- void calc_system_count_bounds (vsize start, vsize end,
- vector<vsize> *min,
- vector<vsize> *max);
-
- void divide_systems (vsize system_count, vector<vsize> const &min,
- vector<vsize> const &max,
- vector<vector<vsize> > *result,
- vector<vsize> *cur);
-
- void line_breaker_args (vsize i, vsize *break_st, vsize *break_end);
- vsize get_min_systems (vsize sys, vsize break_start, vsize break_end);
- vsize get_max_systems (vsize sys, vsize break_start, vsize break_end);
- vector<Column_x_positions> get_line_breaks (vsize sys, vsize sys_count, vsize st, vsize end);
- vector<Line_details> get_line_details (vsize start_break, vsize end_break, vector<vsize> const &div);
+ vsize min_system_count (vsize start, vsize end);
+ vsize max_system_count (vsize start, vsize end);
+ vector<Line_details> line_details (vsize start, vsize end, Line_division const &div);
+
+ void break_into_pieces (vsize start, vsize end, Line_division const &div);
+ vector<SCM> systems ();
+
+
+ vector<Line_division> line_divisions (vsize start,
+ vsize end,
+ vsize system_count,
+ Line_division lower_bound = Line_division (),
+ Line_division upper_bound = Line_division ());
+
+ vector<Break_position> breaks_;
+
+private:
+ vector<Break_position> chunks_;
+ vector<System_spec> all_;
+ vector<Constrained_breaking> line_breaking_;
+
+ vector<Break_position> chunk_list (vsize start, vsize end);
+ Line_division system_count_bounds (vector<Break_position> const &chunks, bool min);
+ void line_breaker_args (vsize i,
+ Break_position const &start,
+ Break_position const &end,
+ vsize *line_breaker_start,
+ vsize *line_breaker_end);
+
+ void line_divisions_rec (vsize system_count,
+ Line_division const &min,
+ Line_division const &max,
+ vector<Line_division> *result,
+ Line_division *cur);
+
+ void create_system_list ();
+ void find_chunks_and_breaks (Break_p);
};
#endif /* PAGE_BREAKING_HH */
Index: lily/include/page-spacing.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/page-spacing.hh,v
retrieving revision 1.1
diff -u -r1.1 page-spacing.hh
--- lily/include/page-spacing.hh 8 Aug 2006 10:01:22 -0000 1.1
+++ lily/include/page-spacing.hh 16 Aug 2006 21:35:06 -0000
@@ -21,10 +21,47 @@
Spacing_result ()
{
penalty_ = 0;
- demerits_ = 0;
+ demerits_ = infinity_f;
}
};
+/* 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);
+};
+
Spacing_result
space_systems_on_min_pages (vector<Line_details> const&,
Real page_height,
Index: lily/include/page-turn-page-breaking.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/page-turn-page-breaking.hh,v
retrieving revision 1.1
diff -u -r1.1 page-turn-page-breaking.hh
--- lily/include/page-turn-page-breaking.hh 8 Aug 2006 10:01:22 -0000 1.1
+++ lily/include/page-turn-page-breaking.hh 16 Aug 2006 21:35:06 -0000
@@ -45,7 +45,7 @@
Real demerits_;
vsize break_pos_; /* index into breaks_ */
- vector<vsize> div_; /* our division of systems between scores on this page */
+ Line_division div_;
vector<vsize> system_count_; /* systems per page */
Break_node ()
@@ -59,12 +59,12 @@
}
};
- std::vector<Break_node> state_;
+ vector<Break_node> state_;
Break_node put_systems_on_pages (vsize start,
vsize end,
vector<Line_details> const &lines,
- vector<vsize> const &system_div,
+ Line_division const &div,
int page_number);
SCM make_lines (vector<Break_node> *breaks);
_______________________________________________
lilypond-devel mailing list
lilypond-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/lilypond-devel
