* input/mutopia/F.Schubert/morgenlied.ly (pianoLH): update tempo.
+2006-08-23 Joe Neeman <joeneeman@gmail.com>
+
+ * input/regression/optimal-page-breaking-hstretch.ly: test for
+ ragged-last-bottom also
+
+ * 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.
+
+ * lily/page-spacing.cc: better support for ragged-bottom and
+ ragged-last-bottom
+
2006-08-22 Han-Wen Nienhuys <hanwen@lilypond.org>
* python/convertrules.py (conv): warning on \tempo{}
systems horizontally so that the vertical spacing will be
more acceptable. The page-spacing-weight parameter
controls the relative importance of vertical/horizontal
-spacing.
+spacing. Because ragged-last-bottom is on, only the
+first page should be horizontally stretched.
"
}
\paper {
#(define page-breaking ly:optimal-breaking)
page-spacing-weight = #10
- ragged-last-bottom = ##f
+ ragged-last-bottom = ##t
}
\relative c' {
+ \repeat unfold 5 {a b c d} \pageBreak
\repeat unfold 5 {a b c d}
}
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 */
*/
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 */
+ Grob *col_; /* if sys_ is a score, this points to the broken column */
+ bool score_ender_;
- Break_position (vsize s=VPOS, vsize brk=VPOS)
+ Break_position (vsize s=VPOS, vsize brk=VPOS, Grob *g=NULL, bool end=false)
{
sys_ = s;
score_break_ = brk;
+ col_ = g;
+ 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_predicate) (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_predicate);
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);
+ 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);
+ 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 ());
+
+ SCM breakpoint_property (vsize breakpoint, char const *str);
+ 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 divide_systems (vsize system_count, vector<vsize> const &min,
- vector<vsize> const &max,
- vector<vector<vsize> > *result,
- vector<vsize> *cur);
+ void line_divisions_rec (vsize system_count,
+ Line_division const &min,
+ Line_division const &max,
+ vector<Line_division> *result,
+ Line_division *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);
+ void create_system_list ();
+ void find_chunks_and_breaks (Break_predicate);
};
#endif /* PAGE_BREAKING_HH */
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, bool ragged, bool ragged_last);
+ 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_;
+
+ bool ragged_;
+ bool ragged_last_;
+
+ 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,
- Real odd_pages_penalty);
+ Real odd_pages_penalty,
+ bool ragged,
+ bool ragged_last);
Spacing_result
space_systems_on_best_pages (vector<Line_details> const&,
Real page_height,
- Real odd_pages_penalty);
+ Real odd_pages_penalty,
+ bool ragged,
+ bool ragged_last);
#endif /* PAGE_SPACING_HH */
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 ()
}
};
- 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);
/*
- 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
#include "prob.hh"
#include "system.hh"
+static bool
+is_break (Grob *g)
+{
+ (void) g; /* shutup warning */
+ return false;
+}
+
Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
- : Page_breaking (pb, false)
+ : Page_breaking (pb, is_break)
{
}
}
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);
- Spacing_result ret = space_systems_on_best_pages (lines, page_h, blank_force);
-
- bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
- bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
+ bool ragged_all = book_->paper_->c_variable ("ragged-bottom");
+ bool ragged_last = book_->paper_->c_variable ("ragged-last-bottom");
+ Spacing_result ret = space_systems_on_best_pages (lines,
+ page_h,
+ blank_force,
+ ragged_all,
+ ragged_last);
/* add in the line penalties */
Real line_force = 0;
line_penalty += lines[i].break_penalty_;
}
- if (ragged_all)
- for (vsize i = 0; i < ret.force_.size () - 1; i++)
- ret.force_[i] = min (0.0, ret.force_[i]);
- if (ragged_all || ragged_last)
- ret.force_.back () = min (0.0, ret.force_.back ());
-
ret.demerits_ = ret.force_[0] * ret.force_[0] * page_weighting;
for (vsize i = 1; i < ret.force_.size (); i++)
{
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;
- }
- } 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];
-
- } while (flip (&d) != DOWN);
- SCM lines = make_lines (best_line_count);
- SCM pages = make_pages (best_result.systems_per_page_, lines);
- return pages;
-}
+ if (cur.demerits_ < this_best_demerits)
+ {
+ this_best_demerits = cur.demerits_;
+ lower_bound = div[d];
+ }
-SCM
-Optimal_page_breaking::make_lines (vector<vsize> line_count)
-{
- assert (line_count.size () == all_.size ());
+ 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;
- 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 ();
+ if (all_lines_stretched)
+ max_page_count = cur_page_count + 1;
}
}
- return ret;
+
+ break_into_pieces (0, end, best_division);
+ SCM lines = systems ();
+ return make_pages (best.systems_per_page_, lines);
}
+
/*
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
#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
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_predicate is_break)
{
book_ = pb;
- create_system_list (allow_intra_score_breaks);
+ create_system_list ();
+ find_chunks_and_breaks (is_break);
}
Page_breaking::~Page_breaking ()
/* 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_);
+
+ if (start.sys_ == sys)
+ *line_breaker_start = start.score_break_;
+ else
+ *line_breaker_start = 0;
+
+ if (end.sys_ == sys)
+ *line_breaker_end = end.score_break_;
+ else
+ *line_breaker_end = VPOS;
+}
- vsize start_col = 0;
- vsize end_col = VPOS;
+void
+Page_breaking::break_into_pieces (vsize start_break, vsize end_break, Line_division const &div)
+{
+ vector<Break_position> chunks = chunk_list (start_break, end_break);
+ assert (chunks.size () == div.size () + 1);
- if (breaks_[*start].sys_ == i)
- start_col = breaks_[*start].score_break_;
- if (breaks_[*end].sys_ == i)
- end_col = breaks_[*end].score_break_;
+ 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);
- assert (end_col && (end_col == VPOS || end_col <= all_[breaks_[*end].sys_].score_break_count_));
- *start = start_col;
- *end = end_col;
+ vector<Column_x_positions> pos = line_breaking_[sys].get_solution (start, end, div[i]);
+ all_[sys].pscore_->root_system ()->break_into_pieces (pos);
+ }
+ }
}
-vector<Column_x_positions>
-Page_breaking::get_line_breaks (vsize i, vsize sys_count, vsize start, vsize end)
+SCM
+Page_breaking::systems ()
{
- assert (all_[i].pscore_);
- line_breaker_args (i, &start, &end);
- return line_breaking_[i].get_solution (start, end, sys_count);
+ SCM ret = SCM_EOL;
+ for (vsize sys = 0; sys < all_.size (); sys++)
+ {
+ if (all_[sys].pscore_)
+ {
+ SCM lines = all_[sys].pscore_->root_system ()->get_paper_systems ();
+ ret = scm_cons (scm_vector_to_list (lines), ret);
+ }
+ else
+ {
+ Prob *pb = all_[sys].prob_;
+ ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
+ pb->unprotect ();
+ }
+ }
+ return scm_append (scm_reverse (ret));
}
vector<Line_details>
-Page_breaking::get_line_details (vsize start_break, vsize end_break, vector<vsize> const &div)
+Page_breaking::line_details (vsize start_break, vsize end_break, Line_division const &div)
{
+ vector<Break_position> chunks = chunk_list (start_break, end_break);
vector<Line_details> ret;
+ assert (chunks.size () == div.size () + 1);
- for (vsize i = next_system (start_break); i <= breaks_[end_break].sys_; i++)
+ for (vsize i = 0; i < chunks.size () - 1; i++)
{
- if (all_[i].pscore_)
+ vsize sys = next_system (chunks[i]);
+ if (all_[sys].pscore_)
{
- vsize div_index = i - next_system (start_break);
- vsize start = start_break;
- vsize end = end_break;
+ vsize start;
+ vsize end;
+ line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
- 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 ());
+ vector<Line_details> details = line_breaking_[sys].get_details (start, end, div[i]);
+ ret.insert (ret.end (), details.begin (), details.end ());
}
else
- ret.push_back (Line_details (all_[i].prob_));
+ {
+ assert (div[i] == 1);
+ ret.push_back (Line_details (all_[sys].prob_));
+ }
}
return ret;
}
-vsize
-Page_breaking::get_min_systems (vsize i, vsize start, vsize end)
-{
- line_breaker_args (i, &start, &end);
- return line_breaking_[i].get_min_systems (start, end);
-}
-
-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);
-}
-
Real
Page_breaking::page_height (int page_num, bool last)
{
return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
}
+SCM
+Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
+{
+ Break_position const &pos = breaks_[breakpoint];
+
+ if (pos.sys_ == VPOS)
+ return SCM_EOL;
+ if (all_[pos.sys_].pscore_)
+ return pos.col_->get_property (str);
+ return all_[pos.sys_].prob_->get_property (str);
+}
+
SCM
Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
{
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.
- Corollary: if allow_intra_score_breaks is false, any \pageTurn or \noPageTurn commands
- in the middle of a score will be ignored.
+ The optimal-breaker needs to have a line-breaker between any two columns
+ with page-break-permission = 'force.
+
+ 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_predicate is_break)
+{
+ 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 = is_break (cols[j]);
+ bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
+ Break_position cur_pos = Break_position (i,
+ line_breaker_columns.size (),
+ cols[j],
+ 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];
+
+ 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;
+}
- /* 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
+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)
{
- for (vsize i = next_system (start); i <= breaks_[end].sys_; i++)
+ 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)
+{
+ 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;
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 ();
}
}
-
/* 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_))
+ return Spacing_result (); /* bad number of pages */
+
+ 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_;
{
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;
+ 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_)
- {
- cur.demerits_ = dem;
- cur.force_ = space.force_;
- cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
- cur.prev_ = page_start - 1;
+ 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;
+ }
}
+
+ 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)
+min_page_count (vector<Line_details> const &lines, Real page_height, bool ragged)
{
vsize ret = 1;
Real cur_rod_height = 0;
for (vsize i = 0; i < lines.size (); i++)
{
- Real next_height = cur_rod_height + lines[i].extent_.length ()
+ 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);
if ((next_height > page_height && cur_rod_height > 0)
|| (i > 0 && lines[i-1].page_permission_ == ly_symbol2scm ("force")))
{
ret++;
- cur_rod_height = lines[i].extent_.length ();
+ cur_rod_height = ragged ? max (ext_len, lines[i].space_) : ext_len;
}
else
cur_rod_height = next_height;
Spacing_result
space_systems_on_min_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);
Spacing_result ret;
if (min_p_count == 1)
{
- Spacing_result candidate1 = space_systems_on_1_page (compressed_lines, page_height);
+ 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);
+ 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)
- ret = space_systems_on_2_pages (compressed_lines, page_height);
+ ret = space_systems_on_2_pages (compressed_lines, page_height, ragged, ragged_last);
else
{
- Page_spacer ps (compressed_lines, page_height);
+ 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;
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);
- 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++)
#include "system.hh"
#include "warn.hh"
+static bool
+is_break (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, is_break)
{
}
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;
+ bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
+ bool ragged_last = last && to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
Real page_h = page_height (1, false); // FIXME
SCM force_sym = last ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
Real blank_force = robust_scm2double (book_->paper_->lookup_variable (force_sym), 0);
- Spacing_result result = space_systems_on_min_pages (lines, page_h, blank_force);
+ Spacing_result result = space_systems_on_min_pages (lines, page_h, blank_force, ragged_all, ragged_last);
Break_node ret;
ret.prev_ = start - 1;
for (vsize start = end; start--;)
{
+ if (start < end-1
+ && breakpoint_property (start+1, "page-turn-permission") == ly_symbol2scm ("force"))
+ break;
+
if (start > 0 && best.demerits_ < state_[start-1].demerits_)
continue;
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);
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_)
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_);
}
- 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;
+
+ return systems ();
}
SCM
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_;
}
projects / lilypond.git / commitdiff