From 30b35498ae0d1a07d6e40d53e4f3fc751fe90acd Mon Sep 17 00:00:00 2001 From: fred Date: Sun, 24 Mar 2002 19:50:25 +0000 Subject: [PATCH] lilypond-0.1.1 --- Documentation/lilyliterature.pod | 43 ++++++-- lily/gourlay-breaking.cc | 177 +++++++++++++++++++++++++++++++ 2 files changed, 209 insertions(+), 11 deletions(-) create mode 100644 lily/gourlay-breaking.cc diff --git a/Documentation/lilyliterature.pod b/Documentation/lilyliterature.pod index 1ea51c9b45..5bba17b138 100644 --- a/Documentation/lilyliterature.pod +++ b/Documentation/lilyliterature.pod @@ -49,6 +49,7 @@ December 1996 [Pamphlet explaining some fine points in music font design HWN] + =head2 Notation with computers Donald Byrd. ``Music Notation by Computer''. Dissertation Indiana @@ -73,11 +74,6 @@ Assisted Research in the Humanities. [Annual editions since 1985, many containing surveys of music typesetting technology. SP] -Wael A. Hegazy and John S. Gourlay. ``Optimal line breaking in music''. In -Document Manipulation and Typography, J.C. van Vliet (ed) 1988. - -[This generalizes TeX's breaking algorithm to music HWN] - David A. Gomberg; ``A Computer-oriented System for Music Printing.'' Computers and the Humanities, Vol.11, pp 63-80. @@ -111,6 +107,13 @@ Computer and Information Science, The Ohio State University, 1987. [Describes the "parser" which converts MusiCopy MDL to MusiCopy Simultaneities & columns HWN] +Wael A. Hegazy and John S. Gourlay. ``Optimal line breaking in +music''. Technical Report OSU-CISRC-8/87-TR33, Department of Computer +and Information Science, The Ohio State University, 1987 + +[This generalizes TeX's breaking algorithm to music. It also appeared in +Document Manipulation and Typography, J.C. van Vliet (ed) 1988. HWN] + Dean K. Roush. ``Using MusiCopy''. Technical Report OSU-CISRC-18/87-TR31, Department of Computer and Information Science, The Ohio State University, 1987 @@ -244,15 +247,12 @@ Kurt Stone. Music Notation in the Twentieth Century. New York: Norton, 1980. -=head2 other stuff +=head2 Other stuff More on GNU Music: http://dept-info.labri.u-bordeaux.fr/~strandh/Gsharp -Tablature: http://wabakimi.carleton.ca/~phacket2/guitar/tabfaq.html - - Peter S. Langston, ``Unix music tools at Bellcore''. Software --- Practice and Experience, Vol. 20(S1), S1/47--S1/61, 1990. @@ -261,15 +261,36 @@ playback. It doesn't mention notation issues, but does come with the grand idea (not) of using music to monitor complex systems. Imagine your nuclear plant supervisor to use AC/DC for checking the reactor HWN] + +=head2 File formats + +Tablature: http://wabakimi.carleton.ca/~phacket2/guitar/tabfaq.html + Cindy Grande, NIFF6a Notation Interchange File Format. Grande -Software Inc., 1995. ftp://blackbox.cartah.washington.edu/pub/ +Software Inc., 1995. ftp://blackbox.cartah.washington.edu/pub/, +http://www.jtauber.com/music/encoding/niff/ [Specs for NIFF, a comprehensive but binary (yuk) format for notation HWN] +SMDL, Standard Musical Description Language +ftp://ftp.ornl.gov/pub/sgml/wg8/smdl/10743.pdf + +MPDL, + +HMSL, Hierarchical Music Structured Language, + +DARMS, + +enigma, + +SCORE, + + =head1 AUTHORS References and comments contributed by Han-Wen Nienhuys (HWN), Miguel Filgueiras, Mark Basinski (MB), Dorothea Blostein, Stephen Page (SP), -Jan Nieuwenhuizen. +Jan Nieuwenhuizen, Peter Kerr. This should really be redone in BibTeX + diff --git a/lily/gourlay-breaking.cc b/lily/gourlay-breaking.cc new file mode 100644 index 0000000000..03f6d3cd7c --- /dev/null +++ b/lily/gourlay-breaking.cc @@ -0,0 +1,177 @@ +/* + gourlay-breaking.cc -- implement Gourlay_breaking + + source file of the GNU LilyPond music typesetter + + (c) 1997 Han-Wen Nienhuys +*/ + +#include "gourlay-breaking.hh" +#include "colhpos.hh" +#include "spring-spacer.hh" +#include "debug.hh" +#include "p-col.hh" +#include "p-score.hh" +#include "paper-def.hh" + + +const HAPPY_DOTS_I = 3; + +/** + Helper to trace back an optimal path + */ +struct Break_node { + /** this was the previous. If negative, this break should not be + considered: this path has infinite energy + + */ + int prev_break_i_; + Real energy_f_; + Col_hpositions line_config_; + Break_node() { + prev_break_i_ = -1; + } +}; + +/** + This algorithms is adapted from + */ + +Array +Gourlay_breaking::do_solve()const +{ + + Array optimal_paths; + Line_of_cols all = all_cols(); + Array breaks = find_break_indices(); + + optimal_paths.set_size(breaks.size()); + + Break_node first_node ; + first_node.prev_break_i_ = -1; + first_node.line_config_.energy_f_ = 0; + + optimal_paths[0] = first_node; + int break_idx=1; + + + for (; break_idx< breaks.size(); break_idx++) { + Array candidates; + Array candidate_lines; + Pointer_list spacer_p_list; + + /* + start with a short line, add measures. At some point + the line becomes infeasible. Then we don't try to add more + */ + for (int start_idx = break_idx; start_idx--; ){ + if (break_idx - start_idx > max_measures_i_) + break; + + if (optimal_paths[start_idx].prev_break_i_ < 0 + && optimal_paths[start_idx].line_config_.energy_f_) + + continue; + + Line_of_cols line = all.slice(breaks[start_idx], breaks[break_idx]+1); + + line[0] = line[0]->postbreak_p_; + line.top() = line.top()->prebreak_p_; + + if (!feasible(line)) + break; + + Col_hpositions approx; + approx.cols = line; + + approx.spacer_l_ = generate_spacing_problem( line ); + spacer_p_list.bottom().add(approx.spacer_l_); + + ((Break_algorithm*)this)->approx_stats_.add( approx.cols ); + approx.approximate_solve_line( ); + + if (approx.energy_f_ > energy_bound_f_ ){ + continue; + } + + + // this is a likely candidate. Store it. + candidate_lines.push( approx ); + candidates.push( start_idx ); + } + + + int minimal_j = -1; + Real minimal_energy = infinity_f; + for (int j=0; j < candidates.size(); j++) { + int start = candidates[j]; + if ( optimal_paths[start].line_config_.energy_f_ + + candidate_lines[j].energy_f_ > minimal_energy) + + continue; + + if ( !candidate_lines[j].satisfies_constraints_b_) { + candidate_lines[j].solve_line( ); + ((Break_algorithm*)this)->exact_stats_.add ( candidate_lines[j].cols ); + } + + Real this_energy + = optimal_paths[start].line_config_.energy_f_ + + candidate_lines[j].energy_f_ ; + + if ( this_energy < minimal_energy ) { + minimal_j = j; + minimal_energy = this_energy; + } + } + + if (minimal_j < 0) { + optimal_paths[break_idx].prev_break_i_ = -1; + optimal_paths[break_idx].line_config_.energy_f_ = infinity_f; + } else { + optimal_paths[break_idx].prev_break_i_ = candidates[minimal_j]; + optimal_paths[break_idx].line_config_ = candidate_lines[minimal_j]; + } + + if ( !(break_idx % HAPPY_DOTS_I) ) + *mlog << "[" << break_idx << "]"< final_breaks; + + /* skip 0-th element, since it is a "dummy" elt*/ + for (int i = optimal_paths.size()-1; i> 0; ) { + final_breaks.push ( i ); + assert ( i > optimal_paths[i].prev_break_i_); + i = optimal_paths[i].prev_break_i_; + } + + Array lines; + for (int i= final_breaks.size(); i--; ) + lines.push ( optimal_paths[final_breaks[i]].line_config_ ); + + + return lines; +} + + +Gourlay_breaking::Gourlay_breaking() +{ + get_line_spacer = Spring_spacer::constructor; + energy_bound_f_ = infinity_f; + max_measures_i_ = INT_MAX; +} + +void +Gourlay_breaking::do_set_pscore() +{ + energy_bound_f_ = pscore_l_->paper_l_->get_var( "gourlay_energybound"); + max_measures_i_ =int (rint( pscore_l_->paper_l_->get_var( "gourlay_maxmeasures"))); +} + -- 2.39.5