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 "spring-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
  24    UGH.  Should think about pre/post break columns.
  25    */
  26 Array<Column_x_positions>
  27 Word_wrap::do_solve () const
  28 {
  29   problem_OK ();
  30
  31   Line_of_cols &allcols (pscore_l_->col_l_arr_);
  32   int curcol_idx = 0;
  33
  34   Array<Column_x_positions> breaking;
  35   Line_of_cols breakpoints (find_breaks ());
  36   assert (breakpoints.size ()>=2);
  37
  38   int break_idx=0;
  39   int line_no = 0;
  40   while (break_idx < breakpoints.size () -1)
  41     {
  42       Column_x_positions minimum;
  43       Column_x_positions current;
  44
  45
  46       // do  another line
  47       line_no ++;
  48       Item *post = breakpoints[break_idx]->find_prebroken_piece (RIGHT);
  49       Paper_column *postcol =dynamic_cast<Paper_column*>(post);
  50
  51       int start_break_idx = break_idx;
  52       current.add_paper_column (postcol);
  53       curcol_idx++;             // skip the breakable.
  54       break_idx++;
  55
  56       while (break_idx < breakpoints.size ())
  57         {
  58           // add another measure.
  59           while (breakpoints[break_idx] != allcols[curcol_idx])
  60             {
  61               current.add_paper_column (allcols[curcol_idx]);
  62               curcol_idx++;
  63             }
  64
  65           Item * pre = breakpoints[break_idx]->find_prebroken_piece (LEFT);
  66           Paper_column* precol = dynamic_cast<Paper_column*>(pre);
  67           current.add_paper_column (precol);
  68
  69           current.spacer_l_ = generate_spacing_problem (current.cols,
  70             pscore_l_->paper_l_->line_dimensions_int (line_no));
  71
  72           // try to solve
  73           if (!feasible (current.cols))
  74             {
  75               if (!minimum.cols.size ())
  76                 {
  77                   warning (_ ("ugh, this measure is too long")
  78                     + ", " + _f ("breakpoint: %d", break_idx)
  79                     + "(" + _ ("generating stupido solution") + ")");
  80                   current.stupid_solution ();
  81                   current.energy_f_ = - 1; // make sure we break out.
  82                 }
  83               else
  84                 current.energy_f_ = infinity_f; // make sure we go back
  85             }
  86           else
  87             {
  88               current.solve_line ();
  89               current.print ();
  90             }
  91
  92           delete current.spacer_l_;
  93           current.spacer_l_ =0;
  94
  95           if (!current.satisfies_constraints_b_ && start_break_idx == break_idx - 1)
  96             {
  97               warning ( _ ("I don't fit; put me on Montignac"));
  98               minimum = current;
  99               break;
 100             }
 101
 102           /*
 103             UGR! bug!
 104            */
 105           if (current.energy_f_ < minimum.energy_f_ || current.energy_f_ < 0)
 106             {
 107               minimum = current;
 108             }
 109           else
 110             {           // we're one col too far.
 111               break_idx--;
 112               while (allcols[curcol_idx] != breakpoints[break_idx])
 113                 curcol_idx --;
 114               break;            // do the next line.
 115             }
 116
 117
 118           // add nobreak version of breakable column
 119           current.cols.top ()=breakpoints[break_idx];
 120           curcol_idx ++;
 121           break_idx++;
 122         }
 123
 124       *mlog << "[" << break_idx << "]" << flush;
 125       breaking.push (minimum);
 126     }
 127   return breaking;
 128 }
 129
 130 Word_wrap::Word_wrap ()
 131 {
 132   get_line_spacer = Spring_spacer::constructor;
 133 }