/*
  optimal-breaking.hh -- break lines and pages optimally
  for a whole Paper_book.

  source file of the GNU LilyPond music typesetter

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

#ifndef OPTIMAL_BREAKING_HH
#define OPTIMAL_BREAKING_HH

#include "constrained-breaking.hh"
#include "lily-guile.hh"

/* Either a paper-score, markup or header. For paper scores, we record the
   size of a single system. For the others, we record the size of the entire
   thing. */
struct System_spec
{
  System_spec (Paper_score*, int);
  System_spec (Prob*);
  System_spec ();

  Paper_score *pscore_;
  Prob *prob_;

  vsize score_break_count_; /* for scores, this is the number of start-points our line-
                               breaker has */
};

struct Break_position
{
  vsize sys_; /* the index in our all_ list */
  vsize score_break_; /* if sys_ is a score, then we start at the score_brk_'th
                         possible page-break in the score */

  Break_position (vsize s=VPOS, vsize brk=VPOS)
  {
    sys_ = s;
    score_break_ = brk;
  }
};

/*
  A node of the sub-algorithm (the problem of spacing a given set of systems
  over a given number of pages)
 */
struct System_spacing_node
{
  Real force_;
  Real turn_penalty_;
  Real demerits_;

  vsize prev_;
  vsize system_count_;

  System_spacing_node ()
  {
    force_ = infinity_f;
    turn_penalty_ = 0;
    demerits_ = infinity_f;
    prev_ = VPOS;
    system_count_ = VPOS;
  }
};

/*
  A much simplified rods-and-springs problem.
 */
struct Page_spacing
{
  Real force_;
  Real page_height_;
  Real rod_height_;
  Real spring_len_;
  Real spring_space_;
  Real inverse_spring_k_;

  Line_details last_line_;

  Page_spacing ()
    {
      page_height_ = 0;
      clear ();
    }

  void calc_force ();

  void append_system (const Line_details &line);
  void prepend_system (const Line_details &line);
  void clear ();
};

/*
   Helper to trace back an optimal path
 */
struct Optimal_break_node
{
  vsize prev_;
  int first_page_number_;
  vsize page_count_;

  Real force_;
  Real penalty_;

  Real line_force_;
  Real line_penalty_; // FIXME: remove this?

  /* true if every score here is too widely spaced */
  bool too_many_lines_;

  /* unlike the Gourlay breaker, this is the sum of all demerits up to,
     and including, this page */
  Real demerits_;
  vsize break_pos_; /* index into breaks_ */

  vector<vsize> div_;  /* our division of systems between scores on this page */
  vector<vsize> system_count_; /* systems per page */

  Optimal_break_node ()
  {
    prev_ = break_pos_ = VPOS;
    penalty_ = force_ = 0;
    line_penalty_ = line_force_ = 0;
    demerits_ = infinity_f;
    first_page_number_ = 0;
    too_many_lines_ = false;
  }

  void print () const
  {
    printf ("prev break %d, demerits %f\n",
	    (int)prev_, demerits_);
  }
};

/*
  A dynamic programming solution to breaking pages
 */
class Optimal_breaking
{
public:
  SCM solve ();

  Optimal_breaking (Paper_book *pb);

private:
  std::vector<Optimal_break_node> state_;
  std::vector<Break_position> breaks_;
  std::vector<System_spec> all_;
  std::vector<Constrained_breaking> line_breaking_;

  Paper_book *book_;

  Real page_height (int page_number, bool last);
  vsize next_system (vsize starting_break_index) const;

  Optimal_break_node put_systems_on_pages (vsize start,
                                           vsize end,
					   vector<Line_details> const &lines,
                                           vector<vsize> const &system_div,
                                           int page_number);

  void create_system_list ();
  std::vector<vsize> find_page_break_indices (Paper_score *pscore);

  SCM make_lines (vector<Optimal_break_node> *breaks);
  SCM make_pages (vector<Optimal_break_node> const &breaks, SCM systems);

  void calc_system_count_bounds (vsize start, vsize end,
                                 vector<vsize> *min,
                                 vector<vsize> *max);

  void divide_systems (vsize system_count, vector<vsize> const &min,
                                           vector<vsize> const &max,
                                           vector<vector<vsize> > *result,
                                           vector<vsize> *cur);

  Real calc_demerits (Optimal_break_node const &me);

  void calc_subproblem (vsize i);

  void line_breaker_args (vsize i, vsize *break_st, vsize *break_end);
  vsize get_min_systems (vsize sys, vsize break_start, vsize break_end);
  vsize get_max_systems (vsize sys, vsize break_start, vsize break_end);
  std::vector<Column_x_positions> get_line_breaks (vsize sys, vsize sys_count, vsize st, vsize end);
  std::vector<Line_details> get_line_details (vsize sys, vsize sys_count, vsize start_break, vsize end_break);
};
#endif /* OPTIMAL_BREAKING_HH */