1 /*
2   This file is part of LilyPond, the GNU music typesetter.
3 
4   Copyright (C) 2006--2020 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 #ifndef PAGE_BREAKING_HH
21 #define PAGE_BREAKING_HH
22 
23 #include "constrained-breaking.hh"
24 #include "page-spacing.hh"
25 
26 /* Either a paper-score, markup or header.
27  */
28 struct System_spec
29 {
System_specSystem_spec30   System_spec (Paper_score *ps)
31   {
32     pscore_ = ps;
33     prob_ = NULL;
34   }
35 
System_specSystem_spec36   System_spec (Prob *pb)
37   {
38     prob_ = pb;
39     pscore_ = NULL;
40   }
41 
42   /* only used as a dummy value in case the book is empty. */
System_specSystem_spec43   System_spec ()
44   {
45     pscore_ = NULL;
46     prob_ = NULL;
47   }
48 
49   Paper_score *pscore_;
50   Prob *prob_;
51 };
52 
53 /*
54   indicates a break point in a page spacing problem. If there are N
55   lines/systems, there are N+1 Break_positions around those lines.
56 */
57 struct Break_position
58 {
59   /*
60     index into system_specs_, if this is VPOS, the Break_position represents the
61     start of the book.
62    */
63   vsize system_spec_index_;
64 
65   /* if system_spec_index_ indexes a score, then we start at the score_brk_'th
66      possible page-break in the score */
67   vsize score_break_;
68 
69   /* if system_spec_index_ indexes a score, this points to the broken column */
70   Grob *col_;
71   bool score_ender_;
72 
73   /* if non-zero, this is the (fixed, uncompressed) number of lines between
74      this Break_position and the previous. */
75   vsize forced_line_count_;
76 
Break_positionBreak_position77   Break_position (vsize s = VPOS, vsize brk = VPOS, Grob *g = NULL, bool end = false)
78   {
79     system_spec_index_ = s;
80     score_break_ = brk;
81     col_ = g;
82     score_ender_ = end;
83     forced_line_count_ = 0;
84   }
85 
86   /*
87     lexicographic in (system_spec_index_, score_break_)
88    */
operator <Break_position89   bool operator < (const Break_position &other) const
90   {
91     return (system_spec_index_ == VPOS && other.system_spec_index_ != VPOS)
92            || (system_spec_index_ < other.system_spec_index_)
93            || (system_spec_index_ == other.system_spec_index_ && score_break_ < other.score_break_);
94   }
95 
operator <=Break_position96   bool operator <= (const Break_position &other) const
97   {
98     return (system_spec_index_ == VPOS)
99            || (system_spec_index_ < other.system_spec_index_ && other.system_spec_index_ != VPOS)
100            || (system_spec_index_ == other.system_spec_index_ && score_break_ <= other.score_break_);
101   }
102 };
103 
104 /*
105   A page breaking problem. Subclasses represent different strategies.
106 
107   Read the large comment at the top of page-breaking.cc for context.
108 */
109 class Page_breaking
110 {
111 public:
112   typedef bool (*Break_predicate) (Grob *);
113   typedef bool (*Prob_break_predicate) (Prob *);
114   typedef std::vector<vsize> Line_division;
115 
116   /*
117     Determine the page breaking, and break scores into lines
118     appropriately.
119 
120     This is the only external entry point. Other public methods are
121     for page breaking util classes to query the problem.
122    */
123   virtual SCM solve () = 0;
124 
125   Page_breaking (Paper_book *pb, Break_predicate, Prob_break_predicate);
126   virtual ~Page_breaking ();
127 
128   bool ragged () const;
129   bool ragged_last () const;
130   bool is_last () const;
131   bool ends_score () const;
132   int systems_per_page () const;
133   int max_systems_per_page () const;
134   int min_systems_per_page () const;
135   Real page_height (int page_number, bool last) const;
136   Real paper_height () const;
137   vsize system_count () const;
138   Real footnote_separator_stencil_height () const;
139   Real footnote_padding () const;
140   Real in_note_padding () const;
141   Real footnote_number_raise () const;
142   Real footnote_footer_padding () const;
143   Real line_count_penalty (int line_count) const;
144   int line_count_status (int line_count) const;
145   bool too_many_lines (int line_count) const;
146   bool too_few_lines (int line_count) const;
147   Real min_whitespace_at_top_of_page (Line_details const &) const;
148   Real min_whitespace_at_bottom_of_page (Line_details const &) const;
149   int orphan_penalty () const;
150 
151 protected:
152   Paper_book *book_;
153 
154   vsize next_system (Break_position const &break_pos) const;
155 
156   SCM make_pages (const std::vector<vsize> &lines_per_page, SCM lines);
157 
158   vsize min_system_count (vsize start, vsize end);
159   vsize max_system_count (vsize start, vsize end);
160 
161   void break_into_pieces (vsize start, vsize end, Line_division const &div);
162   SCM systems ();
163   SCM footnotes ();
164 
165   void set_current_breakpoints (vsize start,
166                                 vsize end,
167                                 vsize system_count,
168                                 Line_division lower_bound = Line_division (),
169                                 Line_division upper_bound = Line_division ());
170   void set_to_ideal_line_configuration (vsize start, vsize end);
171 
172   vsize current_configuration_count () const;
173   Line_division current_configuration (vsize configuration_index) const;
174   Page_spacing_result space_systems_on_n_pages (vsize configuration_index,
175                                                 vsize n, int first_page_num);
176   Page_spacing_result space_systems_on_n_or_one_more_pages (vsize configuration_index, vsize n,
177                                                             int first_page_num,
178                                                             Real penalty_for_fewer_pages);
179   Page_spacing_result space_systems_on_best_pages (vsize configuration_index,
180                                                    int first_page_num);
181   Page_spacing_result space_systems_with_fixed_number_per_page (vsize configuration_index,
182       int first_page_num);
183   Page_spacing_result pack_systems_on_least_pages (vsize configuration_index,
184                                                    int first_page_num);
185   vsize min_page_count (vsize configuration_index, int first_page_num);
186   bool all_lines_stretched (vsize configuration_index);
187   Real blank_page_penalty () const;
188 
189   SCM breakpoint_property (vsize breakpoint, char const *str);
190 
191   vsize last_break_position () const;
192 
193   std::vector<System_spec> system_specs_;
194 private:
195   std::vector<Break_position> breaks_;
196   std::vector<Break_position> chunks_;
197   std::vector<Constrained_breaking> line_breaking_;
198   bool ragged_;
199   bool ragged_last_;
200   int systems_per_page_;
201   int max_systems_per_page_;
202   int min_systems_per_page_;
203   vsize system_count_;
204   Real footnote_separator_stencil_height_;
205   Real footnote_padding_;
206   Real in_note_padding_;
207   Real footnote_number_raise_;
208   Real footnote_footer_padding_;
209   int orphan_penalty_;
210 
211   std::vector<Line_division> current_configurations_;
212   std::vector<Break_position> current_chunks_;
213   vsize current_start_breakpoint_;
214   vsize current_end_breakpoint_;
215 
216   void cache_line_details (vsize configuration_index);
217   void calc_line_heights ();
218   void clear_line_details_cache ();
219   vsize cached_configuration_index_;
220   std::vector<Line_details> cached_line_details_;
221   std::vector<Line_details> uncompressed_line_details_;
222 
223   Real paper_height_;
224   mutable std::vector<Real> page_height_cache_;
225   mutable std::vector<Real> last_page_height_cache_;
226 
227   std::vector<Break_position> chunk_list (vsize start, vsize end) const;
228   Line_division system_count_bounds (std::vector<Break_position> const &chunks, bool min);
229   void line_breaker_args (vsize i,
230                           Break_position const &start,
231                           Break_position const &end,
232                           vsize *line_breaker_start,
233                           vsize *line_breaker_end);
234 
235   void line_divisions_rec (vsize system_count,
236                            Line_division const &min,
237                            Line_division const &max,
238                            Line_division *cur);
239 
240   std::vector<Line_details> line_details (vsize start, vsize end, Line_division const &div);
241   Page_spacing_result space_systems_on_1_page (std::vector<Line_details> const &lines, Real page_height, bool ragged);
242   Page_spacing_result space_systems_on_2_pages (vsize configuration_index, int first_page_num);
243   Page_spacing_result finalize_spacing_result (vsize configuration_index, Page_spacing_result);
244   void create_system_list ();
245   void find_chunks_and_breaks (Break_predicate, Prob_break_predicate);
246   SCM make_page (int page_num, bool last) const;
247   SCM get_page_configuration (SCM systems, int page_num, bool ragged, bool last);
248   SCM draw_page (SCM systems, SCM config, int page_num, bool last);
249 };
250 #endif /* PAGE_BREAKING_HH */
251