X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fsimple-spacer.cc;h=c7d016b27c2dfb894e75cb752b9f73a973977723;hb=38189e6a227753ee6dca31aac448d97071a8551d;hp=be05115a6dda560bf32aae8b4e085e5fa1ce4f4b;hpb=b0722af04579cd67f38c3f3ac51762d186614664;p=lilypond.git diff --git a/lily/simple-spacer.cc b/lily/simple-spacer.cc index be05115a6d..c7d016b27c 100644 --- a/lily/simple-spacer.cc +++ b/lily/simple-spacer.cc @@ -1,60 +1,61 @@ -/* +/* simple-spacer.cc -- implement Simple_spacer - + source file of the GNU LilyPond music typesetter - - (c) 1999--2002 Han-Wen Nienhuys + + (c) 1999--2005 Han-Wen Nienhuys TODO: - add support for different stretch/shrink constants? - */ +#include #include -#include // isinf +#include "libc-extension.hh" // isinf #include "simple-spacer.hh" #include "paper-column.hh" #include "spring.hh" -#include "rod.hh" #include "warn.hh" #include "column-x-positions.hh" #include "spaceable-grob.hh" #include "dimensions.hh" - /* - A simple spacing constraint solver. The approach: + A simple spacing constraint solver. The approach: + + Stretch the line uniformly until none of the constraints (rods) + block. It then is very wide. - Stretch the line uniformly until none of the constraints (rods) - block. It then is very wide. + Compress until the next constraint blocks, - Compress until the next constraint blocks, + Mark the springs over the constrained part to be non-active. - Mark the springs over the constrained part to be non-active. - - Repeat with the smaller set of non-active constraints, until all - constraints blocked, or until the line is as short as desired. + Repeat with the smaller set of non-active constraints, until all + constraints blocked, or until the line is as short as desired. - This is much simpler, and much much faster than full scale - Constrained QP. On the other hand, a situation like this will not - be typeset as dense as possible, because + This is much simpler, and much much faster than full scale + Constrained QP. On the other hand, a situation like this will not + be typeset as dense as possible, because - c4 c4 c4 c4 - veryveryverylongsyllable2 veryveryverylongsyllable2 - " "4 veryveryverylongsyllable2 syllable4 + c4 c4 c4 c4 + veryveryverylongsyllable2 veryveryverylongsyllable2 + " "4 veryveryverylongsyllable2 syllable4 - can be further compressed to + can be further compressed to - c4 c4 c4 c4 - veryveryverylongsyllable2 veryveryverylongsyllable2 - " "4 veryveryverylongsyllable2 syllable4 + c4 c4 c4 c4 + veryveryverylongsyllable2 veryveryverylongsyllable2 + " "4 veryveryverylongsyllable2 syllable4 - Perhaps this is not a bad thing, because the 1st looks better anyway. */ + Perhaps this is not a bad thing, because the 1st looks better anyway. */ +/* + positive force = expanding, negative force = compressing. +*/ Simple_spacer::Simple_spacer () { @@ -62,11 +63,10 @@ Simple_spacer::Simple_spacer () Give an extra penalty for compression. Needed to avoid compressing tightly spaced lines. */ - compression_penalty_b_ = false; active_count_ = 0; - force_f_ = 0.; - indent_f_ =0.0; - default_space_f_ = 20 PT; + force_ = 0.; + indent_ = 0.0; + default_space_ = 20 PT; } void @@ -74,56 +74,56 @@ Simple_spacer::add_rod (int l, int r, Real dist) { if (isinf (dist) || isnan (dist)) { - programming_error ("Weird minimum distance. Ignoring"); + programming_error ("ignoring weird minimum distance"); return; } - Real c = range_stiffness (l,r); + Real c = range_stiffness (l, r); if (isinf (c)) { /* If a spring is fixed, we have to do something here: - we let the rod override the spring. - */ + we let the rod override the spring. + */ Real total_dist = 0.; - for (int i = l ; i < r; i++) - total_dist += springs_[i].ideal_f_; + for (int i = l; i < r; i++) + total_dist += springs_[i].ideal_; if (total_dist < dist) - for (int i = l ; i < r; i++) - springs_[i].ideal_f_ *= dist/total_dist; + for (int i = l; i < r; i++) + springs_[i].ideal_ *= dist / total_dist; return; } - - Real d = range_ideal_len (l,r); + + Real d = range_ideal_len (l, r); Real block_stretch = dist - d; - + Real block_force = c * block_stretch; - force_f_ = force_f_ >? block_force; + force_ = force_ >? block_force; - for (int i=l; i < r; i++) - springs_[i].block_force_f_ = block_force >? - springs_[i].block_force_f_ ; + for (int i = l; i < r; i++) + springs_[i].block_force_ = block_force >? + springs_[i].block_force_; } Real -Simple_spacer::range_ideal_len (int l, int r) const +Simple_spacer::range_ideal_len (int l, int r) const { - Real d =0.; - for (int i=l; i < r; i++) - d += springs_[i].ideal_f_; + Real d = 0.; + for (int i = l; i < r; i++) + d += springs_[i].ideal_; return d; } Real Simple_spacer::range_stiffness (int l, int r) const { - Real den =0.0; - for (int i=l; i < r; i++) + Real den = 0.0; + for (int i = l; i < r; i++) { - if (springs_[i].active_b_) - den += 1 / springs_[i].hooke_f_; + if (springs_[i].is_active_) + den += 1 / springs_[i].hooke_; } return 1 / den; @@ -132,11 +132,11 @@ Simple_spacer::range_stiffness (int l, int r) const Real Simple_spacer::active_blocking_force () const { - Real bf = - infinity_f; - for (int i=0; i < springs_.size (); i++) - if (springs_[i].active_b_) + Real bf = -infinity_f; + for (int i = 0; i < springs_.size (); i++) + if (springs_[i].is_active_) { - bf = bf >? springs_[i].block_force_f_; + bf = bf >? springs_[i].block_force_; } return bf; } @@ -144,55 +144,70 @@ Simple_spacer::active_blocking_force () const Real Simple_spacer::active_springs_stiffness () const { - Real den = 0.0; - for (int i=0; i < springs_.size (); i++) - if (springs_[i].active_b_) - { - den += 1 / springs_[i].hooke_f_; - } - return 1/den; + Real stiff = range_stiffness (0, springs_.size ()); + if (isinf (stiff)) + { + /* + all springs are inactive. Take the stiffness of the + latest spring to block. + */ + + Real max_block_force = -infinity_f; + int max_i = -1; + for (int i = 0; i < springs_.size (); i++) + { + if (springs_[i].block_force_ > max_block_force) + { + max_i = i; + max_block_force = springs_[i].block_force_; + } + } + + stiff = springs_[max_i].hooke_; + } + return stiff; } void Simple_spacer::set_active_states () { /* float comparison is safe, since force is only copied. */ - for (int i=0 ; i = force_f_) + for (int i = 0; i < springs_.size (); i++) + if (springs_[i].is_active_ + && springs_[i].block_force_ >= force_) { - springs_[i].active_b_ = false; - active_count_ --; + springs_[i].is_active_ = false; + active_count_--; } -} +} Real Simple_spacer::configuration_length () const { - Real l =0.; - for (int i=0; i < springs_.size (); i++) - l += springs_[i].length (force_f_); + Real l = 0.; + for (int i = 0; i < springs_.size (); i++) + l += springs_[i].length (force_); return l; } bool -Simple_spacer::active_b () const +Simple_spacer::is_active () const { - return active_count_; + return active_count_; } void Simple_spacer::my_solve_linelen () { - while (active_b ()) + while (is_active ()) { - force_f_ = active_blocking_force (); + force_ = active_blocking_force (); Real conf = configuration_length (); - if (conf < line_len_f_) + if (conf < line_len_) { - force_f_ += (line_len_f_ - conf) * active_springs_stiffness (); + force_ += (line_len_ - conf) * active_springs_stiffness (); break; } else @@ -200,198 +215,244 @@ Simple_spacer::my_solve_linelen () } } - void Simple_spacer::my_solve_natural_len () { - while (active_b ()) + Real line_len_force = 0.0; + + while (is_active ()) { - force_f_ = active_blocking_force () >? 0.0; + force_ = active_blocking_force () >? 0.0; + Real conf = configuration_length (); - if (force_f_ < 1e-8) // ugh., + if (conf < line_len_) + { + line_len_force = force_ + + (line_len_ - conf) + * active_springs_stiffness (); + } + + if (force_ < 1e-8) // ugh., break; - + set_active_states (); } + + force_ = line_len_force; } -void -Simple_spacer::add_columns (Link_array cols) +/****************************************************************/ + +Spring_description::Spring_description () { - for (int i = cols.size (); i--;) - if (gh_pair_p (cols[i]->get_grob_property ("between-cols"))) - { - loose_cols_.push (cols[i]); - cols.del (i); - } - - spaced_cols_ = cols; - for (int i=0; i < cols.size () - 1; i++) - { - Spring_smob *spring = 0; + ideal_ = 0.0; + hooke_ = 0.0; + is_active_ = true; + block_force_ = 0.0; +} - for (SCM s = cols[i]->get_grob_property ("ideal-distances"); - !spring && gh_pair_p (s); - s = ly_cdr (s)) - { - Spring_smob *sp = unsmob_spring (ly_car (s)); - - - if (sp->other_ == cols[i+1]) - spring = sp; - } +bool +Spring_description::is_sane () const +{ + return (hooke_ > 0) + && ideal_ > 0 + && !isinf (ideal_) && !isnan (ideal_); +} - Spring_description desc; - if (spring) - { - desc.ideal_f_ = spring->distance_f_; - desc.hooke_f_ = spring->strength_f_; - } - else - { - programming_error (_f("No spring between column %d and next one", - Paper_column::rank_i (cols[i]) - )); - desc.hooke_f_ = 1.0; - desc.ideal_f_ = default_space_f_; +Real +Spring_description::length (Real f) const +{ + if (!is_active_) + f = block_force_; + return ideal_ + f / hooke_; +} +/****************************************************************/ - continue; - } +/* + TODO: should a add penalty for widely varying spring forces (caused + by constraints, eg. - if (!desc.sane_b ()) - { - programming_error ("Insane spring found. Setting to unit spring."); - cout << "columns " << Paper_column::rank_i (cols[i]) - << " " << Paper_column::rank_i (cols[i+1]) << endl; - desc.hooke_f_ = 1.0; - desc.ideal_f_ = 1.0; - } + ===== + | | + o|o| x ##x - if (isinf (desc.hooke_f_)) - { - desc.active_b_ = false; - springs_.push (desc); - } - else - { - desc.block_force_f_ = - desc.hooke_f_ * desc.ideal_f_; // block at distance 0 - springs_.push (desc); - - active_count_ ++; - } - if (spring->expand_only_b_) - { - compression_penalty_b_ = true; - } - + The ## forces the notes apart; we shouldn't allow the O's to touch + this closely. +*/ +void +Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged) +{ + if (ragged) + spacer_->my_solve_natural_len (); + else + spacer_->my_solve_linelen (); + + positions->force_ = spacer_->force_; + + /* + We used to have a penalty for compression, no matter what, but that + fucked up wtk1-fugue2 (taking 3 full pages.) + */ + positions->config_.push (spacer_->indent_); + for (int i = 0; i < spacer_->springs_.size (); i++) + { + Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_); + positions->config_.push (positions->config_.top () + l); + /* + we have l>= 0 here, up to rounding errors + */ } - - for (int i=0; i < cols.size () - 1; i++) + + /* + For raggedright, we must have a measure of music density: this is + to prevent lots of short lines (which all have force = 0). + */ + if (ragged) { - for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]); - gh_pair_p (s); s = ly_cdr (s)) + positions->satisfies_constraints_ + = positions->config_.top () < spacer_->line_len_; + } + else + positions->satisfies_constraints_ = spacer_->is_active (); + + positions->cols_ = spaced_cols_; + positions->loose_cols_ = loose_cols_; + + /* + Check if breaking constraints are met. + */ + bool break_satisfy = true; + int sz = positions->cols_.size (); + for (int i = sz; i--;) + { + SCM p = positions->cols_[i]->get_property ("penalty"); + if (scm_is_number (p)) { - Grob * other = unsmob_grob (ly_caar (s)); - int oi = cols.find_i (other); - if (oi >= 0) - { - add_rod (i, oi, gh_scm2double (ly_cdar (s))); - } + if (scm_to_double (p) < -9999) + break_satisfy = break_satisfy && (i == 0 || i == sz -1); + if (scm_to_double (p) > 9999) + break_satisfy = break_satisfy && ! (i == 0 || i == sz -1); } } - /* - TODO: should support natural length on only the last line. - */ - if (line_len_f_ < 0) - my_solve_natural_len (); - else - my_solve_linelen (); + positions->satisfies_constraints_ + = positions->satisfies_constraints_ && break_satisfy; } -#include - void -Simple_spacer::solve (Column_x_positions *positions, bool ragged) const +Simple_spacer::add_spring (Real ideal, Real hooke) { - positions->force_f_ = force_f_; - if ((force_f_ < 0)) + Spring_description desc; + + desc.ideal_ = ideal; + desc.hooke_ = hooke; + if (!desc.is_sane ()) { + programming_error ("insane spring found, setting to unit"); - /* - We used to have a penalty for compression, no matter what, but that - fucked up wtk1-fugue2 (taking 3 full pages.) + desc.hooke_ = 1.0; + desc.ideal_ = 1.0; + } - maybe this should be tunable? - */ - if (compression_penalty_b_) - positions->force_f_ *= 2; // hmm. + if (isinf (hooke)) + { + desc.is_active_ = false; } - - positions->config_.push (indent_f_); - for (int i=0; i config_.push (positions->config_.top () + springs_[i].length (0.0)); - } - else - { - positions->config_.push (positions->config_.top () + springs_[i].length (force_f_)); - } + /* + desc.is_active_ ? + */ + desc.block_force_ = -desc.hooke_ * desc.ideal_; // block at distance 0 + + active_count_++; } - positions->cols_ = spaced_cols_; - positions->loose_cols_ = loose_cols_; - - positions->satisfies_constraints_b_ = (line_len_f_ < 0) || active_b (); + springs_.push (desc); +} +static int +compare_paper_column_rank (Grob *const &a, + Grob *const &b) +{ + return Paper_column::get_rank (a) - Paper_column::get_rank (b); +} - /* - Check if breaking constraints are met. - */ - bool break_satisfy = true; - int sz = positions->cols_.size (); - for (int i = sz; i--; ) +void +Simple_spacer_wrapper::add_columns (Link_array const &icols) +{ + Link_array cols (icols); + + for (int i = cols.size (); i--;) + if (scm_is_pair (cols[i]->get_property ("between-cols"))) + { + loose_cols_.push (cols[i]); + cols.del (i); + } + + spaced_cols_ = cols; + for (int i = 0; i < cols.size () - 1; i++) { - SCM p = positions->cols_[i]->get_grob_property( "penalty"); - if (gh_number_p (p)) + Spring_smob *spring = 0; + + for (SCM s = cols[i]->get_property ("ideal-distances"); + !spring && scm_is_pair (s); + s = scm_cdr (s)) { - if (gh_scm2double (p) < -9999) - break_satisfy = break_satisfy && (i == 0 || i == sz -1); - if (gh_scm2double (p) > 9999) - break_satisfy = break_satisfy && !(i == 0 || i == sz -1); + Spring_smob *sp = unsmob_spring (scm_car (s)); + + if (sp->other_ == cols[i + 1]) + spring = sp; } - + + if (!spring) + programming_error (_f ("No spring between column %d and next one", + Paper_column::get_rank (cols[i]))); + + Real ideal = (spring) ? spring->distance_ : spacer_->default_space_; + Real hooke = (spring) ? spring->strength_ : 1.0; + + spacer_->add_spring (ideal, hooke); } - positions->satisfies_constraints_b_ = - positions->satisfies_constraints_b_ && break_satisfy; -} + for (int i = 0; i < cols.size () - 1; i++) + { + for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]); + scm_is_pair (s); s = scm_cdr (s)) + { + Grob *other = unsmob_grob (scm_caar (s)); + int oi = binsearch_links (cols, other, &compare_paper_column_rank); + if (oi >= 0 + && cols[oi] == other) + { + spacer_->add_rod (i, oi, scm_to_double (scm_cdar (s))); + } + } -/****************************************************************/ + if (i + && !to_boolean (cols[i]->get_property ("allow-outside-line"))) + { + Interval e = cols[i]->extent (cols[i], X_AXIS); + if (!e.is_empty ()) + { + spacer_->add_rod (i, cols.size () - 1, e[RIGHT]); + spacer_->add_rod (0, i, e[LEFT]); + } + } + } +} -Spring_description::Spring_description () +Simple_spacer_wrapper::Simple_spacer_wrapper () { - ideal_f_ =0.0; - hooke_f_ =0.0; - active_b_ = true; - block_force_f_ = 0.0; + spacer_ = new Simple_spacer (); } - -bool -Spring_description::sane_b () const +Simple_spacer_wrapper::~Simple_spacer_wrapper () { - return (hooke_f_ > 0) && !isinf (ideal_f_) && !isnan (ideal_f_); + delete spacer_; } -Real -Spring_description::length (Real f) const +Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const &) { - if (!active_b_) - f = block_force_f_; - return ideal_f_ + f / hooke_f_ ; }