]> git.donarmstrong.com Git - lilypond.git/blob - lily/page-spacing.cc
Doc-es: Update of Input.
[lilypond.git] / lily / page-spacing.cc
1 /*
2   This file is part of LilyPond, the GNU music typesetter.
3
4   Copyright (C) 2006--2009 Joe Neeman <joeneeman@gmail.com>
5
6   LilyPond is free software: you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation, either version 3 of the License, or
9   (at your option) any later version.
10
11   LilyPond is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include "page-spacing.hh"
21
22 #include "matrix.hh"
23 #include "page-breaking.hh"
24 #include "warn.hh"
25
26 void
27 Page_spacing::calc_force ()
28 {
29   Real height = page_height_
30     - breaker_->min_whitespace_at_top_of_page (first_line_)
31     - breaker_->min_whitespace_at_bottom_of_page (last_line_);
32
33   if (rod_height_ + last_line_.bottom_padding_ >= height)
34     force_ = infinity_f;
35   else
36     force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_)
37       / max (0.1, inverse_spring_k_);
38 }
39
40 void
41 Page_spacing::resize (Real new_height)
42 {
43   page_height_ = new_height;
44   calc_force ();
45 }
46
47 void
48 Page_spacing::append_system (const Line_details &line)
49 {
50   if (!rod_height_)
51     first_line_ = line;
52
53   rod_height_ += line.title_ ? last_line_.title_padding_ : last_line_.padding_;
54
55   rod_height_ += line.extent_.length ();
56   spring_len_ += line.space_;
57   inverse_spring_k_ += line.inverse_hooke_;
58
59   last_line_ = line;
60
61   calc_force ();
62 }
63
64 void
65 Page_spacing::prepend_system (const Line_details &line)
66 {
67   if (rod_height_)
68     rod_height_ += first_line_.title_ ? line.title_padding_ : line.padding_;
69   else
70     last_line_ = line;
71
72   rod_height_ += line.extent_.length ();
73   spring_len_ += line.space_;
74   inverse_spring_k_ += line.inverse_hooke_;
75
76   first_line_ = line;
77
78   calc_force ();
79 }
80
81 void
82 Page_spacing::clear ()
83 {
84   force_ = rod_height_ = spring_len_ = 0;
85   inverse_spring_k_ = 0;
86 }
87
88
89 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
90   : lines_ (lines)
91 {
92   first_page_num_ = first_page_num;
93   breaker_ = breaker;
94   max_page_count_ = 0;
95   ragged_ = breaker->ragged ();
96   ragged_last_ = breaker->is_last () && breaker->ragged_last ();
97 }
98
99 Page_spacing_result
100 Page_spacer::solve (vsize page_count)
101 {
102   if (page_count > max_page_count_)
103     resize (page_count);
104
105   Page_spacing_result ret;
106
107   vsize system = lines_.size () - 1;
108   vsize extra_systems = 0;
109   vsize extra_pages = 0;
110
111   if (isinf (state_.at (system, page_count-1).demerits_))
112     {
113       programming_error ("tried to space systems on a bad number of pages");
114       /* Usually, this means that we tried to cram too many systems into
115          to few pages. To avoid crashing, we look for the largest number of
116          systems that we can fit properly onto the right number of pages.
117          All the systems that don't fit get tacked onto the last page.
118       */
119       vsize i;
120       for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
121         ;
122
123       if (i)
124         {
125           extra_systems = system - i;
126           system = i;
127         }
128       else
129         {
130           /* try chopping off pages from the end */
131           vsize j;
132           for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
133             ;
134
135           if (j)
136             {
137               extra_pages = page_count - j;
138               page_count = j;
139             }
140           else
141             return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
142         }
143     }
144
145   ret.force_.resize (page_count);
146   ret.systems_per_page_.resize (page_count);
147   ret.penalty_ = state_.at (system, page_count-1).penalty_
148     + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
149
150   ret.demerits_ = 0;
151   for (vsize p = page_count; p--;)
152     {
153       assert (system != VPOS);
154
155       Page_spacing_node const &ps = state_.at (system, p);
156       ret.force_[p] = ps.force_;
157       ret.demerits_ += ps.force_ * ps.force_;
158       if (p == 0)
159         ret.systems_per_page_[p] = system + 1;
160       else
161         ret.systems_per_page_[p] = system - ps.prev_;
162       system = ps.prev_;
163     }
164
165   if (extra_systems)
166     {
167       ret.systems_per_page_.back () += extra_systems;
168       ret.force_.back () = BAD_SPACING_PENALTY;
169     }
170   if (extra_pages)
171     {
172       ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
173       ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
174     }
175
176   return ret;
177 }
178
179 void
180 Page_spacer::resize (vsize page_count)
181 {
182   assert (page_count > 0);
183
184   if (max_page_count_ >= page_count)
185     return;
186
187   state_.resize (lines_.size (), page_count, Page_spacing_node ());
188   for (vsize page = max_page_count_; page < page_count; page++)
189     for (vsize line = page; line < lines_.size (); line++)
190       if (!calc_subproblem (page, line))
191         break;
192
193   max_page_count_ = page_count;
194 }
195
196 // Carries out one step in the dynamic programming algorithm for putting systems
197 // on a fixed number of pages. One call to this routine calculates the best
198 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
199 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
200 //
201 // This algorithm is similar to the constrained-breaking algorithm.
202 bool
203 Page_spacer::calc_subproblem (vsize page, vsize line)
204 {
205   bool last = line == lines_.size () - 1;
206   Page_spacing space (breaker_->page_height (page + first_page_num_, last),
207                       breaker_);
208   Page_spacing_node &cur = state_.at (line, page);
209   bool ragged = ragged_ || (ragged_last_ && last);
210   int line_count = 0;
211
212   for (vsize page_start = line+1; page_start > page && page_start--;)
213     {
214       Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
215
216       space.prepend_system (lines_[page_start]);
217
218       // This 'if' statement is a little hard to parse. It won't consider this configuration
219       // if it is overfull unless the current configuration is the first one with this start
220       // point. We also make an exception (and consider this configuration) if the previous
221       // configuration we tried had fewer lines than min-systems-per-page.
222       if (!breaker_->too_few_lines (line_count)
223           && page_start < line
224           && (isinf (space.force_) || (space.force_ < 0 && ragged)))
225         break;
226
227       line_count += lines_[page_start].compressed_nontitle_lines_count_;
228       if (page > 0 || page_start == 0)
229         {
230           // If the last page is ragged, set its force to zero. This way, we will leave
231           // the last page half-empty rather than trying to balance things out
232           // (which only makes sense in non-ragged situations).
233           if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
234             space.force_ = 0;
235
236           Real demerits = space.force_ * space.force_;
237           /* If a single line is taller than a page, we need to consider it as
238              a possible solution (but we give it a very bad score). */
239           if (isinf (space.force_) && page_start == line)
240             demerits = BAD_SPACING_PENALTY;
241           demerits += (prev ? prev->demerits_ : 0);
242
243           Real penalty = breaker_->line_count_penalty (line_count);
244           if (page_start > 0)
245             penalty += lines_[page_start-1].page_penalty_
246               + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
247
248           /* Deal with widow/orphan lines */
249           /* Last line of paragraph is first line on the new page */
250           if ((page_start > 0) &&
251               (page_start < lines_.size ()) &&
252               (lines_[page_start].last_markup_line_))
253                   penalty += breaker_->orphan_penalty ();
254           /* First line of paragraph is last line on the previous page */
255           if ((page_start > 0) &&
256               (page_start < lines_.size ()) &&
257               (lines_[page_start-1].first_markup_line_))
258                   penalty += breaker_->orphan_penalty ();
259
260           demerits += penalty;
261           if (demerits < cur.demerits_ || page_start == line)
262             {
263               cur.demerits_ = demerits;
264               cur.force_ = space.force_;
265               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
266               cur.system_count_status_ = breaker_->line_count_status (line_count)
267                 | (prev ? prev->system_count_status_ : 0);
268               cur.prev_ = page_start - 1;
269             }
270         }
271
272       if (page_start > 0
273           && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
274         break;
275     }
276   return !isinf (cur.demerits_);
277 }
278