lily/constrained-breaking.cc

   1 /*
   2   constrained-breaking.cc -- implement a line breaker that
   3   support limits on the number of systems
   4
   5   source file of the GNU LilyPond music typesetter
   6
   7   (c) 2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
   8 */
   9
  10 /*
  11   TODO:
  12
  13   * vsize vs. int: casts should not be necessary. Use VPOS iso -1 as
  14   magic signaling value?
  15
  16   * The specification uses A j, k, n and m as variables.
  17
  18   Functions use start,end,sys_count,calc_subproblem as variables. Use the same naming
  19   for the specification as for the code.
  20
  21
  22   FURTHER REMARKS:
  23
  24   *
  25
  26    int a;
  27    int b;
  28
  29   iso.
  30
  31    int a, b;
  32
  33
  34    * no spurious * in <slash><star> <star><slash> comments.
  35
  36
  37  */
  38
  39
  40 #include "constrained-breaking.hh"
  41
  42 #include "international.hh"
  43 #include "main.hh"
  44 #include "output-def.hh"
  45 #include "paper-column.hh"
  46 #include "paper-score.hh"
  47 #include "simple-spacer.hh"
  48 #include "system.hh"
  49 #include "warn.hh"
  50
  51 void
  52 print_constrained_break_nodes (vector<Constrained_break_node> const &arr)
  53 {
  54   for (vsize i = 0; i < arr.size (); i++)
  55     {
  56       printf ("node %d: ", (int)i);
  57       arr[i].print ();
  58     }
  59 }
  60
  61 /**
  62    We use the following optimal substructure. Let W(A) be our weight function.
  63
  64    Let A_{k,n} = (a_{k,n,1}, ... a_{k,n,k}) be the optimal set of line breaks
  65    for k systems and n potential breakpoints. a_{k,n,k} = n (it is the end of
  66    the piece)
  67
  68    Then A_{k+1, m} is contructed from
  69    min_ {k < j < m} ( W(A_{k,j} :: m) )
  70    where by A::m we denote appending m to the list A
  71
  72 */
  73
  74 /* start and sys here are indexed from 0.
  75
  76 max_break is indexed from starting_breakpoints_[start] (for
  77  max_break, starting_breakpoints_[start] is the beginning of the
  78  piece; the smallest value we should ever see here is
  79  starting_breakpoints_[start] + 1) */
  80 bool
  81 Constrained_breaking::calc_subproblem (int start, int sys, int max_break)
  82 {
  83   assert (sys < systems_);
  84   assert (start < (int)start_.size ());
  85   assert (max_break < (int)breaks_.size ());
  86
  87   bool found_something = false;
  88   int start_col = starting_breakpoints_[start];
  89   vector<Constrained_break_node> &st = state_[start];
  90   int rank = breaks_.size () - start_col;
  91   int max_index = max_break - start_col;
  92   for (int j = sys; j < max_index; j++)
  93     {
  94       if (0 == sys && j > 0)
  95         break; /* the first line cannot have its first break after the beginning */
  96
  97       Column_x_positions const &cur = cols_[(j + start_col)*cols_rank_ + max_break];
  98       Column_x_positions prev;
  99       Real prev_dem = 0;
 100
 101       if (sys > 0)
 102         {
 103           prev = st[(sys-1) * rank + j].line_config_;
 104           prev_dem = st[(sys-1) * rank + j].demerits_;
 105         }
 106       if (isinf (prev_dem))
 107         break;
 108
 109       Real dem, force, pen;
 110       combine_demerits(prev, cur, &force, &pen, &dem);
 111       dem += prev_dem;
 112       if (isinf (dem))
 113         continue;
 114
 115       int k = sys*rank + max_index;
 116       if (isinf (st[k].demerits_)
 117           || dem < st[k].demerits_)
 118         {
 119           found_something = true;
 120
 121           /*
 122             TODO:  maybe just copy a Constrained_break_node ?
 123            */
 124           st[k].demerits_ = dem;
 125           st[k].force_ = force;
 126           st[k].penalty_ = pen;
 127           st[k].prev_ = j;
 128           st[k].line_config_ = cur;
 129         }
 130     }
 131   return found_something;
 132 }
 133
 134 vector<Column_x_positions>
 135 Constrained_breaking::solve ()
 136 {
 137   if (!systems_)
 138     {
 139       programming_error (_f ("no system number set in constrained-breaking"));
 140       systems_ = start_.size () / 2;
 141     }
 142
 143   resize ();
 144   return get_solution (0, systems_, -1);
 145 }
 146
 147 void
 148 Constrained_breaking::resize ()
 149 {
 150   if (!breaks_.size ())
 151     {
 152       bool ragged_right = to_boolean (pscore_->layout ()->c_variable ("ragged-right"));
 153       bool ragged_last = to_boolean (pscore_->layout ()->c_variable ("ragged-last"));
 154
 155       /* do all the rod/spring problems */
 156       breaks_ = pscore_->find_break_indices ();
 157       cols_rank_ = breaks_.size ();
 158       all_ = pscore_->root_system ()->columns ();
 159       cols_.resize (breaks_.size () * breaks_.size ());
 160       for (vsize i = 0; i < breaks_.size () - 1; i++)
 161         for (vsize j = i + 1; j < breaks_.size (); j++)
 162           {
 163             vector<Grob*> line (all_.begin () + breaks_[i],
 164                                 all_.begin() + breaks_[j] + 1);
 165
 166             line[0] = dynamic_cast<Item *> (line[0])->find_prebroken_piece (RIGHT);
 167             line.back () = dynamic_cast<Item *> (line.back ())->find_prebroken_piece (LEFT);
 168
 169             cols_[i*cols_rank_ + j].cols_ = line;
 170
 171             /* we have no idea what line this will be -- only whether it is the first */
 172             Interval line_dims = line_dimensions_int (pscore_->layout (), i);
 173             Simple_spacer_wrapper *sp = generate_spacing_problem (line, line_dims);
 174
 175             bool last = j == breaks_.size () - 1;
 176             bool ragged = ragged_right || (last && ragged_last);
 177             sp->solve (&cols_[i*cols_rank_ + j], ragged);
 178
 179             if (!cols_[i*cols_rank_ + j].satisfies_constraints_)
 180               break;
 181             delete sp;
 182           }
 183
 184       /* work out all the starting indices */
 185       for (vsize i = 0; i < start_.size (); i++)
 186         {
 187           vsize j;
 188           for (j = 0; j < breaks_.size () - 1 && breaks_[j] < start_[i]; j++)
 189             ;
 190           starting_breakpoints_.push_back (j);
 191           start_[i] = breaks_[j];
 192         }
 193       state_.resize (start_.size ());
 194     }
 195
 196   for (vsize i = 0; i < state_.size (); i++)
 197     state_[i].resize((breaks_.size () - starting_breakpoints_[i]) * systems_);
 198
 199   /* fill out the matrices */
 200   for (vsize i = 0; i < state_.size (); i++)
 201     for (int j = valid_systems_; j < systems_; j++)
 202       for (vsize k = starting_breakpoints_[i] + j + 1; k < breaks_.size (); k++)
 203         if (!calc_subproblem (i, j, k))
 204           break; /* if we couldn't break this, it is too cramped already */
 205
 206   valid_systems_ = systems_;
 207 }
 208
 209 vector<Column_x_positions>
 210 Constrained_breaking::get_solution (int start, int end, int sys_count)
 211 {
 212   int rank;
 213   int brk;
 214   prepare_solution (start, end, sys_count, &rank, &brk);
 215
 216   vector<Constrained_break_node> const &st = state_[start];
 217   vector<Column_x_positions> ret;
 218
 219   for (int sys = sys_count-1; sys >= 0; sys--)
 220     {
 221       assert (brk > 0);
 222       ret.push_back (st[sys*rank + brk].line_config_);
 223       brk = st[sys*rank + brk].prev_;
 224     }
 225   assert (brk == 0);
 226
 227   reverse (ret);
 228   return ret;
 229 }
 230
 231 Real
 232 Constrained_breaking::get_demerits (int start, int end, int sys_count)
 233 {
 234   int rank;
 235   int brk;
 236   prepare_solution (start, end, sys_count, &rank, &brk);
 237
 238   return state_[start][(sys_count-1)*rank + brk].demerits_;
 239 }
 240
 241 Real
 242 Constrained_breaking::get_force (int start, int end, int sys_count)
 243 {
 244   int rank;
 245   int brk;
 246   prepare_solution (start, end, sys_count, &rank, &brk);
 247   vector<Constrained_break_node> const &st = state_[start];
 248   Real f = 0;
 249
 250   for (int sys = sys_count-1; sys >= 0 && brk >= 0; sys--)
 251     {
 252       f += fabs (st[sys*rank + brk].force_);
 253       brk = st[sys*rank + brk].prev_;
 254     }
 255   if (brk < 0)
 256     f = infinity_f;
 257
 258   return f;
 259 }
 260
 261 Real
 262 Constrained_breaking::get_penalty (int start, int end, int sys_count)
 263 {
 264   int rank;
 265   int brk;
 266   prepare_solution (start, end, sys_count, &rank, &brk);
 267
 268   return state_[start][(sys_count-1)*rank + brk].penalty_;
 269 }
 270
 271 Real
 272 Constrained_breaking::get_page_penalty (int start, int end, int sys_count, int sys_num)
 273 {
 274   int rank;
 275   int brk;
 276   prepare_solution (start, end, sys_count, &rank, &brk);
 277
 278   int sys;
 279   for (sys = sys_count-1; sys > sys_num; sys--)
 280     brk = state_[start][sys*rank + brk].prev_;
 281
 282   if (brk < 0) /* we didn't satisfy constraints */
 283     return 0;
 284   vector<Grob*> &cols = state_[start][sys*rank + brk].line_config_.cols_;
 285   if (cols.empty ())
 286     return 0;
 287
 288   Grob *pc = cols.back ();
 289   if (pc->original ())
 290     {
 291       SCM pen = pc->get_property ("page-penalty");
 292       if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
 293         return scm_to_double (pen);
 294     }
 295   return 0;
 296 }
 297
 298 int
 299 Constrained_breaking::get_min_systems (int start, int end)
 300 {
 301   int rank;
 302   int brk;
 303   prepare_solution (start, end, 1, &rank, &brk);
 304   int sys_count;
 305   vector<Constrained_break_node> const &st = state_[start];
 306
 307   /* sys_count < rank : rank is the # of breakpoints, we can't have more systems */
 308   for (sys_count = 0; sys_count < rank; sys_count++)
 309     {
 310       if (sys_count >= valid_systems_)
 311         {
 312           systems_ = sys_count + 3;
 313           resize ();
 314         }
 315       if (!isinf (st[sys_count*rank + brk].force_))
 316         return sys_count + 1;
 317     }
 318   /* no possible breaks satisfy constraints */
 319   return 0;
 320 }
 321
 322 int
 323 Constrained_breaking::get_max_systems (int start, int end)
 324 {
 325   int brk = (end < 0 || end >= (int)start_.size ()) ? breaks_.size () - 1 : start_[end];
 326   return brk - starting_breakpoints_[start];
 327 }
 328
 329 void
 330 Constrained_breaking::prepare_solution (vsize start, int end, int sys_count, int *rank, int *brk)
 331 {
 332   assert (start < start_.size () && end <= int (start_.size ()));
 333   assert (end < 0 || int (start) < end);
 334   assert (sys_count > 0);
 335
 336   if (sys_count >= valid_systems_)
 337     {
 338       systems_ = sys_count;
 339       resize ();
 340     }
 341   if (end == (int)start_.size ())
 342     end = -1;
 343
 344   *rank = breaks_.size () - starting_breakpoints_[start];
 345   *brk = end < 0 ? breaks_.size () - 1 : starting_breakpoints_[end];
 346   *brk -= starting_breakpoints_[start];
 347 }
 348
 349 Constrained_breaking::Constrained_breaking ()
 350 {
 351   valid_systems_ = systems_ = 0;
 352   start_.push_back (0);
 353 }
 354
 355 Constrained_breaking::Constrained_breaking (vector<int> const &start)
 356   : start_ (start)
 357 {
 358   valid_systems_ = systems_ = 0;
 359 }
 360
 361 void
 362 Constrained_breaking::combine_demerits (Column_x_positions const &prev,
 363                                         Column_x_positions const &col,
 364                                         Real *force,
 365                                         Real *penalty,
 366                                         Real *demerits) const
 367 {
 368   *penalty = 0;
 369   if (col.cols_.empty () || !col.satisfies_constraints_)
 370     *force = infinity_f;
 371   else
 372     {
 373       *force = col.force_;
 374
 375       Grob *pc = col.cols_.back ();
 376       if (pc->original ())
 377         {
 378           SCM pen = pc->get_property ("penalty");
 379           if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
 380             *penalty += scm_to_double (pen);
 381         }
 382     }
 383
 384   *demerits = (*force) * (*force) + abs (prev.force_ - *force) + *penalty;
 385 }
 386