2 page-turn-page-breaking.cc -- implement Page_turn_page_breaking
4 source file of the GNU LilyPond music typesetter
6 (c) 2006 Joe Neeman <joeneeman@gmail.com>
9 #include "page-turn-page-breaking.hh"
11 #include "international.hh"
13 #include "output-def.hh"
14 #include "page-spacing.hh"
15 #include "paper-book.hh"
16 #include "paper-score.hh"
17 #include "paper-system.hh"
21 Page_turn_page_breaking::Page_turn_page_breaking (Paper_book *pb)
22 : Page_breaking (pb, true)
26 Page_turn_page_breaking::~Page_turn_page_breaking ()
31 Page_turn_page_breaking::calc_demerits (const Break_node &me)
35 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 1);
38 prev_f = state_[me.prev_].force_;
39 prev_dem = state_[me.prev_].demerits_;
42 Real dem = me.force_ * me.force_ * page_weighting
43 + me.line_force_ * me.line_force_
44 + fabs (me.force_ - prev_f);
45 if (isinf (me.line_force_) || isinf (me.force_))
48 return dem + prev_dem + me.penalty_ + me.line_penalty_;
51 Page_turn_page_breaking::Break_node
52 Page_turn_page_breaking::put_systems_on_pages (vsize start,
54 vector<Line_details> const &lines,
55 vector<vsize> const &div,
58 bool last = end == breaks_.size () - 1;
59 Real page_h = page_height (1, false); // FIXME
60 SCM force_sym = last ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
61 Real blank_force = robust_scm2double (book_->paper_->lookup_variable (force_sym), 0);
62 Spacing_result result = space_systems_on_min_pages (lines, page_h, blank_force);
65 ret.prev_ = start - 1;
67 ret.first_page_number_ = page_number;
68 ret.page_count_ = result.force_.size ();
70 for (vsize i = 0; i < result.force_.size (); i++)
71 ret.force_ += fabs (result.force_[i]);
73 ret.penalty_ = result.penalty_;
75 ret.system_count_ = result.systems_per_page_;
77 ret.too_many_lines_ = true;
79 ret.line_penalty_ = 0;
80 for (vsize i = 0; i < lines.size (); i++)
82 ret.line_force_ += fabs (lines[i].force_);
83 ret.line_penalty_ += lines[i].break_penalty_;
84 if (lines[i].force_ < 0)
85 ret.too_many_lines_ = false;
91 Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint)
93 vsize end = ending_breakpoint + 1;
96 Break_node this_start_best;
97 vsize prev_best_system_count = 0;
99 for (vsize start = end; start--;)
101 if (start > 0 && best.demerits_ < state_[start-1].demerits_)
107 /* if the last node has an odd number of pages and is not the first page,
109 int p_count = state_[start-1].page_count_;
110 int f_p_num = state_[start-1].first_page_number_;
111 p_num = f_p_num + p_count + ((f_p_num > 1) ? p_count % 2 : 0);
114 vector<vsize> min_systems;
115 vector<vsize> max_systems;
116 vsize min_system_count = 0;
117 vsize max_system_count = 0;
118 this_start_best.demerits_ = infinity_f;
119 calc_system_count_bounds (start, end, &min_systems, &max_systems);
121 /* heuristic: we've prepended some music, only the first system is allowed
123 if (this_start_best.page_count_ == 2 && this_start_best.div_.size ())
125 vsize ds = max_systems.size () - this_start_best.div_.size ();
126 for (vsize i = ds + 1; i < max_systems.size (); i++)
128 assert (this_start_best.div_[i - ds] <= max_systems[i]);
129 max_systems[i] = this_start_best.div_[i - ds];
133 for (vsize i = 0; i < min_systems.size (); i++)
135 min_system_count += min_systems[i];
136 max_system_count += max_systems[i];
141 /* heuristic: we've just added a breakpoint, we'll need at least as
142 many systems as before */
143 min_system_count = max (min_system_count, prev_best_system_count);
144 for (vsize sys_count = min_system_count; sys_count <= max_system_count && ok_page; sys_count++)
146 vector<vector<vsize> > div;
149 divide_systems (sys_count, min_systems, max_systems, &div, &blank);
151 for (vsize d = 0; d < div.size (); d++)
153 vector<Line_details> line = get_line_details (start, end, div[d]);
155 cur = put_systems_on_pages (start, end, line, div[d], p_num);
157 if (cur.page_count_ > 2 &&
158 (start < end - 1 || (!isinf (this_start_best.demerits_)
159 && cur.page_count_ + cur.page_count_ % 2
160 > this_start_best.page_count_ + this_start_best.page_count_ % 2)))
165 cur.demerits_ = calc_demerits (cur);
167 if (cur.demerits_ < this_start_best.demerits_)
170 this_start_best = cur;
171 prev_best_system_count = sys_count;
174 if (!found && this_start_best.too_many_lines_)
177 if (isinf (this_start_best.demerits_))
179 assert (!isinf (best.demerits_) && start < end - 1);
182 if (this_start_best.demerits_ < best.demerits_)
183 best = this_start_best;
185 state_.push_back (best);
189 Page_turn_page_breaking::solve ()
192 message (_f ("Calculating page and line breaks (%d possible page breaks)...",
193 (int)breaks_.size () - 1) + " ");
194 for (vsize i = 0; i < breaks_.size () - 1; i++)
197 progress_indication (string ("[") + to_string (i + 1) + "]");
199 progress_indication ("\n");
201 vector<Break_node> breaking;
202 int i = state_.size () - 1;
205 breaking.push_back (state_[i]);
210 message (_ ("Drawing systems..."));
211 SCM systems = make_lines (&breaking);
212 return make_pages (breaking, systems);
215 /* do the line breaking in all the scores and return a big list of systems */
217 Page_turn_page_breaking::make_lines (vector<Break_node> *psoln)
219 vector<Break_node> &soln = *psoln;
220 for (vsize n = 0; n < soln.size (); n++)
222 vsize start = n > 0 ? soln[n-1].break_pos_ : 0;
223 vsize end = soln[n].break_pos_;
225 /* break each score into pieces */
226 for (vsize i = next_system (start); i <= breaks_[end].sys_; i++)
228 vsize d = i - next_system (start);
231 vector<Column_x_positions> line_brk;
233 line_brk = get_line_breaks (i, soln[n].div_[d], start, end);
234 all_[i].pscore_->root_system ()->break_into_pieces (line_brk);
235 assert (line_brk.size () == soln[n].div_[d]);
241 for (vsize i = 0; i < all_.size (); i++)
244 for (SCM s = scm_vector_to_list (all_[i].pscore_->root_system ()->get_paper_systems ());
245 scm_is_pair (s); s = scm_cdr (s))
247 *tail = scm_cons (scm_car (s), SCM_EOL);
248 tail = SCM_CDRLOC (*tail);
252 *tail = scm_cons (all_[i].prob_->self_scm (), SCM_EOL);
253 all_[i].prob_->unprotect ();
254 tail = SCM_CDRLOC (*tail);
261 Page_turn_page_breaking::make_pages (vector<Break_node> const &soln, SCM systems)
263 vector<vsize> lines_per_page;
264 for (vsize i = 0; i < soln.size (); i++)
266 for (vsize j = 0; j < soln[i].page_count_; j++)
267 lines_per_page.push_back (soln[i].system_count_[j]);
269 if (i > 0 && i < soln.size () - 1 && soln[i].page_count_ % 2)
270 /* add a blank page */
271 lines_per_page.push_back (0);
273 return Page_breaking::make_pages (lines_per_page, systems);