X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fpage-spacing.cc;h=97ff0e45d1c606ce61ebed8324ce78d31d0d7383;hb=5b4b0d6e9a197e8f9eb085b7c2ad78b8be3e5cfc;hp=4d11f0c86595cf5b68b8ba52e59bd2fa9e0dc779;hpb=52c2fa58a215d4d7218d7491fbac51e0de7df31e;p=lilypond.git diff --git a/lily/page-spacing.cc b/lily/page-spacing.cc index 4d11f0c865..97ff0e45d1 100644 --- a/lily/page-spacing.cc +++ b/lily/page-spacing.cc @@ -4,52 +4,41 @@ source file of the GNU LilyPond music typesetter - (c) 2006 Joe Neeman + (c) 2006--2008 Joe Neeman */ #include "page-spacing.hh" #include "matrix.hh" +#include "page-breaking.hh" #include "warn.hh" -/* - A much simplified rods-and-springs problem. - */ -struct Page_spacing -{ - Real force_; - Real page_height_; - Real rod_height_; - Real spring_len_; - Real inverse_spring_k_; - - Line_details last_line_; - - Page_spacing (Real page_height) - { - page_height_ = page_height; - clear (); - } - - void calc_force (); - - void append_system (const Line_details &line); - void prepend_system (const Line_details &line); - void clear (); -}; - void Page_spacing::calc_force () { - if (rod_height_ + last_line_.bottom_padding_ >= page_height_ || !inverse_spring_k_) + /* If the first system is a title, we add back in the page-top-space. */ + Real height = first_line_.title_ ? page_height_ + page_top_space_ : page_height_; + + if (rod_height_ + last_line_.bottom_padding_ >= height) force_ = infinity_f; else - force_ = (page_height_ - rod_height_ - last_line_.bottom_padding_ - spring_len_) / inverse_spring_k_; + force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_) + / max (0.1, inverse_spring_k_); +} + +void +Page_spacing::resize (Real new_height) +{ + page_height_ = new_height; + calc_force (); } void Page_spacing::append_system (const Line_details &line) { + if (!rod_height_) + first_line_ = line; + rod_height_ += last_line_.padding_; rod_height_ += line.extent_.length (); @@ -73,6 +62,8 @@ Page_spacing::prepend_system (const Line_details &line) spring_len_ += line.space_; inverse_spring_k_ += line.inverse_hooke_; + first_line_ = line; + calc_force (); } @@ -83,182 +74,69 @@ Page_spacing::clear () inverse_spring_k_ = 0; } -/* for each forbidden page break, merge the systems around it into one system. */ -static vector -compress_lines (const vector &orig) -{ - vector ret; - - for (vsize i = 0; i < orig.size (); i++) - { - if (i < orig.size () - 1 && orig[i].page_permission_ == SCM_EOL) - { - Line_details compressed = orig[i+1]; - compressed.extent_[DOWN] = orig[i].extent_[DOWN]; - compressed.extent_[UP] = orig[i].extent_[UP] + orig[i+1].extent_.length () + orig[i].padding_; - compressed.space_ += orig[i].space_; - compressed.inverse_hooke_ += orig[i].inverse_hooke_; - - /* we don't need the force_ field for the vertical spacing, - so we use force_ = -1 to signal that the line was compressed - (and force_ = +1 otherwise). - This makes uncompression much easier. */ - compressed.force_ = -1; - ret.push_back (compressed); - i++; - } - else - { - ret.push_back (orig[i]); - ret.back ().force_ = 1; - } - } - return ret; -} - -/* translate the number of systems-per-page into something meaningful for - the uncompressed lines. -*/ -static vector -uncompress_solution (vector const &systems_per_page, - vector const &compressed) -{ - vector ret; - vsize start_sys = 0; - - for (vsize i = 0; i < systems_per_page.size (); i++) - { - int compressed_count = 0; - for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++) - if (compressed[j].force_ < 0) - compressed_count++; - - ret.push_back (systems_per_page[i] + compressed_count); - start_sys += systems_per_page[i]; - } - return ret; -} - -/* the cases for page_count = 1 or 2 can be done in O(n) time. Since they - are by far the most common cases, we have special functions for them */ -static Spacing_result -space_systems_on_1_page (vector const &lines, Real page_height, bool ragged) -{ - Page_spacing space (page_height); - Spacing_result ret; - for (vsize i = 0; i < lines.size (); i++) - space.append_system (lines[i]); - - ret.systems_per_page_.push_back (lines.size ()); - ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_); - ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_; - ret.demerits_ = ret.force_.back () * ret.force_.back () + ret.penalty_; - - return ret; -} - -static Spacing_result -space_systems_on_2_pages (vector const &lines, - Real page_height, - bool ragged, - bool ragged_last) -{ - /* if there is a forced break, this reduces to 2 1-page problems */ - for (vsize i = 0; i < lines.size () - 1; i++) - if (lines[i].page_permission_ == ly_symbol2scm ("force")) - { - vector lines1 (lines.begin (), lines.begin () + i + 1); - vector lines2 (lines.begin () + i + 1, lines.end ()); - Spacing_result p1 = space_systems_on_1_page (lines1, page_height, ragged); - Spacing_result p2 = space_systems_on_1_page (lines2, page_height, ragged || ragged_last); - - p1.systems_per_page_.push_back (p2.systems_per_page_[0]); - p1.force_.push_back (p2.force_[0]); - p1.penalty_ += p2.penalty_ - lines[i].turn_penalty_; - p1.demerits_ += p2.demerits_ - lines[i].turn_penalty_; - return p1; - } - - vector page1_force; - vector page2_force; - Page_spacing page1 (page_height); - Page_spacing page2 (page_height); - - page1_force.resize (lines.size () - 1, infinity_f); - page2_force.resize (lines.size () - 1, infinity_f); - - for (vsize i = 0; i < page1_force.size (); i++) - { - page1.append_system (lines[i]); - page2.prepend_system (lines[lines.size () - 1 - i]); - page1_force[i] = (ragged && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_; - - if (ragged || ragged_last) - page2_force[page2_force.size () - 1 - i] = - (page2.force_ < 0 && i < page1_force.size () - 1) ? infinity_f : 0; - else - page2_force[page2_force.size () - 1 - i] = page2.force_; - } - - vsize best_sys_count = 1; - Real best_demerits = infinity_f; - for (vsize i = 0; i < page1_force.size (); i++) - { - Real dem = page1_force[i] * page1_force[i] - + page2_force[i] * page2_force[i] - + lines[i+1].page_penalty_ - + lines.back ().page_penalty_ + lines.back ().turn_penalty_; - if (dem < best_demerits) - { - best_demerits = dem; - best_sys_count = i+1; - } - } - - Spacing_result ret; - ret.systems_per_page_.push_back (best_sys_count); - ret.systems_per_page_.push_back (lines.size () - best_sys_count); - ret.force_.push_back (page1_force[best_sys_count-1]); - ret.force_.push_back (page2_force[best_sys_count-1]); - ret.penalty_ = lines[best_sys_count-1].page_penalty_ - + lines.back ().page_penalty_ - + lines.back ().turn_penalty_; - ret.demerits_ = best_demerits; - - return ret; -} - -Page_spacer::Page_spacer (vector const &lines, Real page_height, bool ragged, bool ragged_last) +Page_spacer::Page_spacer (vector const &lines, vsize first_page_num, Page_breaking const *breaker) : lines_ (lines) { - page_height_ = page_height; + first_page_num_ = first_page_num; + breaker_ = breaker; max_page_count_ = 0; - ragged_ = ragged; - ragged_last_ = ragged_last; + ragged_ = breaker->ragged (); + ragged_last_ = breaker->is_last () && breaker->ragged_last (); } -Spacing_result +Page_spacing_result Page_spacer::solve (vsize page_count) { if (page_count > max_page_count_) resize (page_count); - Spacing_result ret; - ret.force_.resize (page_count); - ret.systems_per_page_.resize (page_count); + Page_spacing_result ret; vsize system = lines_.size () - 1; + vsize extra_systems = 0; + vsize extra_pages = 0; if (isinf (state_.at (system, page_count-1).demerits_)) { programming_error ("tried to space systems on a bad number of pages"); - return Spacing_result (); /* bad number of pages */ + /* Usually, this means that we tried to cram too many systems into + to few pages. To avoid crashing, we look for the largest number of + systems that we can fit properly onto the right number of pages. + All the systems that don't fit get tacked onto the last page. + */ + vsize i; + for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--) + ; + + if (i) + { + extra_systems = system - i; + system = i; + } + else + { + /* try chopping off pages from the end */ + vsize j; + for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--) + ; + + if (j) + { + extra_pages = page_count - j; + page_count = j; + } + else + return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */ + } } + ret.force_.resize (page_count); + ret.systems_per_page_.resize (page_count); ret.penalty_ = state_.at (system, page_count-1).penalty_ + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_; + ret.demerits_ = 0; for (vsize p = page_count; p--;) { assert (system != VPOS); @@ -272,6 +150,20 @@ Page_spacer::solve (vsize page_count) ret.systems_per_page_[p] = system - ps.prev_; system = ps.prev_; } + + if (extra_systems) + { + ret.systems_per_page_.back () += extra_systems; + ret.demerits_ += 200000; + } + if (extra_pages) + { + ret.force_.insert (ret.force_.end (), extra_pages, 200000); + ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0); + ret.demerits_ += 200000; + } + + ret.demerits_ += ret.penalty_; return ret; } @@ -296,9 +188,11 @@ Page_spacer::resize (vsize page_count) bool Page_spacer::calc_subproblem (vsize page, vsize line) { - Page_spacing space (page_height_); + bool last = line == lines_.size () - 1; + Page_spacing space (breaker_->page_height (page + first_page_num_, last), + breaker_->page_top_space ()); Page_spacing_node &cur = state_.at (line, page); - bool ragged = ragged_ || (ragged_last_ && line == lines_.size () - 1); + bool ragged = ragged_ || (ragged_last_ && last); for (vsize page_start = line+1; page_start > page && page_start--;) { @@ -310,7 +204,7 @@ Page_spacer::calc_subproblem (vsize page, vsize line) if (page > 0 || page_start == 0) { - if (line == lines_.size () - 1 && ragged_last_ && space.force_ > 0) + if (line == lines_.size () - 1 && ragged && last && space.force_ > 0) space.force_ = 0; /* we may have to deal with single lines that are taller than a page */ @@ -340,106 +234,3 @@ Page_spacer::calc_subproblem (vsize page, vsize line) return !isinf (cur.demerits_); } -static vsize -min_page_count (vector const &lines, Real page_height, bool ragged) -{ - vsize ret = 1; - Real cur_rod_height = 0; - - for (vsize i = 0; i < lines.size (); i++) - { - Real ext_len = lines[i].extent_.length (); - Real next_height = cur_rod_height + ext_len - + (ragged ? lines[i].space_ : 0) - + ((cur_rod_height > 0) ? lines[i-1].padding_: 0); - - if ((next_height > page_height && cur_rod_height > 0) - || (i > 0 && lines[i-1].page_permission_ == ly_symbol2scm ("force"))) - { - ret++; - cur_rod_height = ext_len + (ragged ? lines[i].space_ : 0); - } - else - cur_rod_height = next_height; - } - return ret; -} - -Spacing_result -space_systems_on_min_pages (vector const &lines, - Real page_height, - Real odd_pages_penalty, - bool ragged, - bool ragged_last) -{ - vector compressed_lines = compress_lines (lines); - vsize min_p_count = min_page_count (compressed_lines, page_height, ragged); - Spacing_result ret; - - if (min_p_count == 1) - { - Spacing_result candidate1 = space_systems_on_1_page (compressed_lines, page_height, ragged || ragged_last); - candidate1.force_.back () += odd_pages_penalty; - candidate1.demerits_ += odd_pages_penalty; - if (compressed_lines.size () == 1) - ret = candidate1; - else - { - Spacing_result candidate2 = space_systems_on_2_pages (compressed_lines, page_height, ragged, ragged_last); - ret = (candidate1.demerits_ < candidate2.demerits_) ? - candidate1 : candidate2; - } - } - else if (min_p_count == 2) - ret = space_systems_on_2_pages (compressed_lines, page_height, ragged, ragged_last); - else - { - Page_spacer ps (compressed_lines, page_height, ragged, ragged_last); - Spacing_result candidate1 = ps.solve (min_p_count); - if (min_p_count % 2 == 0) - ret = candidate1; - else - { - candidate1.force_.back () += odd_pages_penalty; - candidate1.demerits_ += odd_pages_penalty; - - if (min_p_count == compressed_lines.size ()) - ret = candidate1; - else - { - Spacing_result candidate2 = ps.solve (min_p_count + 1); - ret = (candidate1.demerits_ < candidate2.demerits_) ? - candidate1 : candidate2; - } - } - } - ret.systems_per_page_ = uncompress_solution (ret.systems_per_page_, compressed_lines); - return ret; -} - -Spacing_result -space_systems_on_best_pages (vector const &lines, - Real page_height, - Real odd_pages_penalty, - bool ragged, - bool ragged_last) -{ - vector compressed_lines = compress_lines (lines); - vsize min_p_count = min_page_count (compressed_lines, page_height, ragged); - - Page_spacer ps (compressed_lines, page_height, ragged, ragged_last); - Spacing_result best = ps.solve (min_p_count); - best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0; - best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0; - - for (vsize i = min_p_count+1; i <= compressed_lines.size (); i++) - { - Spacing_result cur = ps.solve (i); - cur.demerits_ += (i % 2) ? odd_pages_penalty : 0; - if (cur.demerits_ < best.demerits_) - best = cur; - } - - best.systems_per_page_ = uncompress_solution (best.systems_per_page_, compressed_lines); - return best; -}