[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: dumb stacking page breaker
From: |
Nicolas Sceaux |
Subject: |
Re: dumb stacking page breaker |
Date: |
Wed, 11 Jul 2007 23:07:45 +0200 |
User-agent: |
Gnus/5.11 (Gnus v5.11) Emacs/22.1 (darwin) |
Nicolas Sceaux <address@hidden> writes:
> When building scores >>20 pages (some of my scores have more than 150),
> the time and amount of memory used by the ly:optimal-page-breaking
> function is crippling (it also used to be the case with the original
> optimal page breaking function).
>
> [...]
>
> 1) compute the line breaks in the most straightforward way, that is
> without considering page breaks or the number of systems per page.
> Just lines as regular as possible wrt horizontal spacing and
> considering the manual line break permissions.
>
> 2) compute the page breaks by stacking on each page as many lines as
> possible, and account for manual page break permissions.
Joe,
Here is a patch where a stacking-page-breaking function is
implemented. May you review it, and tell me if there is something wrong
or some bad coding, before I go on with documentation and regression
tests? The first tests I have made so far are satisfying. (Also
suggestions for a better name are welcome:)
nicolas
diff --git a/lily/include/page-breaking.hh b/lily/include/page-breaking.hh
index 082384d..98ed808 100644
--- a/lily/include/page-breaking.hh
+++ b/lily/include/page-breaking.hh
@@ -116,6 +116,11 @@ protected:
void break_into_pieces (vsize start, vsize end, Line_division const &div);
SCM systems ();
+ vector<Line_details> get_uncompressed_lines (Page_breaking::Line_division
const &div);
+ static vector<Line_details> compress_lines (const vector<Line_details>
&orig);
+ static vector<vsize> uncompress_solution (vector<vsize> const
&systems_per_page,
+ vector<Line_details> const
&compressed);
+
void set_current_breakpoints (vsize start,
vsize end,
vsize system_count,
diff --git a/lily/include/stacking-page-breaking.hh
b/lily/include/stacking-page-breaking.hh
new file mode 100644
index 0000000..61b2b36
--- /dev/null
+++ b/lily/include/stacking-page-breaking.hh
@@ -0,0 +1,30 @@
+/*
+ stacking-page-breaking.hh -- declare a page-breaker that stacks as
+ many systems on a page before moving to the next one. Specialized
+ for books with many pages, or a lot of text.
+
+ source file of the GNU LilyPond music typesetter
+
+ (c) 2007 Nicolas Sceaux <address@hidden>
+*/
+
+#ifndef STACKING_PAGE_BREAKING_HH
+#define STACKING_PAGE_BREAKING_HH
+
+#include "page-breaking.hh"
+#include "page-spacing.hh"
+
+class Stacking_page_breaking: public Page_breaking
+{
+public:
+ virtual SCM solve ();
+
+ Stacking_page_breaking (Paper_book *pb);
+ virtual ~Stacking_page_breaking ();
+
+protected:
+ vector<vsize> compute_page_breaks (vector<Line_details> const &lines,
+ int first_page_num);
+};
+
+#endif /* STACKING_PAGE_BREAKING_HH */
diff --git a/lily/page-breaking-scheme.cc b/lily/page-breaking-scheme.cc
index 2241b50..0a86744 100644
--- a/lily/page-breaking-scheme.cc
+++ b/lily/page-breaking-scheme.cc
@@ -10,6 +10,7 @@
#include "paper-book.hh"
#include "page-turn-page-breaking.hh"
#include "optimal-page-breaking.hh"
+#include "stacking-page-breaking.hh"
LY_DEFINE (ly_page_turn_breaking, "ly:page-turn-breaking",
1, 0, 0, (SCM pb),
@@ -30,3 +31,13 @@ LY_DEFINE (ly_optimal_breaking, "ly:opti
Optimal_page_breaking b (unsmob_paper_book (pb));
return b.solve ();
}
+
+LY_DEFINE (ly_stacking_breaking, "ly:stacking-breaking",
+ 1, 0, 0, (SCM pb),
+ "Break (pages and lines) the @code{Paper_book} object @var{pb}"
+ "without looking for optimal spacing: stack as many lines on"
+ "a page before moving to the next one.")
+{
+ Stacking_page_breaking b (unsmob_paper_book (pb));
+ return b.solve ();
+}
diff --git a/lily/page-breaking.cc b/lily/page-breaking.cc
index 9ad8336..9b6f3a2 100644
--- a/lily/page-breaking.cc
+++ b/lily/page-breaking.cc
@@ -21,8 +21,8 @@
/* for each forbidden page break, merge the systems around it into one
system. */
-static vector<Line_details>
-compress_lines (const vector<Line_details> &orig)
+vector<Line_details>
+Page_breaking::compress_lines (const vector<Line_details> &orig)
{
vector<Line_details> ret;
@@ -56,9 +56,9 @@ compress_lines (const vector<Line_detail
/* translate the number of systems-per-page into something meaningful for
the uncompressed lines.
*/
-static vector<vsize>
-uncompress_solution (vector<vsize> const &systems_per_page,
- vector<Line_details> const &compressed)
+vector<vsize>
+Page_breaking::uncompress_solution (vector<vsize> const &systems_per_page,
+ vector<Line_details> const &compressed)
{
vector<vsize> ret;
vsize start_sys = 0;
@@ -521,39 +521,47 @@ Page_breaking::current_configuration_cou
return current_configurations_.size ();
}
+vector<Line_details>
+Page_breaking::get_uncompressed_lines (Page_breaking::Line_division const &div)
+{
+ vector<Line_details> uncompressed_line_details;
+ SCM padding_scm = book_->paper_->c_variable
("page-breaking-between-system-padding");
+ if (!scm_is_number (padding_scm))
+ padding_scm = book_->paper_->c_variable ("between-system-padding");
+ Real padding = robust_scm2double (padding_scm, 0.0);
+
+ uncompressed_line_details.clear ();
+ for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
+ {
+ vsize sys = next_system (current_chunks_[i]);
+ if (system_specs_[sys].pscore_)
+ {
+ vsize start;
+ vsize end;
+ line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1],
&start, &end);
+ vector<Line_details> details = line_breaking_[sys].line_details
(start, end, div[i]);
+ uncompressed_line_details.insert (uncompressed_line_details.end (),
details.begin (), details.end ());
+ }
+ else
+ {
+ assert (div[i] == 1);
+ uncompressed_line_details.push_back (Line_details
(system_specs_[sys].prob_));
+ uncompressed_line_details.back ().padding_ =
+ robust_scm2double (system_specs_[sys].prob_->get_property
("next-padding"),
+ padding);
+ }
+ }
+ return uncompressed_line_details;
+}
+
void
Page_breaking::cache_line_details (vsize configuration_index)
{
+ /* what is the purpose of cached_configuration_index_? it is never set,
+ save in clear_line_details_cache -- ns */
if (cached_configuration_index_ != configuration_index)
{
- SCM padding_scm = book_->paper_->c_variable
("page-breaking-between-system-padding");
- if (!scm_is_number (padding_scm))
- padding_scm = book_->paper_->c_variable ("between-system-padding");
- Real padding = robust_scm2double (padding_scm, 0.0);
-
- Line_division &div = current_configurations_[configuration_index];
- uncompressed_line_details_.clear ();
- for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
- {
- vsize sys = next_system (current_chunks_[i]);
- if (system_specs_[sys].pscore_)
- {
- vsize start;
- vsize end;
- line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1],
&start, &end);
-
- vector<Line_details> details = line_breaking_[sys].line_details
(start, end, div[i]);
- uncompressed_line_details_.insert (uncompressed_line_details_.end
(), details.begin (), details.end ());
- }
- else
- {
- assert (div[i] == 1);
- uncompressed_line_details_.push_back (Line_details
(system_specs_[sys].prob_));
- uncompressed_line_details_.back ().padding_ =
- robust_scm2double (system_specs_[sys].prob_->get_property
("next-padding"),
- padding);
- }
- }
+ uncompressed_line_details_ = get_uncompressed_lines
(current_configurations_[configuration_index]);
cached_line_details_ = compress_lines (uncompressed_line_details_);
}
}
diff --git a/lily/stacking-page-breaking.cc b/lily/stacking-page-breaking.cc
new file mode 100644
index 0000000..b54702b
--- /dev/null
+++ b/lily/stacking-page-breaking.cc
@@ -0,0 +1,99 @@
+/*
+ stacking-page-breaking.cc -- implement a page-breaker that stacks as
+ many systems on a page before moving to the next one. Specialized
+ for books with many pages, or a lot of text.
+
+ source file of the GNU LilyPond music typesetter
+
+ (c) 2007 Nicolas Sceaux <address@hidden>
+*/
+
+#include "international.hh"
+#include "stacking-page-breaking.hh"
+#include "output-def.hh"
+#include "page-spacing.hh"
+#include "paper-book.hh"
+
+static bool
+is_break (Grob *g)
+{
+ (void) g; /* shutup warning */
+ return false;
+}
+
+Stacking_page_breaking::Stacking_page_breaking (Paper_book *pb)
+ : Page_breaking (pb, is_break)
+{
+}
+
+Stacking_page_breaking::~Stacking_page_breaking ()
+{
+}
+
+vector<vsize>
+Stacking_page_breaking::compute_page_breaks (vector<Line_details> const &lines,
+ int first_page_num)
+{
+ vector<vsize> systems_per_page;
+ vsize line = 0;
+ vsize page_first_line = 0;
+ for (vsize page = 0 ; line < lines.size () ; page ++)
+ {
+ Page_spacing space (page_height (page + first_page_num, false));
+ page_first_line = line;
+ bool go_to_next_page = false;
+ while ((line < lines.size ()) && !go_to_next_page)
+ {
+ space.append_system (lines [line]);
+ if ((line > page_first_line)
+ && (isinf (space.force_)
+ || (lines [line].page_permission_ == ly_symbol2scm
("force"))))
+ {
+ systems_per_page.push_back (line - page_first_line);
+ go_to_next_page = true;
+ }
+ else
+ {
+ if (line == lines.size () - 1)
+ systems_per_page.push_back (line + 1 - page_first_line);
+ line ++;
+ }
+ }
+ }
+ Page_spacing space (page_height (systems_per_page.size () - 1 +
first_page_num, true));
+ for (line = page_first_line ; line < lines.size () ; line ++)
+ {
+ space.append_system (lines [line]);
+ if ((line > page_first_line) && isinf (space.force_))
+ {
+ /* put this line and the following on another page */
+ systems_per_page.back () = line - page_first_line;
+ systems_per_page.push_back (lines.size () - line);
+ break;
+ }
+ }
+ return systems_per_page;
+}
+
+SCM
+Stacking_page_breaking::solve ()
+{
+ vsize end = last_break_position ();
+
+ message ("Computing line breaks...");
+ set_to_ideal_line_configuration (0, end);
+ break_into_pieces (0, end, current_configuration (0));
+
+ message (_ ("Computing page breaks..."));
+ vsize first_page_num = robust_scm2int (book_->paper_->c_variable
("first-page-number"), 1);
+ vector<Line_details> uncompressed_lines = get_uncompressed_lines
(current_configuration (0));
+ vector<Line_details> compressed_lines = compress_lines (uncompressed_lines);
+ vector<vsize> systems_per_page = compute_page_breaks (compressed_lines,
first_page_num);
+ systems_per_page = uncompress_solution (systems_per_page, compressed_lines);
+
+ SCM lines = systems ();
+ return make_pages (systems_per_page, lines);
+}
+
+
+
- dumb stacking page breaker, Nicolas Sceaux, 2007/07/10
- Re: dumb stacking page breaker, Trevor Bača, 2007/07/10
- Re: dumb stacking page breaker, Joe Neeman, 2007/07/10
- Re: dumb stacking page breaker,
Nicolas Sceaux <=
- Re: dumb stacking page breaker, Joe Neeman, 2007/07/12
- Re: dumb stacking page breaker, Nicolas Sceaux, 2007/07/13
- Re: dumb stacking page breaker, Nicolas Sceaux, 2007/07/14
- Re: dumb stacking page breaker, Joe Neeman, 2007/07/14
- Re: dumb stacking page breaker, Nicolas Sceaux, 2007/07/15
- Re: dumb stacking page breaker, Joe Neeman, 2007/07/15