summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJoe Neeman <joeneeman@gmail.com>2009-03-12 15:06:37 -0700
committerJoe Neeman <joeneeman@gmail.com>2009-03-12 15:07:34 -0700
commitdf221999366536dd66fbad10d1a3a32657976d99 (patch)
treec0126276a52b92b626718c201c7887015e7115e1
parent626609cc7a4ae66412702d2c22eef2eb3088917e (diff)
Tie up some loose ends with min-systems-per-page.
Adds regression tests for min-systems-per-page.
-rw-r--r--input/regression/page-breaking-min-systems-per-page1.ly18
-rw-r--r--input/regression/page-breaking-min-systems-per-page2.ly14
-rw-r--r--lily/include/page-breaking.hh1
-rw-r--r--lily/include/page-spacing-result.hh11
-rw-r--r--lily/include/page-spacing.hh4
-rw-r--r--lily/optimal-page-breaking.cc37
-rw-r--r--lily/page-breaking.cc67
-rw-r--r--lily/page-spacing-result.cc1
-rw-r--r--lily/page-spacing.cc18
9 files changed, 134 insertions, 37 deletions
diff --git a/input/regression/page-breaking-min-systems-per-page1.ly b/input/regression/page-breaking-min-systems-per-page1.ly
new file mode 100644
index 0000000000..b8e9ce6a1a
--- /dev/null
+++ b/input/regression/page-breaking-min-systems-per-page1.ly
@@ -0,0 +1,18 @@
+\version "2.13.1"
+
+#(set-default-paper-size "a6")
+
+\header {
+ texidoc = "The min-systems-per-page variable forces each page to have
+a minimum number of systems. Titles do not count as systems here.
+
+This exposes a bug with the current implementation; min-systems-per-page
+is not honored if to do so we would need uneven line breaking."
+ title = "Example"
+}
+
+\paper {
+ min-systems-per-page = 5
+}
+
+{ \repeat unfold 11 { c'1 } \pageBreak \repeat unfold 6 { c'1 } } \ No newline at end of file
diff --git a/input/regression/page-breaking-min-systems-per-page2.ly b/input/regression/page-breaking-min-systems-per-page2.ly
new file mode 100644
index 0000000000..56fb1a61fb
--- /dev/null
+++ b/input/regression/page-breaking-min-systems-per-page2.ly
@@ -0,0 +1,14 @@
+\version "2.13.1"
+
+#(set-default-paper-size "a6")
+
+\header {
+ texidoc = "The min-systems-per-page variable takes precedence over
+the desire not to overfill a page."
+}
+
+\paper {
+ min-systems-per-page = 20
+}
+
+\repeat unfold 21 { c'1 } \ No newline at end of file
diff --git a/lily/include/page-breaking.hh b/lily/include/page-breaking.hh
index 9fa108edd2..c6c1bc02c8 100644
--- a/lily/include/page-breaking.hh
+++ b/lily/include/page-breaking.hh
@@ -108,6 +108,7 @@ public:
Real page_top_space () const;
vsize system_count () const;
Real line_count_penalty (int line_count) const;
+ int line_count_status (int line_count) const;
bool too_many_lines (int line_count) const;
bool too_few_lines (int line_count) const;
diff --git a/lily/include/page-spacing-result.hh b/lily/include/page-spacing-result.hh
index 870fbda7e1..83da406df0 100644
--- a/lily/include/page-spacing-result.hh
+++ b/lily/include/page-spacing-result.hh
@@ -13,11 +13,22 @@
#include "std-vector.hh"
#include "lily-proto.hh"
+// This enum is a bitfield: since we use one System_count_status
+// to represent the system count of several pages simultaneously,
+// it could be that one page has too many systems while another
+// has too few.
+typedef enum {
+ SYSTEM_COUNT_OK = 0,
+ SYSTEM_COUNT_TOO_MANY = 1,
+ SYSTEM_COUNT_TOO_FEW = 2
+} System_count_status;
+
struct Page_spacing_result {
vector<vsize> systems_per_page_;
vector<Real> force_;
Real penalty_;
Real demerits_;
+ int system_count_status_;
Real average_force () const;
vsize page_count () const;
diff --git a/lily/include/page-spacing.hh b/lily/include/page-spacing.hh
index 3730262c75..958a1b21ff 100644
--- a/lily/include/page-spacing.hh
+++ b/lily/include/page-spacing.hh
@@ -26,7 +26,7 @@
BAD_SPACING_PENALTY is for occasions where the spacing is bad.
TERRIBLE_SPACING_PENALTY is for when we are disregarding a user override
- (for example, we are failing to satisfy min-systems-per-page. These user
+ (for example, we are failing to satisfy min-systems-per-page). These user
overrides are more important than getting good spacing, so they get a
larger penalty.
*/
@@ -53,12 +53,14 @@ private:
force_ = infinity_f;
penalty_ = infinity_f;
prev_ = VPOS;
+ system_count_status_ = SYSTEM_COUNT_OK;
}
Real demerits_;
Real force_;
Real penalty_;
vsize prev_;
+ int system_count_status_;
};
Page_breaking const *breaker_;
diff --git a/lily/optimal-page-breaking.cc b/lily/optimal-page-breaking.cc
index 47a2edafbe..13b2669aaf 100644
--- a/lily/optimal-page-breaking.cc
+++ b/lily/optimal-page-breaking.cc
@@ -23,6 +23,11 @@ is_break (Grob *)
return false;
}
+// FIXME: divide the page breaking into subproblems wherever there is a page break.
+// This will allow us to tweak line-breaking independently on both sides of a
+// page break (currently, we only get to request a number of systems for an entire score
+// at a time), which is necessary for min-systems-per-page and \pageBreak to interact
+// correctly.
Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
: Page_breaking (pb, is_break)
{
@@ -102,27 +107,34 @@ Optimal_page_breaking::solve ()
else
cur = space_systems_on_n_or_one_more_pages (i, page_count-1, first_page_num);
- if (cur.demerits_ < best_for_this_sys_count.demerits_ || isinf (best_for_this_sys_count.demerits_))
+ if (cur.demerits_ < best_for_this_sys_count.demerits_)
{
best_for_this_sys_count = cur;
bound = current_configuration (i);
}
}
- if (best_for_this_sys_count.demerits_ < best.demerits_ || isinf (best.demerits_))
+ if (best_for_this_sys_count.demerits_ < best.demerits_)
{
best = best_for_this_sys_count;
best_division = bound;
}
- /* if the pages are stretched on average, stop trying to reduce sys_count */
- if (best_for_this_sys_count.page_count () < page_count
- && best_for_this_sys_count.average_force () > 0)
- break;
-
+ /* Check to see if we already have too few systems. There are two ways
+ we check this: if we are trying one less than the ideal number of pages
+ and the pages are stretched on average then we have too
+ few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
+ have too few systems. In either case, though, we need to continue reducing
+ the number of systems if max-systems-per-page requires it. */
+ if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
+ {
+ if (best_for_this_sys_count.page_count () < page_count
+ && best_for_this_sys_count.average_force () > 0)
+ break;
- if (isinf (best_for_this_sys_count.demerits_))
- break;
+ if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
+ break;
+ }
}
/* try a larger number of systems than the ideal line breaking number. This
@@ -144,19 +156,20 @@ Optimal_page_breaking::solve ()
else
cur = space_systems_on_n_pages (i, page_count, first_page_num);
- if (cur.demerits_ < best.demerits_ || isinf (best.demerits_))
+ if (cur.demerits_ < best.demerits_)
{
best = cur;
best_division = current_configuration (i);
}
- if (cur.demerits_ < best_demerits_for_this_sys_count || isinf (best_demerits_for_this_sys_count))
+ if (cur.demerits_ < best_demerits_for_this_sys_count)
{
best_demerits_for_this_sys_count = cur.demerits_;
bound = current_configuration (i);
}
}
- if (isinf (best_demerits_for_this_sys_count))
+ if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
+ && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
break;
}
diff --git a/lily/page-breaking.cc b/lily/page-breaking.cc
index 3bc8597c2a..1c0d21cdc7 100644
--- a/lily/page-breaking.cc
+++ b/lily/page-breaking.cc
@@ -101,9 +101,20 @@ Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
page_top_space_ = robust_scm2double (pb->paper_->c_variable ("page-top-space"), 0);
- systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0);
- max_systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0);
- min_systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0);
+ systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
+ max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
+ min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
+
+ if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
+ {
+ warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
+ min_systems_per_page_ = max_systems_per_page_ = 0;
+ }
+ if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
+ {
+ warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
+ min_systems_per_page_ = max_systems_per_page_ = 0;
+ }
create_system_list ();
find_chunks_and_breaks (is_break);
@@ -178,6 +189,17 @@ Page_breaking::line_count_penalty (int line_count) const
return 0;
}
+int
+Page_breaking::line_count_status (int line_count) const
+{
+ if (too_many_lines (line_count))
+ return SYSTEM_COUNT_TOO_MANY;
+ if (too_few_lines (line_count))
+ return SYSTEM_COUNT_TOO_FEW;
+
+ return SYSTEM_COUNT_OK;
+}
+
/* translate indices into breaks_ into start-end parameters for the line breaker */
void
Page_breaking::line_breaker_args (vsize sys,
@@ -691,11 +713,10 @@ Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
+ ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
+ int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
- line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
-
- if ((next_height > cur_page_height && cur_rod_height > 0)
- || too_many_lines (line_count)
+ if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
+ || too_many_lines (next_line_count)
|| (i > 0
&& cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
{
@@ -709,6 +730,7 @@ Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
{
cur_rod_height = next_rod_height;
cur_spring_height = next_spring_height;
+ line_count = next_line_count;
}
}
@@ -727,7 +749,8 @@ Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
cur_page_height = page_height (first_page_num + ret - 1, true);
Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
- if (cur_height > cur_page_height
+ if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
+ && cur_height > cur_page_height
/* don't increase the page count if the last page had only one system */
&& cur_rod_height > cached_line_details_.back ().extent_.length ())
ret++;
@@ -918,6 +941,7 @@ Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
Page_spacing_result
Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
{
+ // TODO: add support for min/max-systems-per-page.
Page_spacing_result res;
vsize page = 0;
vsize page_first_line = 0;
@@ -987,7 +1011,7 @@ Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result
Real line_force = 0;
Real line_penalty = 0;
- Real page_force = 0;
+ Real page_demerits = res.penalty_;
Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
@@ -999,10 +1023,8 @@ Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result
for (vsize i = 0; i < res.force_.size (); i++)
{
Real f = res.force_[i];
- if (isinf (f) && res.systems_per_page_[i] == 1)
- page_force += BAD_SPACING_PENALTY;
- else
- page_force += f * f;
+
+ page_demerits += min(f*f, BAD_SPACING_PENALTY);
}
/* for a while we tried averaging page and line forces across pages instead
@@ -1010,7 +1032,7 @@ Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result
with a very bad page force (for example because of a forced page break),
the page breaker will put in a _lot_ of pages so that the bad force
becomes averaged out over many pages. */
- res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
+ res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
return res;
}
@@ -1038,6 +1060,7 @@ Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real
ret.systems_per_page_.push_back (lines.size ());
ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
+ ret.system_count_status_ |= line_count_status (line_count);
/* don't do finalize_spacing_result () because we are only an internal function */
return ret;
@@ -1074,6 +1097,12 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n
// on min-systems-per-page and max-systems-per-page.
vector<Real> page1_penalty;
vector<Real> page2_penalty;
+
+ // page1_status and page2_status keep track of whether the min-systems-per-page
+ // and max-systems-per-page constraints are satisfied.
+ vector<int> page1_status;
+ vector<int> page2_status;
+
Page_spacing page1 (page1_height, page_top_space_);
Page_spacing page2 (page2_height, page_top_space_);
int page1_line_count = 0;
@@ -1083,6 +1112,8 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n
page2_force.resize (cached_line_details_.size () - 1, infinity_f);
page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
+ page1_status.resize (cached_line_details_.size () - 1, 0);
+ page2_status.resize (cached_line_details_.size () - 1, 0);
/* find the page 1 and page 2 forces for each page-breaking position */
for (vsize i = 0; i < page1_force.size (); i++)
@@ -1094,6 +1125,7 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n
page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
page1_penalty[i] = line_count_penalty (page1_line_count);
+ page1_status[i] = line_count_status (page1_line_count);
if (ragged2)
page2_force[page2_force.size () - 1 - i] =
@@ -1101,6 +1133,7 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n
else
page2_force[page2_force.size () - 1 - i] = page2.force_;
page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
+ page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
}
/* find the position that minimises the sum of the page forces */
@@ -1109,14 +1142,11 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n
for (vsize i = 0; i < page1_force.size (); i++)
{
Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
- // FIXME: Why do we look at unevenness here? We don't use it in
- // finalize_spacing_result, so this gives us a different measure of demerits.
- Real uneven = 2 * (page1_force[i] - page2_force[i]);
// NOTE: we treat max-systems-per-page and min-systems-per-page as soft
// constraints. That is, we penalize harshly when they don't happen
// but we don't completely reject.
- Real dem = uneven * uneven + f
+ Real dem = f
+ page1_penalty[i] + page2_penalty[i]
+ cached_line_details_[i+1].page_penalty_
+ cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
@@ -1132,6 +1162,7 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n
ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
ret.force_.push_back (page1_force[best_sys_count-1]);
ret.force_.push_back (page2_force[best_sys_count-1]);
+ ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
+ cached_line_details_.back ().page_penalty_
+ cached_line_details_.back ().turn_penalty_
diff --git a/lily/page-spacing-result.cc b/lily/page-spacing-result.cc
index f3d5b21e22..19ae1d9b76 100644
--- a/lily/page-spacing-result.cc
+++ b/lily/page-spacing-result.cc
@@ -14,6 +14,7 @@ Page_spacing_result::Page_spacing_result ()
{
penalty_ = 0;
demerits_ = infinity_f;
+ system_count_status_ = SYSTEM_COUNT_OK;
}
vsize
diff --git a/lily/page-spacing.cc b/lily/page-spacing.cc
index 3eb4ecfe53..c60f0d88b1 100644
--- a/lily/page-spacing.cc
+++ b/lily/page-spacing.cc
@@ -198,15 +198,19 @@ Page_spacer::calc_subproblem (vsize page, vsize line)
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;
- line_count += lines_[page_start].compressed_nontitle_lines_count_;
space.prepend_system (lines_[page_start]);
- // FIXME: The following line doesn't respect min-systems-per-page. More
- // generally, what should we do when respecting min-systems-per-page
- // would cause a page to be overfull?
- if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged)))
+
+ // This 'if' statement is a little hard to parse. It won't consider this configuration
+ // if it is overfull unless the current configuration is the first one with this start
+ // point. We also make an exception (and consider this configuration) if the previous
+ // configuration we tried had fewer lines than min-systems-per-page.
+ if (!breaker_->too_few_lines (line_count)
+ && page_start < line
+ && (isinf (space.force_) || (space.force_ < 0 && ragged)))
break;
+ line_count += lines_[page_start].compressed_nontitle_lines_count_;
if (page > 0 || page_start == 0)
{
if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
@@ -221,7 +225,7 @@ Page_spacer::calc_subproblem (vsize page, vsize line)
Real penalty = breaker_->line_count_penalty (line_count);
if (page_start > 0)
- penalty = lines_[page_start-1].page_penalty_
+ penalty += lines_[page_start-1].page_penalty_
+ (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
demerits += penalty;
@@ -230,6 +234,8 @@ Page_spacer::calc_subproblem (vsize page, vsize line)
cur.demerits_ = demerits;
cur.force_ = space.force_;
cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
+ cur.system_count_status_ = breaker_->line_count_status (line_count)
+ | (prev ? prev->system_count_status_ : 0);
cur.prev_ = page_start - 1;
}
}