lily/spring-spacer.cc

   1 /*
   2   spring-spacer.cc -- implement Spring_spacer
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1996--1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9
  10 #include <math.h>
  11 #include <limits.h>
  12 #include "killing-cons.tcc"
  13 #include "spring-spacer.hh"
  14 #include "paper-column.hh"
  15 #include "debug.hh"
  16 #include "dimensions.hh"
  17 #include "qlp.hh"
  18 #include "unionfind.hh"
  19 #include "idealspacing.hh"
  20 #include "pointer.tcc"
  21 #include "score-column.hh"
  22 #include "paper-def.hh"
  23 #include "colhpos.hh"
  24 #include "main.hh"
  25
  26 Vector
  27 Spring_spacer::default_solution() const
  28 {
  29   return try_initial_solution();
  30 }
  31
  32 Score_column*
  33 Spring_spacer::scol_l (int i)
  34 {
  35   return dynamic_cast<Score_column*>(cols_[i].pcol_l_);
  36 }
  37
  38 const Real COLFUDGE=1e-3;
  39 template class P<Real>;         // ugh.
  40
  41 bool
  42 Spring_spacer::contains_b (Paper_column const *w)
  43 {
  44   for (int i=0; i< cols_.size(); i++)
  45     if (cols_[i].pcol_l_ == w)
  46       return true;
  47   return false;
  48 }
  49
  50
  51 void
  52 Spring_spacer::OK() const
  53 {
  54 #ifndef NDEBUG
  55   for (int i = 1; i < cols_.size(); i++)
  56     assert (cols_[i].rank_i_ > cols_[i-1].rank_i_);
  57 #endif
  58 }
  59
  60 /**
  61   Make sure no unconnected columns happen.
  62  */
  63 void
  64 Spring_spacer::handle_loose_cols()
  65 {
  66   Union_find connected (cols_.size());
  67   Array<int> fixed;
  68
  69   for (Cons<Idealspacing> *i  = ideal_p_list_; i; i = i->next_)
  70     {
  71       connected.connect (i->car_->cols_drul_[LEFT],i->car_->cols_drul_[RIGHT]);
  72     }
  73   for (int i = 0; i < cols_.size(); i++)
  74     if (cols_[i].fixed_b())
  75       fixed.push (i);
  76   for (int i=1; i < fixed.size(); i++)
  77     connected.connect (fixed[i-1], fixed[i]);
  78
  79   /*
  80     connect unconnected columns with distances of 1.0;
  81    */
  82   for (int i = cols_.size(); i--;)
  83     {
  84       if (! connected.equiv (fixed[0], i))
  85         {
  86           connected.connect (i-1, i);
  87           connect (i-1, i, 1.0, 1.0);
  88         }
  89     }
  90 }
  91
  92 bool
  93 Spring_spacer::check_constraints (Vector v) const
  94 {
  95   int dim=v.dim();
  96   assert (dim == cols_.size());
  97   DOUT << "checking " << v;
  98   for (int i=0; i < dim; i++)
  99     {
 100       if (cols_[i].fixed_b() &&
 101           abs (cols_[i].fixed_position() - v (i)) > COLFUDGE)
 102         {
 103           DOUT << "Fixpos broken\n";
 104           return false;
 105         }
 106       Array<Spacer_rod> const &rods (cols_[i].rods_[RIGHT]);
 107       for (int j =0; j < rods.size (); j++)
 108         {
 109           int other =rods[j].other_idx_;
 110           Real diff =v (other) - v (i) ;
 111           if (COLFUDGE +diff <  rods[j].distance_f_)
 112             {
 113               DOUT << "i, other_i: " << i << "  " << other << '\n';
 114               DOUT << "dist, minimal = " << diff << " "
 115                    << rods[j].distance_f_ << '\n';
 116               return false;
 117             }
 118         }
 119
 120     }
 121   return true;
 122 }
 123
 124 /** try to generate a solution which obeys the min
 125     distances and fixed positions
 126  */
 127 Vector
 128 Spring_spacer::try_initial_solution() const
 129 {
 130   Vector v;
 131   if (!try_initial_solution_and_tell (v))
 132     {
 133       warning (_ ("I'm too fat; call Oprah"));
 134     }
 135   return v;
 136
 137 }
 138
 139 bool
 140 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
 141 {
 142   int dim=cols_.size();
 143   bool succeeded = true;
 144   Vector initsol (dim);
 145
 146   assert (cols_[0].fixed_b ());
 147   DOUT << "fixpos 0 " << cols_[0].fixed_position ();
 148   for (int i=0; i < dim; i++)
 149     {
 150       Real min_x = i ?  initsol (i-1) : cols_[0].fixed_position ();
 151       Array<Spacer_rod> const &sr_arr(cols_[i].rods_[LEFT]);
 152       for (int j=0; j < sr_arr.size (); j++)
 153         {
 154           min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
 155         }
 156       initsol (i) = min_x;
 157
 158       if (cols_[i].fixed_b())
 159         {
 160           initsol (i)=cols_[i].fixed_position();
 161           if (initsol (i) < min_x )
 162             {
 163               DOUT << "failing: init, min : " << initsol (i) << " " << min_x << '\n';
 164               initsol (i) = min_x;
 165               succeeded = false;
 166             }
 167         }
 168     }
 169   v = initsol;
 170
 171   DOUT << "tried and told solution: " << v;
 172   if (!succeeded)
 173     DOUT << "(failed)\n";
 174   return succeeded;
 175 }
 176
 177
 178
 179 // generate the matrices
 180 void
 181 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
 182 {
 183   quad.fill (0);
 184   lin.fill (0);
 185   c = 0;
 186
 187   for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
 188     {
 189       Idealspacing *i = p->car_;
 190       int l = i->cols_drul_[LEFT];
 191       int r = i->cols_drul_[RIGHT];
 192
 193       quad (r,r) += i->hooke_f_;
 194       quad (r,l) -= i->hooke_f_;
 195       quad (l,r) -= i->hooke_f_;
 196       quad (l,l) += i->hooke_f_;
 197
 198       lin (r) -= i->space_f_*i->hooke_f_;
 199       lin (l) += i->space_f_*i->hooke_f_;
 200
 201       c += sqr (i->space_f_);
 202     }
 203
 204   if (quad.dim() > 10)
 205     quad.set_band();
 206
 207
 208 }
 209
 210 void
 211 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
 212 {
 213   for (int j=0; j < cols_.size(); j++)
 214     if (cols_[j].fixed_b())
 215       qp.add_fixed_var (j,cols_[j].fixed_position());
 216 }
 217
 218 // put the constraints into the LP problem
 219 void
 220 Spring_spacer::make_constraints (Mixed_qp& lp) const
 221 {
 222   int dim=cols_.size();
 223
 224   for (int j=0; j < dim -1; j++)
 225     {
 226       Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
 227       for (int i = 0; i < rod_arr.size (); i++)
 228         {
 229           Vector c1(dim);
 230           c1(rod_arr[i].other_idx_)=1.0 ;
 231           c1(j)=-1.0 ;
 232
 233           lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
 234         }
 235     }
 236 }
 237
 238
 239 Real
 240 Spring_spacer::calculate_energy_f (Vector solution) const
 241 {
 242   Real e = 0.0;
 243   for (Cons<Idealspacing>*p =ideal_p_list_; p; p = p->next_)
 244     {
 245       Idealspacing * i = p->car_;
 246       e += i->energy_f(solution(i->cols_drul_[RIGHT]) - solution(i->cols_drul_[LEFT]));
 247     }
 248
 249   return e;
 250 }
 251 void
 252 Spring_spacer::lower_bound_solution (Column_x_positions*positions) const
 253 {
 254   Mixed_qp lp (cols_.size());
 255   make_matrices (lp.quad_,lp.lin_, lp.const_term_);
 256   set_fixed_cols (lp);
 257
 258   Vector start (cols_.size());
 259   start.fill (0.0);
 260   Vector solution_vec (lp.solve (start));
 261
 262   DOUT << "Lower bound sol: " << solution_vec;
 263   positions->energy_f_ = calculate_energy_f (solution_vec);
 264   positions->config_ = solution_vec;
 265   positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 266 }
 267
 268 Spring_spacer::Spring_spacer ()
 269 {
 270   ideal_p_list_ =0;
 271   energy_normalisation_f_ = 1.0;
 272 }
 273
 274 void
 275 Spring_spacer::solve (Column_x_positions*positions) const
 276 {
 277   DOUT << "Spring_spacer::solve ()...";
 278
 279   Vector solution_try;
 280
 281   bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
 282   if  (constraint_satisfaction)
 283     {
 284       Mixed_qp lp (cols_.size());
 285       make_matrices (lp.quad_,lp.lin_, lp.const_term_);
 286       make_constraints (lp);
 287       set_fixed_cols (lp);
 288
 289       Vector solution_vec (lp.solve (solution_try));
 290
 291       positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 292       if (!positions->satisfies_constraints_b_)
 293         {
 294           WARN << _ ("solution doesn't satisfy constraints") << '\n' ;
 295         }
 296       positions->energy_f_ = calculate_energy_f (solution_vec);
 297       positions->config_ = solution_vec;
 298     }
 299   else
 300     {
 301       positions->set_stupid_solution (solution_try);
 302     }
 303
 304   DOUT << "Finished Spring_spacer::solve ()...";
 305 }
 306
 307 /**
 308   add one column to the problem.
 309 */
 310 void
 311 Spring_spacer::add_column (Paper_column  *col, bool fixed, Real fixpos)
 312 {
 313   Column_info c (col,(fixed)? &fixpos :  0);
 314   int this_rank =  cols_.size();
 315   c.rank_i_ = this_rank;
 316
 317   for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
 318     {
 319       Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
 320       int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
 321       if (left_idx < 0)
 322         continue;
 323
 324       if (cols_[left_idx].pcol_l_ != cr.other_l_)
 325         continue;
 326
 327       Spacer_rod l_rod;
 328       l_rod.distance_f_ = cr.distance_f_;
 329       l_rod.other_idx_ = left_idx;
 330       c.rods_[LEFT].push (l_rod);
 331
 332       Spacer_rod r_rod;
 333       r_rod.distance_f_ = cr.distance_f_;
 334       r_rod.other_idx_ = this_rank;
 335       cols_[left_idx].rods_[RIGHT].push (r_rod);
 336     }
 337
 338   for (int i=0; i < col->spring_arr_drul_[LEFT].size (); i++)
 339     {
 340       Column_spring &cr = col->spring_arr_drul_[LEFT][i];
 341       int idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
 342       if (idx < 0)
 343         continue;
 344
 345       if (cols_[idx].pcol_l_ != cr.other_l_)
 346         continue;
 347       connect (idx, this_rank, cr.distance_f_, cr.strength_f_);
 348     }
 349
 350   cols_.push (c);
 351 }
 352
 353
 354 void
 355 Spring_spacer::print() const
 356 {
 357 #ifndef NPRINT
 358   for (int i=0; i < cols_.size(); i++)
 359     {
 360       DOUT << "col " << i << " ";
 361       cols_[i].print();
 362     }
 363
 364   for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
 365     {
 366       p->car_->print();
 367     }
 368 #endif
 369 }
 370
 371
 372 void
 373 Spring_spacer::connect (int i, int j, Real d, Real h)
 374 {
 375   assert(d >= 0 && d <= 100 CM);
 376   assert(h >=0);
 377
 378   Idealspacing * s = new Idealspacing;
 379
 380   s->cols_drul_[LEFT] = i ;
 381   s->cols_drul_[RIGHT] = j;
 382   s->space_f_ = d;
 383   s->hooke_f_ = h;
 384
 385   ideal_p_list_ = new Killing_cons<Idealspacing> (s, ideal_p_list_);
 386 }
 387
 388 void
 389 Spring_spacer::prepare()
 390 {
 391   handle_loose_cols();
 392   print();
 393 }
 394
 395 Line_spacer*
 396 Spring_spacer::constructor()
 397 {
 398   return new Spring_spacer;
 399 }
 400
 401
 402
 403
 404 Spring_spacer::~Spring_spacer()
 405 {
 406   delete ideal_p_list_;
 407 }