lily/include/linespace.hh

   1 /*
   2   linespace.hh -- declare Colinfo, Spacing_problem
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1996,1997 Han-Wen Nienhuys <hanwen@stack.nl>
   7 */
   8
   9
  10 #ifndef LINESPACE_HH
  11 #define LINESPACE_HH
  12 #include "glob.hh"
  13 #include "plist.hh"
  14 #include "varray.hh"
  15 #include "vector.hh"
  16 #include "interval.hh"
  17 #include "pointer.hh"
  18
  19 /// helper struct for #Spacing_problem#
  20 struct Colinfo {
  21     PCol *pcol_l_;
  22     P<Real> fixpos_p_;
  23     Interval width;
  24     int rank_i_;
  25     /// did some tricks to make this column come out.
  26     bool ugh_b_;
  27     /* *************** */
  28     Colinfo();
  29     Colinfo(PCol *,Real const *);
  30
  31     void print() const;
  32     bool fixed() const { return fixpos_p_.get_C();}
  33     Real fixed_position()const { return *fixpos_p_; }
  34     Real minright() const { return width.right; }
  35     Real minleft() const { return -width.left; }
  36 };
  37
  38
  39 /** the problem, given by the columns (which include constraints) and
  40     intercolumn spacing. The problem is:
  41
  42     Generate a spacing which
  43     \begin{itemize}
  44     \item
  45     Satisfies spacing constraints (notes can't be printed through each other)
  46     \item
  47     Looks good, ie tries to conform to  an ideal spacing as much as possible.
  48     \end{itemize}
  49     This is converted by regarding idealspacing as "springs" attached
  50     to columns. The equilibrium of one spring is the ideal
  51     distance. The columns have a size, this imposes "hard" constraints
  52     on the distances. This transforms the problem into a quadratic
  53     programming problem with linear constraints.
  54
  55     The quality is given by the total potential energy in the
  56     springs. The lower the energy, the better the configuration.
  57
  58     TODO: make item widths work per pstaff.
  59
  60 */
  61 class Spacing_problem {
  62     Array<Idealspacing const *> ideals;
  63     Array<Colinfo> cols;
  64     Array<Colinfo> loose_col_arr_;
  65
  66     /// mark column #i# as being loose.
  67     void loosen_column(int i);
  68     /// the index of #c# in #cols#
  69     int col_id(PCol const *c) const;
  70
  71     /// generate an (nonoptimal) solution
  72     Vector find_initial_solution() const;
  73
  74     /// check if problem is too tight
  75     bool check_feasible() const;
  76
  77     /// does #this# contain the column #w#?
  78     bool contains(PCol const *w);
  79
  80     /// make the energy function
  81     void make_matrices(Matrix &quad, Vector &lin,Real&) const;
  82
  83     /// generate the LP constraints
  84     void make_constraints(Mixed_qp& lp) const;
  85
  86
  87     void handle_loose_cols();
  88     void position_loose_cols(Vector &) const;
  89 public:
  90     Array<PCol*> error_pcol_l_arr() const;
  91
  92     /** solve the spacing problem
  93
  94       @return the column positions, and the energy (last element)
  95
  96       */
  97     Array<Real> solve() const;
  98
  99
 100     /**
 101        add a idealspacing to the problem.
 102
 103     One pair of columns can have no, one or more idealspacings,
 104     since they can be "summed" if the columns to which #i# refers are
 105     not in this problem, the spacing is ignored.
 106     */
 107     void add_ideal(Idealspacing const *i);
 108
 109
 110     /** add a col to the problem. columns have to be added left to right. The column contains
 111       info on it's minimum width.
 112     */
 113     void add_column(PCol  *, bool fixed=false, Real fixpos=0.0);
 114
 115
 116
 117     bool check_constraints(Vector v) const;
 118
 119     Vector try_initial_solution() const;
 120     void OK() const;
 121     void print() const;
 122     void print_ideal(Idealspacing const *)const;
 123     void prepare();
 124 };
 125
 126
 127 #endif