X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fsimple-spacer.cc;h=5f28644ba6451acd847da9e2036f6f45b61282ec;hb=5bbfc22fce036b9b69df5e420de93e11da23c05e;hp=83e2978556a5f45887cd43bc3d9c407bc27d5fc8;hpb=3df9923cfb65cc141b68b7258c965da417cba6d7;p=lilypond.git diff --git a/lily/simple-spacer.cc b/lily/simple-spacer.cc index 83e2978556..e21cbbf0ef 100644 --- a/lily/simple-spacer.cc +++ b/lily/simple-spacer.cc @@ -1,12 +1,23 @@ /* - simple-spacer.cc -- implement Simple_spacer + This file is part of LilyPond, the GNU music typesetter. - source file of the GNU LilyPond music typesetter - - (c) 1999--2006 Han-Wen Nienhuys + Copyright (C) 1999--2014 Han-Wen Nienhuys TODO: - add support for different stretch/shrink constants? + + LilyPond is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + LilyPond is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with LilyPond. If not, see . */ #include @@ -14,7 +25,7 @@ #include "column-x-positions.hh" #include "dimensions.hh" #include "international.hh" -#include "libc-extension.hh" // isinf +#include "libc-extension.hh" // isinf #include "paper-column.hh" #include "simple-spacer.hh" #include "spaceable-grob.hh" @@ -59,18 +70,20 @@ Simple_spacer::Simple_spacer () { - force_ = 0.; + line_len_ = 0.0; + force_ = 0.0; fits_ = true; + ragged_ = true; } Real -Simple_spacer::force () +Simple_spacer::force () const { return force_; } bool -Simple_spacer::fits () +Simple_spacer::fits () const { return fits_; } @@ -78,9 +91,12 @@ Simple_spacer::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 c = range_stiffness (l, r, dist > d); Real block_stretch = dist - d; + + if (isinf (c) && block_stretch == 0) /* take care of the 0*infinity_f case */ + return 0; return c * block_stretch; } @@ -99,14 +115,19 @@ Simple_spacer::add_rod (int l, int r, Real 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; + for (int i = l; i < r; i++) + { + if (spring_dist) + springs_[i].set_distance (springs_[i].distance () * dist / spring_dist); + else + springs_[i].set_distance (dist / (r - l)); + } return; } force_ = max (force_, block_force); for (int i = l; i < r; i++) - springs_[i].block_force_ = max (block_force, springs_[i].block_force_); + springs_[i].set_blocking_force (max (block_force, springs_[i].blocking_force ())); } Real @@ -114,60 +135,65 @@ Simple_spacer::range_ideal_len (int l, int r) const { Real d = 0.; for (int i = l; i < r; i++) - d += springs_[i].ideal_; + d += springs_[i].distance (); return d; } Real -Simple_spacer::range_stiffness (int l, int r) const +Simple_spacer::range_stiffness (int l, int r, bool stretch) const { Real den = 0.0; for (int i = l; i < r; i++) - den += springs_[i].inverse_hooke_; + den += stretch ? springs_[i].inverse_stretch_strength () + : springs_[i].inverse_compress_strength (); return 1 / den; } Real -Simple_spacer::configuration_length () const +Simple_spacer::configuration_length (Real force) const { Real l = 0.; for (vsize i = 0; i < springs_.size (); i++) - l += springs_[i].length (force_); + l += springs_[i].length (force); return l; } +void +Simple_spacer::set_force (Real force) +{ + force_ = force; +} + void Simple_spacer::solve (Real line_len, bool ragged) { - Real conf = configuration_length (); + Real conf = configuration_length (force_); 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_) + if (conf < line_len_) force_ = expand_line (); else if (conf > line_len_) force_ = compress_line (); + + if (ragged && force_ < 0) + fits_ = false; } Real Simple_spacer::expand_line () { double inv_hooke = 0; - double cur_len = configuration_length (); + double cur_len = configuration_length (force_); fits_ = true; - for (vsize i=0; i < springs_.size (); i++) - inv_hooke += springs_[i].inverse_hooke_; + for (vsize i = 0; i < springs_.size (); i++) + inv_hooke += springs_[i].inverse_stretch_strength (); + + if (inv_hooke == 0.0) /* avoid division by zero. If springs are infinitely stiff */ + inv_hooke = 1e-6; /* then report a very large stretching force */ assert (cur_len <= line_len_); return (line_len_ - cur_len) / inv_hooke + force_; @@ -176,32 +202,59 @@ Simple_spacer::expand_line () Real Simple_spacer::compress_line () { - double inv_hooke = 0; - double cur_len = configuration_length (); + double cur_len = configuration_length (force_); double cur_force = force_; + bool compressed = false; + + /* just because we are in compress_line () doesn't mean that the line + will actually be compressed (as in, a negative force) because + we start out with a stretched line. Here, we check whether we + will be compressed or stretched (so we know which spring constant to use) */ + if (configuration_length (0.0) > line_len_) + { + cur_force = 0.0; + cur_len = configuration_length (0.0); + compressed = true; + } 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++) + vector sorted_springs = springs_; + sort (sorted_springs.begin (), sorted_springs.end (), greater ()); + + /* inv_hooke is the total flexibility of currently-active springs */ + double inv_hooke = 0; + vsize i = sorted_springs.size (); + for (; i && sorted_springs[i - 1].blocking_force () < cur_force; i--) + inv_hooke += compressed + ? sorted_springs[i - 1].inverse_compress_strength () + : sorted_springs[i - 1].inverse_stretch_strength (); + /* i now indexes the first active spring, so */ + for (; i < sorted_springs.size (); i++) { - Spring_description sp = sorted_springs[i]; + Spring sp = sorted_springs[i]; + + if (isinf (sp.blocking_force ())) + break; - assert (sp.block_force_ <= cur_force); - if (isinf (sp.block_force_)) - break; + double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke; + if (cur_len - block_dist < line_len_) + { + cur_force += (line_len_ - cur_len) / inv_hooke; + cur_len = line_len_; + + /* + Paranoia check. + */ + assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6); + return cur_force; + } - 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_; + inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength (); + cur_force = sp.blocking_force (); } fits_ = false; @@ -209,24 +262,10 @@ Simple_spacer::compress_line () } void -Simple_spacer::add_spring (Real ideal, Real inverse_hooke) +Simple_spacer::add_spring (Spring const &sp) { - Spring_description desc; - - desc.ideal_ = ideal; - desc.inverse_hooke_ = inverse_hooke; - if (!desc.is_sane ()) - { - programming_error ("insane spring found, setting to unit"); - - 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); + force_ = max (force_, sp.blocking_force ()); + springs_.push_back (sp); } vector @@ -236,79 +275,64 @@ Simple_spacer::spring_positions () const ret.push_back (0.); for (vsize i = 0; i < springs_.size (); i++) - ret.push_back (ret.back () + springs_[i].length (ragged_ ? 0.0 : force_)); + ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_)); return ret; } -/****************************************************************/ - -Spring_description::Spring_description () -{ - ideal_ = 0.0; - inverse_hooke_ = 0.0; - block_force_ = 0.0; -} - -bool -Spring_description::is_sane () const -{ - return (inverse_hooke_ >= 0) - && ideal_ > 0 - && !isinf (ideal_) && !isnan (ideal_); -} - Real -Spring_description::length (Real f) const +Simple_spacer::force_penalty (bool ragged) const { - return ideal_ + max (f, block_force_) * inverse_hooke_; + /* If we are ragged-right, we don't want to penalise according to the force, + but according to the amount of whitespace that is present after the end + of the line. */ + if (ragged) + return max (0.0, line_len_ - configuration_length (0.0)); + + /* Use a convex compression penalty. */ + Real f = force_; + return f - (f < 0 ? f * f * f * f * 2 : 0); } /****************************************************************/ -/* - TODO: should a add penalty for widely varying spring forces (caused - by constraints, eg. - - - . ===== - . | | - .o|o|x ##x - . - - The ## forces the notes apart; we shouldn't allow the O's to touch - this closely. -*/ - -struct Rod_desc +struct Rod_description { vsize r_; Real dist_; - bool operator< (const Rod_desc r) + bool operator < (const Rod_description r) { return r_ < r.r_; } - Rod_desc () {} - Rod_desc (vsize r, Real d) + Rod_description () + { + r_ = 0; + dist_ = 0; + } + + Rod_description (vsize r, Real d) { r_ = r; dist_ = d; } }; -struct Column_desc +struct Column_description { - 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_; + vector rods_; + vector end_rods_; /* use these if they end at the last column of the line */ + Spring spring_; + Spring end_spring_; + + SCM break_permission_; Interval keep_inside_line_; -}; -static int compare_paper_column_rank (Grob *const &a, Grob *const &b); + Column_description () + { + break_permission_ = SCM_EOL; + } +}; static bool is_loose (Grob *g) @@ -316,197 +340,182 @@ is_loose (Grob *g) return (scm_is_pair (g->get_object ("between-cols"))); } -static Grob* +static Grob * maybe_find_prebroken_piece (Grob *g, Direction d) { - Grob *ret = dynamic_cast (g)->find_prebroken_piece (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) +static Grob * +next_spaceable_column (vector const &list, vsize starting) { - for (vsize i = starting+1; i < list.size (); i++) + 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]) - && !Item::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) +static Column_description +get_column_description (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; + Column_description description; 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_); + description.spring_ = Spaceable_grob::get_spring (col, next_col); + + if (col_index + 1 < cols.size ()) + { + Grob *end_col = dynamic_cast (cols[col_index + 1])->find_prebroken_piece (LEFT); + if (end_col) + description.end_spring_ = Spaceable_grob::get_spring (col, end_col); + } 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); + Grob *other = Grob::unsmob (scm_caar (s)); + vsize j = binary_search (cols, other, Paper_column::less_than, col_index); if (j != VPOS) - { - 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 (cols[j] == other) + description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s)))); + else /* it must end at the LEFT prebroken_piece */ + /* see Spanner::set_spacing_rods for more comments on how + to deal with situations where we don't know if we're + ending yet on the left prebroken piece */ + description.end_rods_.push_back (Rod_description (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; + description.keep_inside_line_ = col->extent (col, X_AXIS); + + description.break_permission_ = col->get_property ("line-break-permission"); + return description; } vector -get_line_forces (vector const &icols, vector breaks, - Real line_len, Real indent, bool ragged) +get_line_forces (vector const &columns, + Real line_len, Real indent, bool ragged) { + vector breaks; 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++) + vector non_loose; + vector cols; + SCM force_break = ly_symbol2scm ("force"); + + for (vsize i = 0; i < columns.size (); i++) + if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i])) + non_loose.push_back (columns[i]); + + breaks.clear (); + breaks.push_back (0); + cols.push_back (Column_description ()); + for (vsize i = 1; i + 1 < non_loose.size (); i++) { - if (b < breaks.size () && breaks[b] == i) - { - breaks[b] = cols.size (); - b++; - } - if (!is_loose (icols[i])) - cols.push_back (get_column_desc (icols, i, false)); + if (Paper_column::is_breakable (non_loose[i])) + breaks.push_back (cols.size ()); + + cols.push_back (get_column_description (non_loose, i, false)); } - breaks.back () = cols.size () - 1; + breaks.push_back (cols.size ()); + force.resize (breaks.size () * breaks.size (), infinity_f); - for (vsize b = 0; b < breaks.size () - 1; b++) + for (vsize b = 0; b + 1 < breaks.size (); b++) { - cols[breaks[b]] = get_column_desc (icols, breaks[b], true); + cols[breaks[b]] = get_column_description (non_loose, breaks[b], true); vsize st = breaks[b]; - for (vsize c = b+1; c < breaks.size (); c++) - { - 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++) - { - 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; - } - } + for (vsize c = b + 1; c < breaks.size (); c++) + { + vsize end = breaks[c]; + Simple_spacer spacer; + + for (vsize i = breaks[b]; i < end - 1; i++) + spacer.add_spring (cols[i].spring_); + spacer.add_spring (cols[end - 1].end_spring_); + + for (vsize i = breaks[b]; i < end; i++) + { + 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_penalty (ragged); + + if (!spacer.fits ()) + { + if (c == b + 1) + force[b * breaks.size () + c] = -200000; + else + force[b * breaks.size () + c] = infinity_f; + break; + } + if (end < cols.size () && cols[end].break_permission_ == force_break) + break; + } } return force; } Column_x_positions -get_line_configuration (vectorconst &columns, - Real line_len, - Real indent, - bool ragged) +get_line_configuration (vector const &columns, + Real line_len, + Real indent, + bool ragged) { - vector cols; + vector 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++) + ret.cols_.push_back (dynamic_cast (columns[0])->find_prebroken_piece (RIGHT)); + for (vsize i = 1; i + 1 < columns.size (); i++) { if (is_loose (columns[i])) - ret.loose_cols_.push_back (columns[i]); + ret.loose_cols_.push_back (columns[i]); else - ret.cols_.push_back (columns[i]); + ret.cols_.push_back (columns[i]); } - ret.cols_.push_back (dynamic_cast (columns.back ())->find_prebroken_piece (LEFT)); - - cols.resize (ret.cols_.size () - 1); + ret.cols_.push_back (dynamic_cast (columns.back ())->find_prebroken_piece (LEFT)); /* 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++) + the end_XXX_ fields of our column_description */ + for (vsize i = 0; i + 1 < ret.cols_.size (); i++) { - cols[i] = get_column_desc (ret.cols_, i, i == 0); - spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_); + cols.push_back (get_column_description (ret.cols_, i, i == 0)); + spacer.add_spring (cols[i].spring_); } 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_); + { + for (vsize r = 0; r < cols[i].rods_.size (); r++) + spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_); + + if (!cols[i].keep_inside_line_.is_empty ()) + { + spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]); + spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]); + } + } spacer.solve (line_len, ragged); - ret.force_ = spacer.force (); + ret.force_ = spacer.force_penalty (ragged); - /* - 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; @@ -516,25 +525,31 @@ get_line_configuration (vectorconst &columns, /* Check if breaking constraints are met. */ - int sz = ret.cols_.size (); - for (int i = sz; i--;) + for (vsize i = 1; i + 1 < ret.cols_.size (); i++) { - SCM p = ret.cols_[i]->get_property ("penalty"); - if (scm_is_number (p)) - { - if (scm_to_double (p) < -9999) - ret.satisfies_constraints_ = ret.satisfies_constraints_ && (i == 0 || i == sz -1); - if (scm_to_double (p) > 9999) - ret.satisfies_constraints_ = ret.satisfies_constraints_ && ! (i == 0 || i == sz -1); - } + SCM p = ret.cols_[i]->get_property ("line-break-permission"); + if (p == ly_symbol2scm ("force")) + ret.satisfies_constraints_ = false; } return ret; } -static int -compare_paper_column_rank (Grob *const &a, - Grob *const &b) +#include "ly-smobs.icc" + +IMPLEMENT_SIMPLE_SMOBS (Simple_spacer); +IMPLEMENT_DEFAULT_EQUAL_P (Simple_spacer); + +SCM +Simple_spacer::mark_smob (SCM /* x */) +{ + return SCM_EOL; +} + +int +Simple_spacer::print_smob (SCM /* x */, SCM p, scm_print_state *) { - return Paper_column::get_rank (a) - Paper_column::get_rank (b); + scm_puts ("#", p); + return 1; } +