[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: |
Tue, 14 Feb 2006 11:43:52 +1100 |
|
User-agent: |
Mozilla Thunderbird 1.0.7 (X11/20051121) |
Oops, I sent this to myself rather than the list...
Anyway, I hope to have a (preliminary) version of the page/line
breaker combination up later today, so people can at least see the
design and ideas in it.
Ok, it took a bit longer than I thought, but here it is.
Known limitations:
- it won't let you start on the right-hand page
- it will choke badly (and probably crash) if it can't find
line-breaking that satisfies constraints
- it is slow
- the loop-breaking in Optimal_breaking::calc_subproblem is
particularly ugly and one reason for the slowness
- it prints a lot of debugging output
You use it by adding #(define page-breaking ly:optimal-breaking) in the
book's \paper block. The (paper-block) variables "blank-page-force" and
"blank-last-page-force" contain the penalties for leaving blank pages in
the middle and end of the score (the blank page will always be the
right-hand page). "system-height" specifies the height that the
page-breaker assumes systems to be. It doesn't affect how the systems
are actually spaced out at the end, just how they are broken into pages.
Any other questions, please ask.
Index: lily/book.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/book.cc,v
retrieving revision 1.55
diff -u -r1.55 book.cc
--- lily/book.cc 6 Feb 2006 01:13:58 -0000 1.55
+++ lily/book.cc 14 Feb 2006 00:27:16 -0000
@@ -125,10 +125,9 @@
paper_book->add_performance (perf->self_scm ());
else if (Paper_score *pscore = dynamic_cast<Paper_score *>
(output))
{
- SCM systems = pscore->get_paper_systems ();
if (ly_is_module (score->header_))
paper_book->add_score (score->header_);
- paper_book->add_score (systems);
+ paper_book->add_score (pscore->self_scm ());
}
outputs = scm_cdr (outputs);
Index: lily/break-algorithm.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/break-algorithm.cc,v
retrieving revision 1.54
diff -u -r1.54 break-algorithm.cc
--- lily/break-algorithm.cc 11 Feb 2006 11:35:18 -0000 1.54
+++ lily/break-algorithm.cc 14 Feb 2006 00:27:16 -0000
@@ -89,7 +89,7 @@
}
vector<Column_x_positions>
-Break_algorithm::solve () const
+Break_algorithm::solve ()
{
vector<Column_x_positions> h= do_solve ();
Index: lily/gourlay-breaking.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/gourlay-breaking.cc,v
retrieving revision 1.93
diff -u -r1.93 gourlay-breaking.cc
--- lily/gourlay-breaking.cc 11 Feb 2006 11:35:18 -0000 1.93
+++ lily/gourlay-breaking.cc 14 Feb 2006 00:27:17 -0000
@@ -75,7 +75,7 @@
inspiration.
*/
vector<Column_x_positions>
-Gourlay_breaking::do_solve () const
+Gourlay_breaking::do_solve ()
{
vector<Break_node> optimal_paths;
vector<Grob*> all
Index: lily/paper-book.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/paper-book.cc,v
retrieving revision 1.129
diff -u -r1.129 paper-book.cc
--- lily/paper-book.cc 11 Feb 2006 11:35:17 -0000 1.129
+++ lily/paper-book.cc 14 Feb 2006 00:27:19 -0000
@@ -365,7 +365,7 @@
pages_ = SCM_EOL;
SCM proc = paper_->c_variable ("page-breaking");
- pages_ = scm_apply_0 (proc, scm_list_2 (systems (), self_scm ()));
+ pages_ = scm_apply_0 (proc, scm_list_1(self_scm ()));
return pages_;
}
Index: lily/paper-score.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/paper-score.cc,v
retrieving revision 1.96
diff -u -r1.96 paper-score.cc
--- lily/paper-score.cc 11 Feb 2006 11:35:17 -0000 1.96
+++ lily/paper-score.cc 14 Feb 2006 00:27:19 -0000
@@ -28,7 +28,7 @@
layout_ = layout;
system_ = 0;
systems_ = SCM_EOL;
- paper_systems_ = SCM_EOL;
+ paper_systems_ = SCM_BOOL_F;
}
Paper_score::Paper_score (Paper_score const &s)
@@ -91,11 +91,6 @@
pc.back ()->set_property ("breakable", SCM_BOOL_T);
system_->pre_processing ();
-
- vector<Column_x_positions> breaking = calc_breaking ();
- system_->break_into_pieces (breaking);
-
- paper_systems_ = system_->get_paper_systems ();
}
System *
@@ -111,7 +106,13 @@
}
SCM
-Paper_score::get_paper_systems () const
+Paper_score::get_paper_systems ()
{
+ if (paper_systems_ == SCM_BOOL_F)
+ {
+ vector<Column_x_positions> breaking = calc_breaking ();
+ system_->break_into_pieces (breaking);
+ paper_systems_ = system_->get_paper_systems ();
+ }
return paper_systems_;
}
Index: lily/score.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/score.cc,v
retrieving revision 1.177
diff -u -r1.177 score.cc
--- lily/score.cc 6 Feb 2006 01:13:58 -0000 1.177
+++ lily/score.cc 14 Feb 2006 00:27:19 -0000
@@ -135,8 +135,7 @@
if (ly_is_module (header))
paper_book->add_score (header);
- SCM systems = pscore->get_paper_systems ();
- paper_book->add_score (systems);
+ paper_book->add_score (pscore->self_scm ());
paper_book->classic_output (outname);
paper_book->unprotect ();
Index: lily/system.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/system.cc,v
retrieving revision 1.138
diff -u -r1.138 system.cc
--- lily/system.cc 11 Feb 2006 11:35:17 -0000 1.138
+++ lily/system.cc 14 Feb 2006 00:27:24 -0000
@@ -205,7 +205,7 @@
for (vsize i = 0; i < breaking.size (); i++)
{
System *system = dynamic_cast<System *> (clone (i));
- system->rank_ = i;
+ system->rank_ = broken_intos_.size ();
vector<Grob*> c (breaking[i].cols_);
pscore_->typeset_system (system);
Index: lily/include/break-algorithm.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/break-algorithm.hh,v
retrieving revision 1.31
diff -u -r1.31 break-algorithm.hh
--- lily/include/break-algorithm.hh 11 Feb 2006 11:35:17 -0000 1.31
+++ lily/include/break-algorithm.hh 14 Feb 2006 00:27:24 -0000
@@ -30,14 +30,14 @@
Simple_spacer_wrapper *generate_spacing_problem (vector<Grob*> const &,
Interval) const;
- virtual vector<Column_x_positions> do_solve () const = 0;
+ virtual vector<Column_x_positions> do_solve () = 0;
public:
virtual ~Break_algorithm ();
Simple_spacer *(*get_line_spacer) ();
Break_algorithm ();
void set_pscore (Paper_score *);
- vector<Column_x_positions> solve () const;
+ vector<Column_x_positions> solve ();
};
#endif // BREAK_HH
Index: lily/include/gourlay-breaking.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/gourlay-breaking.hh,v
retrieving revision 1.21
diff -u -r1.21 gourlay-breaking.hh
--- lily/include/gourlay-breaking.hh 11 Feb 2006 11:35:16 -0000 1.21
+++ lily/include/gourlay-breaking.hh 14 Feb 2006 00:27:24 -0000
@@ -16,7 +16,7 @@
*/
struct Gourlay_breaking : public Break_algorithm
{
- vector<Column_x_positions> do_solve () const;
+ vector<Column_x_positions> do_solve ();
Gourlay_breaking ();
Real combine_demerits (Column_x_positions const &, Column_x_positions const
&) const;
};
Index: lily/include/paper-book.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/paper-book.hh,v
retrieving revision 1.37
diff -u -r1.37 paper-book.hh
--- lily/include/paper-book.hh 3 Feb 2006 01:32:16 -0000 1.37
+++ lily/include/paper-book.hh 14 Feb 2006 00:27:24 -0000
@@ -48,6 +48,9 @@
void output (SCM output_channel);
};
+class Prob;
+void set_system_penalty (Prob *ps, SCM header);
+
DECLARE_UNSMOB (Paper_book, paper_book)
#endif /* PAPER_BOOK_HH */
Index: lily/include/paper-score.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/paper-score.hh,v
retrieving revision 1.39
diff -u -r1.39 paper-score.hh
--- lily/include/paper-score.hh 11 Feb 2006 11:35:16 -0000 1.39
+++ lily/include/paper-score.hh 14 Feb 2006 00:27:24 -0000
@@ -30,7 +30,7 @@
void typeset_system (System *);
vector<Column_x_positions> calc_breaking ();
- SCM get_paper_systems () const;
+ SCM get_paper_systems ();
protected:
virtual void process ();
virtual void derived_mark () const;
Index: ly/paper-defaults.ly
===================================================================
RCS file: /sources/lilypond/lilypond/ly/paper-defaults.ly,v
retrieving revision 1.22
diff -u -r1.22 paper-defaults.ly
--- ly/paper-defaults.ly 10 Feb 2006 12:27:42 -0000 1.22
+++ ly/paper-defaults.ly 14 Feb 2006 00:27:24 -0000
@@ -57,6 +57,12 @@
%%
between-system-padding = #(* 4 mm)
+ %%
+ %% the assumed system height that we use for page-breaking
+ system-height = #(* 20 mm)
+ blank-page-force = 15
+ blank-last-page-force = 0
+
after-title-space = 5 \mm
before-title-space = 10 \mm
between-title-space = 2 \mm
Index: scm/layout-page-layout.scm
===================================================================
RCS file: /sources/lilypond/lilypond/scm/layout-page-layout.scm,v
retrieving revision 1.14
diff -u -r1.14 layout-page-layout.scm
--- scm/layout-page-layout.scm 6 Feb 2006 01:13:59 -0000 1.14
+++ scm/layout-page-layout.scm 14 Feb 2006 00:27:24 -0000
@@ -136,6 +136,151 @@
(if (ly:output-def-lookup layout 'write-page-layout #f)
(write-page-breaks pages)))
+(define-public (space-systems paper-book page-height lines ragged?)
+ (define paper (ly:paper-book-paper paper-book))
+ (let* ((global-inter-system-space
+ (ly:output-def-lookup paper 'between-system-space))
+ (top-space
+ (ly:output-def-lookup paper 'page-top-space))
+ (global-fixed-dist (ly:output-def-lookup paper
'between-system-padding))
+
+ (system-vector (list->vector
+ (append lines
+ (if (<= (length lines) 1)
+ '(#f)
+ '()))))
+ (staff-extents
+ (list->vector
+ (append (map paper-system-staff-extents lines)
+ (if (<= (length lines) 1)
+ '((0 . 0))
+ '()))))
+
+ (real-extents
+ (list->vector
+ (append
+ (map
+ (lambda (sys) (paper-system-extent sys Y)) lines)
+ (if (<= (length lines) 1)
+ '((0 . 0))
+ '()))))
+
+ (system-count (vector-length real-extents))
+ (topskip (max
+ (+
+ top-space
+ (interval-end (vector-ref staff-extents 0)))
+ (interval-end (vector-ref real-extents 0))
+ ))
+ (last-system (vector-ref system-vector (1- system-count)))
+ (bottom-space (if (ly:prob? last-system)
+ (ly:prob-property last-system 'bottom-space 0.0)
+ 0.0))
+ (space-left (- page-height
+ bottom-space
+ (apply + (map interval-length
+ (vector->list real-extents)))))
+
+ (space (- page-height
+ topskip
+ bottom-space
+ (- (interval-start
+ (vector-ref real-extents (1- system-count))))))
+
+ (calc-spring
+ (lambda (idx)
+ (let* (
+ (upper-system (vector-ref system-vector idx))
+ (between-space (ly:prob-property upper-system 'next-space
+
global-inter-system-space))
+ (fixed-dist (ly:prob-property upper-system 'next-padding
+ global-fixed-dist))
+
+ (this-system-ext (vector-ref staff-extents idx))
+ (next-system-ext (vector-ref staff-extents (1+ idx)))
+ (fixed (max 0 (- (+ (interval-end next-system-ext)
+ fixed-dist)
+ (interval-start this-system-ext))))
+ (title1? (and (vector-ref system-vector idx)
+ (paper-system-title? (vector-ref
system-vector idx)
+ )))
+ (title2? (and
+ (vector-ref system-vector (1+ idx))
+ (paper-system-title? (vector-ref system-vector
(1+ idx)))))
+ (ideal (+
+ (cond
+ ((and title2? title1?)
+ (ly:output-def-lookup paper 'between-title-space))
+ (title1?
+ (ly:output-def-lookup paper 'after-title-space))
+ (title2?
+ (ly:output-def-lookup paper 'before-title-space))
+ (else between-space))
+ fixed))
+ (hooke (/ 1 (- ideal fixed))))
+ (list ideal hooke))))
+
+ (springs (map calc-spring (iota (1- system-count))))
+ (calc-rod
+ (lambda (idx)
+ (let* (
+ (upper-system (vector-ref system-vector idx))
+ (fixed-dist (ly:prob-property upper-system 'next-padding
+ global-fixed-dist))
+ (this-system-ext (vector-ref real-extents idx))
+ (next-system-ext (vector-ref real-extents (1+ idx)))
+
+ (distance (max (- (+ (interval-end next-system-ext)
+ fixed-dist)
+ (interval-start this-system-ext)
+ ) 0))
+ (entry (list idx (1+ idx) distance)))
+ entry)))
+ (rods (map calc-rod (iota (1- system-count))))
+
+ ;; we don't set ragged based on amount space left.
+ ;; ragged-bottomlast = ##T is much more predictable
+ (result (ly:solve-spring-rod-problem
+ springs rods space
+ ragged?))
+
+ (force (car result))
+ (positions
+ (map (lambda (y)
+ (+ y topskip))
+ (cdr result))))
+
+ (if #f ;; debug.
+ (begin
+ (display (list "\n# systems: " system-count
+ "\nreal-ext" real-extents "\nstaff-ext" staff-extents
+ "\ninterscore" global-inter-system-space
+ "\nspace-left" space-left
+ "\nspring,rod" springs rods
+ "\ntopskip " topskip
+ " space " space
+ "\npage-height" page-height
+ "\nragged" ragged?
+ "\nforce" force
+ "\nres" (cdr result)
+ "\npositions" positions "\n"))))
+
+ (cons force positions)))
+
+(define-public (make-page-from-systems p-book lines p-num prev ragged? last?)
+ (let*
+ ((page (make-page
+ (layout->page-init (ly:paper-book-paper p-book))
+ 'paper-book p-book
+ 'lines lines
+ 'page-number p-num
+ 'prev prev
+ 'is-last last?))
+ (height (page-printable-height page))
+ (posns (cdr (space-systems p-book height lines ragged?))))
+ (page-set-property! page 'configuration posns)
+ page))
+
;; Optimal distribution of
;; lines over pages; line breaks are a given.
@@ -145,11 +290,12 @@
;; - separate function for word-wrap style breaking?
;; - ragged-bottom? ragged-last-bottom?
-(define-public (optimal-page-breaks lines paper-book)
+(define-public (optimal-page-breaks paper-book)
"Return pages as a list starting with 1st page. Each page is a 'page Prob."
(define MAXPENALTY 1e9)
(define paper (ly:paper-book-paper paper-book))
+ (define lines (ly:paper-book-systems paper-book))
;; ugh.
(define page-alist (layout->page-init (ly:paper-book-paper paper-book)))
@@ -181,136 +327,6 @@
inter-system-space))
user)))
- (define (space-systems page-height lines ragged?)
- (let* ((global-inter-system-space
- (ly:output-def-lookup paper 'between-system-space))
- (top-space
- (ly:output-def-lookup paper 'page-top-space))
- (global-fixed-dist (ly:output-def-lookup paper
'between-system-padding))
-
- (system-vector (list->vector
- (append lines
- (if (= (length lines) 1)
- '(#f)
- '()))))
- (staff-extents
- (list->vector
- (append (map paper-system-staff-extents lines)
- (if (= (length lines) 1)
- '((0 . 0))
- '()))))
-
- (real-extents
- (list->vector
- (append
- (map
- (lambda (sys) (paper-system-extent sys Y)) lines)
- (if (= (length lines) 1)
- '((0 . 0))
- '()))))
-
- (system-count (vector-length real-extents))
- (topskip (max
- (+
- top-space
- (interval-end (vector-ref staff-extents 0)))
- (interval-end (vector-ref real-extents 0))
- ))
- (last-system (vector-ref system-vector (1- system-count)))
- (bottom-space (if (ly:prob? last-system)
- (ly:prob-property last-system 'bottom-space 0.0)
- 0.0))
- (space-left (- page-height
- bottom-space
- (apply + (map interval-length
- (vector->list real-extents)))))
-
- (space (- page-height
- topskip
- bottom-space
- (- (interval-start
- (vector-ref real-extents (1- system-count))))))
-
- (calc-spring
- (lambda (idx)
- (let* (
- (upper-system (vector-ref system-vector idx))
- (between-space (ly:prob-property upper-system 'next-space
-
global-inter-system-space))
- (fixed-dist (ly:prob-property upper-system 'next-padding
- global-fixed-dist))
-
- (this-system-ext (vector-ref staff-extents idx))
- (next-system-ext (vector-ref staff-extents (1+ idx)))
- (fixed (max 0 (- (+ (interval-end next-system-ext)
- fixed-dist)
- (interval-start this-system-ext))))
- (title1? (and (vector-ref system-vector idx)
- (paper-system-title? (vector-ref
system-vector idx)
- )))
- (title2? (and
- (vector-ref system-vector (1+ idx))
- (paper-system-title? (vector-ref system-vector
(1+ idx)))))
- (ideal (+
- (cond
- ((and title2? title1?)
- (ly:output-def-lookup paper
'between-title-space))
- (title1?
- (ly:output-def-lookup paper 'after-title-space))
- (title2?
- (ly:output-def-lookup paper 'before-title-space))
- (else between-space))
- fixed))
- (hooke (/ 1 (- ideal fixed))))
- (list ideal hooke))))
-
- (springs (map calc-spring (iota (1- system-count))))
- (calc-rod
- (lambda (idx)
- (let* (
- (upper-system (vector-ref system-vector idx))
- (fixed-dist (ly:prob-property upper-system 'next-padding
- global-fixed-dist))
- (this-system-ext (vector-ref real-extents idx))
- (next-system-ext (vector-ref real-extents (1+ idx)))
-
- (distance (max (- (+ (interval-end next-system-ext)
- fixed-dist)
- (interval-start this-system-ext)
- ) 0))
- (entry (list idx (1+ idx) distance)))
- entry)))
- (rods (map calc-rod (iota (1- system-count))))
-
- ;; we don't set ragged based on amount space left.
- ;; ragged-bottomlast = ##T is much more predictable
- (result (ly:solve-spring-rod-problem
- springs rods space
- ragged?))
-
- (force (car result))
- (positions
- (map (lambda (y)
- (+ y topskip))
- (cdr result))))
-
- (if #f ;; debug.
- (begin
- (display (list "\n# systems: " system-count
- "\nreal-ext" real-extents "\nstaff-ext" staff-extents
- "\ninterscore" global-inter-system-space
- "\nspace-left" space-left
- "\nspring,rod" springs rods
- "\ntopskip " topskip
- " space " space
- "\npage-height" page-height
- "\nragged" ragged?
- "\nforce" force
- "\nres" (cdr result)
- "\npositions" positions "\n"))))
-
- (cons force positions)))
-
(define (walk-paths done-lines best-paths current-lines last? current-best)
"Return the best optimal-page-break-node that contains
CURRENT-LINES. DONE-LINES.reversed ++ CURRENT-LINES is a consecutive
@@ -335,7 +351,7 @@
(and ragged-last?
last?)))
(height (page-printable-height this-page))
- (vertical-spacing (space-systems height current-lines ragged?))
+ (vertical-spacing (space-systems paper-book height current-lines
ragged?))
(satisfied-constraints (car vertical-spacing))
(force (if satisfied-constraints
(if (and last? ragged-last?)
Index: scm/page.scm
===================================================================
RCS file: /sources/lilypond/lilypond/scm/page.scm,v
retrieving revision 1.7
diff -u -r1.7 page.scm
--- scm/page.scm 10 Feb 2006 12:27:42 -0000 1.7
+++ scm/page.scm 14 Feb 2006 00:27:26 -0000
@@ -191,12 +191,31 @@
head-stencil))
+;; this is basically calc-printable-page height, but it works just from the
paper-book
+(define-public (calc-page-height p-book p-number last?)
+ (let*
+ ((layout (ly:paper-book-paper p-book))
+ (scopes (ly:paper-book-scopes p-book))
+ (head (page-headfoot layout scopes p-number 'make-header
'head-separation UP last?))
+ (foot (page-headfoot layout scopes p-number 'make-footer
'foot-separation DOWN last?))
+ (h (- (ly:output-def-lookup layout 'paper-height)
+ (ly:output-def-lookup layout 'top-margin)
+ (ly:output-def-lookup layout 'bottom-margin)))
+ (available
+ (- h (if (ly:stencil? head)
+ (interval-length (ly:stencil-extent head Y))
+ 0)
+ (if (ly:stencil? foot)
+ (interval-length (ly:stencil-extent foot Y))
+ 0))))
+ available))
+
+
(define (page-header-or-footer page dir)
(let*
((p-book (page-property page 'paper-book))
(layout (ly:paper-book-paper p-book))
(scopes (ly:paper-book-scopes p-book))
- (lines (page-lines page))
(number (page-page-number page))
(last? (page-property page 'is-last))
)
@@ -379,9 +398,6 @@
(let*
((p-book (page-property page 'paper-book))
(layout (ly:paper-book-paper p-book))
- (scopes (ly:paper-book-scopes p-book))
- (number (page-page-number page))
- (last? (page-property page 'is-last))
(h (- (ly:output-def-lookup layout 'paper-height)
(ly:output-def-lookup layout 'top-margin)
(ly:output-def-lookup layout 'bottom-margin)))
Index: scm/paper.scm
===================================================================
RCS file: /sources/lilypond/lilypond/scm/paper.scm,v
retrieving revision 1.65
diff -u -r1.65 paper.scm
--- scm/paper.scm 6 Feb 2006 01:13:59 -0000 1.65
+++ scm/paper.scm 14 Feb 2006 00:27:26 -0000
@@ -7,6 +7,7 @@
(define-public (set-paper-dimension-variables mod)
(module-define! mod 'dimension-variables
'(pt mm cm in staff-height staff-space
+ system-height
page-top-space
between-system-space between-system-padding
line-width indent paper-width paper-height
horizontal-shift
/*
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();
}
/*
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)
{
paper_score_ = true;
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"));
n_score_brk_ = n_brks;
}
System_spec::System_spec (Prob *pb)
{
paper_score_ = false;
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;
n_score_brk_ = 0;
}
System_spec::System_spec (SCM header, Paper_book *pb)
{
Stencil title = pb->score_title (header);
paper_score_ = false;
pscore_ = 0;
SCM props = pb->paper_->lookup_variable (ly_symbol2scm
("score-title-properties"));
prob_ = make_paper_system (props);
paper_system_set_stencil (prob_, title);
set_system_penalty (prob_, header);
size_ = title.extent (Y_AXIS).length ();
penalty_ = scm_to_double (prob_->get_property ("penalty"));
// these get determined later
between_size_ = 0;
between_space_ = 0;
n_score_brk_ = 0;
}
System_spec::System_spec ()
{
paper_score_ = true;
size_ = between_size_ = between_space_ = 0;
pscore_ = 0;
prob_ = 0;
n_score_brk_ = 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::sys_idx (int start) const
{
int sys = breaks_[start].sys_;
if (sys < 0) // beginning of the piece
return 0;
if (all_[sys].paper_score_ && all_[sys].n_score_brk_ >
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 j = 0;
int p1_sys_left = me.p1_sys_ - 1;
int p2_sys_left = me.p1_sys_ + me.p2_sys_ - 1;
int start = prev_break;
int end = me.break_pos_;
Real line_f = 0, line_pen = 0;
for (vsize i = sys_idx (prev_break); (int)i <= breaks_[me.break_pos_].sys_;
i++)
{
if (all_[i].paper_score_)
{
int nsys = me.div_[j++];
if (p1_sys_left >= 0 && p1_sys_left < nsys)
break_pen += get_page_penalty (i, nsys, start, end, p1_sys_left);
if (p2_sys_left >= 0 && p2_sys_left < nsys)
break_pen += get_page_penalty (i, nsys, start, end, p2_sys_left);
p1_sys_left -= nsys;
p2_sys_left -= nsys;
line_f += get_line_force (i, nsys, start, end);
line_pen += get_line_penalty (i, nsys, start, end);
}
else
{
p1_sys_left--;
p2_sys_left--;
}
}
assert (me.line_demerits_ == line_f);
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;
me.demerits_ += prev_dem + break_pen + all_[breaks_[end].sys_].penalty_ +
breaks_[end].penalty_ + line_pen;
assert (!isinf (line_f) || me.demerits_ > 200);
}
void
Optimal_breaking::line_brk_args (vsize i, int &start, int &end)
{
assert (all_[i].paper_score_);
assert (sys_idx (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_].n_score_brk_);
start = start_col;
end = end_col;
}
Real
Optimal_breaking::get_page_penalty (vsize i, int nsys, int start, int end, int
sys_num)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_page_penalty (start, end, nsys, sys_num);
}
vector<Column_x_positions>
Optimal_breaking::get_line_breaks (vsize i, int nsys, int start, int end)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_soln (start, end, nsys);
}
Real
Optimal_breaking::get_line_break_dems (vsize i, int nsys, int start, int end)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_demerits (start, end, nsys);
}
Real
Optimal_breaking::get_line_force (vsize i, int nsys, int start, int end)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_force (start, end, nsys);
}
Real
Optimal_breaking::get_line_penalty (vsize i, int nsys, int start, int end)
{
line_brk_args (i, start, end);
return line_breaking_[i].get_penalty (start, end, nsys);
}
// TODO: allow starting on the right-hand page
// this is quite long, but I can't see any obvious places to split it
Real
Optimal_breaking::best_page_force (vector<System_spec> const &sys,
int nsys,
vector<int> const &div,
int p_num,
bool last,
int &p1_sys)
{
SCM ph = ly_lily_module_constant("calc-page-height");
Real p1_h, p1_last_h, p2_h;
vector<System_spec const*> rep_sys;
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);
SCM b = book_->self_scm ();
p1_h = scm_to_double (
scm_apply_0 (ph, scm_list_3 (b, scm_from_int (p_num), SCM_BOOL_F)));
if (last)
p1_last_h = scm_to_double (
scm_apply_0 (ph, scm_list_3 (b, scm_from_int (p_num), SCM_BOOL_T)));
p2_h = scm_to_double (
scm_apply_0 (ph, scm_list_3 (b, scm_from_int (p_num),
scm_from_bool(last))));
Real p1_sys_h = 0, p2_sys_h = 0;
Real p1_spr_len = 0, p2_spr_len = 0; // spring lengths
Real p1_inv_k = 0, p2_inv_k = 0; // inverse spring contants
Real p1_spr_space = p1_h, p2_spr_space = p2_h;
// repeat each score for the number of systems it has
vsize score_idx = 0;
for (vsize i = 0; i < sys.size (); i++)
{
if (sys[i].paper_score_)
{
for (vsize j = 0; (int)j < div[score_idx]; j++)
rep_sys.push_back (&sys[i]);
score_idx++;
}
else
rep_sys.push_back (&sys[i]);
}
if (rep_sys.size () < (vsize)nsys)
return infinity_f; // we don't have any scores so we can't increase nsys
// start with everything on the first page
for (vsize i = 0; i < rep_sys.size (); i++)
{
p1_sys_h += rep_sys[i]->size_ + rep_sys[i]->between_size_;
p1_spr_len += rep_sys[i]->between_space_;
p1_spr_space -= rep_sys[i]->between_size_;
p1_inv_k++;
}
p1_sys_h -= rep_sys.back ()->between_size_;
p1_spr_space += rep_sys.back ()->between_size_;
Real force = (p1_sys_h < (last ? p1_last_h : p1_h)) ?
(p1_spr_space - p1_spr_len) / p1_inv_k : infinity_f;
Real best = force;
if (ragged && !isinf(force))
force = max (0.0, force);
else
force = fabs (force);
if (!last)
force += robust_scm2double (book_->paper_->c_variable ("blank-page-force"),
0.0);
else
force += robust_scm2double (book_->paper_->c_variable
("blank-last-page-force"), 0.0);
p1_sys = nsys;
// move things over one system at a time
System_spec const *me;
System_spec const *prev;
for (vsize i = rep_sys.size () - 1; i > 0; i--)
{
me = rep_sys[i];
prev = rep_sys[i-1];
p1_sys_h -= me->size_ + prev->between_size_;
p1_spr_len -= me->between_space_;
p1_spr_space += prev->between_size_;
p1_inv_k--;
p2_sys_h += me->size_;
p2_spr_len += me->between_space_;
if (i < rep_sys.size () - 1)
{
p2_sys_h += me->between_size_;
p2_spr_space -= me->between_size_;
}
p2_inv_k++;
if (p2_sys_h >= p2_h) // it's only going to get worse if we add more
systems
return force;
if (p1_sys_h >= p1_h)
continue;
Real p1_f = (p1_spr_space - p1_spr_len) / p1_inv_k;
Real p2_f = (p2_spr_space - p2_spr_len) / p2_inv_k;
p1_f = ragged_all ? max (0.0, p1_f) : fabs (p1_f);
p2_f = ragged ? max (0.0, p2_f) : fabs (p2_f);
if (p1_f + p2_f + prev->penalty_ < best)
{
best = p1_f + p2_f + prev->penalty_;
force = p1_f + p2_f;
p1_sys = i;
}
}
return force;
}
void
Optimal_breaking::calc_subproblem(int i)
{
vsize end = i + 1;
Optimal_break_node best;
Optimal_break_node cur;
cur.break_pos_ = end;
bool bad_page_and_lines = false;
for (int start = end - 1; start >= 0; start--)
{
int p_num = (start == 0) ? 1 : state_[start-1].page_number_ + 2;
int n_scores = 0;
int n_probs = 0;
vector<System_spec> systems (all_.begin () + sys_idx (start),
all_.begin () + breaks_[end].sys_ + 1);
Optimal_break_node this_break_best;
cur.page_number_ = p_num;
cur.prev_ = start - 1;
for (vsize j = sys_idx (start); (int)j <= breaks_[end].sys_; j++)
{
if (all_[j].paper_score_)
n_scores++;
else
n_probs++;
}
bool ok_page = true;
bool each_nsys_bad_lines = true;
bool bad_lines = false;
for (int nsys = n_scores + n_probs; ok_page; nsys++)
{
vector<vector<int> > div;
divide_systems (nsys - n_probs, n_scores, div, vector<int> ());
bool each_div_bad_lines = true;
for (vsize d = 0; d < div.size (); d++)
{
Real line_f = 0;
cur.force_ = best_page_force (systems, nsys, div[d], p_num,
end == breaks_.size () - 1,
cur.p1_sys_);
vsize k = 0;
for (vsize j = 0; j < systems.size (); j++)
if (systems[j].paper_score_)
line_f += get_line_force (j + sys_idx(start), div[d][k++],
start, end);
bad_lines = isinf (line_f);
if (!bad_lines)
each_div_bad_lines = false;
if (isinf (cur.force_))
{
ok_page = false;
break;
}
cur.div_ = div[d];
cur.p2_sys_ = nsys - cur.p1_sys_;
cur.line_demerits_ = line_f;
calc_demerits (cur);
if (isinf(this_break_best.demerits_) || cur.demerits_ <
this_break_best.demerits_)
{
this_break_best = cur;
this_break_best.div_ = div[d];
}
}
if (!each_div_bad_lines)
each_nsys_bad_lines = false;
if (each_div_bad_lines && !each_nsys_bad_lines)
break; // lines are too sparse, no point adding more systems
else if (each_div_bad_lines && !ok_page) // lines and pages are too
dense
{
bad_page_and_lines = true;
break;
}
}
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 both page and lines are too dense, there's no point making them
denser
if (isinf (best.demerits_) || this_break_best.demerits_ < best.demerits_)
best = this_break_best;
if (bad_page_and_lines)
break;
}
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;
vsize pscore_idx = 0;
/* break each score into pieces */
for (vsize i = sys_idx (start); (int) i <= breaks_[end].sys_; i++)
{
if (all_[i].paper_score_)
{
vector<Column_x_positions> line_brk;
Real dems = get_line_force (i, soln[n].div_[pscore_idx], start,
end);
if (isinf (dems))
::message (_("WTF? I chose an infinite-demerits line
breaking"));
line_brk = get_line_breaks (i, soln[n].div_[pscore_idx], start,
end);
all_[i].pscore_->root_system ()->break_into_pieces (line_brk);
pscore_idx++;
n_systems += line_brk.size ();
}
else
n_systems++;
}
assert (n_systems == soln[n].p1_sys_ + soln[n].p2_sys_);
total_n_systems += n_systems;
}
SCM ret = SCM_EOL;
SCM *tail = &ret;
for (vsize i = 0; i < all_.size (); i++)
{
if (all_[i].paper_score_)
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);
tail = SCM_CDRLOC (*tail);
all_[i].prob_->unprotect ();
}
}
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++)
{
SCM page_num = scm_from_int (soln[i].page_number_);
SCM last = scm_from_bool (i == soln.size () - 1 && soln[i].p2_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].p1_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].p2_sys_)
{
page_num = scm_from_int (soln[i].page_number_ + 1);
last = scm_from_bool (i == soln.size () - 1);
lines = SCM_EOL;
ragged = scm_from_bool (ragged_all || (to_boolean (last) &&
ragged_last));
for (int j = 0; j < soln[i].p2_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
* before the current system */
void
Optimal_breaking::add_break_penalty (SCM header)
{
int sys = all_.size () - 2;
if (sys < 0)
return;
Real pen = 0;
if (ly_is_module (header))
{
SCM force = ly_module_lookup (header, ly_symbol2scm ("breakbefore"));
if (SCM_VARIABLEP (force)
&& scm_is_bool (SCM_VARIABLE_REF (force)))
{
pen = to_boolean (SCM_VARIABLE_REF (force)) ? -10000 : 10000;
}
}
if (all_[sys].paper_score_)
{
// check if there's already a breakpoint there
if (breaks_.back ().sys_ == sys
&& breaks_.back ().score_brk_ == all_[sys].n_score_brk_)
breaks_.back ().penalty_ += pen;
else
breaks_.push_back (Break_position (sys, all_[sys].n_score_brk_, pen));
}
else
{
// there shouldn't already be a breakpoint there
breaks_.push_back (Break_position (sys, -1, pen));
}
}
bool
Optimal_breaking::add_prob (SCM props, Stencil sten)
{
if (sten.is_empty ())
return false;
Prob *ps = make_paper_system (props);
paper_system_set_stencil (ps, sten);
all_.push_back (System_spec (ps));
all_.back ().penalty_ = 10000; // by default, we don't want to break
// after a title
// we don't actually use this -- it's a dummy to make indices easier
line_breaking_.push_back (Restrained_breaking ());
return true;
}
void
Optimal_breaking::create_system_list()
{
nscores_ = 0;
breaks_.push_back (Break_position ());
SCM props = book_->paper_->lookup_variable (ly_symbol2scm
("book-title-properties"));
if (add_prob (props, book_->book_title ()))
add_break_penalty (book_->header_);
SCM page_properties
= scm_call_1 (ly_lily_module_constant ("layout-extract-page-properties"),
book_->paper_->self_scm ());
SCM header = SCM_EOL;
for (SCM s = scm_reverse (book_->scores_); s != SCM_EOL; s = scm_cdr (s))
{
if (ly_is_module (scm_car (s)))
{
header = scm_car (s);
}
else if (Music_output *mop = unsmob_music_output (scm_car (s)))
{
if (Paper_score *pscore = dynamic_cast<Paper_score *> (mop))
{
SCM props = book_->paper_->lookup_variable (ly_symbol2scm
("score-title-properties"));
if (add_prob (props, book_->score_title (header)))
add_break_penalty (header);
/* add a breakpoint at the end of the last score, if necessary */
if (all_.size () && all_.back ().paper_score_)
breaks_.push_back (
Break_position (all_.size () - 1, all_.back
().n_score_brk_));
vector<int> score_brk = find_page_break_indices (pscore);
all_.push_back (System_spec (pscore, score_brk.size () + 1));
nscores_++;
for (vsize i = 0; i < score_brk.size(); i++)
breaks_.push_back (Break_position (all_.size () - 1, i + 1));
// include a page breaker at the start of the score
score_brk.insert (score_brk.begin (), 0);
line_breaking_.push_back (Restrained_breaking (score_brk));
line_breaking_.back ().set_pscore (pscore);
}
}
else if (Text_interface::is_markup (scm_car (s)))
{
SCM t = Text_interface::interpret_markup (book_->paper_->self_scm (),
page_properties,
scm_car (s));
// TODO: init props
if (add_prob (SCM_EOL, *unsmob_stencil (t)))
all_.back ().prob_->set_property ("is-title", SCM_BOOL_T);
// FIXME: figure out penalty.
//set_system_penalty (ps, scores_[i].header_);
}
else
assert (0);
}
// add the ending breakpoint
if (all_.back ().paper_score_)
breaks_.push_back (Break_position (all_.size () - 1, all_.back
().n_score_brk_));
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].paper_score_;
bool title2 = !all_[i+1].paper_score_;
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::divide_systems(int nsystems, int nscores,
vector<vector<int> > &result,
const vector<int> &cur)
{
assert (nscores <= nsystems);
if (nscores == 0)
{
result.push_back (cur);
}
else if (nscores == 1)
{
vector<int> v = cur;
v.push_back (nsystems);
result.push_back (v);
}
else
{
nscores--;
for (int i = 1; i <= nsystems - nscores; i++)
{
vector<int> v = cur;
v.push_back (i);
divide_systems (nsystems-i, nscores, result, v);
}
}
}
/*
restrained-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 "restrained-breaking.hh"
#include <cmath> // rint
#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"
/// How often to print operator pacification marks?
const int HAPPY_DOTS_I = 3;
void
print_restrained_break_nodes (vector<Restrained_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_idx and sys here are indexed from 0.
* max_brk is indexed from start_brk_idx_[start_idx]
* (for max_brk, start_brk_idx_[start_idx] is the beginning
* of the piece; the smallest value we should ever see here is
* start_brk_idx_[start_idx] + 1) */
bool
Restrained_breaking::calc_subproblem (int start_idx, int sys, int max_brk)
{
assert (sys < systems_);
assert (start_idx < (int)start_.size ());
assert (max_brk < (int)breaks_.size ());
bool found_something = false;
int start_col = start_brk_idx_[start_idx];
vector<Restrained_break_node> &st = state_[start_idx];
int rank = breaks_.size () - start_col;
int max_idx = max_brk - start_col;
for (int j=sys; j < max_idx; 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_brk];
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_idx].demerits_)
|| dem < st[sys*rank + max_idx].demerits_)
{
found_something = true;
st[sys*rank + max_idx].demerits_ = dem;
st[sys*rank + max_idx].force_ = force;
st[sys*rank + max_idx].penalty_ = pen;
st[sys*rank + max_idx].prev_ = j;
st[sys*rank + max_idx].line_config_ = cur;
}
}
return found_something;
}
vector<Column_x_positions>
Restrained_breaking::do_solve ()
{
resize ();
return get_soln(0, systems_, -1);
}
void
Restrained_breaking::resize ()
{
static int num_spacings = 0;
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);
num_spacings++;
if (!cols_[i*cols_rank_ + j].satisfies_constraints_)
break;
delete sp;
}
::message (_f("calculated %d spacing problems\n", num_spacings));
// 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++)
;
start_brk_idx_.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 () - start_brk_idx_[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 = start_brk_idx_[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>
Restrained_breaking::get_soln (int start_idx, int end_idx, int nsys)
{
int rank, brk;
prepare_solution (start_idx, end_idx, nsys, rank, brk);
vector<Restrained_break_node> const &st = state_[start_idx];
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
Restrained_breaking::get_demerits (int start_idx, int end_idx, int nsys)
{
int rank, brk;
prepare_solution (start_idx, end_idx, nsys, rank, brk);
return state_[start_idx][(nsys-1)*rank + brk].demerits_;
}
Real
Restrained_breaking::get_force (int start_idx, int end_idx, int nsys)
{
int rank, brk;
prepare_solution (start_idx, end_idx, nsys, rank, brk);
vector<Restrained_break_node> const &st = state_[start_idx];
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
Restrained_breaking::get_penalty (int start_idx, int end_idx, int nsys)
{
int rank, brk;
prepare_solution (start_idx, end_idx, nsys, rank, brk);
return state_[start_idx][(nsys-1)*rank + brk].penalty_;
}
Real
Restrained_breaking::get_page_penalty (int start_idx, int end_idx, int nsys,
int sys_num)
{
int rank, brk;
prepare_solution (start_idx, end_idx, nsys, rank, brk);
int sys;
for (sys = nsys-1; sys > sys_num; sys--)
brk = state_[start_idx][sys*rank + brk].prev_;
if (brk < 0) // we didn't satisfy constraints
return 0;
vector<Grob*> &cols = state_[start_idx][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;
}
void
Restrained_breaking::prepare_solution (int start_idx, int end_idx, int nsys,
int &rank, int &brk)
{
assert (start_idx < (int)start_.size () && end_idx <= (int)start_.size ());
assert (end_idx < 0 || start_idx < end_idx);
assert (nsys > 0);
if (nsys >= valid_systems_)
{
systems_ = nsys;
resize ();
}
if (end_idx == (int)start_.size ())
end_idx = -1;
rank = breaks_.size () - start_brk_idx_[start_idx];
brk = end_idx < 0 ? breaks_.size () - 1 : start_brk_idx_[end_idx];
brk -= start_brk_idx_[start_idx];
}
Restrained_breaking::Restrained_breaking ()
{
valid_systems_ = systems_ = 0;
start_.push_back (0);
}
Restrained_breaking::Restrained_breaking (vector<int> const &start):
start_ (start)
{
valid_systems_ = systems_ = 0;
}
void
Restrained_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;
}
/*
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 "restrained-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 (SCM header, Paper_book*);
System_spec (Prob*);
System_spec ();
bool paper_score_;
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 n_score_brk_; // 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;
}
};
/**
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<int> div_; // our division of system between scores on this page
int p1_sys_, p2_sys_; // number of systems on each page
Optimal_break_node ()
{
prev_ = -1;
p1_sys_ = p2_sys_ = -1;
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<Restrained_breaking> line_breaking_;
Paper_book *book_;
int nscores_;
int sys_idx (int starting_brk_idx) const;
Real page_force (std::vector<System_spec> const &sys,
int score_systems,
Real size);
void split_systems (std::vector<System_spec> const &sys,
std::vector<System_spec> &p1,
std::vector<System_spec> &p2,
int &n_p1_psys,
int &n_p2_psys,
int nsys,
int n_p1_sys,
vector<int> const &score_sys_div);
/* 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 (and return the force).
* Also set the number of systems for the first page. */
Real best_page_force (std::vector<System_spec> const &sys,
int nsys,
vector<int> const &score_sys_div,
int p_num,
bool last,
int &p1_sys);
void create_system_list ();
std::vector<int> find_page_break_indices (Paper_score *pscore);
bool add_prob (SCM props, Stencil sten);
void add_break_penalty (SCM header);
/* 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 all possible ways of dividing nsystems between nscores */
void divide_systems (int nsystems, int nscores,
vector<vector<int> > &result,
const vector<int> &cur);
void calc_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_idx, int nsys, int break_st, int
break_end, int sys_num);
Real get_line_break_dems (vsize sys_idx, int nsys, int break_st, int
break_end);
Real get_line_force (vsize sys_idx, int nsys, int break_st, int break_end);
Real get_line_penalty (vsize sys_idx, int nsys, int break_st, int
break_end);
std::vector<Column_x_positions> get_line_breaks (vsize sys_idx, int nsys,
int st, int end);
};
#endif // OPTIMAL_BREAKING_HH
/*
restrained-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 Restrained_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_;
Restrained_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 Restrained_breaking : public Break_algorithm
{
public:
std::vector<Column_x_positions> do_solve ();
Restrained_breaking ();
Restrained_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_idx, int end_idx, int
nsys);
Real get_demerits (int start_idx, int end_idx, int nsys);
Real get_force (int start_idx, int end_idx, int nsys);
Real get_penalty (int start_idx, int end_idx, int nsys);
// get the page penalty of system number sys_idx with the given breaking
Real get_page_penalty (int start_idx, int end_idx, int nsys, int sys_idx);
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<Restrained_break_node> > state_;
vector<int> start_; // the columns at which we might be asked to
start breaking
vector<int> start_brk_idx_; // the corresponding index in breaks_
vector<Grob*> all_;
std::vector<int> breaks_;
void prepare_solution (int start_idx, int end_idx, int nsys, 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_idx, int systems, int max_brk);
void resize ();
};
#endif // RESTRAINED_BREAKING_HH
- Re: setting the number of pages for a score, Joe Neeman, 2006/02/09
- Re: setting the number of pages for a score, Han-Wen Nienhuys, 2006/02/09
- Re: setting the number of pages for a score, Joe Neeman, 2006/02/09
- Re: setting the number of pages for a score, Han-Wen Nienhuys, 2006/02/10
- Re: setting the number of pages for a score, Han-Wen Nienhuys, 2006/02/12
- Re: setting the number of pages for a score, Joe Neeman, 2006/02/12
- Re: setting the number of pages for a score, Han-Wen Nienhuys, 2006/02/12
- Re: setting the number of pages for a score, Joe Neeman, 2006/02/12
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 <=
- 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, 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