/***************************************************************************
                          main.cpp  -  description
                             -------------------
    begin                : Son Apr 14 16:50:49 CEST 2002
    copyright            : (C) 2002 by Sven Klauke
    email                : sklauke@wiwi.uni-bielefeld.de
                           Insitute of Mathematical Economics (IMW)
                           University of Bielfeld, Germany
                           http://www.wiwi.uni-bielefeld.de/~imw/
***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <stdio.h>
#include <fstream.h>
#include <math.h>
#include <vector>
#include <gmpxx.h>
#include <gmp.h>
#include "func.h"
enum {ON,OFF};
int flag_redundant=0;
char cla[4];

int card(int n, int k)
{
  int erg=0;
  for(int i=0;i<n;i++)
    erg+=(k >> (n-i-1)) % 2;
  return erg;
}

void show_help(void)
{
  cout << "usage: lpnuc name_of_the_game" << endl;
  cout << "V : show version number" << endl;
  exit(1);
}

void show_version_number()
{
  cout << "LPNucleolus Version 0.1" << endl;
  exit(1);
}

void getopt(char *argument)
{
  string s(argument);
  if(s.find("V")!=s.npos)
    show_version_number();
  if(s.find("h")!=s.npos)
    show_help();
  if(s.find("r")!=s.npos)
    {
      flag_redundant=1;
      s.replace(s.find("r"),1,"");
    }
  if(s.size()>1)
    {
      cout << "unknown option: " << s << endl;
      show_help();
    }
}

int main(int argc, char *argv[])
{
  int n;
  double v_i;
  int i,j;
  char game_file[80];
  char result_lc_file[80];
  char result_nuc_file[80];
  char game_name[80];
  clock_t start,end;
  for(i=1;i<argc;i++)
    if(argv[i][0]=='-') strcat(cla,argv[i]);
  for(i=1;i<argc;i++)
    {
      if(argv[i][0]!='-')
   	{
	  sprintf(game_name,"%s",argv[i]);
	  sprintf(game_file,"game.%s",argv[i]);
	  sprintf(result_lc_file,"result.lc.%s",argv[i]);
	  sprintf(result_nuc_file,"result.nuc.%s",argv[i]);
	}
    }
  if (cla[0]=='-') getopt(cla);	

  ifstream fin (game_file);
  if(!fin)
    {	
      cout << game_file << " not found." << endl;
      exit(1);
    }
  fin >> n;
  int koalitionen = (int) pow (2, n);
  vector<int> v(0);
  for (i = 0; i < koalitionen; i++)
    {
      fin >> v_i;
      v.push_back(v_i);
    }	
  cout << endl << endl << endl << "--" << endl;
  cout << "LPNucleolus: Calculate the prenucleolus by solving a" << endl;
  cout << "sequence of linear programs." << endl;
  cout << "Copyright (C) 2002 by Sven Klauke, sklauke@wiwi.uni-bielefeld.de" << endl;
  start=clock();
  /* ------------------------------------------------------------------------------ */
  /* Leastcore computation                                                          */
  /* ------------------------------------------------------------------------------ */
  cout << endl << "Calculating the least-core ... (Step 1)" << endl << endl;
  vector<vector<mpq_class> > lc;
  lc=leastcore(n,v,flag_redundant);
  ofstream lcout(result_lc_file);
  cout << "Vertices of the least-core (" << lc.size() << "):" << endl << endl;
  lcout << "Vertices of the least-core (" << lc.size() << "):" << endl << endl;
  for(i=0;i<(int)lc.size();i++)
    {
      for(j=0;j<n;j++)
	{
	  cout << lc[i][j] << " ";
	  lcout << lc[i][j] << " ";
	}
      cout << endl;
      lcout << endl;
    }
  cout << endl << endl;
  lcout << endl << endl;
  lcout << "--" << endl;
  lcout << "Lpnucleolus: Computation of the prenucleolus of a game" << endl;
  lcout << "(C) 2002 by" << endl;
  lcout << "Sven Klauke, Institute of Mathematical Economics (IMW)" << endl;
  lcout << "University of Bielefeld, Germany" << endl;
  lcout.close();
  cout << "The Least Core is written to file " << result_lc_file << endl << endl;

  // end the algorithm, if |LC|=1
  int step=2;
  
  if((int)lc.size()==1)
    {
      end=clock();
      cout << "Computation terminated after the first step." << endl << endl;
      cout << "Computation time is " << (double)end/CLOCKS_PER_SEC-(double)start/CLOCKS_PER_SEC << " sec." << endl << endl;
      cout << "The prenucleolus of the game " << game_file << " is:" << endl << endl;
      for(j=0;j<n;j++)
	cout << lc[0][j] << " ";
      cout << endl;
      
      ofstream resout(result_nuc_file);
      resout << "The Prenucleolus of " << game_file << ":" << endl << endl;
      for(j=0;j<n;j++)
	resout << lc[0][j] << " ";
      resout << endl;
      resout << endl << endl;
      resout << "--" << endl;
      resout << "Lpnucleolus: Computation of the prenucleolus of a game" << endl;
      resout << "Copyright (C) 2002 by" << endl;
      resout << "Sven Klauke, Institute of Mathematical Economics (IMW)" << endl;
      resout << "University of Bielefeld, Germany" << endl;
      resout << "sklauke@wiwi.uni-bielefelde.de" << endl;
      resout.close();
      return 1;
    }

  // determination of the relevant coalitions for the next step
  vector<int> remaining_coalitions(koalitionen-2);
  vector<int> non_constant_coalitions(0);
  for(i=1;i<koalitionen-1;i++)
    remaining_coalitions[i-1]=i;
  vector<vector<mpq_class> > current_vertices(0);
  for(i=0;i<(int)lc.size();i++)
    current_vertices.push_back(lc[i]);
  int lc_vertex;
  mpq_class x_s;
  mpq_class prev_x_s;

  do {
    cout << endl << "Step " << step << endl << endl;
    for(i=0;i<(int)remaining_coalitions.size();i++)
      {
    	//cout << "checking coalition " << remaining_coalitions[i] << endl;
	for(lc_vertex=0;lc_vertex<(int)current_vertices.size();lc_vertex++)
	  {
	    //cout << "vertex " << lc_vertex+1 << " :" << endl;
	    x_s=0;
	    for(j=0;j<n;j++)
	      x_s=x_s+current_vertices[lc_vertex][j]*((remaining_coalitions[i] >> (n-j-1)) % 2);
	    //cout << "sum: " << x_s << endl;
	    if(lc_vertex==0)
	      {
		prev_x_s=x_s;
      		//cout << "first vertex, storing x_s" << endl;
	      }
	    else
	      {
        	//cout << "previous value was " << prev_x_s << endl;
        	if(x_s!=prev_x_s)
		  {
		    //cout << "not equal, adding coalition " << remaining_coalitions[i] << endl;
		    non_constant_coalitions.push_back(remaining_coalitions[i]);
		    break;
		  }
        	//else
		//cout << "equal, try on" << endl;
	      }
	  }// all vertices
      }// all remaining coalitions
    //cout << non_constant_coalitions.size() << " non_constant_coalitions" << endl;
    current_vertices.clear();
    current_vertices=setup_and_calc_lp(n,v,non_constant_coalitions,flag_redundant);
    cout << "Remaining vertices after Step " << step << " :" << endl << endl;
    for(i=0;i<(int)current_vertices.size();i++)
      {
    	for(j=0;j<n;j++)
	  cout << current_vertices[i][j] << " ";
	cout << endl;
      }
    cout << endl;
    remaining_coalitions.clear();
    for(i=0;i<(int)non_constant_coalitions.size();i++)
      remaining_coalitions.push_back(non_constant_coalitions[i]);
    non_constant_coalitions.clear();
    step++;
  }while(current_vertices.size()!=1);
  end=clock();
  cout << "Computation terminated after " << step-1 << " steps." << endl << endl;
  cout << "Computation time is " << (double)end/CLOCKS_PER_SEC-(double)start/CLOCKS_PER_SEC << " sec." << endl << endl;
  cout << "The prenucleolus of " << game_file << " is:" << endl << endl;
  for(j=0;j<n;j++)
    cout << current_vertices[0][j] << " ";
  cout << endl << endl << endl;

  ofstream resout(result_nuc_file);
  resout << "The Prenucleolus of " << game_file << ":" << endl << endl;
  for(j=0;j<n;j++)
    resout << current_vertices[0][j] << " ";
  resout << endl;
  resout << endl << endl;
  resout << "--" << endl;
  resout << "Lpnucleolus: Computation of the prenucleolus of a game" << endl;
  resout << "(C) 2002 by" << endl;
  resout << "Sven Klauke, Institute of Mathematical Economics (IMW)" << endl;
  resout << "University of Bielefeld, Germany" << endl;
  resout.close();
}