X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fsimple-spacer.cc;h=a37f040c86206122844051bc5fd343db864c16e3;hb=f1b93c0d52ef9229f8b58acc2ec8207ed50f5bee;hp=515d3c0eebff23c295ea893d0fdb541307bb28a1;hpb=9e32b4b17ebf295c2553bdd8d494a564ebc64af1;p=lilypond.git diff --git a/lily/simple-spacer.cc b/lily/simple-spacer.cc index 515d3c0eeb..a37f040c86 100644 --- a/lily/simple-spacer.cc +++ b/lily/simple-spacer.cc @@ -1,22 +1,19 @@ -/* +/* simple-spacer.cc -- implement Simple_spacer - + source file of the GNU LilyPond music typesetter - - (c) 1999--2004 Han-Wen Nienhuys + + (c) 1999--2005 Han-Wen Nienhuys TODO: - add support for different stretch/shrink constants? - */ -#include "simple-spacer.hh" - #include -#include - -#include // isinf +#include +#include "libc-extension.hh" // isinf +#include "simple-spacer.hh" #include "paper-column.hh" #include "spring.hh" #include "warn.hh" @@ -25,42 +22,39 @@ #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 () @@ -71,7 +65,7 @@ Simple_spacer::Simple_spacer () */ active_count_ = 0; force_ = 0.; - indent_ =0.0; + indent_ = 0.0; default_space_ = 20 PT; } @@ -80,44 +74,43 @@ 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++) + 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_ *= 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_ = force_ >? block_force; + force_ = max (force_, block_force); - for (int i=l; i < r; i++) - springs_[i].block_force_ = block_force >? - springs_[i].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++) + Real d = 0.; + for (int i = l; i < r; i++) d += springs_[i].ideal_; return d; } @@ -125,11 +118,11 @@ Simple_spacer::range_ideal_len (int l, int r) const 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].is_active_) - den += 1 / springs_[i].hooke_; + den += 1 * springs_[i].inverse_hooke_; } return 1 / den; @@ -138,29 +131,27 @@ 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++) + Real bf = -infinity_f; + for (int i = 0; i < springs_.size (); i++) if (springs_[i].is_active_) - { - bf = bf >? springs_[i].block_force_; - } + bf = max (bf, springs_[i].block_force_); return bf; } Real Simple_spacer::active_springs_stiffness () const { - Real stiff = range_stiffness (0, springs_.size ()); + 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++) + for (int i = 0; i < springs_.size (); i++) { if (springs_[i].block_force_ > max_block_force) { @@ -169,7 +160,7 @@ Simple_spacer::active_springs_stiffness () const } } - stiff = springs_[max_i].hooke_; + stiff = 1/springs_[max_i].inverse_hooke_; } return stiff; } @@ -178,20 +169,20 @@ void Simple_spacer::set_active_states () { /* float comparison is safe, since force is only copied. */ - for (int i=0 ; i = force_) { springs_[i].is_active_ = false; - active_count_ --; + active_count_--; } -} +} Real Simple_spacer::configuration_length () const { - Real l =0.; - for (int i=0; i < springs_.size (); i++) + Real l = 0.; + for (int i = 0; i < springs_.size (); i++) l += springs_[i].length (force_); return l; @@ -200,7 +191,7 @@ Simple_spacer::configuration_length () const bool Simple_spacer::is_active () const { - return active_count_; + return active_count_; } void @@ -221,131 +212,46 @@ Simple_spacer::my_solve_linelen () } } - void Simple_spacer::my_solve_natural_len () { Real line_len_force = 0.0; - + while (is_active ()) { - force_ = active_blocking_force () >? 0.0; + force_ = max (active_blocking_force (), 0.0); Real conf = configuration_length (); if (conf < line_len_) { line_len_force = force_ + (line_len_ - conf) - * active_springs_stiffness(); + * active_springs_stiffness (); } - + if (force_ < 1e-8) // ugh., break; - + set_active_states (); } force_ = line_len_force; } -LY_DEFINE(ly_solve_spring_rod_problem, "ly:solve-spring-rod-problem", - 4, 1, 0, (SCM springs, SCM rods, SCM length, SCM ragged), - "Solve a spring and rod problem for @var{count} objects, that " - "are connected by @var{count-1} springs, and an arbitrary number of rods " - "Springs have the format (ideal, hooke) and rods (idx1, idx2, distance) " - "@var{length} is a number, @var{ragged} a boolean " - "Return: a list containing the force (positive for stretching, " - "negative for compressing and #f for non-satisfied constraints) " - "followed by the @var{spring-count}+1 positions of the objects. " - ) -{ - int len = scm_ilength (springs); - if (len == 0) - return scm_list_2 (scm_from_double (0.0), scm_from_double (0.0)); - - SCM_ASSERT_TYPE (len >= 0, springs, SCM_ARG1, __FUNCTION__, "list of springs"); - SCM_ASSERT_TYPE (scm_ilength (rods) >= 0, rods, SCM_ARG2, __FUNCTION__, "list of rods"); - SCM_ASSERT_TYPE (scm_is_number (length) || length == SCM_BOOL_F, - length, SCM_ARG3, __FUNCTION__, "number or #f"); - - - bool is_ragged = ragged == SCM_BOOL_T; - Simple_spacer spacer; - for (SCM s = springs; scm_is_pair (s); s = scm_cdr (s)) - { - Real ideal = scm_to_double (scm_caar (s)); - Real hooke = scm_to_double (scm_cadar (s)); - - spacer.add_spring (ideal, hooke); - } - - for (SCM s = rods; scm_is_pair (s); s = scm_cdr (s)) - { - SCM entry = scm_car (s); - int l = scm_to_int (scm_car (entry)); - int r = scm_to_int (scm_cadr (entry)); - entry = scm_cddr (entry); - - Real distance = scm_to_double (scm_car (entry)); - spacer.add_rod (l, r, distance); - } - - spacer.line_len_ = scm_to_double (length); - - if (is_ragged) - spacer.my_solve_natural_len (); - else - spacer.my_solve_linelen (); - - Array posns; - posns.push (0.0); - for (int i = 0; i < spacer.springs_.size(); i++) - { - Real l = spacer.springs_[i].length ((is_ragged) ? 0.0 : spacer.force_); - posns.push (posns.top() + l); - } - - - - SCM force_return = SCM_BOOL_F; - if (!isinf (spacer.force_) - && (spacer.is_active () || is_ragged)) - { - force_return = scm_from_double (spacer.force_); - } - - if (is_ragged - && posns.top () > spacer.line_len_) - { - force_return = SCM_BOOL_F; - } - - SCM retval= SCM_EOL; - for (int i = posns.size(); i--;) - { - retval = scm_cons (scm_from_double (posns[i]), retval); - } - - retval = scm_cons (force_return, retval); - return retval; -} - - /****************************************************************/ Spring_description::Spring_description () { - ideal_ =0.0; - hooke_ =0.0; + ideal_ = 0.0; + inverse_hooke_ = 0.0; is_active_ = true; block_force_ = 0.0; } - bool Spring_description::is_sane () const { - return (hooke_ > 0) + return (inverse_hooke_ >= 0) && ideal_ > 0 && !isinf (ideal_) && !isnan (ideal_); } @@ -355,28 +261,25 @@ Spring_description::length (Real f) const { if (!is_active_) f = block_force_; - return ideal_ + f / hooke_ ; + return ideal_ + f * inverse_hooke_; } /****************************************************************/ - /* - TODO: should a add penalty for widely varying spring forces (caused by constraints, eg. - ===== - | | - o|o| x ##x - + . ===== + . | | + .o|o|x ##x + . 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) +Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged) { if (ragged) spacer_->my_solve_natural_len (); @@ -384,29 +287,29 @@ Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged) 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++) + for (int i = 0; i < spacer_->springs_.size (); i++) { - Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_); + 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 + we have l>= 0 here, up to rounding errors */ } /* 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) { - positions->satisfies_constraints_ = - positions->config_.top () < spacer_->line_len_ ; + positions->satisfies_constraints_ + = positions->config_.top () < spacer_->line_len_; } else positions->satisfies_constraints_ = spacer_->is_active (); @@ -416,123 +319,117 @@ Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged) /* Check if breaking constraints are met. - */ + */ bool break_satisfy = true; - int sz = positions->cols_.size (); - for (int i = sz; i--; ) + int sz = positions->cols_.size (); + for (int i = sz; i--;) { - SCM p = positions->cols_[i]->get_property ( "penalty"); + SCM p = positions->cols_[i]->get_property ("penalty"); if (scm_is_number (p)) { 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); + break_satisfy = break_satisfy && ! (i == 0 || i == sz -1); } - } - positions->satisfies_constraints_ = - positions->satisfies_constraints_ && break_satisfy; + positions->satisfies_constraints_ + = positions->satisfies_constraints_ && break_satisfy; } void -Simple_spacer::add_spring (Real ideal, Real hooke) +Simple_spacer::add_spring (Real ideal, Real inverse_hooke) { Spring_description desc; desc.ideal_ = ideal; - desc.hooke_ = hooke; + desc.inverse_hooke_ = inverse_hooke; if (!desc.is_sane ()) { - programming_error ("Insane spring found. Setting to unit spring."); + programming_error ("insane spring found, setting to unit"); - desc.hooke_ = 1.0; + desc.inverse_hooke_ = 1.0; desc.ideal_ = 1.0; } - - if (isinf (hooke)) - { - desc.is_active_ = false; - } + + if (!inverse_hooke) + desc.is_active_ = false; else { /* - desc.is_active_ ? + desc.is_active_ ? */ - desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0 - - active_count_ ++; + desc.block_force_ = -desc.ideal_ / desc.inverse_hooke_; + // block at distance 0 + + active_count_++; } springs_.push (desc); } static int -compare_paper_column_rank (Grob *const &a, - Grob *const &b) +compare_paper_column_rank (Grob *const &a, + Grob *const &b) { - return Paper_column::get_rank (a) - Paper_column::get_rank (b); + return Paper_column::get_rank (a) - Paper_column::get_rank (b); } 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); - } - + cols.clear (); + + for (int i = 0; i < icols.size (); i++) + if (scm_is_pair (icols[i]->get_object ("between-cols"))) + loose_cols_.push (icols[i]); + else + cols.push (icols[i]); + spaced_cols_ = cols; - for (int i=0; i < cols.size () - 1; i++) + for (int i = 0; i < cols.size () - 1; i++) { Spring_smob *spring = 0; - for (SCM s = cols[i]->get_property ("ideal-distances"); + for (SCM s = cols[i]->get_object ("ideal-distances"); !spring && scm_is_pair (s); s = scm_cdr (s)) { Spring_smob *sp = unsmob_spring (scm_car (s)); - - - if (sp->other_ == cols[i+1]) + + 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]) - )); + 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); + Real inverse_hooke = (spring) ? spring->inverse_strength_ : 1.0; + + spacer_->add_spring (ideal, inverse_hooke); } - - for (int i=0; i < cols.size () - 1; i++) + + 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) - { - spacer_->add_rod (i, oi, scm_to_double (scm_cdar (s))); - } + Grob *other = unsmob_grob (scm_caar (s)); + int j = binsearch_links (cols, other, &compare_paper_column_rank); + if (j >= 0 && cols[j] == other) + spacer_->add_rod (i, j, scm_to_double (scm_cdar (s))); } if (i - && !to_boolean (cols[i]->get_property ("allow-outside-line"))) + && to_boolean (cols[i]->get_property ("keep-inside-line"))) { Interval e = cols[i]->extent (cols[i], X_AXIS); - if (!e.is_empty()) + if (!e.is_empty ()) { - spacer_->add_rod (i, cols.size()-1, e[RIGHT]); + spacer_->add_rod (i, cols.size () - 1, e[RIGHT]); spacer_->add_rod (0, i, e[LEFT]); } } @@ -549,7 +446,6 @@ Simple_spacer_wrapper::~Simple_spacer_wrapper () delete spacer_; } - -Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const&) +Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const &) { }