/***************************************************************************
                          nuk.cpp  -  description
                             -------------------
    begin                : Die Feb 19 12:20:21 CET 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/   I
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   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.                                   *
 *                                                                         *
 ***************************************************************************/
#include <math.h>
#include "nuk.h"
#include "rand.h"
#include <vector>
#include <algorithm>
#include <fstream>

vector<double> calc_nuc(int n, vector<double> v, double min_schrittweite)
{
  int i,j;
  double x_s,v_s;
  double summe=0.0;
  int angenommen;
  int erfolglos;
  int t1,t2;
  int s_hyp=0;

  int versuche;
  int koalitionen=(int)pow(2,n);
  vector<int> kontrolle(koalitionen);
  vector<double> imputation_old(n);
  vector<double> imputation_new(n);
  vector<double> excess_old(koalitionen);
  vector<double> excess_new(koalitionen);

  for (i = 0; i < n ; i++)
    {
      if(v[koalitionen-1]==1)
	imputation_old[i] = v[koalitionen - 1] / n;
      else
	imputation_old[i]=int(v[koalitionen-1]/n);
    }
  imputation_new = imputation_old;

  for (i = 0; i < koalitionen; i++)
    {
      x_s = 0;
      for (j = 0; j < n; j++)

	x_s += j_in_i (j, i) * imputation_old[j];
      v_s = v[i];
      excess_old[i] = v_s - x_s;
    }
  excess_old[0]=0;
  if(n<=4)
    excess_old[koalitionen-1]=fabs(excess_old[koalitionen-1]/min_schrittweite);
  else
    excess_old[koalitionen-1]=0.0;
  sort(excess_old.begin(),excess_old.end());
  reverse(excess_old.begin(),excess_old.end());
  for(double schrittweite=0.1;schrittweite>min_schrittweite;schrittweite/=10.0)
    {
      versuche=10000;
      int weiter = 1;
      angenommen=0;
      erfolglos=0;
      t1=t2=0;
      do {
	weiter = 1;
	summe=0.0;
	if (angenommen)
	  {
	    for (i = 0; i < n; i++)
	      {
		imputation_new[i] = imputation_old[i] 
		  + (double)(j_in_i(i,t1)-j_in_i(i,t2)) * schrittweite;
		//imputation_new[i] = imputation_old[i] 
		//  + (double)(j_in_i(i,t1)-j_in_i(i,t2)) * schrittweite * (1.0+double(zufall(8)));
		summe+=imputation_new[i];
	      }
	  }
	else
	  {
	    t1=zufall(koalitionen-1);
	    t2=zufall(koalitionen-1);
	    s_hyp=zufall(n-1);
	    summe=0.0;
	    kontrolle[t1]=kontrolle[t1]+1;
	    kontrolle[t2]=kontrolle[t2]+1;
	    for (i = 0; i < n; i++)
	      {
		    imputation_new[i] =
		      imputation_old[i] + 
		    (double)(j_in_i(i,t1)-j_in_i(i,t2)) 
		    * schrittweite;
		    summe+=imputation_new[i];
	      }
	  }
	if(n>4)
	  imputation_new[s_hyp]+=(v[koalitionen-1]-summe);

	for (i = 1; i < koalitionen; i++)
	  {
	    x_s = 0;
	    for (j = 0; j < n; j++)
	      x_s += double(j_in_i (j, i)) * imputation_new[j];
	    v_s = v[i];
	    excess_new[i] = (double(int((v_s - x_s)/min_schrittweite+0.5)*min_schrittweite));
	    //excess_new[i]=v_s-x_s;
	    if(fabs(excess_new[i])<min_schrittweite) excess_new[i]=0.0;
	  }
	excess_new[0]=0.0;
	if(n<=4)
	  excess_new[koalitionen-1]=fabs(excess_new[koalitionen-1])/min_schrittweite;
	sort(excess_new.begin(),excess_new.end());
	reverse(excess_new.begin(),excess_new.end());
	if ((excess_new<excess_old)&&(excess_new!=excess_old))
	  {
	    weiter = 1;
	    angenommen = 1;
	    erfolglos=0;
	    imputation_old = imputation_new;
	    excess_old = excess_new;
	  }
	else
	  {
	    erfolglos++;
	    if (erfolglos >= versuche)
	      weiter = 0;
	    else
	      weiter = 1;
	    imputation_new = imputation_old;
	    angenommen = 0;
	  }
      } while(weiter);
	for(i=0;i<n;i++)
	cout << imputation_new[i] << " ";
	cout << endl;
    }
  return imputation_new;
}