/***************************************************************************
                          func.cpp  -  description
                             -------------------
    begin                : Wed Mar 13 2002
    copyright            : (C) 2002 by Sven Klauke
    email                : sklauke@wiwi.uni-bielefeld.de
                           Institute of Mathematical Economics (IMW)
                           University of Bielefeld, 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.                                   *
 *                                                                         *
 ***************************************************************************/

extern "C"{
#include "balance.h"
}
#include <gmpxx.h>
#include <math.h>
#include "func.h"
#include "leastcore.h"
#include <fstream.h>

int member(int n, int player, int coalition)
{
	return (coalition >> (n-player-1)) % 2;
}

/*
  check_linspan:
  - returns 1, if the profile vector of coalition k_new is in the linear span 
  of the profile vectors of the coalitions in k, returns 0 otherwise
  - called from main.cpp within the balancedness check (not implemented in
  current version 0.1)
  - calls linear_span in balance.c
*/
int check_linspan(int n, vector<int> k,int k_new)
{
  int i,j;
  int s=(int)k.size();
  vector<vector< int> > p(n,s+1);
  for(i=0;i<n;i++)
    {
      p[i][0]=-1*(k_new >> (n-i-1)) % 2;
      for(j=0;j<s;j++)
	p[i][j+1]=(k[j] >> (n-i-1)) % 2;
    }
  int *pptr[n];
  for(i=0;i<n;i++)
    pptr[i]=&p[i][0];
  int erg=linear_span(n,s+1,pptr);
  return erg;
}

/*
  check_balance:
  - returns 1, if the coalitions in k are balanced, returns 0 otherwise
  - called from main.cpp within the balancedness check (not implemented 
  in current version 0.1)
  - calls balance in balance.c
*/

int check_balance(int n,vector<int> k)
{
  int i,j;
  int s=(int)k.size();
  vector<vector<int> > p(n+s,s+1);
  for(i=0;i<s;i++)
    {
      p[i][0]=0;
      for(j=0;j<s;j++)
	{
	  if(i==j)
	    p[i][j+1]=1;
	  else
	    p[i][j+1]=0;
	}
    }
  for(i=0;i<n;i++)
    {
      p[s+i][0]=1;
      for(j=0;j<s;j++)
	p[s+i][j+1]=-1*((k[j] >> (n-i-1)) % 2);
    }
  int *pptr[n+s];
  for(i=0;i<n+s;i++)
    pptr[i]=&p[i][0];
  int erg=balance(n,s,pptr);
  return erg;
}

/*
  leastcore:
  - sets up the linear program for calculating the least core and
  solves it
  - returns the vertices of the least core
  - called from main.cpp
  - calls calc_leastcore in leastcore.c
  - the vertices of the leastcore are written in file "lc" by
  calc_leastcore
*/

vector<vector<mpq_class> > leastcore(int n,vector<int> v,int flag_redundant)
{
  int k=(int)pow(2,n);
  int i,j;
  int p[k-1][n+2];
  for(i=1;i<k-1;i++)
    {
      p[i-1][0]=-1*v[i];
      for(j=0;j<n;j++)
	p[i-1][j+1]=(i >> (n-j-1)) % 2;
      p[i-1][n+1]=1;
    }
  p[k-2][0]=v[k-1];
  for(i=0;i<n;i++)
    p[k-2][i+1]=-1;
  p[k-2][n+1]=0;
  int *pptr[k-1];
  for(i=0;i<k-1;i++)
    pptr[i]=&p[i][0];
  int lc_size=calc_leastcore(n,pptr,flag_redundant);
  vector<vector<mpq_class> > lc(lc_size);
  vector<mpq_class> lc_elem(n);
  ifstream fin("lc"); // file containg the vertices of the least core
  string inp;
  do{
    fin >> inp;}while(inp!="rational");
  for(i=0;i<lc_size;i++)
    {
      fin >> inp;
      for(j=0;j<n;j++)
	{
	  mpq_class x;
	  fin >> x;
	  lc_elem[j]=x;
	}
      lc[i]=lc_elem;
    }
  return lc;
}

/*
  setup_and_calc_lp:
  - sets up and solves the intermediate linear program in the calculation of the
  prenucleolus
  - returns the vertices of the region of optimal solutions
  - called from main.cpp
  - calls calc_lp in leastcore .c
  - the vertices are written in file "lc" by calc_lp
*/

vector<vector<mpq_class> > setup_and_calc_lp(int n,vector<int> v, vector<int> coalitions, int flag_redundant)
{
  int k=(int)pow(2,n);
  int i,j;
  int p[coalitions.size()+1][n+2];
  for(i=0;i<(int)coalitions.size();i++)
    {
      p[i][0]=-1*v[coalitions[i]];
      for(j=0;j<n;j++)
	p[i][j+1]=(coalitions[i] >> (n-j-1)) % 2;
      p[i][n+1]=1;
    }
  p[coalitions.size()][0]=v[k-1];
  for(i=0;i<n;i++)
    p[coalitions.size()][i+1]=-1;
  p[coalitions.size()][n+1]=0;
  int *pptr[coalitions.size()+1];
  for(i=0;i<(int)coalitions.size()+1;i++)
    pptr[i]=&p[i][0];
  int lp_size=calc_lp(n,coalitions.size()+1,pptr,flag_redundant);
  vector<vector<mpq_class> > lp(lp_size);
  vector<mpq_class> lp_elem(n);
  ifstream fin("lc");
  string inp;
  do{
    fin >> inp;}while(inp!="rational");
  for(i=0;i<lp_size;i++)
    {
      fin >> inp;
      for(j=0;j<n;j++)
	{
    	  mpq_class x;
	  fin >> x;
    	  lp_elem[j]=x;
	}
      lp[i]=lp_elem;
    }
  return lp;
}