/*
  *
  * rehearsal.cpp:	Source c++ code solving "Scheduling Rehearsal Problem"
  * Implemented by: 	Psallidas Fotis (using naxos project implemented by Nikos Pothitos)
  * std code :		std06170
  * Project Reference:	Logic Programming Project 6.0
  *
  */

#include <naxos.h>
#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include "strtok.h"

using namespace std;
using namespace naxos;

	int
main (int argc, char *argv[])
{

	try  {
		double starttime,endtime;
		unsigned int i,j;
		NsIntVarArray Vars,Dur,SVars,*P,*A,*L,CostArray,*RH,*RL,*C;
		NsProblemManager pm;
		int k;
		NsDeque< NsInt >* Solution = NULL;
		//  Checking input arguments.
		if ( argc  !=  2 )   {
			cerr << "Correct syntax is:\t" << argv[0] << " <input_filename>\n";
			return  1;
		}
		//  Opening input filename, e.g. `rehearsal_data.pl'.
		ifstream  file(argv[1]);
		if ( ! file )   {
			cerr << "Could not open `" << argv[1] << "'\n";
			return  1;
		}
		string  input, tok;
		NsDeque< NsDeque<NsInt> >  players;
		NsDeque<NsInt>             durations;
		//  Reading input file line by line.
		while ( getline(file,input) )    {
			StrTokenizer  tokens(input, "([,]).");
			tok  =  tokens.next();
			if ( tok == "players"  ||  tok == "         " )    {
				players.push_back( NsDeque<NsInt>() );
				while ( ! (tok = tokens.next()).empty() )
					players.back().push_back(atoi(tok.c_str()));
			}  else if ( tok  ==  "durations" )  {  
				while ( ! (tok = tokens.next()).empty() ){
					durations.push_back(atoi(tok.c_str()));
				}
			}  else if ( tok  !=  "" )    {
				cerr << "Unknown predicate `" << tok<< "'\n";
				return  1;
			}
		}

		file.close();

		/* Declare Variables */
		for(i = 0 ; i < durations.size() ; i++){
			Vars.push_back( NsIntVar(pm,0,durations.size()-1));
		}
		P = new NsIntVarArray[players.size()];
	
		/* Basic Constraints */
		pm.add( NsAllDiff(Vars));
		pm.add( Vars[0] < Vars[durations.size()-1] );

		/* Element Duration */
		for(i = 0 ; i < durations.size() ; ++i)
			Dur.push_back(durations[Vars[i]]);

		/* Element Players */
		for(i = 0 ; i < players.size() ; i++)
		for(j = 0 ; j < players[i].size() ; j++)
			P[i].push_back(players[i][Vars[j]]) ;

		/* Declare Arrive and Left lists for every player */
		A = new NsIntVarArray[players.size()];
		L = new NsIntVarArray[players.size()];
		
		
		/*
		 *	For player i
		 *	* if	j == 0 	: Arrive[i][0] = Player[i][0]
		 *	* else (j != 0)	: Arrive[i][j] = (A[i][j-1] or P[i][j])
		 *	Definition of Arrive list can be found in the given paper
		 *		Constraint Programming in Practice:
		 *			Scheduling a Rehearsal
		 */
		for( i = 0 ; i < players.size() ; i++){
			A[i].push_back(P[i][0]);
			for(j = 1 ; j < durations.size() ; j++ ){
				A[i].push_back(A[i][j-1] == 1 || P[i][j] == 1);
			}
		}
		
		RH = new NsIntVarArray[players.size()];
		RL = new NsIntVarArray[players.size()];

		/* 
		 *	For player i
		 *	Reverse P[i] making RH 
		 *	*	if    j == 0 	:   RL[i][0] = RH[i][0] 
		 *	*	else (j != 0)	:   RL[i][j] = (RL[i][j-1] or RH[i][j])	
		 *	Left[i] = Reversed RL[i]
		 *	Definition of Left list can be found in the given paper
		 *		Constraint Programming in Practice:
		 *			Scheduling a Rehearsal
		 */
		for( i = 0 ; i < players.size() ; i++){
			for(k = durations.size()-1 ; k >= 0 ; k--){
				RH[i].push_back(P[i][k]);
			}
			RL[i].push_back(RH[i][0]);
			for(k = 1 ; k < (signed int)durations.size() ; k++){
				RL[i].push_back(RH[i][k] == 1 || RL[i][k-1] == 1);
			}
			for(k = durations.size()-1 ; k >= 0 ; k--){
				L[i].push_back(RL[i][k]);
			}
		}

		/*
		 *	Now that we have declared Arrive and Left lists
		 *	we can declare cost.
		 *	For every player we declare a list C[i]
		 *	which is C[i][j] = [ (Arrive[i][j] or P[i][j]) and ( Left[i][j] or P[i][j] ) and ( P[i][j] == 0 ) ] * Dur[j]
		 *	CostArray is used to host all those C[i][j] and finally Cost is the Sum of CostArray.
	 	 *	Definition of Cost can be found in the given paper
		 *		Constraint Programming in Practice:
		 *			Scheduling a Rehearsal
		 */
		C = new NsIntVarArray[players.size()];
		for(i = 0 ; i < players.size() ; i++){
			for( j = 0 ; j < durations.size() ; j++){
				C[i].push_back( ( ( A[i][j] == 1 || P[i][j] == 1 ) && ( L[i][j] == 1 || P[i][j] == 1 ) && ( P[i][j] == 0 )) * Dur[j]);
			}
			for( j = 0 ; j < durations.size() ; j++){
				CostArray.push_back(C[i][j]);
			}
		}


		/* 
		 *	To further optimize csp
		 *	We transform variables' list so that
		 *	SVars[k] = Vars[i] and SVars[k+1] = Vars[Vars.size-1-i]
		 *	Where Svars is the final variables' set.
		 */
		for(i = 0 ,j = Vars.size()-1 ; i <= j ; i++,j--){
			SVars.push_back(Vars[i]);
			if(i!=j){
				SVars.push_back(Vars[Vars.size()-1-i]);
			}
		}
		pm.addGoal( new NsgLabeling(SVars) );
		NsIntVar Cost = NsSum(CostArray);
		pm.minimize(Cost);
				
		starttime = clock();
	
		/* solve rehearsal problem */

		while (pm.nextSolution() != false){
			if( Solution != NULL) delete Solution;
			Solution = new NsDeque< NsInt>();
			for(i = 0 ; i < durations.size() ; i++){
				Solution->push_back(Vars[i].value()+1);
			}
			cout<<"Found Solution with cost: "<<Cost<<endl;
		
		}
		endtime = clock();
		cout<<"Solution: [";
		for(i = 0 ; i < durations.size() ; i++){
			cout<<" ["<<(*Solution)[i]<<"]";
			if(i!=durations.size()-1)cout<<",";
		}
		cout<<" ]"<<endl;
		cout<<"Time: "<<(endtime-starttime)/CLOCKS_PER_SEC<<" sec"<<endl;
	}  catch (exception& exc)  {
		cerr << exc.what() << "\n";
	}  catch (...)  {
		cerr << "Unknown exception" << "\n";
	}
}