From 9243e62f6ee1bdda0dc135bef206492720619a6c Mon Sep 17 00:00:00 2001 From: fred Date: Tue, 26 Mar 2002 22:26:06 +0000 Subject: [PATCH] lilypond-1.2.8 --- VERSION | 2 +- lily/break-algorithm.cc | 37 +++-- lily/include/line-spacer.hh | 28 ++-- lily/include/simple-spacer.hh | 72 +++++++++- lily/include/spring-spacer.hh | 5 +- lily/simple-spacer.cc | 252 +++++++++++++++++++++++++++++++++- lily/spring-spacer.cc | 44 ++++-- 7 files changed, 384 insertions(+), 56 deletions(-) diff --git a/VERSION b/VERSION index 061bf0a5ce..fd4e7556ab 100644 --- a/VERSION +++ b/VERSION @@ -1,7 +1,7 @@ PACKAGE_NAME=LilyPond MAJOR_VERSION=1 MINOR_VERSION=2 -PATCH_LEVEL=7 +PATCH_LEVEL=8 MY_PATCH_LEVEL= # use the above to send patches: MY_PATCH_LEVEL is always empty for a diff --git a/lily/break-algorithm.cc b/lily/break-algorithm.cc index 8291f81a23..6674d5bcf0 100644 --- a/lily/break-algorithm.cc +++ b/lily/break-algorithm.cc @@ -16,6 +16,9 @@ #include "paper-column.hh" #include "cpu-timer.hh" #include "command-request.hh" +#include "spring-spacer.hh" +#include "simple-spacer.hh" + String Col_stats::str () const @@ -76,7 +79,6 @@ Break_algorithm::find_breaks () const if (all[i]->breakable_b ()) retval.push (all[i]); - if (linelength <=0) while (retval.size () >2) retval.del (1); @@ -85,29 +87,34 @@ Break_algorithm::find_breaks () const } - - - Line_spacer* Break_algorithm::generate_spacing_problem (Line_of_cols curline, Interval line) const { - // ugh - Spring_spacer * sp= dynamic_cast ((*get_line_spacer) ()); + Real r = pscore_l_->paper_l_->get_var ("simple_spacing_solver"); + + Line_spacer * sp = 0; + if (r) + sp = new Simple_spacer; + else + sp = new Spring_spacer; + + sp->default_space_f_ = pscore_l_->paper_l_->get_var ("loose_column_distance"); - sp->paper_l_ = pscore_l_->paper_l_; - sp->add_column (curline[0], true, line[LEFT]); - for (int i=1; i< curline.size ()-1; i++) - sp->add_column (curline[i]); + sp->indent_f_ = line[LEFT]; - if (line.length () > 0) + /* + sort out how interfacing this should work; + */ + if (line.empty_b()) { - sp->add_column (curline.top (), true, line[RIGHT]); - sp->energy_normalisation_f_ = sqr (line.length ()); + sp->line_len_f_ = -1; } else - sp->add_column (curline.top ()); - + sp->line_len_f_ = line.length (); + + sp->add_columns (curline); sp->prepare (); + return sp; } diff --git a/lily/include/line-spacer.hh b/lily/include/line-spacer.hh index 07f4b67570..ee51de4770 100644 --- a/lily/include/line-spacer.hh +++ b/lily/include/line-spacer.hh @@ -25,8 +25,10 @@ class Line_spacer { public: - Paper_def * paper_l_; - Paper_def *paper_l() const; + Real indent_f_; + Real line_len_f_; + Real default_space_f_; + Line_spacer(); /** solve the spacing problem @@ -38,27 +40,13 @@ public: return a lower bound on the energy */ virtual void lower_bound_solution (Column_x_positions *) const=0; - - /** add a col to the problem. columns have to be added left to - right. The column contains info on it's minimum width. */ - virtual void add_column (Paper_column *, bool fixed=false, Real fixpos=0.0)=0; + /** - can the posed problem be solved? - - @pre - - prepare() was called - - */ - virtual bool check_constraints (Vector v) const=0; - - /** - generate a solution which can't fail - */ - virtual Vector default_solution() const=0; + Define the problem. LINELEN < 0 signifies natural width spacing. + */ - + virtual void add_columns (Link_array)=0; virtual void OK() const{} virtual void print() const{} diff --git a/lily/include/simple-spacer.hh b/lily/include/simple-spacer.hh index c122c64e2c..80f7a32904 100644 --- a/lily/include/simple-spacer.hh +++ b/lily/include/simple-spacer.hh @@ -10,8 +10,78 @@ #ifndef SIMPLE_SPACER_HH #define SIMPLE_SPACER_HH -class Simple_spacer { +#include "parray.hh" +#include "line-spacer.hh" + +struct Spring_description +{ + Real ideal_f_; + Real hooke_f_; + bool active_b_; + + Real block_force_f_; + + Real length (Real force) const; + Spring_description (); + Real energy_f (Real) const; +}; + +/** + A simple spacing constraint solver. The approach: + + Stretch the line uniformly until none of the constraints (rods) + block. It then is very wide. + + + 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. + + 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 + + + c4 c4 c4 c4 + veryveryverylongsyllable2 veryveryverylongsyllable2 + " "4 veryveryverylongsyllable2 syllable4 + + + Perhaps this is not a bad thing, because the 1st looks better anyway. */ +struct Simple_spacer: public Line_spacer +{ + Array springs_; + Real force_f_; + + Simple_spacer (); + + virtual void solve (Column_x_positions *) const; + virtual void lower_bound_solution (Column_x_positions *) const; + virtual void add_columns (Link_array); + + void my_solve_linelen (); + void my_solve_natural_len (); + Real active_springs_stiffness () const; + Real range_stiffness (int, int) const; + void add_rod (int l, int r, Real dist); + Real range_ideal_len (int l, int r)const; + Real active_blocking_force ()const; + Real configuration_length ()const; + void set_active_states (); + Real energy_f () const; + + bool active_b () const; }; #endif /* SIMPLE_SPACER_HH */ diff --git a/lily/include/spring-spacer.hh b/lily/include/spring-spacer.hh index ffab17f066..7359f6a1a6 100644 --- a/lily/include/spring-spacer.hh +++ b/lily/include/spring-spacer.hh @@ -51,7 +51,7 @@ private: Spring_spacer (Spring_spacer const&s); Cons *ideal_p_list_; Array cols_; - + Real indent_f_; /// the index of #c# in #cols# int col_id (Paper_column const *c) const; @@ -86,7 +86,8 @@ public: virtual ~Spring_spacer (); virtual void solve (Column_x_positions*) const; virtual void lower_bound_solution (Column_x_positions*) const; - virtual void add_column (Paper_column *, bool fixed=false, Real fixpos=0.0); + virtual void add_columns (Link_array); + void add_column (Paper_column *, bool, Real); virtual Vector default_solution() const; virtual bool check_constraints (Vector v) const; diff --git a/lily/simple-spacer.cc b/lily/simple-spacer.cc index 3616155b02..47eff23a03 100644 --- a/lily/simple-spacer.cc +++ b/lily/simple-spacer.cc @@ -1,10 +1,258 @@ /* - simple-spacer.cc -- implement Simple_spacer + simple-spacer.cc -- implement Simple_spacer source file of the GNU LilyPond music typesetter (c) 1999 Han-Wen Nienhuys + + TODO: + - add support for different stretch/shrink constants? + - Use force as a minimizing function, and use it to discourage mixes of + wide and tight lines. - */ +*/ + + +#include "simple-spacer.hh" +#include "paper-column.hh" +#include "spring.hh" +#include "rod.hh" +#include "warn.hh" +#include "column-x-positions.hh" + +Simple_spacer::Simple_spacer () +{ + force_f_ = 0.; +} + +void +Simple_spacer::add_rod (int l, int r, Real dist) +{ + Real c = range_stiffness (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; + + for (int i=l; i < r; i++) + springs_[i].block_force_f_ = block_force >? + springs_[i].block_force_f_ ; +} + +Real +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_; + return d; +} + +Real +Simple_spacer::range_stiffness (int l, int r) const +{ + Real den =0.0; + for (int i=l; i < r; i++) + den += 1 / springs_[i].hooke_f_; + + return 1 / den; +} + +Real +Simple_spacer::active_blocking_force () 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 +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; +} + +void +Simple_spacer::set_active_states () +{ + // safe, since + // force is only copied. + for (int i=0 ; i = force_f_) + springs_[i].active_b_ = false; +} + +Real +Simple_spacer::configuration_length () const +{ + Real l =0.; + for (int i=0; i < springs_.size (); i++) + l += springs_[i].length (force_f_); + + return l; +} + +Real +Spring_description::length (Real f) const +{ + if (!active_b_) + f = block_force_f_; + return ideal_f_ + f / hooke_f_ ; +} + +bool +Simple_spacer::active_b () const +{ + for (int i=0; i < springs_.size (); i++) + if (springs_[i].active_b_) + return true; + return false; +} + +void +Simple_spacer::my_solve_linelen () +{ + while (active_b ()) + { + force_f_ = active_blocking_force (); + Real conf = configuration_length (); + + if (conf < line_len_f_) + { + force_f_ += (line_len_f_ - conf) * active_springs_stiffness (); + break; + } + else + set_active_states (); + } +} + + +void +Simple_spacer::my_solve_natural_len () +{ + while (active_b ()) + { + force_f_ = active_blocking_force () >? 0.0; + + if (force_f_ < 1e-8) // ugh., + break; + + set_active_states (); + } +} + +void +Simple_spacer::add_columns (Link_array cols) +{ + for (int i=0; i < cols.size () - 1; i++) + { + Paper_column * c = cols [i]; + Column_spring *to_next = 0; + for (int j =0; !to_next && j < c->spring_arr_drul_[RIGHT].size( ); j++) + { + Column_spring &sp = c->spring_arr_drul_[RIGHT] [j]; + if (sp.other_l_ != cols[i+1]) + continue; + + to_next = &sp; + } + + Spring_description desc; + if (to_next) + { + desc.hooke_f_ = to_next->strength_f_; + desc.ideal_f_ = to_next->distance_f_; + } + else + { + desc.hooke_f_ = 1.0; + desc.ideal_f_ = default_space_f_; + } + desc.block_force_f_ = - desc.hooke_f_ * desc.ideal_f_; // block at distance 0 + springs_.push (desc); + } + + for (int i=0; i < cols.size () - 1; i++) + { + Array * rods = &cols [i]->minimal_dists_arr_drul_[RIGHT]; + for (int j =0; j < rods->size( ); j++) + { + int oi = cols.find_i (rods->elem (j).other_l_ ); + if (oi >= 0) + { + add_rod (i, oi, rods->elem (j).distance_f_); + } + } + } + + if (line_len_f_ < 0) + my_solve_natural_len (); + else + my_solve_linelen (); +} + +void +Simple_spacer::solve (Column_x_positions *positions) const +{ + positions->energy_f_ = energy_f (); // abs (force_f_); + positions->config_.push (indent_f_); + for (int i=0; i config_.push (positions->config_.top () + springs_[i].length (force_f_)); + } + + positions->satisfies_constraints_b_ = active_b (); +} + +void +Simple_spacer::lower_bound_solution (Column_x_positions * posns) const +{ + solve (posns); +} + + +Spring_description::Spring_description( ) +{ + ideal_f_ =0.0; + hooke_f_ =0.0; + active_b_ = true; + block_force_f_ = 0.0; +} + +Real +Spring_description::energy_f (Real force) const +{ + Real stretch = (force >? block_force_f_) / hooke_f_; + Real e = 0.5 * stretch * stretch * hooke_f_; + + /* + be harder to compress. + */ + if (stretch < 0) + e *= 4; + + return e; +} +Real +Simple_spacer::energy_f () const +{ + Real e =0.; + for (int i=0; i get_var ("loose_column_distance"); + Real d = default_space_f_; for (int i = cols_.size(); i--;) { if (! connected.equiv (fixed[0], i)) @@ -259,6 +259,8 @@ Spring_spacer::lower_bound_solution (Column_x_positions*positions) const Vector start (cols_.size()); start.fill (0.0); Vector solution_vec (lp.solve (start)); + for (int i=0; i < solution_vec.dim (); i++) + solution_vec(i) += indent_f_; DOUT << "Lower bound sol: " << solution_vec; positions->energy_f_ = calculate_energy_f (solution_vec); @@ -275,8 +277,6 @@ Spring_spacer::Spring_spacer () void Spring_spacer::solve (Column_x_positions*positions) const { - DOUT << "Spring_spacer::solve ()..."; - Vector solution_try; bool constraint_satisfaction = try_initial_solution_and_tell (solution_try); @@ -286,14 +286,19 @@ Spring_spacer::solve (Column_x_positions*positions) const make_matrices (lp.quad_,lp.lin_, lp.const_term_); make_constraints (lp); set_fixed_cols (lp); - + + Vector solution_vec (lp.solve (solution_try)); - + for (int i=0; i < solution_vec.dim (); i++) + solution_vec(i) += indent_f_; + + positions->satisfies_constraints_b_ = check_constraints (solution_vec); if (!positions->satisfies_constraints_b_) { - WARN << _ ("solution doesn't satisfy constraints") << '\n' ; + warning (_("solution doesn't satisfy constraints")); } + positions->energy_f_ = calculate_energy_f (solution_vec); positions->config_ = solution_vec; } @@ -302,11 +307,12 @@ Spring_spacer::solve (Column_x_positions*positions) const positions->set_stupid_solution (solution_try); } - DOUT << "Finished Spring_spacer::solve ()..."; } /** add one column to the problem. + + TODO: ugh merge with add_columns. */ void Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos) @@ -352,6 +358,22 @@ Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos) } +void +Spring_spacer::add_columns (Link_array cols) +{ + energy_normalisation_f_ = sqr (line_len_f_); + add_column (cols[0], true, 0.0); + for (int i=1; i< cols.size ()-1; i++) + add_column (cols[i],false,0.0); + + if (line_len_f_ > 0) + add_column (cols.top (), true, line_len_f_); + else + add_column (cols.top (), false, 0); +} + + + void Spring_spacer::print() const { @@ -403,14 +425,6 @@ Spring_spacer::prepare() print(); } -Line_spacer* -Spring_spacer::constructor() -{ - return new Spring_spacer; -} - - - Spring_spacer::~Spring_spacer() { -- 2.39.5