From 293cd1987c74965e29e236cb5a72b2c6f7fc88a8 Mon Sep 17 00:00:00 2001 From: fred Date: Sun, 24 Mar 2002 19:54:23 +0000 Subject: [PATCH] lilypond-0.1.9 --- lily/spring-spacer.cc | 481 ++++++++++++++++++++++++------------------ 1 file changed, 281 insertions(+), 200 deletions(-) diff --git a/lily/spring-spacer.cc b/lily/spring-spacer.cc index d060529d63..64059065dd 100644 --- a/lily/spring-spacer.cc +++ b/lily/spring-spacer.cc @@ -25,13 +25,13 @@ Vector Spring_spacer::default_solution()const { - return try_initial_solution() ; + return try_initial_solution() ; } Score_column* Spring_spacer::scol_l (int i) { - return (Score_column*)cols[i].pcol_l_; + return (Score_column*)cols[i].pcol_l_; } const Real COLFUDGE=1e-3; @@ -40,10 +40,10 @@ template class P; // ugh. bool Spring_spacer::contains (PCol const *w) { - for (int i=0; i< cols.size(); i++) + for (int i=0; i< cols.size(); i++) if (cols[i].pcol_l_ == w) return true; - return false; + return false; } @@ -51,9 +51,9 @@ void Spring_spacer::OK() const { #ifndef NDEBUG - for (int i = 1; i < cols.size(); i++) + for (int i = 1; i < cols.size(); i++) assert (cols[i].rank_i_ > cols[i-1].rank_i_); - for (int i = 1; i < loose_col_arr_.size(); i++) + for (int i = 1; i < loose_col_arr_.size(); i++) assert (loose_col_arr_[i].rank_i_ > loose_col_arr_[i-1].rank_i_); #endif } @@ -64,24 +64,27 @@ Spring_spacer::OK() const void Spring_spacer::handle_loose_cols() { - Union_find connected (cols.size()); - Array fixed; - for (PCursor i (ideal_p_list_.top()); i.ok (); i++){ + Union_find connected (cols.size()); + Array fixed; + for (PCursor i (ideal_p_list_.top()); i.ok (); i++) + { connected.connect (i->left_i_,i->right_i_); } - for (int i = 0; i < cols.size(); i++) + for (int i = 0; i < cols.size(); i++) if (cols[i].fixed()) fixed.push (i); - for (int i=1; i < fixed.size(); i++) + for (int i=1; i < fixed.size(); i++) connected.connect (fixed[i-1], fixed[i]); - for (int i = cols.size(); i--;) { - if (! connected.equiv (fixed[0], i)) { + for (int i = cols.size(); i--;) + { + if (! connected.equiv (fixed[0], i)) + { warning ("unconnected column: " + String (i)); loosen_column (i); - } + } } - OK(); + OK(); } @@ -92,30 +95,36 @@ Spring_spacer::handle_loose_cols() void Spring_spacer::position_loose_cols (Vector &sol_vec)const { - if (!loose_col_arr_.size()) + if (!loose_col_arr_.size()) return ; - assert (sol_vec.dim()); - Array fix_b_arr; - fix_b_arr.set_size (cols.size() + loose_col_arr_.size ()); - Real utter_right_f=-infinity_f; - Real utter_left_f =infinity_f; - for (int i=0; i < loose_col_arr_.size(); i++) { + assert (sol_vec.dim()); + Array fix_b_arr; + fix_b_arr.set_size (cols.size() + loose_col_arr_.size ()); + Real utter_right_f=-infinity_f; + Real utter_left_f =infinity_f; + for (int i=0; i < loose_col_arr_.size(); i++) + { fix_b_arr[loose_col_arr_[i].rank_i_] = false; } - for (int i=0; i < cols.size(); i++) { + for (int i=0; i < cols.size(); i++) + { int r= cols[i].rank_i_; fix_b_arr[r] = true; utter_right_f = utter_right_f >? sol_vec (i); utter_left_f = utter_left_f 0) ?sol_vec (j-1) : utter_left_f; Real right_pos_f = @@ -130,18 +139,19 @@ Spring_spacer::position_loose_cols (Vector &sol_vec)const v (i) = (r - left_rank)*left_pos_f/ d_r + (right_rank - r) *right_pos_f /d_r; - } + } } - sol_vec = v; + sol_vec = v; } bool Spring_spacer::check_constraints (Vector v) const { - int dim=v.dim(); - assert (dim == cols.size()); - - for (int i=0; i < dim; i++) { + int dim=v.dim(); + assert (dim == cols.size()); + + for (int i=0; i < dim; i++) + { if (cols[i].fixed()&& abs (cols[i].fixed_position() - v (i)) > COLFUDGE) @@ -162,35 +172,41 @@ Spring_spacer::check_constraints (Vector v) const return false; } - return true; + return true; } bool Spring_spacer::check_feasible() const { - Vector sol (try_initial_solution()); - return check_constraints (sol); + Vector sol (try_initial_solution()); + return check_constraints (sol); } /// generate a solution which obeys the min distances and fixed positions Vector Spring_spacer::try_initial_solution() const { - int dim=cols.size(); - Vector initsol (dim); - for (int i=0; i < dim; i++) { - if (cols[i].fixed()) { + int dim=cols.size(); + Vector initsol (dim); + for (int i=0; i < dim; i++) + { + if (cols[i].fixed()) + { initsol (i)=cols[i].fixed_position(); - if (i > 0) { + if (i > 0) + { Real r =initsol (i-1) + cols[i-1].minright(); - if (initsol (i) < r) { + if (initsol (i) < r) + { warning ("overriding fixed position"); initsol (i) =r; - } - } + } + } - } else { + } + else + { Real mindist=cols[i-1].minright() +cols[i].minleft(); if (mindist < 0.0) @@ -199,7 +215,7 @@ Spring_spacer::try_initial_solution() const } } - return initsol; + return initsol; } @@ -207,20 +223,21 @@ Spring_spacer::try_initial_solution() const Vector Spring_spacer::find_initial_solution() const { - Vector v (try_initial_solution()); - assert (check_constraints (v)); - return v; + Vector v (try_initial_solution()); + assert (check_constraints (v)); + return v; } // generate the matrices void Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const { - quad.fill (0); - lin.fill (0); - c = 0; - - for (PCursor i (ideal_p_list_.top()); i.ok (); i++) { + quad.fill (0); + lin.fill (0); + c = 0; + + for (PCursor i (ideal_p_list_.top()); i.ok (); i++) + { int l = i->left_i_; int r = i->right_i_; @@ -239,116 +256,122 @@ Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const void Spring_spacer::set_fixed_cols (Mixed_qp &qp)const { - for (int j=0; j < cols.size(); j++) + for (int j=0; j < cols.size(); j++) if (cols[j].fixed()) qp.add_fixed_var (j,cols[j].fixed_position()); - + } // put the constraints into the LP problem void Spring_spacer::make_constraints (Mixed_qp& lp) const { - int dim=cols.size(); - for (int j=0; j < dim; j++) { + int dim=cols.size(); + for (int j=0; j < dim; j++) + { Colinfo c=cols[j]; - if (j > 0){ + if (j > 0) + { Vector c1(dim); c1(j)=1.0 ; c1(j-1)=-1.0 ; lp.add_inequality_cons (c1, cols[j-1].minright() + cols[j].minleft()); - } + } } } void Spring_spacer::lower_bound_solution (Col_hpositions*positions)const { - Mixed_qp lp (cols.size()); - make_matrices (lp.quad,lp.lin, lp.const_term); - set_fixed_cols (lp); + Mixed_qp lp (cols.size()); + make_matrices (lp.quad,lp.lin, lp.const_term); + set_fixed_cols (lp); - Vector start (cols.size()); - start.fill (0.0); - Vector solution_vec (lp.solve (start)); + Vector start (cols.size()); + start.fill (0.0); + Vector solution_vec (lp.solve (start)); - positions->energy_f_ = lp.eval (solution_vec); - positions->config = solution_vec; - positions->satisfies_constraints_b_ = check_constraints (solution_vec); + positions->energy_f_ = lp.eval (solution_vec); + positions->config = solution_vec; + positions->satisfies_constraints_b_ = check_constraints (solution_vec); } void Spring_spacer::solve (Col_hpositions*positions) const { - assert (check_feasible()); + assert (check_feasible()); - Mixed_qp lp (cols.size()); - make_matrices (lp.quad,lp.lin, lp.const_term); - make_constraints (lp); - set_fixed_cols (lp); - Vector start=find_initial_solution(); - Vector solution_vec (lp.solve (start)); + Mixed_qp lp (cols.size()); + make_matrices (lp.quad,lp.lin, lp.const_term); + make_constraints (lp); + set_fixed_cols (lp); + Vector start=find_initial_solution(); + Vector solution_vec (lp.solve (start)); - positions->satisfies_constraints_b_ = check_constraints (solution_vec); - if (!positions->satisfies_constraints_b_) { + positions->satisfies_constraints_b_ = check_constraints (solution_vec); + if (!positions->satisfies_constraints_b_) + { WARN << "solution doesn't satisfy constraints.\n" ; } - position_loose_cols (solution_vec); - positions->energy_f_ = lp.eval (solution_vec); - positions->config = solution_vec; - positions->error_col_l_arr_ = error_pcol_l_arr(); - + position_loose_cols (solution_vec); + positions->energy_f_ = lp.eval (solution_vec); + positions->config = solution_vec; + positions->error_col_l_arr_ = error_pcol_l_arr(); + } /** - add one column to the problem. + add one column to the problem. */ void Spring_spacer::add_column (PCol *col, bool fixed, Real fixpos) { - Colinfo c (col,(fixed)? &fixpos : 0); - if (cols.size()) + Colinfo c (col,(fixed)? &fixpos : 0); + if (cols.size()) c.rank_i_ = cols.top().rank_i_+1; - else + else c.rank_i_ = 0; - cols.push (c); + cols.push (c); } Line_of_cols Spring_spacer::error_pcol_l_arr()const { - Array retval; - for (int i=0; i< cols.size(); i++) + Array retval; + for (int i=0; i< cols.size(); i++) if (cols[i].ugh_b_) retval.push (cols[i].pcol_l_); - for (int i=0; i < loose_col_arr_.size(); i++) { + for (int i=0; i < loose_col_arr_.size(); i++) + { retval.push (loose_col_arr_[i].pcol_l_); } - return retval; + return retval; } void Spring_spacer::loosen_column (int i) { - Colinfo c=cols.get (i); - for (PCursor j (ideal_p_list_.top()); j.ok (); j++){ + Colinfo c=cols.get (i); + for (PCursor j (ideal_p_list_.top()); j.ok (); j++) + { if (j->left_i_ == i|| j->right_i_ == i) j.del(); else j++; } - c.ugh_b_ = true; - - int j=0; - for (; j < loose_col_arr_.size(); j++) { + c.ugh_b_ = true; + + int j=0; + for (; j < loose_col_arr_.size(); j++) + { if (loose_col_arr_[j].rank_i_ > c.rank_i_) break; } - loose_col_arr_.insert (c,j); + loose_col_arr_.insert (c,j); } @@ -356,11 +379,13 @@ void Spring_spacer::print() const { #ifndef NPRINT - for (int i=0; i < cols.size(); i++) { + for (int i=0; i < cols.size(); i++) + { DOUT << "col " << i<<' '; cols[i].print(); } - for (PCursor i (ideal_p_list_.top()); i.ok (); i++){ + for (PCursor i (ideal_p_list_.top()); i.ok (); i++) + { i->print(); } #endif @@ -370,13 +395,92 @@ Spring_spacer::print() const void Spring_spacer::connect (int i, int j, Real d, Real h) { - Idealspacing * s = new Idealspacing; - s->left_i_ = i; - s->right_i_ = j; - s->space_f_ = d; - s->hooke_f_ = h; + assert( d >= 0 && d <= 100 CM); + assert( h >=0); + + Idealspacing * s = new Idealspacing; + s->left_i_ = i; + s->right_i_ = j; + s->space_f_ = d; + s->hooke_f_ = h; + + ideal_p_list_.bottom().add (s); +} + + + + +void +Spring_spacer::prepare() +{ + calc_idealspacing(); + handle_loose_cols(); + print(); +} + +Line_spacer* +Spring_spacer::constructor() +{ + return new Spring_spacer; +} + + + +/** + get the shortest_playing running note at a time. */ +void +Spring_spacer::get_ruling_durations(Array &shortest_playing_arr, + Array &context_shortest_arr) +{ + for (int i=0; i < cols.size(); i++) + scol_l (i)->preprocess(); + + int start_context_i=0; + Moment context_shortest = infinity_mom; + context_shortest_arr.set_size(cols.size()); + + for (int i=0; i < cols.size(); i++) + { + Moment now = scol_l (i)->when(); + Moment shortest_playing = infinity_mom; + + if (scol_l(i)->breakable_b()) + { + for (int ji=i; ji >= start_context_i; ji--) + context_shortest_arr[ji] = context_shortest; + start_context_i = i; + context_shortest = infinity_mom; + } + if (scol_l(i)->durations.size()) + { + context_shortest = context_shortest durations[0]; + } + // ji was j, but triggered ICE + for (int ji=i+1; ji --; ) + { + if (scol_l(ji)->durations.size() && + now - scol_l(ji)->when() >= shortest_playing) + break; + + for (int k = scol_l (ji)->durations.size(); + k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now; + ) + { + shortest_playing = shortest_playing durations[k]; + } + } + shortest_playing_arr.push(shortest_playing); + } - ideal_p_list_.bottom().add (s); +#ifndef NPRINT + DOUT << "shortest_playing/:[ "; + for (int i=0; i < shortest_playing_arr.size(); i++) + { + DOUT << shortest_playing_arr[i] << " "; + DOUT << context_shortest_arr[i] << ", "; + } + DOUT << "]\n"; +#endif } /** @@ -397,109 +501,86 @@ Spring_spacer::connect (int i, int j, Real d, Real h) void Spring_spacer::calc_idealspacing() { - - for (int i=0; i < cols.size(); i++) - scol_l (i)->preprocess(); - - /* get the shortest running note at a time. */ - Array shortest_arr; - for (int i=0; i < cols.size(); i++) { - Moment now = scol_l (i)->when(); - Moment shortest = infinity_mom; - // ji was j, but triggered ICE - for (int ji=i+1; ji --; ) { - if (scol_l(ji)->durations.size() && - now - scol_l(ji)->when() >= shortest) - break; - - for (int k = scol_l (ji)->durations.size(); - k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now; - ) - { - shortest = shortest durations[k]; - } - } - shortest_arr.push(shortest); - } - -#ifndef NPRINT - DOUT << "shortest:[ "; - for (int i=0; i < shortest_arr.size(); i++) - DOUT << shortest_arr[i] << " "; - DOUT << "]\n"; -#endif + Array shortest_playing_arr; + Array context_shortest_arr; + get_ruling_durations(shortest_playing_arr, context_shortest_arr); + - Array ideal_arr_; - Array hooke_arr_; - for (int i=0; i < cols.size(); i++){ - ideal_arr_.push (-1.0); - hooke_arr_.push (1.0); - } + Array ideal_arr_; + Array hooke_arr_; + for (int i=0; i < cols.size(); i++){ + ideal_arr_.push (-1.0); + hooke_arr_.push (1.0); + } - for (int i=0; i < cols.size(); i++) { - if ( !scol_l (i)->musical_b()) { - Real symbol_distance =cols[i].minright() + 2 PT; - Real durational_distance = 0; - - if (i+1 < cols.size()) { - Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ; - /* - ugh should use shortest distance - */ - if (delta_t) - durational_distance = paper_l()->duration_to_dist (delta_t) ; - symbol_distance += cols[i+1].minleft(); + for (int i=0; i < cols.size(); i++) + { + if ( !scol_l (i)->musical_b()) + { + Real symbol_distance =cols[i].minright() + 2 PT; + Real durational_distance = 0; + + if (i+1 < cols.size()) + { + Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ; + + Real k= paper_l()->arithmetic_constant(context_shortest_arr[i]); + /* + ugh should use shortest_playing distance + */ + if (delta_t) + durational_distance = paper_l()->duration_to_dist (delta_t,k); + symbol_distance += cols[i+1].minleft(); } - ideal_arr_[i] = symbol_distance >? durational_distance; - hooke_arr_[i] = 2.0; + ideal_arr_[i] = symbol_distance >? durational_distance; + hooke_arr_[i] = 2.0; } } - for (int i=0; i < cols.size(); i++) { - if (scol_l (i)->musical_b()) { - Moment shortest_len = shortest_arr[i]; - if ( ! shortest_len) { - warning ("Can't find a ruling note at " - +String (scol_l (i)->when())); - shortest_len = 1; + for (int i=0; i < cols.size(); i++) + { + if (scol_l (i)->musical_b()) + { + Moment shortest_playing_len = shortest_playing_arr[i]; + Moment context_shortest = context_shortest_arr[i]; + if ( ! shortest_playing_len) + { + warning ("Can't find a ruling note at " + +String (scol_l (i)->when())); + shortest_playing_len = 1; + } + if ( ! context_shortest ) + { + warning("No minimum in measure at " + + String (scol_l (i)->when())); + context_shortest = 1; } - Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when (); - Real dist = paper_l()->duration_to_dist (shortest_len); - dist *= delta_t / shortest_len; - if (!scol_l (i+1)->musical_b()) { - - Real minimum_dist = cols[i+1].minleft() + 2 PT + cols[i].minright () ; - if (ideal_arr_[i+1] + minimum_dist < dist) { - ideal_arr_[i] = dist - ideal_arr_[i+1]; - // hooke_arr_[i+1] =1.0; + Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when (); + Real k= paper_l()->arithmetic_constant(context_shortest); + Real dist = paper_l()->duration_to_dist (shortest_playing_len, k); + dist *= delta_t / shortest_playing_len; + + /* all sorts of ugliness to avoid running into bars/clefs, but not taking + extra space if this is not needed */ + if (!scol_l (i+1)->musical_b()) + { + Real minimum_dist = cols[i+1].minleft() + 2 PT + cols[i].minright () ; + if (ideal_arr_[i+1] + minimum_dist < dist) + { + ideal_arr_[i] = dist - ideal_arr_[i+1]; + // hooke_arr_[i+1] =1.0; } else { - ideal_arr_[i] = minimum_dist; + ideal_arr_[i] = minimum_dist; } - + } else - ideal_arr_[i] = dist; + ideal_arr_[i] = dist; } } - for (int i=0; i < ideal_arr_.size()-1; i++) { - assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0); - connect (i, i+1, ideal_arr_[i], hooke_arr_[i]); + for (int i=0; i < ideal_arr_.size()-1; i++) + { + assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0); + connect (i, i+1, ideal_arr_[i], hooke_arr_[i]); } } - - - -void -Spring_spacer::prepare() -{ - calc_idealspacing(); - handle_loose_cols(); - print(); -} - -Line_spacer* -Spring_spacer::constructor() -{ - return new Spring_spacer; -} - -- 2.39.5