/* Copyright (C) 2001  Dale Schuurmans, Finnegan Southey                     */
/* This work is licensed under the Gnu General Public License (see gpl.txt). */

/* An independent re-implementation of the Casanova solver. */
/* (Hoos & Boutlier 2000)                                   */

#include <stdlib.h>
#include <stdio.h>
#include <values.h>
#include <limits.h>
#include "cop.h"

typedef double REAL;

int n, m, N, M;
int *X, *A, *nCs, **Cs, **Ccoefs;
int *B, *nXs, **Xs, **Xcoefs;
int MaxCoef, MinB, MaxB;
int steps, dsteps, considered, r;
int opt, minfeasobj;


int *touch, **competitors, *numcompet, *loss; 
int *xout, *whereout, *time, *solution;
int *AA, maxopt;
REAL *score;


void ALLOCATE(double par1, double par2, int par3, int par4, double par5, int par6, int par7)
{
   int x, xx, i, c, j;

   AA = (int *) calloc(n, sizeof(int));
   loss = (int *) calloc(n, sizeof(int));
   for (x = 0; x < n; x++) AA[x] = -A[x];
   maxopt = -opt;
   touch = (int *) calloc(n, sizeof(int));
   competitors = (int **) calloc(n, sizeof(int *));
   numcompet = (int *) calloc(n, sizeof(int));
   for (x = 0; x < n; x++) competitors[x] = (int *) calloc(n, sizeof(int));
   xout = (int *) calloc(n, sizeof(int));
   whereout = (int *) calloc(n, sizeof(int));
   time = (int *) calloc(n, sizeof(int));
   solution = (int *) calloc(n, sizeof(int));
   score = (REAL *) calloc(n, sizeof (REAL));
	 
	 for (x = 0; x < n; x++) {
      numcompet[x] = 0;
      for (xx = 0; xx < n; xx++)
         if (xx == x)
            touch[xx] = 1;
         else
            touch[xx] = 0;
      for (j = 0; j < nCs[x]; j++) {
         c = Cs[x][j];
         for (i = 0;  i < nXs[c]; i++)
            if ( !touch[ xx = Xs[c][i] ] ) {
               competitors[x][ numcompet[x]++ ] = xx;
               touch[xx] = 1;
            };
      }
   }
}


void SEARCH(double par1, double par2, int par3, int par4, double par5, int par6, int par7)
{
   int R = par3;
   int T = par4;
   double wp = par1;
   double np = par2;
   int WP = (int) (1.0/wp + 0.5);
   int NP = (int) (1.0/np + 0.5);

   int x, xx, i, j, numout, xflip, x2, t;
   int curval, maxval, curloss, numsolution;
   REAL maxscore, score2;
   
   steps = considered = dsteps = maxval = 0;

   for (r = 0; r < R; r++) {  /*******************************************/

      for (x = 0; x < n; x++) {
         X[x] = -1;
         xout[x] = x;
         whereout[x] = x;
         time[x] = 0;
         loss[x] = 0;
      }
      numout = n;
      curval = 0;
      considered++;

      for (t = 0; t < T; t++) {              /***************************/

         if (maxval >= -opt) break;

         maxscore = score2 = -DBL_MAX;
         xflip = x2 = -1;

         if (lrand48()%WP == 0) {

            xflip = xout[lrand48()%numout];

         } else {

            for (i = 0; i < numout; i++) {
               x = xout[i];
               score[x] = (AA[x] - loss[x]) / (REAL) nCs[x];

               if (score[x] > maxscore || 
                         (score[x] == maxscore && time[x] < time[xflip])) {
                  score2 = maxscore;
                  maxscore = score[x];
                  x2 = xflip;
                  xflip = x;
               } else if (score[x] > score2 || 
                                (score[x] == score2 && time[x] < time[x2])) {
                  score2 = score[x];
                  x2 = x;
               }
            }
            if (time[xflip] > time[x2] && lrand48()%NP == 0) {
               xflip = x2;
            }
         }

         steps++;
         considered += numout;

         X[xflip] = 1;
         time[xflip] = t;
         loss[xflip] = 0;

         numout--;
         xout[whereout[xflip]] = xout[numout];
         whereout[xout[numout]] = whereout[xflip];
         xout[numout] = xflip;
         whereout[xflip] = numout;

         curloss = 0;
         for (i = 0; i < numcompet[xflip]; i++) {
            x = competitors[xflip][i];
            loss[x] += AA[xflip];
			if (X[x] > 0) {
               X[x] = -1;
               curloss += AA[x];
               xout[whereout[x]] = xout[numout];
               whereout[xout[numout]] = whereout[x];
               xout[numout] = x;
               whereout[x] = numout;
               numout++;
               for (j = 0; j < numcompet[x]; j++) {
                  xx = competitors[x][j];
                  if (xx != xflip) loss[xx] -= AA[x];
               }
            }
         }
         curval += AA[xflip] - curloss;

         if (curval > maxval) {
            maxval = curval;
            for (i = 0; i < n - numout; i++) solution[i] = xout[numout+i];
            numsolution = n - numout;

/*
checkval = 0;
for (i = numout; i < n; i++) checkval += A[xout[i]];
printf("r%d t%d mv%d: ", r, t, checkval);
for (i = numout; i < n; i++) printf("x%d ", xout[i]);
printf("\n");
*/

         }

      }                                      /***************************/
      if (maxval >= -opt) break;

   }                          /*******************************************/
   minfeasobj = -maxval;

/*
checkval = 0;
for (i = 0; i < numsolution; i++) checkval += A[solution[i]];
printf("final value=%d\n", checkval);
printf("bids: ");
for (i = 0; i < numsolution; i++) printf("%d ", solution[i]);
printf("\n");
*/
}


void CLEANUP()
{
   int x;

   free(AA);
   free(loss);
   free(touch);
   free(numcompet);
   free(xout);
   free(whereout);
   free(time);
   free(solution);
   free(score);
   for (x = 0; x < n; x++) free(competitors[x]);
   free(competitors);
}