lily/word-wrap.cc

   1 /*
   2   word-wrap.cc -- implement Word_wrap
   3
   4   source file of the LilyPond music typesetter
   5
   6   (c)  1997--1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9 #include "word-wrap.hh"
  10 #include "paper-def.hh"
  11 #include "paper-score.hh"
  12 #include "debug.hh"
  13 #include "paper-column.hh"
  14 #include "line-spacer.hh"
  15
  16
  17 /** El stupido.  Add a measure until we're past the optimum.
  18
  19
  20    A Dynamic Programming type of algorithm
  21    similar to TeX's is in Gourlay_breaking
  22
  23    UGH.  Should think about pre/post break columns.
  24    */
  25 Array<Column_x_positions>
  26 Word_wrap::do_solve () const
  27 {
  28   problem_OK ();
  29
  30   Line_of_cols &allcols (pscore_l_->col_l_arr_);
  31   int curcol_idx = 0;
  32
  33   Array<Column_x_positions> breaking;
  34   Line_of_cols breakpoints (find_breaks ());
  35   assert (breakpoints.size ()>=2);
  36
  37   int break_idx=0;
  38   while (break_idx < breakpoints.size () -1)
  39     {
  40       Column_x_positions minimum;
  41       Column_x_positions current;
  42
  43
  44       // do  another line
  45
  46       Item *post = breakpoints[break_idx]->find_broken_piece (RIGHT);
  47       Paper_column *postcol =dynamic_cast<Paper_column*>(post);
  48
  49       int start_break_idx = break_idx;
  50       current.add_paper_column (postcol);
  51       curcol_idx++;             // skip the breakable.
  52       break_idx++;
  53
  54       while (break_idx < breakpoints.size ())
  55         {
  56           // add another measure.
  57           while (breakpoints[break_idx] != allcols[curcol_idx])
  58             {
  59               current.add_paper_column (allcols[curcol_idx]);
  60               curcol_idx++;
  61             }
  62
  63           Item * pre = breakpoints[break_idx]->find_broken_piece (LEFT);
  64           Paper_column* precol = dynamic_cast<Paper_column*>(pre);
  65           current.add_paper_column (precol);
  66
  67           current.spacer_l_ = generate_spacing_problem (current.cols_,
  68             pscore_l_->paper_l_->line_dimensions_int (breaking.size ()));
  69
  70           // try to solve
  71           if (!feasible (current.cols_))
  72             {
  73               if (!minimum.cols_.size ())
  74                 {
  75                   warning (_f ("Ugh, this measure is too long, breakpoint: %d",
  76                     break_idx));
  77                   warning (_ ("Generating stupido solution"));
  78                   current.stupid_solution ();
  79                   current.energy_f_ = - 1; // make sure we break out.
  80                 }
  81               else
  82                 current.energy_f_ = infinity_f; // make sure we go back
  83             }
  84           else
  85             {
  86               current.solve_line ();
  87               current.print ();
  88             }
  89
  90           delete current.spacer_l_;
  91           current.spacer_l_ =0;
  92
  93           if (!current.satisfies_constraints_b_ && start_break_idx == break_idx - 1)
  94             {
  95               warning ( _ ("I don't fit; put me on Montignac"));
  96               minimum = current;
  97               break;
  98             }
  99
 100           /*
 101             UGR! bug!
 102            */
 103           if (current.energy_f_ < minimum.energy_f_ || current.energy_f_ < 0)
 104             {
 105               minimum = current;
 106             }
 107           else
 108             {           // we're one col too far.
 109               break_idx--;
 110               while (allcols[curcol_idx] != breakpoints[break_idx])
 111                 curcol_idx --;
 112               break;            // do the next line.
 113             }
 114
 115
 116           // add nobreak version of breakable column
 117           current.cols_.top ()=breakpoints[break_idx];
 118           curcol_idx ++;
 119           break_idx++;
 120         }
 121
 122       *mlog << "[" << break_idx << "]" << flush;
 123       breaking.push (minimum);
 124     }
 125   *mlog << endl;
 126   return breaking;
 127 }
 128