/*
  page-spacing.cc - implement routines for spacing
  systems vertically on pages

  source file of the GNU LilyPond music typesetter

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

#include "page-spacing.hh"

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

  Line_details last_line_;

  Page_spacing (Real page_height)
    {
      page_height_ = page_height;
      clear ();
    }

  void calc_force ();

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

void
Page_spacing::calc_force ()
{
  if (rod_height_ - last_line_.bottom_padding_ >= page_height_ || !inverse_spring_k_)
    force_ = infinity_f;
  else
    force_ = (page_height_ - rod_height_ - last_line_.bottom_padding_ - spring_len_) / inverse_spring_k_;
}

void
Page_spacing::append_system (const Line_details &line)
{
  rod_height_ += last_line_.padding_;

  rod_height_ += line.extent_;
  spring_len_ += line.space_;
  inverse_spring_k_ += line.inverse_hooke_;

  last_line_ = line;

  calc_force ();
}

void
Page_spacing::prepend_system (const Line_details &line)
{
  if (rod_height_)
    rod_height_ += line.padding_;
  else
    last_line_ = line;

  rod_height_ += line.extent_;
  spring_len_ += line.space_;
  inverse_spring_k_ += line.inverse_hooke_;

  calc_force ();
}

void
Page_spacing::clear ()
{
  force_ = rod_height_ = spring_len_ = 0;
  inverse_spring_k_ = 0;
  last_line_.padding_ = 0;
}

/* for each forbidden page break, merge the systems around it into one system. */
static vector<Line_details>
compress_lines (const vector<Line_details> &orig)
{
  vector<Line_details> ret;

  for (vsize i = 0; i < orig.size (); i++)
    {
      if (i < orig.size () - 1 && orig[i].page_permission_ == SCM_EOL)
	{
	  Line_details compressed = orig[i+1];
	  compressed.extent_ += orig[i].extent_ + orig[i].padding_;
	  compressed.space_ += orig[i].space_;
	  compressed.inverse_hooke_ += orig[i].inverse_hooke_;
	  /* we don't need the force_ field for the vertical spacing,
	     so we use force_ = -1 to signal that the line was compressed.
	     This makes uncompression much easier. */
	  compressed.force_ = -1;
	  ret.push_back (compressed);
	  i++;
	}
      else
	{
	  ret.push_back (orig[i]);
	  ret.back ().force_ = 1;
	}
    }
  return ret;
}

/* translate the number of systems-per-page into something meaningful for
   the uncompressed lines.
*/
static vector<vsize>
uncompress_solution (vector<vsize> const &sol,
		     vector<Line_details> const &compressed)
{
  vector<vsize> ret;
  vsize start_sys = 0;

  for (vsize i = 0; i < sol.size (); i++)
    {
      int compressed_count = 0;
      for (vsize j = start_sys; j < start_sys + sol[i]; j++)
	if (compressed[j].force_ < 0)
	  compressed_count++;

      ret.push_back (sol[i] + compressed_count);
      start_sys += sol[i];
    }
  return ret;
}

/* the cases for page_count = 1 or 2 can be done in O(n) time. Since they
   are by far the most common cases, we have special functions for them */
static Spacing_result
space_systems_on_1_page (vector<Line_details> const &lines, Real page_height)
{
  Page_spacing space (page_height);
  Spacing_result ret;

  for (vsize i = 0; i < lines.size (); i++)
    space.append_system (lines[i]);

  ret.systems_per_page_.push_back (lines.size ());
  ret.force_.push_back (space.force_);
  ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
  ret.demerits_ = fabs (ret.force_.back ()) + ret.penalty_;

  return ret;
}

static Spacing_result
space_systems_on_2_pages (vector<Line_details> const &lines, Real page_height)
{
  /* if there is a forced break, this reduces to 2 1-page problems */
  SCM sym = ly_symbol2scm ("force");
  for (vsize i = 0; i < lines.size () - 1; i++)
    if (lines[i].page_permission_ == sym)
      {
	vector<Line_details> lines1 (lines.begin (), lines.begin () + i + 1);
	vector<Line_details> lines2 (lines.begin () + i + 1, lines.end ());
	Spacing_result p1 = space_systems_on_1_page (lines1, page_height);
	Spacing_result p2 = space_systems_on_1_page (lines2, page_height);

	p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
	p1.force_.push_back (p2.force_[0]);
	p1.penalty_ += p2.penalty_ - lines[i].turn_penalty_;
	return p1;
      }

  vector<Real> page1_force;
  vector<Real> page2_force;
  Page_spacing page1 (page_height);
  Page_spacing page2 (page_height);

  page1_force.resize (lines.size () - 1);
  page2_force.resize (lines.size () - 1);

  for (vsize i = 0; i < page1_force.size (); i++)
    {
      page1.append_system (lines[i]);
      page2.prepend_system (lines[lines.size () - 1 - i]);
      page1_force[i] = page1.force_;
      page2_force[page2_force.size () - 1 - i] = page2.force_;
    }

  vsize best_sys_count = 1;
  Real best_demerits = infinity_f;
  for (vsize i = 0; i < page1_force.size (); i++)
    {
      Real dem = fabs (page1_force[i]) + fabs (page2_force[i]) + lines[i+1].page_penalty_;
      if (dem < best_demerits)
	{
	  best_demerits = dem;
	  best_sys_count = i+1;
	}
    }

  Spacing_result ret;
  ret.systems_per_page_.push_back (best_sys_count);
  ret.systems_per_page_.push_back (lines.size () - best_sys_count);
  ret.force_.push_back (page1_force[best_sys_count-1]);
  ret.force_.push_back (page2_force[best_sys_count-1]);
  ret.penalty_ = lines[best_sys_count-1].page_penalty_
    + lines.back ().page_penalty_
    + lines.back ().turn_penalty_;
  ret.demerits_ = best_demerits;

  return ret;
}

/* for page_count > 2, we use a dynamic algorithm similar to
   constrained-breaking -- we have a class that stores the intermediate
   calculations so they can be reused for querying different page counts.
*/

struct Page_spacing_node
{
  Page_spacing_node ()
  {
    demerits_ = infinity_f;
    force_ = infinity_f;
    penalty_ = infinity_f;
    prev_ = VPOS;
  }

  Real demerits_;
  Real force_;
  Real penalty_;
  vsize prev_;
};

class Page_spacer
{
public:
  Page_spacer (vector<Line_details> const &lines, Real page_height);
  Spacing_result solve (vsize page_count);

private:
  Real page_height_;
  vector<Line_details> lines_;
  vector<Page_spacing_node> state_;
  vsize max_page_count_;

  void resize (vsize page_count);
  bool calc_subproblem (vsize page, vsize lines);
};

Page_spacer::Page_spacer (vector<Line_details> const &lines, Real page_height)
  : lines_ (lines)
{
  page_height_ = page_height;
  max_page_count_ = 0;
}

Spacing_result
Page_spacer::solve (vsize page_count)
{
  if (page_count > max_page_count_)
    resize (page_count);

  Spacing_result ret;
  ret.force_.resize (page_count);
  ret.systems_per_page_.resize (page_count);

  vsize rank = lines_.size ();
  vsize system = lines_.size () - 1;

  ret.penalty_ = state_[(page_count-1)*rank + system].penalty_
    + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;

  for (vsize p = page_count - 1; p != VPOS; p--)
    {
      assert (system != VPOS);

      Page_spacing_node const &ps = state_[p*rank + system];
      ret.force_[p] = ps.force_;
      ret.demerits_ += fabs (ps.force_);
      if (p == 0)
	ret.systems_per_page_[p] = system + 1;
      else
	ret.systems_per_page_[p] = system - ps.prev_;
      system = ps.prev_;
    }
  ret.demerits_ += ret.penalty_;
  return ret;
}

void
Page_spacer::resize (vsize page_count)
{
  assert (page_count > 0);

  if (max_page_count_ >= page_count)
    return;

  state_.resize (page_count * lines_.size ());
  for (vsize page = max_page_count_; page < page_count; page++)
    for (vsize line = page; line < lines_.size (); line++)
      if (!calc_subproblem (page, line))
	break;

  max_page_count_ = page_count;
}

bool
Page_spacer::calc_subproblem (vsize page, vsize line)
{
  Page_spacing space (page_height_);
  vsize rank = lines_.size ();

  Page_spacing_node &cur = state_[page*rank + line];

  for (vsize page_start = line; page_start >= page && page_start != VPOS; page_start--)
    {
      Page_spacing_node const *prev = page > 0 ? &state_[(page-1)*rank + page_start - 1] : 0;

      space.prepend_system (lines_[page_start]);
      if (isinf (space.force_))
	break;

      if (page == 0 && page_start > 0)
	continue;

      Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
      Real penalty = 0;
      if (page_start > 0)
	penalty = lines_[page_start-1].page_penalty_
	  + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;

      dem += penalty;
      if (dem < cur.demerits_)
	{
	  cur.demerits_ = dem;
	  cur.force_ = space.force_;
	  cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
	  cur.prev_ = page_start - 1;
	}
    }
  return !isinf (cur.demerits_);
}

static vsize
min_pages (vector<Line_details> const &lines, Real page_height)
{
  vsize ret = 1;
  Real cur_rod_height = 0;
  SCM sym = ly_symbol2scm ("force");

  for (vsize i = 0; i < lines.size (); i++)
    {
      Real next_height = cur_rod_height + lines[i].extent_
	+ ((i > 0 && cur_rod_height > 0) ? lines[i-1].padding_: 0);

      if ((next_height > page_height && cur_rod_height > 0)
	  || (i > 0 && lines[i-1].page_permission_ == sym))
	{
	  ret++;
	  cur_rod_height = lines[i].extent_;
	}
      else
	cur_rod_height = next_height;
    }
  return ret;
}

Spacing_result
space_systems_on_min_pages (vector<Line_details> const &lines,
			    Real page_height,
			    Real odd_pages_penalty)
{
  vector<Line_details> compressed_lines = compress_lines (lines);
  vsize min_p = min_pages (compressed_lines, page_height);
  Spacing_result ret;

  if (min_p == 1)
    {
      Spacing_result candidate1 = space_systems_on_1_page (compressed_lines, page_height);
      candidate1.force_.back () += odd_pages_penalty;
      candidate1.demerits_ += odd_pages_penalty;
      if (compressed_lines.size () == 1)
	ret = candidate1;
      else
	{
	  Spacing_result candidate2 = space_systems_on_2_pages (compressed_lines, page_height);
	  ret = (candidate1.demerits_ < candidate2.demerits_) ?
	    candidate1 : candidate2;
	}
    }
  else if (min_p == 2)
    ret = space_systems_on_2_pages (compressed_lines, page_height);
  else
    {
      Page_spacer ps (lines, page_height);
      Spacing_result candidate1 = ps.solve (min_p);
      if (min_p % 2 == 0 || min_p == lines.size ())
	ret = candidate1;
      else
	{
	  Spacing_result candidate2 = ps.solve (min_p + 1);
	  candidate1.force_.back () += odd_pages_penalty;
	  candidate1.demerits_ += odd_pages_penalty;
	  ret = (candidate1.demerits_ < candidate2.demerits_) ?
	    candidate1 : candidate2;
	}
    }
  ret.systems_per_page_ = uncompress_solution (ret.systems_per_page_, compressed_lines);
  return ret;
}