X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fsimple-spacer.cc;h=0c595f1d94b165c66a652ef31918f843f1892f67;hb=7693db10b018da89a3123cb4c9e21e3956638c56;hp=fa75e433a7cdcbb8ad96607461db8b2922ae04e5;hpb=fa65a4be862681bc8b06207b9013a07b47ee7f56;p=lilypond.git diff --git a/lily/simple-spacer.cc b/lily/simple-spacer.cc index fa75e433a7..0c595f1d94 100644 --- a/lily/simple-spacer.cc +++ b/lily/simple-spacer.cc @@ -1,72 +1,87 @@ -/* +/* simple-spacer.cc -- implement Simple_spacer - + source file of the GNU LilyPond music typesetter - - (c) 1999--2002 Han-Wen Nienhuys + + (c) 1999--2006 Han-Wen Nienhuys TODO: - add support for different stretch/shrink constants? - */ -#include -#include // isinf +#include -#include "simple-spacer.hh" +#include "column-x-positions.hh" +#include "dimensions.hh" +#include "international.hh" +#include "libc-extension.hh" // isinf #include "paper-column.hh" +#include "simple-spacer.hh" +#include "spaceable-grob.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. - - Repeat with the smaller set of non-active constraints, until all - constraints blocked, or until the line is as short as desired. + Mark the springs over the constrained part to be non-active. - 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 + Repeat with the smaller set of non-active constraints, until all + constraints blocked, or until the line is as short as desired. - c4 c4 c4 c4 - veryveryverylongsyllable2 veryveryverylongsyllable2 - " "4 veryveryverylongsyllable2 syllable4 + 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 - 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 () { - /* - 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.; + fits_ = true; +} + +Real +Simple_spacer::force () +{ + return force_; +} + +bool +Simple_spacer::fits () +{ + return fits_; +} + +Real +Simple_spacer::rod_force (int l, int r, Real dist) +{ + Real c = range_stiffness (l, r); + Real d = range_ideal_len (l, r); + Real block_stretch = dist - d; + return c * block_stretch; } void @@ -74,310 +89,446 @@ 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); - if (isinf (c)) + Real block_force = rod_force (l, r, dist); + + if (isinf (block_force)) { - /* - If a spring is fixed, we have to do something here: - we let the rod override the spring. - */ - Real total_dist = 0.; - for (int i = l ; i < r; i++) - total_dist += springs_[i].ideal_f_; - - if (total_dist < dist) - for (int i = l ; i < r; i++) - springs_[i].ideal_f_ *= dist/total_dist; + Real spring_dist = range_ideal_len (l, r); + if (spring_dist < dist) + for (int i = l; i < r; i++) + springs_[i].ideal_ *= dist / spring_dist; return; } - - Real d = range_ideal_len (l,r); - Real block_stretch = dist - d; - - Real block_force = c * block_stretch; - force_f_ = force_f_ >? block_force; - - for (int i=l; i < r; i++) - springs_[i].block_force_f_ = block_force >? - springs_[i].block_force_f_ ; + force_ = max (force_, block_force); + for (int i = l; i < r; i++) + springs_[i].block_force_ = max (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++) - { - if (springs_[i].active_b_) - den += 1 / springs_[i].hooke_f_; - } + Real den = 0.0; + for (int i = l; i < r; i++) + den += springs_[i].inverse_hooke_; return 1 / den; } Real -Simple_spacer::active_blocking_force () const +Simple_spacer::configuration_length () const { - Real bf = - infinity_f; - for (int i=0; i < springs_.size (); i++) - if (springs_[i].active_b_) - { - bf = bf >? springs_[i].block_force_f_; - } - return bf; -} + Real l = 0.; + for (vsize i = 0; i < springs_.size (); i++) + l += springs_[i].length (force_); -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; + return l; } void -Simple_spacer::set_active_states () +Simple_spacer::solve (Real line_len, bool ragged) { - /* float comparison is safe, since force is only copied. */ - for (int i=0 ; i = force_f_) - { - springs_[i].active_b_ = false; - active_count_ --; - } -} + Real conf = configuration_length (); + + ragged_ = ragged; + line_len_ = line_len; + if (ragged) + { + force_ = 0; + fits_ = configuration_length () <= line_len_; + /* we need to calculate a force here to prevent a bunch of short lines */ + if (fits_) + force_ = expand_line (); + } + else if (conf < line_len_) + force_ = expand_line (); + else if (conf > line_len_) + force_ = compress_line (); +} Real -Simple_spacer::configuration_length () const +Simple_spacer::expand_line () { - Real l =0.; - for (int i=0; i < springs_.size (); i++) - l += springs_[i].length (force_f_); + double inv_hooke = 0; + double cur_len = configuration_length (); - return l; + fits_ = true; + for (vsize i=0; i < springs_.size (); i++) + inv_hooke += springs_[i].inverse_hooke_; + + assert (cur_len <= line_len_); + return (line_len_ - cur_len) / inv_hooke + force_; } -bool -Simple_spacer::active_b () const +Real +Simple_spacer::compress_line () { - return active_count_; + double inv_hooke = 0; + double cur_len = configuration_length (); + double cur_force = force_; + + fits_ = true; + for (vsize i=0; i < springs_.size (); i++) + inv_hooke += springs_[i].inverse_hooke_; + + assert (line_len_ <= cur_len); + + vector sorted_springs = springs_; + sort (sorted_springs.begin (), sorted_springs.end (), greater ()); + for (vsize i = 0; i < sorted_springs.size (); i++) + { + Spring_description sp = sorted_springs[i]; + + assert (sp.block_force_ <= cur_force); + if (isinf (sp.block_force_)) + break; + + double block_dist = (cur_force - sp.block_force_) * inv_hooke; + if (cur_len - block_dist <= line_len_) + return cur_force + (line_len_ - cur_len) / inv_hooke; + cur_len -= block_dist; + inv_hooke -= sp.inverse_hooke_; + cur_force = sp.block_force_; + } + + fits_ = false; + return cur_force; } void -Simple_spacer::my_solve_linelen () +Simple_spacer::add_spring (Real ideal, Real inverse_hooke) { - while (active_b ()) + Spring_description desc; + + desc.ideal_ = ideal; + desc.inverse_hooke_ = inverse_hooke; + if (!desc.is_sane ()) { - force_f_ = active_blocking_force (); - Real conf = configuration_length (); + programming_error ("insane spring found, setting to unit"); - if (conf < line_len_f_) - { - force_f_ += (line_len_f_ - conf) * active_springs_stiffness (); - break; - } - else - set_active_states (); + desc.inverse_hooke_ = 1.0; + desc.ideal_ = 1.0; } + + desc.block_force_ = -desc.ideal_ / desc.inverse_hooke_; + // block at distance 0 + + springs_.push_back (desc); +} + +vector +Simple_spacer::spring_positions () const +{ + vector ret; + ret.push_back (0.); + + for (vsize i = 0; i < springs_.size (); i++) + ret.push_back (ret.back () + springs_[i].length (ragged_ ? 0.0 : force_)); + return ret; } +/****************************************************************/ -void -Simple_spacer::my_solve_natural_len () +Spring_description::Spring_description () { - while (active_b ()) - { - force_f_ = active_blocking_force () >? 0.0; + ideal_ = 0.0; + inverse_hooke_ = 0.0; + block_force_ = 0.0; +} - if (force_f_ < 1e-8) // ugh., - break; - - set_active_states (); - } +bool +Spring_description::is_sane () const +{ + return (inverse_hooke_ >= 0) + && ideal_ > 0 + && !isinf (ideal_) && !isnan (ideal_); } -void -Simple_spacer::add_columns (Link_array cols) +Real +Spring_description::length (Real f) const { - 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; + return ideal_ + max (f, block_force_) * inverse_hooke_; +} - 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; - } +/****************************************************************/ - 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_; +/* + TODO: should a add penalty for widely varying spring forces (caused + by constraints, eg. - continue; - } - if (!desc.sane_b ()) - { - programming_error ("Insane spring found. Setting to unit spring."); + . ===== + . | | + .o|o|x ##x + . - 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; - } + The ## forces the notes apart; we shouldn't allow the O's to touch + this closely. +*/ - if (isinf (desc.hooke_f_)) - { - desc.active_b_ = false; - springs_.push (desc); - } - else +struct Rod_desc +{ + vsize r_; + Real dist_; + + bool operator< (const Rod_desc r) + { + return r_ < r.r_; + } + + Rod_desc () {} + Rod_desc (vsize r, Real d) + { + r_ = r; + dist_ = d; + } +}; + +struct Column_desc +{ + vector rods_; + vector end_rods_; /* use these if they end at the last column of the line */ + Real ideal_; + Real inverse_hooke_; + Real end_ideal_; + Real end_inverse_hooke_; + Interval keep_inside_line_; +}; + +static int compare_paper_column_rank (Grob *const &a, Grob *const &b); + +static bool +is_loose (Grob *g) +{ + return (scm_is_pair (g->get_object ("between-cols"))); +} + +static Grob* +maybe_find_prebroken_piece (Grob *g, Direction d) +{ + Grob *ret = dynamic_cast (g)->find_prebroken_piece (d); + if (ret) + return ret; + return g; +} + +static Grob* +next_spaceable_column (vector const &list, vsize starting) +{ + for (vsize i = starting+1; i < list.size (); i++) + if (!is_loose (list[i])) + return list[i]; + return 0; +} + +/* this only returns non-NULL if the line-ending column is the next + spaceable-or-breakable column */ +static Grob* +next_line_ending_column (vector const &list, vsize starting) +{ + vsize i = starting + 1; + for (; i < list.size () + && is_loose (list[i]) + && !Paper_column::is_breakable (list[i]); + i++) + ; + return dynamic_cast (list[i])->find_prebroken_piece (LEFT); +} + +static void +get_column_spring (Grob *this_col, Grob *next_col, Real *ideal, Real *inv_hooke) +{ + Spring_smob *spring = 0; + + for (SCM s = this_col->get_object ("ideal-distances"); + !spring && scm_is_pair (s); + s = scm_cdr (s)) + { + Spring_smob *sp = unsmob_spring (scm_car (s)); + + if (sp->other_ == next_col) + spring = sp; + } + + if (!spring) + programming_error (_f ("No spring between column %d and next one", + Paper_column::get_rank (this_col))); + + *ideal = (spring) ? spring->distance_ : 5.0; + *inv_hooke = (spring) ? spring->inverse_strength_ : 1.0; +} + +static Column_desc +get_column_desc (vector const &cols, vsize col_index, bool line_starter) +{ + Grob *col = cols[col_index]; + if (line_starter) + col = maybe_find_prebroken_piece (col, RIGHT); + + Column_desc desc; + Grob *next_col = next_spaceable_column (cols, col_index); + if (next_col) + get_column_spring (col, next_col, &desc.ideal_, &desc.inverse_hooke_); + Grob *end_col = next_line_ending_column (cols, col_index); + if (end_col) + get_column_spring (col, end_col, &desc.end_ideal_, &desc.end_inverse_hooke_); + + for (SCM s = Spaceable_grob::get_minimum_distances (col); + scm_is_pair (s); s = scm_cdr (s)) + { + Grob *other = unsmob_grob (scm_caar (s)); + vsize j = binary_search (cols, other, &compare_paper_column_rank, col_index); + if (j != VPOS) { - desc.block_force_f_ = - desc.hooke_f_ * desc.ideal_f_; // block at distance 0 - springs_.push (desc); - - active_count_ ++; + if (cols[j] == other) + desc.rods_.push_back (Rod_desc (j, scm_to_double (scm_cdar (s)))); + else /* it must end at the LEFT prebroken_piece */ + desc.end_rods_.push_back (Rod_desc (j, scm_to_double (scm_cdar (s)))); } + } + if (!line_starter && to_boolean (col->get_property ("keep-inside-line"))) + desc.keep_inside_line_ = col->extent (col, X_AXIS); + return desc; +} - if (spring->expand_only_b_) +vector +get_line_forces (vector const &icols, vector breaks, + Real line_len, Real indent, bool ragged) +{ + vector force; + force.resize (breaks.size () * breaks.size ()); + + vector cols; + vsize b = 1; + cols.push_back (Column_desc ()); + for (vsize i = 1; i < icols.size () - 1; i++) + { + if (b < breaks.size () && breaks[b] == i) { - compression_penalty_b_ = true; + breaks[b] = cols.size (); + b++; } - + if (!is_loose (icols[i])) + cols.push_back (get_column_desc (icols, i, false)); } - - for (int i=0; i < cols.size () - 1; i++) + breaks.back () = cols.size () - 1; + + for (vsize b = 0; b < breaks.size () - 1; b++) { - for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]); - gh_pair_p (s); s = ly_cdr (s)) + cols[breaks[b]] = get_column_desc (icols, breaks[b], true); + vsize st = breaks[b]; + + for (vsize c = b+1; c < breaks.size (); c++) { - Grob * other = unsmob_grob (ly_caar (s)); - int oi = cols.find_i (other); - if (oi >= 0) + vsize end = breaks[c]; + Simple_spacer spacer; + + for (vsize i = breaks[b]; i < end - 1; i++) + spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_); + spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].inverse_hooke_); + + + for (vsize i = breaks[b]; i < end; i++) { - add_rod (i, oi, gh_scm2double (ly_cdar (s))); + for (vsize r = 0; r < cols[i].rods_.size (); r++) + if (cols[i].rods_[r].r_ < end) + spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_); + for (vsize r = 0; r < cols[i].end_rods_.size (); r++) + if (cols[i].end_rods_[r].r_ == end) + spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_); + if (!cols[i].keep_inside_line_.is_empty ()) + { + spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]); + spacer.add_rod (0, i - st, cols[i].keep_inside_line_[LEFT]); + } + } + spacer.solve ((b == 0) ? line_len - indent : line_len, ragged); + force[b * breaks.size () + c] = spacer.force (); + if (!spacer.fits ()) + { + force[b * breaks.size () + c] = infinity_f; + break; } } } - - /* - TODO: should support natural length on only the last line. - */ - if (line_len_f_ < 0) - my_solve_natural_len (); - else - my_solve_linelen (); + return force; } -#include - -void -Simple_spacer::solve (Column_x_positions *positions) const +Column_x_positions +get_line_configuration (vectorconst &columns, + Real line_len, + Real indent, + bool ragged) { - positions->force_f_ = force_f_; - if ((force_f_ < 0)) - { - positions->force_f_ *= 1.3; - if (compression_penalty_b_) - positions->force_f_ *= 2; // hmm. - } - - positions->config_.push (indent_f_); - for (int i=0; i cols; + Simple_spacer spacer; + Column_x_positions ret; + + ret.cols_.push_back (dynamic_cast (columns[0])->find_prebroken_piece (RIGHT)); + for (vsize i = 1; i < columns.size () - 1; i++) { - positions->config_.push (positions->config_.top () + springs_[i].length (force_f_)); + if (is_loose (columns[i])) + ret.loose_cols_.push_back (columns[i]); + else + ret.cols_.push_back (columns[i]); } - positions->cols_ = spaced_cols_; - positions->loose_cols_ = loose_cols_; - - positions->satisfies_constraints_b_ = (line_len_f_ < 0) || active_b (); + ret.cols_.push_back (dynamic_cast (columns.back ())->find_prebroken_piece (LEFT)); + cols.resize (ret.cols_.size () - 1); - /* - Check if breaking constraints are met. - */ - bool break_satisfy = true; - int sz = positions->cols_.size (); - for (int i = sz; i--; ) + /* since we've already put our line-ending column in the column list, we can ignore + the end_XXX_ fields of our column_desc */ + for (vsize i = 0; i < cols.size (); i++) { - SCM p = positions->cols_[i]->get_grob_property( "penalty"); - if (gh_number_p (p)) - { - 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); - } - + cols[i] = get_column_desc (ret.cols_, i, i == 0); + spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_); } + for (vsize i = 0; i < cols.size (); i++) + for (vsize r = 0; r < cols[i].rods_.size (); r++) + spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_); - positions->satisfies_constraints_b_ = - positions->satisfies_constraints_b_ && break_satisfy; -} + spacer.solve (line_len, ragged); + ret.force_ = spacer.force (); -/****************************************************************/ + /* + We used to have a penalty for compression, no matter what, but that + fucked up wtk1-fugue2 (taking 3 full pages.) + */ + ret.config_ = spacer.spring_positions (); + for (vsize i = 0; i < ret.config_.size (); i++) + ret.config_[i] += indent; -Spring_description::Spring_description () -{ - ideal_f_ =0.0; - hooke_f_ =0.0; - active_b_ = true; - block_force_f_ = 0.0; -} + ret.satisfies_constraints_ = spacer.fits (); + /* + Check if breaking constraints are met. + */ + for (vsize i = 1; i < ret.cols_.size () - 1; i++) + { + SCM p = ret.cols_[i]->get_property ("line-break-permission"); + if (p == ly_symbol2scm ("force")) + ret.satisfies_constraints_ = false; + } -bool -Spring_description::sane_b () const -{ - return (hooke_f_ > 0) && !isinf (ideal_f_) && !isnan (ideal_f_); + return ret; } -Real -Spring_description::length (Real f) const +static int +compare_paper_column_rank (Grob *const &a, + Grob *const &b) { - if (!active_b_) - f = block_force_f_; - return ideal_f_ + f / hooke_f_ ; + return Paper_column::get_rank (a) - Paper_column::get_rank (b); }