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