/*
  optimal-breaking.cc -- implement Optimal_breakinr

  source file of the GNU LilyPond music typesetter

  (c) 2006 Han-Wen Nienhuys <address@hidden>
*/

#include "optimal-breaking.hh"

#include "international.hh"
#include "item.hh"
#include "output-def.hh"
#include "page-spacing.hh"
#include "paper-book.hh"
#include "paper-score.hh"
#include "paper-system.hh"
#include "system.hh"
#include "warn.hh"

System_spec::System_spec (Paper_score *ps, int break_count)
{
  pscore_ = ps;
  prob_ = 0;
  score_break_count_ = break_count;
}

System_spec::System_spec (Prob *pb)
{
  pscore_ = 0;
  prob_ = pb;
  score_break_count_ = 0;
}

System_spec::System_spec ()
{
  pscore_ = 0;
  prob_ = 0;
  score_break_count_ = 0;
}

/* for Optimal_breaking, the start index (when we are dealing with the stuff
   between a pair of breakpoints) refers to the break_ index of the end of
   the previous page. So the system index of the start of the current page
   could either be the same as the end of the previous page or one more than
   it. */

/* Turn a break index into the sys index that starts the next page */
vsize Optimal_breaking::next_system (vsize start) const
{
  vsize sys = breaks_[start].sys_;

  if (sys == VPOS) /* beginning of the piece */
    return 0;
  if (all_[sys].pscore_ && all_[sys].score_break_count_ > breaks_[start].score_break_)
    return sys; /* the score overflows the previous page */
  return sys + 1; /* this page starts with a new sys */
}

Optimal_breaking::Optimal_breaking (Paper_book *pb)
{
  book_ = pb;
  create_system_list ();
}

Real
Optimal_breaking::calc_demerits (const Optimal_break_node &me)
{
  Real prev_f = 0;
  Real prev_dem = 0;
  Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 1);
  if (me.prev_ != VPOS)
    {
      prev_f = state_[me.prev_].force_;
      prev_dem = state_[me.prev_].demerits_;
    }

  Real dem = me.force_ * me.force_ * page_weighting
           + me.line_force_ * me.line_force_
           + fabs (me.force_ - prev_f);
  if (isinf (me.line_force_) || isinf (me.force_))
    dem = infinity_f;

  return dem + prev_dem + me.penalty_ + me.line_penalty_;
}

void
Optimal_breaking::line_breaker_args (vsize i, vsize *start, vsize *end)
{
  assert (all_[i].pscore_);
  assert (next_system (*start) <= i && i <= breaks_[*end].sys_);

  vsize start_col = 0;
  vsize end_col = VPOS;

  if (breaks_[*start].sys_ == i)
    start_col = breaks_[*start].score_break_;
  if (breaks_[*end].sys_ == i)
    end_col = breaks_[*end].score_break_;

  assert (end_col && (end_col == VPOS || end_col <= all_[breaks_[*end].sys_].score_break_count_));
  *start = start_col;
  *end = end_col;
}

vector<Column_x_positions>
Optimal_breaking::get_line_breaks (vsize i, vsize sys_count, vsize start, vsize end)
{
  assert (all_[i].pscore_);
  line_breaker_args (i, &start, &end);
  return line_breaking_[i].get_solution (start, end, sys_count);
}

vector<Line_details>
Optimal_breaking::get_line_details (vsize i, vsize sys_count, vsize start, vsize end)
{
  if (all_[i].pscore_)
    {
      line_breaker_args (i, &start, &end);
      return line_breaking_[i].get_details (start, end, sys_count);
    }
  Line_details d;
  d.force_ = 0;
  d.extent_ = unsmob_stencil (all_[i].prob_->get_property ("stencil")) ->extent (Y_AXIS).length ();
  d.padding_ = 0;
  d.space_ = 1.0;
  d.inverse_hooke_ = 1.0;
  d.page_permission_ = SCM_EOL;
  d.turn_penalty_ = 0;

  vector<Line_details> ret;
  ret.push_back (d);
  return ret;
}

vsize
Optimal_breaking::get_min_systems (vsize i, vsize start, vsize end)
{
  line_breaker_args (i, &start, &end);
  return line_breaking_[i].get_min_systems (start, end);
}

vsize
Optimal_breaking::get_max_systems (vsize i, vsize start, vsize end)
{
  line_breaker_args (i, &start, &end);
  return line_breaking_[i].get_max_systems (start, end);
}

Real
Optimal_breaking::page_height (int page_num, bool last)
{
  SCM mod = scm_c_resolve_module ("scm page");
  SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
  SCM make_page = scm_c_module_lookup (mod, "make-page");

  calc_height = scm_variable_ref (calc_height);
  make_page = scm_variable_ref (make_page);

  SCM page = scm_apply_0 (make_page, scm_list_n (
                  book_->self_scm (),
                  ly_symbol2scm ("page-number"), scm_from_int (page_num),
                  ly_symbol2scm ("is-last"), scm_from_bool (last),
                  SCM_UNDEFINED));
  SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
  return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
}

Optimal_break_node
Optimal_breaking::put_systems_on_pages (vsize start,
                                        vsize end,
					vector<Line_details> const &lines,
                                        vector<vsize> const &div,
                                        int page_number)
{
  bool last = end == breaks_.size () - 1;
  Real page_h = page_height (1, false); // FIXME
  const char *blank_force_str = (last ? "blank-last-page-force" : "blank-page-force");
  Real blank_force = robust_scm2double (book_->paper_->c_variable (blank_force_str), 0);
  Spacing_result result = space_systems_on_min_pages (lines, page_h, blank_force);

  Optimal_break_node ret;
  ret.prev_ = start - 1;
  ret.break_pos_ = end;
  ret.first_page_number_ = page_number;
  ret.page_count_ = result.force_.size ();
  ret.force_ = 0;
  for (vsize i = 0; i < result.force_.size (); i++)
    ret.force_ += fabs (result.force_[i]);

  ret.penalty_ = result.penalty_;
  ret.div_ = div;
  ret.system_count_ = result.systems_per_page_;

  ret.too_many_lines_ = true;
  ret.line_force_ = 0;
  for (vsize i = 0; i < lines.size (); i++)
    {
      ret.line_force_ += fabs (lines[i].force_);
      if (lines[i].force_ < 0)
	ret.too_many_lines_ = false;
    }
  return ret;
}

void
Optimal_breaking::calc_subproblem(vsize i)
{
  vsize end = i + 1;
  Optimal_break_node best;
  Optimal_break_node cur;
  Optimal_break_node this_start_best;
  vsize prev_best_system_count = 0;

  for (vsize start = end - 1; start != VPOS; start--)
    {
      if (start > 0 && best.demerits_ < state_[start-1].demerits_)
        continue;

      int p_num = 1;
      if (start > 0)
        {
          /* if the last node has an odd number of pages and is not the first page,
             add a blank page */
          int p_count = state_[start-1].page_count_;
          int f_p_num = state_[start-1].first_page_number_;
          p_num = f_p_num + p_count + ((f_p_num > 1) ? p_count % 2 : 0);
        }

      vector<vsize> min_systems;
      vector<vsize> max_systems;
      vsize min_system_count = 0;
      vsize max_system_count = 0;
      this_start_best.demerits_ = infinity_f;
      calc_system_count_bounds (start, end, &min_systems, &max_systems);

      /* heuristic: we've prepended some music, only the first system is allowed
         to get more lines */
      if (this_start_best.page_count_ == 2 && this_start_best.div_.size ())
        {
          vsize ds = max_systems.size () - this_start_best.div_.size ();
          for (vsize i = ds + 1; i < max_systems.size (); i++)
            {
              assert (this_start_best.div_[i - ds] <= max_systems[i]);
              max_systems[i] = this_start_best.div_[i - ds];
            }
        }

      for (vsize i = 0; i < min_systems.size (); i++)
        {
          min_system_count += min_systems[i];
          max_system_count += max_systems[i];
        }

      bool ok_page = true;

      /* heuristic: we've just added a breakpoint, we'll need at least as
         many systems as before */
      min_system_count = max (min_system_count, prev_best_system_count);
      for (vsize sys_count = min_system_count; sys_count <= max_system_count && ok_page; sys_count++)
        {
          vector<vector<vsize> > div;
          vector<vsize> blank;
          bool found = false;
          divide_systems (sys_count, min_systems, max_systems, &div, &blank);

          for (vsize d = 0; d < div.size (); d++)
            {
	      vector<Line_details> line;
	      /* repeat each score for the number of systems it has */
	      for (vsize i = next_system (start); i <= breaks_[end].sys_; i++)
		{
		  vector<Line_details> l = get_line_details (i,
							     div[d][i - next_system (start)],
							     start, end);
		  for (vsize j = 0; j < l.size (); j++)
		    line.push_back (l[j]);
		}


              cur = put_systems_on_pages (start, end, line, div[d], p_num);

              if (cur.page_count_ > 2 &&
		  (start < end - 1 || (!isinf (this_start_best.demerits_)
				       && cur.page_count_ + cur.page_count_ % 2
				          > this_start_best.page_count_ + this_start_best.page_count_ % 2)))
                {
                  ok_page = false;
                  break;
                }
	      cur.demerits_ = calc_demerits (cur);

              if (cur.demerits_ < this_start_best.demerits_)
                {
                  found = true;
                  this_start_best = cur;
                  prev_best_system_count = sys_count;
                }
            }
          if (!found && this_start_best.too_many_lines_)
            break;
        }
      if (isinf (this_start_best.demerits_))
        {
          assert (!isinf (best.demerits_) && start < end - 1);
          break;
        }
      if (this_start_best.demerits_ < best.demerits_)
        best = this_start_best;
    }
  state_.push_back (best);
}

SCM
Optimal_breaking::solve ()
{
  state_.clear ();
  message (_f ("Calculating page and line breaks (%d possible page breaks)...",
               (int)breaks_.size () - 1) + " ");
  for (vsize i = 0; i < breaks_.size () - 1; i++)
    {
      calc_subproblem (i);
      progress_indication (string ("[") + to_string (i + 1) + "]");
    }
  progress_indication ("\n");

  vector<Optimal_break_node> breaking;
  int i = state_.size () - 1;
  while (i >= 0)
    {
      breaking.push_back (state_[i]);
      i = state_[i].prev_;
    }
  reverse (breaking);

  message (_ ("Drawing systems..."));
  SCM systems = make_lines (&breaking);
  return make_pages (breaking, systems);
}

/* do the line breaking in all the scores and return a big list of systems */
SCM
Optimal_breaking::make_lines (vector<Optimal_break_node> *psoln)
{
  vector<Optimal_break_node> &soln = *psoln;
  for (vsize n = 0; n < soln.size (); n++)
    {
      vsize start = n > 0 ? soln[n-1].break_pos_ : 0;
      vsize end = soln[n].break_pos_;

      /* break each score into pieces */
      for (vsize i = next_system (start); i <= breaks_[end].sys_; i++)
        {
          vsize d = i - next_system (start);
          if (all_[i].pscore_)
            {
              vector<Column_x_positions> line_brk;

              line_brk = get_line_breaks (i, soln[n].div_[d], start, end);
              all_[i].pscore_->root_system ()->break_into_pieces (line_brk);
              assert (line_brk.size () == soln[n].div_[d]);
            }
        }
    }
  SCM ret = SCM_EOL;
  SCM *tail = &ret;
  for (vsize i = 0; i < all_.size (); i++)
    {
      if (all_[i].pscore_)
        for (SCM s = scm_vector_to_list (all_[i].pscore_->root_system ()->get_paper_systems ());
              scm_is_pair (s); s = scm_cdr (s))
          {
            *tail = scm_cons (scm_car (s), SCM_EOL);
            tail = SCM_CDRLOC (*tail);
          }
      else
        {
          *tail = scm_cons (all_[i].prob_->self_scm (), SCM_EOL);
          all_[i].prob_->unprotect ();
          tail = SCM_CDRLOC (*tail);
        }
    }
  return ret;
}

SCM
Optimal_breaking::make_pages (vector<Optimal_break_node> const &soln, SCM systems)
{
  SCM prev_page = SCM_BOOL_F;
  SCM make_page = ly_lily_module_constant ("make-page-from-systems");
  SCM book = book_->self_scm ();
  bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
  bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
  SCM ret = SCM_EOL;

  for (vsize i = 0; i < soln.size (); i++)
    {
      for (vsize j = 0; j < soln[i].page_count_; j++)
        {
          SCM page_num = scm_from_int (soln[i].first_page_number_ + j);
          SCM last = scm_from_bool (i == soln.size () - 1 && j == soln[i].page_count_ - 1);
          SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
          SCM lines = SCM_EOL;

          for (vsize k = 0; k < soln[i].system_count_[j] && systems != SCM_EOL; k++, systems = scm_cdr(systems))
            lines = scm_cons (scm_car (systems), lines);
          lines = scm_reverse (lines);

          SCM page = scm_apply_0 (make_page,
                      scm_list_n (book, lines, page_num, prev_page, ragged, last, SCM_UNDEFINED));
          ret = scm_cons (page, ret);
        }
      if (i > 0 && i < soln.size () - 1 && soln[i].page_count_ % 2)
        {
          /* add a blank page */
          SCM page_num = scm_from_int (soln[i].first_page_number_ + soln[i].page_count_);
          SCM page = scm_apply_0 (make_page,
                      scm_list_n (book, SCM_EOL, page_num, prev_page, ragged_all, SCM_BOOL_F, SCM_UNDEFINED));
          ret = scm_cons (page, ret);
        }
    }
  return scm_reverse (ret);
}

void
Optimal_breaking::create_system_list ()
{
  breaks_.push_back (Break_position ());

  SCM specs = book_->get_system_specs ();
  for (SCM s = specs; s != SCM_EOL; s = scm_cdr (s))
    {
      if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
        {
          /* add a breakpoint at the end of the last score, if necessary */
          if (all_.size () && all_.back ().pscore_)
            breaks_.push_back (Break_position (all_.size () - 1,
                                               all_.back ().score_break_count_));

          vector<vsize> score_brk = find_page_break_indices (ps);
          all_.push_back (System_spec (ps, score_brk.size () + 1));

          for (vsize i = 0; i < score_brk.size(); i++)
            breaks_.push_back (Break_position (all_.size () - 1, i + 1));

          /* include a line breaker at the start of the score */
          score_brk.insert (score_brk.begin (), 0);
          line_breaking_.push_back (Constrained_breaking (score_brk));
          line_breaking_.back ().set_pscore (ps);
        }
      else
        {
          Prob *pb = unsmob_prob (scm_car (s));
          assert (pb);

          pb->protect ();
          // ignore penalties (from break-before) in favour of using \pageBreak at the
          // end of the score
          if (all_.size () && all_.back ().pscore_)
            breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_));
          all_.push_back (System_spec (pb));
          line_breaking_.push_back (Constrained_breaking ());
        }
    }

  /* add the ending breakpoint */
  if (all_.back ().pscore_)
    breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_));
  else
    breaks_.push_back (Break_position (all_.size () - 1));
}

vector<vsize>
Optimal_breaking::find_page_break_indices(Paper_score *pscore)
{
  vector<Grob*> all = pscore->root_system ()->columns ();
  vector<vsize> ret;

  /* we don't include breaks at the beginning and end */
  for (vsize i = 0; i < all.size () - 1; i++)
    if (scm_is_symbol (all[i]->get_property ("page-turn-permission")))
      ret.push_back(i);

  return ret;
}

void
Optimal_breaking::calc_system_count_bounds (vsize start, vsize end,
                                            vector<vsize> *min,
                                            vector<vsize> *max)
{
  for (vsize i = next_system (start); i <= breaks_[end].sys_; i++)
    {
      if (all_[i].pscore_)
        {
          min->push_back (get_min_systems (i, start, end));
          max->push_back (get_max_systems (i, start, end));
        }
      else
        {
          min->push_back (1);
          max->push_back (1);
        }
    }
}

/* calculate all possible ways of dividing system_count between the System_specs */
void
Optimal_breaking::divide_systems (vsize system_count,
                                  vector<vsize> const &min_sys,
                                  vector<vsize> const &max_sys,
                                  vector<vector<vsize> > *result,
                                  vector<vsize> *cur_division)
{
  vsize my_index = cur_division->size ();
  vsize others_min = 0;
  vsize others_max = 0;

  for (vsize i = my_index + 1; i < min_sys.size (); i++)
    {
      others_min += min_sys[i];
      others_max += max_sys[i];
    }
  others_max = min (others_max, system_count);
  vsize real_min = max (min_sys[my_index], system_count - others_max);
  vsize real_max = min (max_sys[my_index], system_count - others_min);

  assert (real_min <= real_max);
  assert (real_min > 0);
  for (vsize i = real_min; i <= real_max; i++)
    {
      cur_division->push_back (i);
      if (my_index == min_sys.size () - 1)
        result->push_back (*cur_division);
      else
        divide_systems (system_count - i, min_sys, max_sys, result, cur_division);
      cur_division->pop_back ();
    }
}