/**
   @file validator.cc 
   @brief Validates a solution for an instance on the Generalized
   Balanced Academic Curriculum Problem (GBAPC) for the formulation
   proposed in [Di Gaspero and Schaerf, 2008, submitted to HM-2008]

   This file contains all class and function definitions of the validator.
   It is compiled on Linux (or Windows+Cygwin) with GNU C++ with the command:
   g++ -o validator validator.cc
   It is used with the command (e.g., on instance UD1):
     ./validator <input_file> <solution_file> [cost_formulation (default: quadratic)]
   For example on instance UD1 and solution my_sol.out
   ./validator UD1.gbac my_sol.out
   ./validator UD1.gbac my_sol.out linear

   The input and output files are assumed to be correct (but some
   errors are caught).

   @author Andrea Schaerf (schaerf@uniud.it), 
   Luca Di Gaspero (l.digaspero@uniud.it)
   @version 1.1
   @date 30 December 2009
*/

#include <vector>
#include <string>
#include <iostream>
#include <cmath>
#include <fstream>
#include <stdexcept>
#include <cstring>

using namespace std;

class Course
{
  friend class BACP_Input;
private:
  string name;
  unsigned credits;
};

class Curriculum 
{
  friend class BACP_Input;
  friend ostream& operator<<(ostream&, const Curriculum&);
public:
  void AddMember(unsigned e) { members.push_back(e); }
private:
  string name;
  vector<unsigned> members;
  double avg_credits;
  unsigned floor_avg_credits, ceil_avg_credits;
};

class BACP_Input
{
  friend ostream& operator<<(ostream& os, const BACP_Input& in);
public:
  BACP_Input(string file_name);
  unsigned Periods() const { return periods; }
  unsigned Years() const { return years; }
  unsigned PeriodsPerYear() const { return periods_per_year; }
  unsigned Courses() const { return courses; }
  unsigned Curricula() const { return curricula; }
  unsigned MinCourses() const { return min_courses; }
  unsigned MaxCourses() const { return max_courses; }

  unsigned CourseCurricula(unsigned c) const { return curricula_list[c].size(); }
  unsigned CourseCurriculum(unsigned c, unsigned a) const { return curricula_list[c][a]; }
  bool Undesired(unsigned c, unsigned p) const { return undesired[c][p]; }

  unsigned FloorAvgCredits(unsigned q) const { return curricula_vect[q].floor_avg_credits; }
  unsigned CeilAvgCredits(unsigned q) const { return curricula_vect[q].ceil_avg_credits; }
  string CurriculumName(unsigned q) const { return curricula_vect[q].name; }

  unsigned Credits(unsigned c) const { return course_vect[c].credits; }
  string CourseName(unsigned c) const { return course_vect[c].name; }
  bool Prerequisite(unsigned c1, unsigned c2) const { return prerequisite[c1][c2]; }
  unsigned CourseBeforeNumber(unsigned c) const { return course_before_list[c].size(); }
  unsigned CourseAfterNumber(unsigned c) const { return course_after_list[c].size(); }
  unsigned CourseBeforeList(unsigned c, unsigned a) const { return course_before_list[c][a]; }
  unsigned CourseAfterList(unsigned c, unsigned a) const { return course_after_list[c][a]; }

  int CourseIndex(string course_name) const;
private:
  unsigned periods, years, periods_per_year, courses, curricula,  min_courses, max_courses;
	   
  vector<Course> course_vect;
  vector<vector<bool> > prerequisite;
  vector<Curriculum> curricula_vect;
  vector<vector<bool> > undesired;

  // redundant data (for accelerating access)
  vector<vector<unsigned> > course_before_list;
  vector<vector<unsigned> > course_after_list;
  vector<vector<unsigned> > curricula_list;
  vector<vector<bool> > course_curriculum_membership;
};


class BACP_Output
{
  friend ostream& operator<<(ostream& os, const BACP_Output& st);
  friend bool operator==(const BACP_Output& st1, const BACP_Output& st2);
public:
  BACP_Output(const BACP_Input& i, string file_name);
  BACP_Output& operator=(const BACP_Output& st);
  unsigned operator[](unsigned c) const { return course_period[c]; }
  unsigned& operator[](unsigned c) { return course_period[c]; }
  unsigned CreditsPerPeriod(unsigned q, unsigned p) const { return credits_per_period[q][p]; }
  unsigned CoursesPerPeriod(unsigned q, unsigned p) const { return courses_per_period[q][p]; }
  void AddCourseToPeriod(unsigned c, unsigned p);
  void RemoveCourseFromPeriod(unsigned c, unsigned p); 
  const BACP_Input& in;
private:
  vector<unsigned> course_period; 
  // redundant data  (for accelerating access)
  vector<vector<unsigned> > credits_per_period, courses_per_period;
};

class Validator
{
public:
  Validator(const BACP_Input & i, const BACP_Output & s, bool q) : in(i), st(s), QUADRATIC(q), PREFERENCE_COST(q?5:22), SPREAD_COST(q?1:10) {}
  void PrintCosts(ostream& os) const;
  void PrintTotalCost(ostream& os) const;
  void PrintViolations(ostream& os) const;
private:
  unsigned CostsOnLoadSpread() const;	       
  unsigned CostsOnMinMaxLoad() const;	       
  unsigned CostsOnPrerequisites() const;	       
  unsigned CostsOnPreferences() const;     

  void PrintViolationsOnLoadSpread(ostream& os) const;
  void PrintViolationsOnMinMaxLoad(ostream& os) const;
  void PrintViolationsOnPrerequisites(ostream& os) const;
  void PrintViolationsOnPreferences(ostream& os) const;

  const BACP_Input& in;  
  const BACP_Output& st; 
  const bool QUADRATIC;
  const unsigned PREFERENCE_COST;
  const unsigned SPREAD_COST;
};

// END OF HEADER

int main(int argc, char* argv[])
{
  bool quadratic;
  if (argc != 3 && argc != 4)
    {
      string error = "Usage:  " + string(argv[0]) + " <input_file> <solution_file> [cost_formulation (default: quadratic)]";
      throw logic_error(error); 	
    }
  else if (argc == 3 || strcmp(argv[3], "quadratic") == 0)
    quadratic = true;
  else if (strcmp(argv[3], "linear") == 0)    
    quadratic = false; // linear costs
  else
    throw logic_error("Supported cost fornulations: linear and quadratic"); 	

  BACP_Input input(argv[1]);
  BACP_Output output(input,argv[2]);
  Validator validator(input, output, quadratic);

  validator.PrintViolations(cout);
  cout << endl;
  validator.PrintCosts(cout);
  cout << endl;
  cout << "Summary: ";
  validator.PrintTotalCost(cout);
  return 0;
}

BACP_Input::BACP_Input(string file_name)
{
  ifstream is(file_name.c_str());
  if (is.fail())
    throw runtime_error("Cannot open input file!"); 	
  const unsigned BUF_SIZE = 256;
  char buffer[BUF_SIZE];
  unsigned num_prereq, curriculum_size, num_undesired, total_credits = 0;
  unsigned c, c1, c2, c3, a2, a3, p, q, pr, y;
  int val;
  string course_name, course_name1, course_name2;
  string error;

  is.getline(buffer,BUF_SIZE);
  is >> buffer >> years;
  is >> buffer >> periods_per_year;
  is >> buffer >> courses;
  is >> buffer >> curricula;
  is >> buffer >> min_courses >> max_courses;
  is >> buffer >> num_prereq;
  is >> buffer >> num_undesired;

  periods = years * periods_per_year;

  course_vect.resize(courses);
  curricula_vect.resize(curricula); 

  prerequisite.resize(courses,vector<bool>(courses,false));
  undesired.resize(courses,vector<bool>(periods,false));

  curricula_list.resize(courses);
  course_curriculum_membership.resize(courses, vector<bool>(curricula,false));
  course_before_list.resize(courses);
  course_after_list.resize(courses);

  is >> buffer;

  for (c = 0; c < courses; c++)
    {
      is >> course_vect[c].name >> course_vect[c].credits;
    }

  is >> buffer;

  for (q = 0; q < curricula; q++)
    {
      total_credits = 0;
      is >> curricula_vect[q].name >> curriculum_size;
      for (unsigned i1 = 0; i1 < curriculum_size; i1++)
	{
	  is >> course_name;
	  val = CourseIndex(course_name);
	  if (val == -1)
	    {
	      error = "Course " + course_name + " does not exist";
	      throw logic_error(error); 	
	    }
	  else
	    c1 = (unsigned) val;
	  curricula_vect[q].AddMember(c1);
	  course_curriculum_membership[c1][q] = true;
	  curricula_list[c1].push_back(q);
	  total_credits += course_vect[c1].credits;
	}
      
      curricula_vect[q].avg_credits = (double) total_credits / periods;
      curricula_vect[q].floor_avg_credits = (unsigned) floor(curricula_vect[q].avg_credits);
      curricula_vect[q].ceil_avg_credits = (unsigned) ceil(curricula_vect[q].avg_credits);
    }


  is >> buffer;
  for (p = 0; p < num_prereq; p++)
    {
      is >> course_name1 >> course_name2;
      val = CourseIndex(course_name1);
      if (val == -1)
	{
	  error = "Course " + course_name1 + " does not exist";
	  throw logic_error(error); 	
	}
      else
	c1 = (unsigned) val;
      val = CourseIndex(course_name2);
      if (val == -1)
	{
	  error = "Course " + course_name2 + " does not exist";
	  throw logic_error(error); 	
	}
      else
	c2 = (unsigned) val;
      if (prerequisite[c1][c2])
	{
	  error = "Duplicated prerequisite between " + course_name1 + " and " + course_name2;
	  throw logic_error(error); 
	}		  
      prerequisite[c1][c2] = true;
      course_before_list[c2].push_back(c1);
      course_after_list[c1].push_back(c2);
    }

  // Insert transitive precedences
  for (c1 = 0; c1 < courses; c1++)
    for (a2 = 0; a2 < course_after_list[c1].size(); a2++)
      {
	c2 = course_after_list[c1][a2];
	for (a3 = 0; a3 < course_after_list[c2].size(); a3++)
	  {
	    c3 = course_after_list[c2][a3];
	    if (!prerequisite[c1][c3])
	      {
		if (c1 == c3)
		  {
		    error = "Precedence cycle on : " + course_vect[c1].name;
		    throw logic_error(error); 
		  }
		else
		  {
		    prerequisite[c1][c3] = true;
		    course_before_list[c3].push_back(c1);
		    course_after_list[c1].push_back(c3);
		  }
	      }
	  }
      }

  is >> buffer;

  for (pr = 0; pr < num_undesired; pr++)
    {
      is >> course_name >> p;
      val = CourseIndex(course_name);
      if (val == -1)
	{
	  error = "Course " + course_name + " does not exist";
	  throw logic_error(error); 	
	}
      else
	c = (unsigned) val;      
      for (y = 0; y < years; y++)
	undesired[c][p + y*periods_per_year] = true;
    }
  
  is >> buffer;
  is.close();
}

int BACP_Input::CourseIndex(string course_name) const
{
  unsigned c;
  for (c = 0; c < courses; c++)
    if (course_vect[c].name == course_name)
      return c;
  return -1;
}


BACP_Output::BACP_Output(const BACP_Input& my_in, string file_name)
  : in(my_in), course_period(in.Courses()), 
    credits_per_period(in.Curricula(),vector<unsigned>(in.Periods())), 
    courses_per_period(in.Curricula(),vector<unsigned>(in.Periods())) 
{
  ifstream is(file_name.c_str());
  string error;
  if (is.fail())
    throw runtime_error("Cannot open solution file!"); 	

  string course_name;
  unsigned p, i;
  int c;

  for (i = 0; i < in.Courses(); i++)
    {
      is >> course_name >> p; 
      c = in.CourseIndex(course_name);
      if (c == -1)
	{
	  error = "Course " + course_name + " does not exist (in the solution file)";
	  throw runtime_error(error.c_str()); 	
	}
      course_period[c] = p;
      AddCourseToPeriod(c,p);
    }
  is.close();
}

void BACP_Output::AddCourseToPeriod(unsigned c, unsigned p)
{
  unsigned a, q;
  for (a = 0; a < in.CourseCurricula(c); a++)
    {
      q = in.CourseCurriculum(c,a);	 
      courses_per_period[q][p]++;
      credits_per_period[q][p] += in.Credits(c);
    }
}

void BACP_Output::RemoveCourseFromPeriod(unsigned c, unsigned p)
{
  unsigned a, q;
  for (a = 0; a < in.CourseCurricula(c); a++)
    {
      q = in.CourseCurriculum(c,a);	 
      courses_per_period[q][p]--;
      credits_per_period[q][p] -= in.Credits(c);
    }
}
 
ostream& operator<<(ostream& os, const BACP_Output& st)
{
  unsigned c;
  for (c = 0; c < st.in.Courses(); c++)
    os << st[c] << ' ';
  return os;
}

istream& operator>>(istream& is, BACP_Output& st)
{
  unsigned c;
  for (c = 0; c < st.in.Courses(); c++)
    {
      is >> st[c];
      st.AddCourseToPeriod(c,st[c]);
    }
  return is;
}

void Validator::PrintCosts(ostream& os) const
{
  os << "Violations of Period Load (hard) : " <<  CostsOnMinMaxLoad() << endl;
  os << "Violations of Prerequisites (hard) : " <<  CostsOnPrerequisites() << endl;
  os << "Cost of Load Spreading (soft) : " <<  CostsOnLoadSpread() * SPREAD_COST << endl;
  os << "Cost of Preferences (soft) : " <<  CostsOnPreferences() * PREFERENCE_COST << endl;
}

void Validator::PrintTotalCost(ostream& os) const
{
  unsigned violations, total_cost = 0;

  violations = CostsOnMinMaxLoad() + CostsOnPrerequisites();
  total_cost =  CostsOnLoadSpread() * SPREAD_COST + CostsOnPreferences() * PREFERENCE_COST;
  if (violations > 0)
    os << "Violations = " << violations << ", ";
  os <<  "Total Cost = " << total_cost  << endl;
}

void Validator::PrintViolations(ostream& os) const
{
  PrintViolationsOnMinMaxLoad(os);
  PrintViolationsOnPrerequisites(os);
  PrintViolationsOnLoadSpread(os);
  PrintViolationsOnPreferences(os);
}

unsigned Validator::CostsOnLoadSpread() const
{
  unsigned cost = 0, p, q;
  int extra_credits, missing_credits;
  
  for (q = 0; q < in.Curricula(); q++) 
    {
      for (p = 0; p < in.Periods(); p++)
	{  
	  extra_credits = st.CreditsPerPeriod(q,p) - in.CeilAvgCredits(q);
	  missing_credits = in.FloorAvgCredits(q) - st.CreditsPerPeriod(q,p);
	  if (extra_credits > 0)
	    cost += extra_credits * (QUADRATIC?extra_credits:1);	     
	  else if (missing_credits > 0)
	    cost += missing_credits * (QUADRATIC?missing_credits:1);
	}
    }
  return cost;
}
	       
unsigned Validator::CostsOnMinMaxLoad() const
{
  unsigned p, q, cost = 0;
  for (q = 0; q < in.Curricula(); q++) 
    {
      for (p = 0; p < in.Periods(); p++)
	{ 
	  if (st.CoursesPerPeriod(q,p) < in.MinCourses())
	    cost += in.MinCourses() - st.CoursesPerPeriod(q,p);
	  else if (st.CoursesPerPeriod(q,p) > in.MaxCourses())
	    cost += st.CoursesPerPeriod(q,p) - in.MaxCourses();
	}
    }
  return cost;
}
	       
unsigned Validator::CostsOnPrerequisites() const
{
  unsigned c1, c2, a, cost = 0;
  for (c1 = 0; c1 < in.Courses(); c1++)
    {
      for (a = 0; a < in.CourseBeforeNumber(c1); a++)
	{
	  c2 = in.CourseBeforeList(c1,a);
	  if (st[c1] <= st[c2])
	    cost++;
	}
    }
  return cost;
}
	       
unsigned Validator::CostsOnPreferences() const
{
  unsigned c, cost = 0;
  for (c = 0; c < in.Courses(); c++)
    if (in.Undesired(c,st[c]))
      cost++;
  return cost;
}
     

void Validator::PrintViolationsOnLoadSpread(ostream& os) const
{
  unsigned p, q;
  int extra_credits, missing_credits;
  
  for (q = 0; q < in.Curricula(); q++) 
    {
      for (p = 0; p < in.Periods(); p++)
	{  
	  extra_credits = st.CreditsPerPeriod(q,p) - in.CeilAvgCredits(q);
	  missing_credits = in.FloorAvgCredits(q) - st.CreditsPerPeriod(q,p);
	  if (extra_credits > 0)
	    os << "Too many credits (" << st.CreditsPerPeriod(q,p) << '/' << in.CeilAvgCredits(q) << ") for curriculum " 
	       << in.CurriculumName(q) << " in period " 
	       << p << " (cost = " << extra_credits * (QUADRATIC?extra_credits:1) * SPREAD_COST << ")" << endl;
	  else if (missing_credits > 0)
	    os << "Too few credits (" << st.CreditsPerPeriod(q,p) << '/' << in.FloorAvgCredits(q) << ") for curriculum " 
	       << in.CurriculumName(q) << " in period " 
	       << p << " (cost = " << missing_credits * (QUADRATIC?missing_credits:1)  * SPREAD_COST << ")" << endl;
	  
	}
    }
}

void Validator::PrintViolationsOnMinMaxLoad(ostream& os) const
{
  unsigned p, q;
  for (q = 0; q < in.Curricula(); q++) 
    {
      for (p = 0; p < in.Periods(); p++)
	{    
	  if (st.CoursesPerPeriod(q,p) < in.MinCourses())
	    os << "Too few courses (" << st.CoursesPerPeriod(q,p) << ") for curriculum " 
	       << in.CurriculumName(q) << " in period " << p 
	       << " (min = " << in.MinCourses() << ")" << endl;
	  else if (st.CoursesPerPeriod(q,p) > in.MaxCourses())
	    os << "Too many courses (" << st.CoursesPerPeriod(q,p) << ") for curriculum " 
	       << in.CurriculumName(q) << " in period " << p 
	       << " (max = " << in.MaxCourses() << ")" << endl;
	}
    }
}

void Validator::PrintViolationsOnPrerequisites(ostream& os) const
{
  unsigned c1, c2, a;
  for (c1 = 0; c1 < in.Courses(); c1++)
    {
      for (a = 0; a < in.CourseBeforeNumber(c1); a++)
	{
	  c2 = in.CourseBeforeList(c1,a);
	  if (st[c1] <= st[c2])
	    os << "Course " << in.CourseName(c1) << " (" << st[c1] 
	       << ") should be after " << in.CourseName(c2) << " (" << st[c2] << ")" << endl;
	}
    }
}

void Validator::PrintViolationsOnPreferences(ostream& os) const
{
  unsigned c;
  for (c = 0; c < in.Courses(); c++)
    if (in.Undesired(c,st[c]))
      os << "Course " << in.CourseName(c) << " in undesired period " << st[c] << endl;
}