[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: setting the number of pages for a score
|
From: |
Joe Neeman |
|
Subject: |
Re: setting the number of pages for a score |
|
Date: |
Sun, 19 Feb 2006 16:41:51 +1100 |
|
User-agent: |
Mozilla Thunderbird 1.0.7 (X11/20051121) |
I've cleaned up most (all?) of the issues that you brought up with my
previous code. I've moved some things around to improve readability and
I've addressed a few of the performance problems. Also, it is now
possible to force (or prevent) starting on the right hand page by using
"first-page-right = ##t" in the \paper block. It will still crash if
line breaking doesn't satisfy constraints and it still requires manual
addition of possible break points.
I'm not so sure about my changes to make-page, but it makes calling
make-page from C++ easier and it doesn't adversely affect any current
usage...
/*
optimal-breaking.cc -- implement Optimal_breakinr
source file of the GNU LilyPond music typesetter
(c) 2006 Han-Wen Nienhuys <address@hidden>
*/
#include "optimal-breaking.hh"
#include "main.hh"
#include "item.hh"
#include "paper-book.hh"
#include "output-def.hh"
#include "system.hh"
#include "paper-score.hh"
#include "paper-system.hh"
#include "text-interface.hh"
#include "warn.hh"
#include "ly-smobs.icc"
#include "gourlay-breaking.hh"
#include "international.hh"
System_spec::System_spec (Paper_score *ps, int n_brks)
{
pscore_ = ps;
prob_ = 0;
Output_def *l = ps->layout ();
size_ = scm_to_double (l->c_variable ("system-height"));
penalty_ = 0;
between_size_ = scm_to_double (l->c_variable ("between-system-padding"));
between_space_ = scm_to_double (l->c_variable ("between-system-space"));
score_break_count_ = n_brks;
}
System_spec::System_spec (Prob *pb)
{
pscore_ = 0;
prob_ = pb;
Stencil *s = unsmob_stencil (pb->get_property ("stencil"));
size_ = s->extent (Y_AXIS).length ();
/* these get determined later */
penalty_ = 0;
between_size_ = 0;
between_space_ = 0;
score_break_count_ = 0;
}
System_spec::System_spec ()
{
size_ = between_size_ = between_space_ = 0;
pscore_ = 0;
prob_ = 0;
score_break_count_ = 0;
}
/* for Optimal_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
* could either be the same as the end of the previous page or one more than
* it. */
/* Turn a break index into the sys index that starts the next page */
int Optimal_breaking::next_system (int start) const
{
int sys = breaks_[start].sys_;
if (sys < 0) /* beginning of the piece */
return 0;
if (all_[sys].pscore_ && all_[sys].score_break_count_ >
breaks_[start].score_brk_)
return sys; /* the score overflows the previous page */
return sys + 1; /* this page starts with a new sys */
}
Optimal_breaking::Optimal_breaking (Paper_book *pb)
{
book_ = pb;
create_system_list ();
}
void
Optimal_breaking::calc_demerits (Optimal_break_node &me)
{
Real prev_f = 0;
Real prev_dem = 0;
Real break_pen = 0;
int prev_break = 0;
if (me.prev_ >= 0)
{
prev_f = state_[me.prev_].force_;
prev_dem = state_[me.prev_].demerits_;
prev_break = state_[me.prev_].break_pos_;
}
int cur_system = 1; /* for tracking down which system the page breaks */
int start = prev_break;
int end = me.break_pos_;
Real line_f = 0, line_pen = 0;
for (vsize i = next_system (prev_break); (int)i <=
breaks_[me.break_pos_].sys_; i++)
{
if (all_[i].pscore_)
{
int sys_count = me.div_[i - next_system (prev_break)];
if (cur_system <= me.left_page_sys_
&& cur_system + sys_count > me.left_page_sys_)
break_pen += get_page_penalty (i, sys_count, start, end,
me.left_page_sys_ - cur_system);
if (cur_system + sys_count > me.left_page_sys_ + me.right_page_sys_)
break_pen += get_page_penalty (i, sys_count, start, end,
me.left_page_sys_ + me.right_page_sys_ -
cur_system);
cur_system += sys_count;
line_f += get_line_force (i, sys_count, start, end);
line_pen += get_line_penalty (i, sys_count, start, end);
}
else
{
if (cur_system == me.left_page_sys_)
break_pen += all_[i].penalty_;
cur_system++;
}
}
// TODO: make line vs. page weighting configurable
me.demerits_ = me.force_ * me.force_ + line_f * line_f * 4.0 + fabs
(me.force_ - prev_f);
if (isinf (line_f)) /* make failed line-breaking very unattractive */
me.demerits_ = (me.force_ + 20000.0) * 10;
if (isinf (me.force_)) /* failed page breaking not quite as bad */
me.demerits_ = 20000.0;
if (me.page_number_ == 1 && scm_is_bool (book_->paper_->c_variable
("first-page-right")))
me.demerits_ += (to_boolean (book_->paper_->c_variable ("first-page-right"))
&& me.right_page_sys_ == 0) ? -10000 : 10000;
me.demerits_ += prev_dem + break_pen + all_[breaks_[end].sys_].penalty_
+ breaks_[end].penalty_ + line_pen;
}
void
Optimal_breaking::line_brk_args (vsize i, int &start, int &end)
{
assert (all_[i].pscore_);
assert (next_system (start) <= (int)i && (int)i <= breaks_[end].sys_);
int start_col = 0;
int end_col = -1;
if (breaks_[start].sys_ == (int)i)
start_col = breaks_[start].score_brk_;
if (breaks_[end].sys_ == (int)i)
end_col = breaks_[end].score_brk_;
assert (end_col && end_col <= all_[breaks_[end].sys_].score_break_count_);
start = start_col;
end = end_col;
}
Real
Optimal_breaking::get_page_penalty (vsize i, int sys_count, int start, int end,
int sys_num)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_page_penalty (start, end, sys_count, sys_num);
}
vector<Column_x_positions>
Optimal_breaking::get_line_breaks (vsize i, int sys_count, int start, int end)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_soln (start, end, sys_count);
}
Real
Optimal_breaking::get_line_break_dems (vsize i, int sys_count, int start, int
end)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_demerits (start, end, sys_count);
}
Real
Optimal_breaking::get_line_force (vsize i, int sys_count, int start, int end)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_force (start, end, sys_count);
}
Real
Optimal_breaking::get_line_penalty (vsize i, int sys_count, int start, int end)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_penalty (start, end, sys_count);
}
vsize
Optimal_breaking::get_min_systems (vsize i, int start, int end)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_min_systems (start, end);
}
vsize
Optimal_breaking::get_max_systems (vsize i, int start, int end)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_max_systems (start, end);
}
Real
Optimal_breaking::page_height (int page_num, bool last)
{
SCM mod = scm_c_resolve_module ("scm page");
SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
SCM make_page = scm_c_module_lookup (mod, "make-page");
calc_height = scm_variable_ref (calc_height);
make_page = scm_variable_ref (make_page);
SCM page = scm_apply_0 (make_page, scm_list_n (
book_->self_scm (),
ly_symbol2scm ("page-number"), scm_from_int (page_num),
ly_symbol2scm ("is-last"), scm_from_bool (last),
SCM_UNDEFINED));
SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
return scm_to_double (height);
}
void
Optimal_breaking::shift_system (const System_spec &sys,
const System_spec &prev,
Drul_array<Page_spacing> &pages)
{
pages[LEFT].rod_height_ -= sys.size_ + prev.between_size_;
pages[LEFT].spring_len_ -= sys.between_space_;
pages[LEFT].spring_space_ += prev.between_size_;
pages[LEFT].inverse_spring_k_--;
if (pages[RIGHT].rod_height_)
{
pages[RIGHT].rod_height_ += sys.between_size_;
pages[RIGHT].spring_space_ -= sys.between_size_;
}
pages[RIGHT].rod_height_ += sys.size_;
pages[RIGHT].spring_len_ += sys.between_space_;
pages[RIGHT].inverse_spring_k_++;
Direction d = LEFT;
do
{
if (pages[d].rod_height_ >= pages[d].page_height_)
pages[d].force_ = infinity_f;
else
pages[d].force_ = (pages[d].spring_space_ - pages[d].spring_len_)
/ pages[d].inverse_spring_k_;
}
while ((flip (&d)) != LEFT);
}
void
Optimal_breaking::fill_page (vector<System_spec> const &sys, Page_spacing &page)
{
page.rod_height_ = 0;
page.spring_space_ = page.page_height_;
page.spring_len_ = 0;
page.inverse_spring_k_ = 0;
for (vsize i = 0; i < sys.size (); i++)
{
page.rod_height_ += sys[i].size_ + sys[i].between_size_;
page.spring_len_ += sys[i].between_space_;
page.spring_space_ -= sys[i].between_size_;
page.inverse_spring_k_++;
}
page.rod_height_ -= sys.back ().between_size_;
page.spring_space_ += sys.back ().between_size_;
page.force_ = (page.rod_height_ < page.page_height_) ?
(page.spring_space_ - page.spring_len_) /
page.inverse_spring_k_ : infinity_f;
}
void
Optimal_breaking::best_page (vector<System_spec> const &sys,
Optimal_break_node &me)
{
Drul_array<Page_spacing> page;
vector<System_spec> rep_sys;
bool last = me.break_pos_ == (int) breaks_.size () - 1;
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 = ragged_all || (last && ragged_last);
page[LEFT].page_height_ = page_height (me.page_number_, last);
page[RIGHT].page_height_ = page_height (me.page_number_ + 1, last);
/* repeat each score for the number of systems it has */
for (vsize i = 0; i < sys.size (); i++)
for (vsize j = 0; j < me.div_[i]; j++)
rep_sys.push_back (sys[i]);
fill_page (rep_sys, page[LEFT]);
if (ragged && !isinf(page[LEFT].force_))
me.force_ = max (0.0, page[LEFT].force_);
else
me.force_ = fabs (page[LEFT].force_);
if (!last)
me.force_ += robust_scm2double (book_->paper_->c_variable
("blank-page-force"), 0.0);
else
me.force_ += robust_scm2double (book_->paper_->c_variable
("blank-last-page-force"), 0.0);
if (me.page_number_ == 1)
{
me.left_page_sys_ = 0;
me.right_page_sys_ = rep_sys.size ();
me.page_number_ = 0; /* because, for this configuration, we start on the
right page */
}
else
{
me.left_page_sys_ = rep_sys.size ();
me.right_page_sys_ = 0;
}
calc_demerits (me);
/* move things over one system at a time */
Optimal_break_node cur = me;
page[RIGHT].spring_space_ = page[RIGHT].page_height_;
for (vsize i = rep_sys.size () - 1; i > 0; i--)
{
shift_system (rep_sys[i], rep_sys[i-1], page);
if (isinf (page[RIGHT].force_)) /* it's only going to get worse if we add
more systems */
return;
if (isinf (page[LEFT].force_))
continue;
page[LEFT].force_ = ragged_all ? max (0.0, page[LEFT].force_) : fabs
(page[LEFT].force_);
page[RIGHT].force_ = ragged ? max (0.0, page[RIGHT].force_) : fabs
(page[RIGHT].force_);
cur.force_ = fabs (page[LEFT].force_) + fabs (page[RIGHT].force_)
+ fabs (page[LEFT].force_ - page[RIGHT].force_);
cur.left_page_sys_ = i;
cur.right_page_sys_ = rep_sys.size () - i;
calc_demerits (cur);
if (cur.demerits_ < me.demerits_)
{
me = cur;
if (!me.page_number_)
me.page_number_ = 1;
}
}
}
void
Optimal_breaking::calc_subproblem(int i)
{
int end = i + 1;
Optimal_break_node best;
Optimal_break_node cur;
cur.break_pos_ = end;
for (int start = end - 1; start >= 0; start--)
{
int p_num = (start == 0) ? 1 : state_[start-1].page_number_ + 2;
vector<System_spec> systems (all_.begin () + next_system (start),
all_.begin () + breaks_[end].sys_ + 1);
Optimal_break_node this_break_best;
cur.page_number_ = p_num;
cur.prev_ = start - 1;
vector<vsize> min_systems, max_systems;
int min_system_count = 0, max_system_count = 0;
calc_system_bounds (start, end, min_systems, max_systems);
for (vsize i = 0; i < min_systems.size (); i++)
{
min_system_count += min_systems[i];
max_system_count += max_systems[i];
}
bool ok_page = true;
for (int sys_count = min_system_count; sys_count <= max_system_count &&
ok_page; sys_count++)
{
vector<vector<vsize> > div;
vector<vsize> blank;
divide_systems (sys_count, min_systems, max_systems, div, blank);
for (vsize d = 0; d < div.size (); d++)
{
cur.div_ = div[d];
best_page (systems, cur);
Real line_f = 0;
for (vsize j = 0; j < systems.size (); j++)
if (systems[j].pscore_)
line_f += get_line_force (j + next_system(start), div[d][j],
start, end);
if (isinf (cur.force_))
{
ok_page = false;
break;
}
cur.line_demerits_ = line_f;
if (isinf(this_break_best.demerits_) || cur.demerits_ <
this_break_best.demerits_)
{
this_break_best = cur;
this_break_best.div_ = div[d];
}
}
}
if (isinf (cur.demerits_) && start == end - 1)
{
programming_error (_f ("couldn't break between %d and %d", start,
end));
assert (0);
}
/*message (_f ("the page between %d and %d has prev=%d, force=%f, dem=%f,
line_dem=%f",
start, end, this_break_best.prev_+1,
this_break_best.force_,
this_break_best.demerits_,
this_break_best.line_demerits_));*/
if (isinf (best.demerits_) || this_break_best.demerits_ < best.demerits_)
best = this_break_best;
}
state_.push_back (best);
}
SCM
Optimal_breaking::solve ()
{
state_.clear ();
message (_f ("Calculating page and line breaks (%d possible page breaks)...",
(int)breaks_.size () - 1) + " ");
for (vsize i = 0; i < breaks_.size () - 1; i++)
{
calc_subproblem (i);
progress_indication (string ("[") + to_string (i + 1) + "]");
}
progress_indication ("\n");
vector<Optimal_break_node> soln;
int i = state_.size () - 1;
while (i >= 0)
{
soln.push_back (state_[i]);
i = state_[i].prev_;
}
reverse (soln);
SCM systems = do_line_breaking (soln);
return make_pages (soln, systems);
}
/* do the line breaking in all the scores and return a big list of systems */
SCM
Optimal_breaking::do_line_breaking (vector<Optimal_break_node> const &soln)
{
int total_n_systems = 0;
for (vsize n = 0; n < soln.size (); n++)
{
vsize start = n > 0 ? soln[n-1].break_pos_ : 0;
vsize end = soln[n].break_pos_;
int n_systems = 0;
/* break each score into pieces */
for (vsize i = next_system (start); (int) i <= breaks_[end].sys_; i++)
{
vsize d = i - next_system (start);
if (all_[i].pscore_)
{
vector<Column_x_positions> line_brk;
Real dems = get_line_force (i, soln[n].div_[d], start, end);
if (isinf (dems))
::message (_("WTF? I chose an infinite-demerits line
breaking"));
line_brk = get_line_breaks (i, soln[n].div_[d], start, end);
all_[i].pscore_->root_system ()->break_into_pieces (line_brk);
n_systems += line_brk.size ();
}
else
n_systems++;
}
assert (n_systems == soln[n].left_page_sys_ + soln[n].right_page_sys_);
total_n_systems += n_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);
}
}
assert (scm_to_int (scm_length (ret)) == total_n_systems);
return ret;
}
SCM
Optimal_breaking::make_pages (vector<Optimal_break_node> const &soln, SCM
systems)
{
SCM prev_page = SCM_BOOL_F;
SCM make_page = ly_lily_module_constant ("make-page-from-systems");
SCM book = book_->self_scm ();
bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
bool ragged_last = to_boolean (book_->paper_->c_variable
("ragged-last-bottom"));
SCM ret = SCM_EOL;
for (vsize i = 0; i < soln.size (); i++)
{
if (i > 0 || soln[i].left_page_sys_)
{
SCM page_num = scm_from_int (soln[i].page_number_);
SCM last = scm_from_bool (i == soln.size () - 1 &&
soln[i].right_page_sys_ == 0);
SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) &&
ragged_last));
SCM lines = SCM_EOL;
for (int j = 0; j < soln[i].left_page_sys_; j++, systems =
scm_cdr(systems))
lines = scm_cons (scm_car (systems), lines);
lines = scm_reverse (lines);
SCM page = scm_apply_0 (make_page,
scm_list_n (book, lines, page_num, prev_page, ragged,
last, SCM_UNDEFINED));
ret = scm_cons (page, ret);
}
if (i < soln.size () - 1 || soln[i].right_page_sys_)
{
SCM page_num = scm_from_int (soln[i].page_number_ + 1);
SCM last = scm_from_bool (i == soln.size () - 1);
SCM lines = SCM_EOL;
SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) &&
ragged_last));
for (int j = 0; j < soln[i].right_page_sys_; j++, systems =
scm_cdr(systems))
lines = scm_cons (scm_car (systems), lines);
lines = scm_reverse (lines);
SCM page = scm_apply_0 (make_page,
scm_list_n (book, lines, page_num, prev_page, ragged,
last, SCM_UNDEFINED));
ret = scm_cons (page, ret);
}
}
return scm_reverse (ret);
}
/* unlike the default page breaker, we store our penalties in the system that
* ends the page */
void
Optimal_breaking::add_break_penalty (Prob *pb)
{
if (all_.empty ())
return;
int sys = all_.size () - 1;
Real pen = robust_scm2double (pb->get_property ("penalty"), 0.0);
if (all_.back ().pscore_)
{
/* check if there's already a breakpoint there */
if (breaks_.back ().sys_ == sys
&& breaks_.back ().score_brk_ == all_.back ().score_break_count_)
breaks_.back ().penalty_ += pen;
else
breaks_.push_back (Break_position (sys, all_[sys].score_break_count_,
pen));
}
else
breaks_.push_back (Break_position (sys, -1, pen));
}
void
Optimal_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<int> 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);
}
else
{
Prob *pb = unsmob_prob (scm_car (s));
assert (pb);
pb->protect ();
add_break_penalty (pb);
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));
/* add extra title space */
Real bet = scm_to_double (book_->paper_->c_variable ("between-title-space"));
Real after = scm_to_double (book_->paper_->c_variable ("after-title-space"));
Real before = scm_to_double (book_->paper_->c_variable
("before-title-space"));
for (vsize i = 0; i < all_.size () - 1; i++)
{
bool title1 = !all_[i].pscore_
&& to_boolean (all_[i].prob_->get_property ("is-title"));
bool title2 = !all_[i+1].pscore_
&& to_boolean (all_[i+1].prob_->get_property ("is-title"));
if (title1 && !all_[i].penalty_)
all_[i].penalty_ = 10000;
if (title1 && title2)
all_[i].between_size_ += bet;
else if (title1)
all_[i].between_size_ += before;
else if (title2)
all_[i+1].between_size_ += after;
}
}
vector<int>
Optimal_breaking::find_page_break_indices(Paper_score *pscore)
{
vector<Grob*> all = pscore->root_system ()->columns ();
vector<int> ret;
/* we don't include breaks at the beginning and end */
for (vsize i = 0; i < all.size () - 1; i++)
if (Item::is_breakable (all[i]) &&
scm_is_number (all[i]->get_property ("page-penalty")) &&
robust_scm2double (all[i]->get_property ("page-penalty"), 0) < 0)
ret.push_back(i);
return ret;
}
void
Optimal_breaking::calc_system_bounds (vsize start, vsize end,
vector<vsize> &min,
vector<vsize> &max)
{
for (int i = next_system (start); i <= breaks_[end].sys_; 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);
}
}
}
void
Optimal_breaking::divide_systems (int system_count,
vector<vsize> const &min_sys,
vector<vsize> const &max_sys,
vector<vector<vsize> > &result,
vector<vsize> &cur_division)
{
vsize my_index = cur_division.size ();
int others_min = 0, others_max = 0;
for (vsize i = my_index + 1; i < min_sys.size (); i++)
{
others_min += min_sys[i];
others_max += max_sys[i];
}
vsize real_min = max ((int)min_sys[my_index], system_count - others_max);
vsize real_max = min ((int)max_sys[my_index], system_count - others_min);
assert (real_min <= real_max);
for (vsize i = real_min; i <= real_max; i++)
{
cur_division.push_back (i);
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);
cur_division.pop_back ();
}
}
/*
optimal-breaking-scheme.cc -- implement Optimal_breaking bindings
source file of the GNU LilyPond music typesetter
(c) 2006 Han-Wen Nienhuys <address@hidden>
*/
#include "paper-book.hh"
#include "optimal-breaking.hh"
LY_DEFINE (ly_optimal_breaking, "ly:optimal-breaking",
1, 0, 0, (SCM pb),
"Optimally break (pages and lines) the Paper_book PB, returning its
pages.")
{
Optimal_breaking b (unsmob_paper_book (pb));
return b.solve();
}
/*
constrained-breaking.cc -- implement a line breaker that
support limits on the number of systems
source file of the GNU LilyPond music typesetter
(c) 1997--2005 Han-Wen Nienhuys <address@hidden>
*/
#include "constrained-breaking.hh"
#include <cmath>
#include <cstdio>
using namespace std;
#include "warn.hh"
#include "main.hh"
#include "paper-column.hh"
#include "paper-score.hh"
#include "output-def.hh"
#include "simple-spacer.hh"
#include "system.hh"
#include "international.hh"
void
print_constrained_break_nodes (vector<Constrained_break_node> const &arr)
{
for (vsize i = 0; i < arr.size (); i++)
{
printf ("node %d: ", (int)i);
arr[i].print ();
}
}
/**
We use the following optimal substructure. Let W(A) be our weight function.
Let A_{k,n} = (a_{k,n,1}, ... a_{k,n,k}) be the optimal set of line breaks
for k systems and n potential breakpoints. a_{k,n,k} = n (it is the end of
the piece)
Then A_{k+1, m} is contructed from
min_ {k < j < m} ( W(A_{k,j} :: m) )
where by A::m we denote appending m to the list A
*/
/* start and sys here are indexed from 0.
* max_break is indexed from starting_breakpoints_[start]
* (for max_break, starting_breakpoints_[start] is the beginning
* of the piece; the smallest value we should ever see here is
* starting_breakpoints_[start] + 1) */
bool
Constrained_breaking::calc_subproblem (int start, int sys, int max_break)
{
assert (sys < systems_);
assert (start < (int)start_.size ());
assert (max_break < (int)breaks_.size ());
bool found_something = false;
int start_col = starting_breakpoints_[start];
vector<Constrained_break_node> &st = state_[start];
int rank = breaks_.size () - start_col;
int max_index = max_break - start_col;
for (int j=sys; j < max_index; j++)
{
if (0 == sys && j > 0)
break; /* the first line cannot have its first break after the
beginning */
Column_x_positions const &cur = cols_[(j + start_col)*cols_rank_ +
max_break];
Column_x_positions prev;
Real prev_dem = 0;
if (sys > 0)
{
prev = st[(sys-1) * rank + j].line_config_;
prev_dem = st[(sys-1) * rank + j].demerits_;
}
if (isinf (prev_dem))
break;
Real dem, force, pen;
combine_demerits(prev, cur, force, pen, dem);
dem += prev_dem;
if (isinf (dem))
continue;
if (isinf (st[sys*rank + max_index].demerits_)
|| dem < st[sys*rank + max_index].demerits_)
{
found_something = true;
st[sys*rank + max_index].demerits_ = dem;
st[sys*rank + max_index].force_ = force;
st[sys*rank + max_index].penalty_ = pen;
st[sys*rank + max_index].prev_ = j;
st[sys*rank + max_index].line_config_ = cur;
}
}
return found_something;
}
vector<Column_x_positions>
Constrained_breaking::do_solve ()
{
resize ();
return get_soln(0, systems_, -1);
}
void
Constrained_breaking::resize ()
{
if (!breaks_.size ())
{
/* do all the rod/spring problems */
breaks_ = find_break_indices ();
cols_rank_ = breaks_.size ();
all_ = pscore_->root_system ()->columns ();
cols_.resize (breaks_.size () * breaks_.size ());
for (vsize i = 0; i < breaks_.size () - 1; i++)
for (vsize j = i + 1; j < breaks_.size (); j++)
{
vector<Grob*> line (all_.begin () + breaks_[i],
all_.begin() + breaks_[j] + 1);
line[0] = dynamic_cast<Item *> (line[0])->find_prebroken_piece
(RIGHT);
line.back () = dynamic_cast<Item *> (line.back
())->find_prebroken_piece (LEFT);
cols_[i*cols_rank_ + j].cols_ = line;
/* we have no idea what line this will be -- only whether it is
the first */
Interval line_dims = line_dimensions_int (pscore_->layout (), i);
Simple_spacer_wrapper *sp = generate_spacing_problem (line,
line_dims);
/* TODO: support raggedness */
sp->solve (&cols_[i*cols_rank_ + j], false);
if (!cols_[i*cols_rank_ + j].satisfies_constraints_)
break;
delete sp;
}
/* work out all the starting indices */
for (vsize i = 0; i < start_.size (); i++)
{
vsize j;
for (j = 0; j < breaks_.size () - 1 && breaks_[j] < start_[i]; j++)
;
starting_breakpoints_.push_back (j);
start_[i] = breaks_[j];
}
state_.resize (start_.size ());
}
if (!systems_) systems_ = 4; /* just to make this compatible with Gourlay */
for (vsize i = 0; i < state_.size (); i++)
state_[i].resize((breaks_.size () - starting_breakpoints_[i]) * systems_);
/* fill out the matrices */
for (vsize i = 0; i < state_.size (); i++)
for (int j = valid_systems_; j < systems_; j++)
for (vsize k = starting_breakpoints_[i] + j + 1; k < breaks_.size (); k++)
if (!calc_subproblem (i, j, k))
break; /* if we couldn't break this, it is too cramped already */
valid_systems_ = systems_;
}
vector<Column_x_positions>
Constrained_breaking::get_soln (int start, int end, int nsys)
{
int rank, brk;
prepare_solution (start, end, nsys, rank, brk);
vector<Constrained_break_node> const &st = state_[start];
vector<Column_x_positions> ret;
for (int sys = nsys-1; sys >= 0; sys--)
{
assert (brk > 0);
ret.push_back( st[sys*rank + brk].line_config_ );
brk = st[sys*rank + brk].prev_;
}
assert (brk == 0);
reverse (ret);
return ret;
}
Real
Constrained_breaking::get_demerits (int start, int end, int nsys)
{
int rank, brk;
prepare_solution (start, end, nsys, rank, brk);
return state_[start][(nsys-1)*rank + brk].demerits_;
}
Real
Constrained_breaking::get_force (int start, int end, int nsys)
{
int rank, brk;
prepare_solution (start, end, nsys, rank, brk);
vector<Constrained_break_node> const &st = state_[start];
Real f = 0;
for (int sys = nsys-1; sys >= 0 && brk >= 0; sys--)
{
f += fabs (st[sys*rank + brk].force_);
brk = st[sys*rank + brk].prev_;
}
if (brk < 0)
f = infinity_f;
return f;
}
Real
Constrained_breaking::get_penalty (int start, int end, int nsys)
{
int rank, brk;
prepare_solution (start, end, nsys, rank, brk);
return state_[start][(nsys-1)*rank + brk].penalty_;
}
Real
Constrained_breaking::get_page_penalty (int start, int end, int nsys, int
sys_num)
{
int rank, brk;
prepare_solution (start, end, nsys, rank, brk);
int sys;
for (sys = nsys-1; sys > sys_num; sys--)
brk = state_[start][sys*rank + brk].prev_;
if (brk < 0) /* we didn't satisfy constraints */
return 0;
vector<Grob*> &cols = state_[start][sys*rank + brk].line_config_.cols_;
if (cols.empty ())
return 0;
Grob *pc = cols.back ();
if (pc->original ())
{
SCM pen = pc->get_property ("page-penalty");
if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
return scm_to_double (pen);
}
return 0;
}
int
Constrained_breaking::get_min_systems (int start, int end)
{
int rank, brk;
prepare_solution (start, end, 1, rank, brk);
int nsys;
vector<Constrained_break_node> const &st = state_[start];
/* nsys < rank : rank is the # of breakpoints, we can't have more systems */
for (nsys = 0; nsys < rank; nsys++)
{
if (nsys >= valid_systems_)
{
systems_ = nsys + 3;
resize ();
}
if (!isinf (st[nsys*rank + brk].force_))
return nsys + 1;
}
/* no possible breaks satisfy constraints */
return 0;
}
int
Constrained_breaking::get_max_systems (int start, int end)
{
int brk = (end < 0 || end >= (int)start_.size ()) ? breaks_.size () - 1 :
start_[end];
return brk - starting_breakpoints_[start];
}
void
Constrained_breaking::prepare_solution (int start, int end, int nsys, int
&rank, int &brk)
{
assert (start < (int)start_.size () && end <= (int)start_.size ());
assert (end < 0 || start < end);
assert (nsys > 0);
if (nsys >= valid_systems_)
{
systems_ = nsys;
resize ();
}
if (end == (int)start_.size ())
end = -1;
rank = breaks_.size () - starting_breakpoints_[start];
brk = end < 0 ? breaks_.size () - 1 : starting_breakpoints_[end];
brk -= starting_breakpoints_[start];
}
Constrained_breaking::Constrained_breaking ()
{
valid_systems_ = systems_ = 0;
start_.push_back (0);
}
Constrained_breaking::Constrained_breaking (vector<int> const &start):
start_ (start)
{
valid_systems_ = systems_ = 0;
}
void
Constrained_breaking::combine_demerits (Column_x_positions const &prev,
Column_x_positions const &col,
Real &force,
Real &penalty,
Real &demerits) const
{
penalty = 0;
if (col.cols_.empty () || !col.satisfies_constraints_)
force = infinity_f;
else
{
force = col.force_;
Grob *pc = col.cols_.back ();
if (pc->original ())
{
SCM pen = pc->get_property ("penalty");
if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
penalty += scm_to_double (pen);
}
}
demerits = force * force + abs (prev.force_ - force) + penalty;
}
/*
constrained-breaking.hh -- declare a line breaker that
supports limits on the number of systems
source file of the GNU LilyPond music typesetter
(c) 1997--2005 Han-Wen Nienhuys <address@hidden>
*/
#ifndef RESTRAINED_BREAKING_HH
#define RESTRAINED_BREAKING_HH
#include "break-algorithm.hh"
/**
Helper to trace back an optimal path
*/
struct Constrained_break_node
{
/** the number of bars in all the systems before this one
*/
int prev_;
/** unlike the Gourlay breaker, this is the sum of all demerits up to,
* and including, this line */
Real demerits_;
Real force_;
Real penalty_;
Column_x_positions line_config_;
Constrained_break_node ()
{
prev_ = -1;
demerits_ = infinity_f;
force_ = infinity_f;
penalty_ = 0;
line_config_.satisfies_constraints_ = false;
}
void print () const
{
printf ("prev break %d, demerits %f\n",
prev_, demerits_);
}
};
/**
A dynamic programming solution to breaking scores into lines
*/
class Constrained_breaking : public Break_algorithm
{
public:
std::vector<Column_x_positions> do_solve ();
Constrained_breaking ();
Constrained_breaking (std::vector<int> const &start_col_posns);
/* return an optimal solution with n_sys systems */
/* (n_sys must be less than systems_) and with */
/* max column index no greater than max_col */
std::vector<Column_x_positions> get_soln(int start, int end, int sys_count);
Real get_demerits (int start, int end, int sys_count);
Real get_force (int start, int end, int sys_count);
Real get_penalty (int start, int end, int sys_count);
int get_max_systems (int start, int end);
int get_min_systems (int start, int end);
/* get the page penalty of system number sys with the given breaking */
Real get_page_penalty (int start, int end, int sys_count, int sys);
private:
int valid_systems_;
int systems_;
/* the (i,j)th entry is the column configuration for breaking between
* columns i and j */
std::vector<Column_x_positions> cols_;
int cols_rank_;
/* the [i](j,k)th entry is the score for fitting the first k bars onto the
* first j systems, starting at the i'th allowed starting column */
std::vector<std::vector<Constrained_break_node> > state_;
vector<int> start_; /* the columns at which we might be asked to
start breaking */
vector<int> starting_breakpoints_; /* the corresponding index in breaks_ */
vector<Grob*> all_;
std::vector<int> breaks_;
void prepare_solution (int start, int end, int sys_count, int &rank, int
&brk);
void combine_demerits (Column_x_positions const &, Column_x_positions const
&,
Real &force, Real &pen, Real &dem) const;
/* return false if we could not break this subproblem at all */
bool calc_subproblem(int start, int systems, int max_break_index);
void resize ();
};
#endif /* RESTRAINED_BREAKING_HH */
/*
optimal-breaking.hh -- break lines and pages optimally
for a whole Paper_book.
source file of the GNU LilyPond music typesetter
(c) 2006 Han-Wen Nienhuys <address@hidden>
*/
#ifndef OPTIMAL_PAGE_BREAKING_HH
#define OPTIMAL_PAGE_BREAKING_HH
#include "constrained-breaking.hh"
#include "lily-guile.hh"
class Prob;
class Paper_score;
/* Either a paper-score, markup or header. For paper scores, we record the
* size of a single system. For the others, we record the size of the entire
* thing. */
struct System_spec
{
System_spec (Paper_score*, int);
System_spec (Prob*);
System_spec ();
Real size_;
Real between_size_; // just like size_ but we ignore it for the last system
Real between_space_;
Real penalty_; // we need a break penalty here as well as in
// Break_position because the break positions are only at
// possible page turns -- this could be a page break w/o
// a page turn
Paper_score *pscore_;
Prob *prob_;
int score_break_count_; // for scores, this is the number of start-points our
line-
// breaker has
};
struct Break_position
{
int sys_; /* the index in our all_ list */
int score_brk_; // if sys_ is a score, then we start at the score_brk_'th
// possible page-break in the score
Real penalty_;
Break_position(int s=-1, int brk=-1, Real pen=0)
{
sys_ = s;
score_brk_ = brk;
penalty_ = pen;
}
};
/**
* A much simplified rods-and-springs problem.
*/
struct Page_spacing
{
Real force_;
Real page_height_;
Real rod_height_;
Real spring_len_;
Real spring_space_;
Real inverse_spring_k_;
Page_spacing ()
{
force_ = page_height_ = rod_height_ = spring_len_ = 0;
spring_space_ = inverse_spring_k_ = 0;
}
};
/**
Helper to trace back an optimal path
*/
struct Optimal_break_node
{
int prev_;
int page_number_;
Real force_;
/** unlike the Gourlay breaker, this is the sum of all demerits up to,
* and including, this page */
Real demerits_;
Real line_demerits_;
int break_pos_; // index into breaks_
vector<vsize> div_; // our division of systems between scores on this page
int left_page_sys_, right_page_sys_; // number of systems on each page
Optimal_break_node ()
{
prev_ = -1;
left_page_sys_ = right_page_sys_ = -1;
line_demerits_ = force_ = 0;
demerits_ = infinity_f;
page_number_ = 0;
}
void print () const
{
printf ("prev break %d, demerits %f\n",
prev_, demerits_);
}
};
/**
A dynamic programming solution to breaking pages
*/
class Optimal_breaking
{
public:
// return a list of pages
SCM solve ();
Optimal_breaking (Paper_book *pb);
private:
// the ith entry is for distributing the first i page-breakable-chunks
std::vector<Optimal_break_node> state_;
std::vector<Break_position> breaks_;
// list of Paper_score and Prob objects
std::vector<System_spec> all_;
// One line breaker for each paper score
std::vector<Constrained_breaking> line_breaking_;
Paper_book *book_;
int next_system (int starting_brk_index) const;
Real page_height (int pnum, bool last);
void fill_page (vector<System_spec> const &sys, Page_spacing &page);
/* move the given system from the left page to the right page,
* updating all the forces. prev will now be the last system on the
* left page */
void shift_system (const System_spec &sys,
const System_spec &prev,
Drul_array<Page_spacing> &pages);
/* given a group of systems and a scheme for dividing the
* score_systems between available scores, find the optimum way
* of dividing the systems between two pages. Set left_page_sys_,
* right_page_sys_, force_ and page_penalty_. */
void best_page (std::vector<System_spec> const &sys,
Optimal_break_node &me);
void create_system_list ();
std::vector<int> find_page_break_indices (Paper_score *pscore);
void add_break_penalty (Prob *pb);
/* return a vector of all the systems */
SCM do_line_breaking (vector<Optimal_break_node> const &soln);
/* return a list of pages */
SCM make_pages (vector<Optimal_break_node> const &soln, SCM systems);
/* calculate the min and max numbers of systems for each system_spec */
void calc_system_bounds (vsize start, vsize end,
vector<vsize> &min,
vector<vsize> &max);
/* calculate all possible ways of dividing system_count between the
System_specs */
void divide_systems (int system_count, vector<vsize> const &min,
vector<vsize> const &max,
vector<vector<vsize> > &result,
vector<vsize> &cur);
void calc_demerits (Optimal_break_node &me);
void calc_page_demerits (Optimal_break_node &me);
void calc_subproblem (int);
void line_brk_args (vsize i, int &break_st, int &break_end);
Real get_page_penalty (vsize sys, int sys_count, int break_st, int
break_end, int sys_num);
Real get_line_break_dems (vsize sys, int sys_count, int break_st, int
break_end);
Real get_line_force (vsize sys, int sys_count, int break_st, int break_end);
Real get_line_penalty (vsize sys, int sys_count, int break_st, int
break_end);
vsize get_min_systems (vsize sys, int break_start, int break_end);
vsize get_max_systems (vsize sys, int break_start, int break_end);
std::vector<Column_x_positions> get_line_breaks (vsize sys, int sys_count,
int st, int end);
};
#endif // OPTIMAL_BREAKING_HH
- Re: setting the number of pages for a score, (continued)
Re: setting the number of pages for a score, Jan Nieuwenhuizen, 2006/02/10
Re: setting the number of pages for a score, Joe Neeman, 2006/02/13
- Re: setting the number of pages for a score, Han-Wen Nienhuys, 2006/02/14
- Re: setting the number of pages for a score, Joe Neeman, 2006/02/14
- Re: setting the number of pages for a score, Han-Wen Nienhuys, 2006/02/14
- Re: setting the number of pages for a score, Han-Wen Nienhuys, 2006/02/14
- Re: setting the number of pages for a score, Joe Neeman, 2006/02/14
- Re: setting the number of pages for a score, Joe Neeman, 2006/02/15
Re: setting the number of pages for a score,
Joe Neeman <=
Re: setting the number of pages for a score, Joe Neeman, 2006/02/19
Re: setting the number of pages for a score, Han-Wen Nienhuys, 2006/02/19
Re: setting the number of pages for a score, Joe Neeman, 2006/02/19
Re: setting the number of pages for a score, Han-Wen Nienhuys, 2006/02/19
Re: setting the number of pages for a score, Joe Neeman, 2006/02/19
Re: setting the number of pages for a score, Joe Neeman, 2006/02/19
Re: setting the number of pages for a score, Werner LEMBERG, 2006/02/20
Re: setting the number of pages for a score, Joe Neeman, 2006/02/20
Re: setting the number of pages for a score, Werner LEMBERG, 2006/02/21
Re: setting the number of pages for a score, Joe Neeman, 2006/02/21