linespace.hh

   1 #ifndef PROBLEM_HH
   2 #define PROBLEM_HH
   3
   4 #include "glob.hh"
   5 #include "list.hh"
   6 #include "vray.hh"
   7 #include "cols.hh"
   8 #include "matrix.hh"
   9
  10 /// helper struct for #Spacing_problem#
  11 struct Colinfo {
  12     const PCol *col;
  13     bool fixed;
  14     Real fixpos;
  15     Colinfo() {
  16         fixed=false;
  17         col=0;
  18     }
  19     void print() const;
  20     Real minright()const { return col->width().max; }
  21     Real minleft()const { return -col->width().min; }
  22 };
  23
  24
  25 /// spacing for one line.
  26 class Spacing_problem {
  27     svec<const Idealspacing*> ideals;
  28     svec<Colinfo> cols;
  29
  30     /// the index of #c# in #cols#
  31     int col_id(const PCol *c) const;
  32
  33     /// generate an (nonoptimal) solution
  34     Vector find_initial_solution() const;
  35
  36     /// check if problem is too tight
  37     bool check_feasible() const;
  38     /// does #this# contain the column #w#?
  39     bool contains(const PCol *w);
  40
  41     /// make the energy function
  42     void make_matrices(Matrix &quad, Vector &lin,Real&) const;
  43
  44     /// generate the LP constraints
  45     void make_constraints(Optimisation_problem& lp) const;
  46
  47 public:
  48     /// solve the spacing problem
  49     svec<Real> solve() const;
  50     /**
  51     return the column positions, and the energy (last element)
  52     */
  53     /// add a idealspacing to the problem.
  54     void add_ideal(const Idealspacing *i);
  55
  56     /**
  57     One pair of columns can have no, one or more idealspacings,
  58     since they can be "summed" if the columns to which #i# refers are
  59     not in this problem, the spacing is ignored.
  60     */
  61
  62
  63     /// add a col to the problem
  64     void add_column(const PCol *, bool fixed=false, Real fixpos=0.0);
  65     /** columns have to be added left to right. The column contains
  66       info on it's minimum width.
  67     */
  68
  69
  70     bool check_constraints(Vector v) const;
  71
  72     Vector try_initial_solution() const;
  73     void OK() const;
  74     void print() const;
  75     void print_ideal(const Idealspacing*)const;
  76 };
  77
  78
  79 /** the problem, given by the columns (which include constraints) and
  80     intercolumn spacing. The problem is:
  81
  82     Generate a spacing which
  83     \begin{itemize}
  84     \item
  85     Satisfies spacing constraints (notes can't be printed through each other)
  86     \item
  87     Looks good, ie tries to conform to  an ideal spacing as much as possible.
  88     \end{itemize}
  89     This is converted by regarding idealspacing as "springs" attached
  90     to columns. The equilibrium of one spring is the ideal
  91     distance. The columns have a size, this imposes "hard" constraints
  92     on the distances. This transforms the problem into a quadratic
  93     programming problem with linear constraints.
  94
  95     The quality is given by the total potential energy in the
  96     springs. The lower the energy, the better the configuration.
  97 */
  98 #endif