/* ======================================================================
	     test_mulknap.c, David Pisinger          june 1998 
   ====================================================================== */

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <stdarg.h>
#include <values.h>
#include <string.h>
#include <math.h>
#include <signal.h>
#include "mulknap.h"


/* ======================================================================
				   macros
   ====================================================================== */

#define TESTS          20

#define srand(x)     srand48(x)
#define random(x)    (lrand48() % (long) (x))

#define TRUE  1                /* boolean values */
#define FALSE 0


/* ======================================================================
			      global variables
   ====================================================================== */

FILE *trace;


/* ======================================================================
				 type declarations
   ====================================================================== */

typedef int           boolean;
typedef long          ntype;   /* number of states         */
typedef short         itype;   /* item profits and weights */
typedef long          stype;   /* sum of pofit or weight   */
typedef float         ftype;   /* product type (sufficient precision) */
typedef double        ptype;   /* product type (sufficient precision) */
typedef signed char   mtype;   /* number of knapsacks      */
typedef unsigned long btype;   /* binary solution vector   */

typedef int (*funcptr) (const void *, const void *);

/* item record */
typedef struct irec {
  itype    p;     /* profit */
  itype    w;     /* weight */
  mtype    x;     /* optimal solution variable */
  mtype    y;     /* current solution */
  mtype    a;     /* consider only after a */
  mtype    r;     /* reduced ? */
} item;


/* ======================================================================
                                  debug routines
   ====================================================================== */

static void error(char *str, ...)
{
  va_list args;

  va_start(args, str);
  vprintf(str, args); printf("\n");
  va_end(args);
  exit(-1);
}


/* ======================================================================
                                showitems
   ====================================================================== */

void showitems(int n, int m, int *p, int *w, int *x, int *c)
{
  int i;
  int j, k;
  int ps, ws, *wsum;
  boolean checked;

  fprintf(trace,"items\n");
  for (i = 0; i != n; i++) {
    fprintf(trace,"%3d: %1d (%d,%d)\n", i+1, x[i], p[i], w[i]);
  }
  fprintf(trace,"capacities\n");
  for (i = 0; i != m; i++) {
    fprintf(trace,"c[%d] %d\n", i+1, c[i]);
  }
}

 
/* ======================================================================
                                sumitems
   ====================================================================== */

int sumitems(int n, int m, int *p, int *w, int *x, int *c, int z)
{
  int i;
  int j, k;
  int ps, ws, csum, *wsum;
  boolean checked;

  /* printf("sumitems %d\n", n); */
  wsum = malloc(m*sizeof(int));
  ps = 0;
  for (j = 0; j < m; j++) wsum[j] = 0;
  for (i = 0; i != n; i++) {
    if (x[i] != 0) {
      if (x[i] < 0) error("too small x");
      if (x[i] > m) error("too big x");
      ps += p[i]; wsum[x[i]-1] += w[i];
    }
  }

  ws = 0; csum = 0;
  for (j = 0; j != m; j++) {
    if (wsum[j] > c[j])
      error("overfilled c[%hd]: w %ld, c %ld\n", j+1, wsum[j], c[j]);
    ws += wsum[j]; csum =+ c[j];
  }
  free(wsum);
  /* printf("sumitems (%ld,%ld)\n", ps, ws); */
  if (ps != z) error("bad solution\n");
  return csum;
}


/* ======================================================================
                                capless
   ====================================================================== */

static int capless(int *a, int *b)
{
  /* function for sorting capacities in increasing order */
  return (*a - *b);
}


/* ======================================================================
			       sumdata
   ====================================================================== */

void sumdata(int n1, int m1, int r1, int t1, int s1, 
             int iterates1, int tightened1, int reduced1, int coresize1,
             int gub1, int z1, int csum1, int tottime1)
{
  static long n;
  static long r;
  static long m;
  static long t;
  static long s;
  static long checked     = 0;
  static long iterates    = 0;
  static long tightened   = 0;
  static long coresize    = 0;
  static long tottime     = 0;
  static long gap         = 0;
  static long reduced     = 0;
  static long zsum        = 0;
  static long csum        = 0;
  double mean;

  if (n1 == 0) {
    mean = tottime / (1000 * (double) TESTS);
    fprintf(trace,"n        = %ld\n", n);
    fprintf(trace,"r        = %ld\n", r);
    fprintf(trace,"m        = %ld\n", m);
    fprintf(trace,"t        = %ld\n", t);
    fprintf(trace,"sim      = %ld\n", s);
    fprintf(trace,"iterates = %.1lf\n", iterates      / (double)     TESTS);
    fprintf(trace,"tighten  = %.1lf\n", tightened     / (double)         1);
    fprintf(trace,"gap      = %.1lf\n", gap           / (double)     TESTS);
    fprintf(trace,"reduced  = %.1lf\n", reduced       / (double)         1);
    fprintf(trace,"coresize = %.1lf\n", coresize      / (double)     TESTS);
    fprintf(trace,"zsum     = %.0lf\n", zsum          / (double)         1);
    fprintf(trace,"csum     = %.0lf\n", csum          / (double)         1);
    fprintf(trace,"time     = %.2lf\n", mean          / (double)         1);
  } else {
    iterates    += iterates1;
    if (tightened1 > tightened) tightened = tightened1;
    if (reduced1   > reduced  ) reduced = reduced1;
    coresize    += coresize1;
    gap         += gub - z1;
    zsum         = ((zsum + z1) % 1000);
    csum         = ((csum + csum1) % 1000);
    tottime     += tottime1;

    n = n1;
    m = m1;
    r = r1;
    t = t1;
    s = s1;
  }
}


/* ======================================================================
                                maketest
   ====================================================================== */

void maketest(int n, int m, int *p, int *w, int *x, int *c, int type, int r, 
              boolean similar)
{
  register int i;
  register itype minw, maxw;
  register stype sum;
  stype csum, c4, c2, maxc;
  boolean ok;
  int r1, j;

  r1 = r / 10;

  for (;;) {
    sum  = 0;
    minw = r;
    maxw = 0;
    for (i = 0; i != n; i++) {
      w[i] = random(r-9) + 10;   /* weigts in [10,R] */
      if (w[i] < minw) minw = w[i];
      if (w[i] > maxw) maxw = w[i];
      switch (type) {
        case  1: p[i] = random(r) + 1;
                 break;
        case  2: do { 
                   p[i] = random(2 * r1 + 1) + w[i] - r1;
                 } while (p[i] <= 0);
                 break;
        case  3: p[i] = w[i] + 10;
                 break;
        case  4: p[i] = w[i];
                 break;
        default: p = 0;
      }
      sum += w[i];
      x[i] = 0;
    }

    csum = 0; 
    c4 = (0.4 * sum) / m;
    c2 = (0.2 * sum) / m;
    for (j = 0; j < m-1; j++) {
      if (similar) {
        c[j] = c4 + random(c2);
      } else {
        c[j] = random(sum / 2 - csum);
      }
      csum += c[j];
    }
    c[m-1] = sum/2 - csum;
    csum += c[m-1];
   
    ok = TRUE;
    for (j = 0, maxc = 0; j < m; j++) {
      if (c[j] <= 0) ok = FALSE;
      if (c[j] < minw) ok = FALSE;
      if (c[j] > maxc) maxc = c[j];
    }
    if (maxw > maxc) ok = FALSE;
    if (sum <= csum) ok = FALSE;
    if (ok) break;
  }

  /* printf("maketest sum %ld, csum %ld\n", sum, csum); */
  if (csum >= sum) error("maketest too greedy");
  qsort(c, m, sizeof(int), (funcptr) capless); /* capacities must be ordered */
}


/* ======================================================================
				main
   ====================================================================== */

void main(int argc, char *argv[])
{
  int n, r, m, type, s, v, z, csum;
  int *p, *w, *x, *c;
  char sim[80];

  if (argc == 6) {
    n = atoi(argv[1]);
    r = atoi(argv[2]);
    m = atoi(argv[3]);
    type = atoi(argv[4]);
    s = (strcmp(argv[5], "s") == 0);
    printf("Mulknap %d, %d, %d, %d, %c\n", n, r, m, type, (s ? 's' : 'd'));
  } else {
    printf("Mulknap\n");
    printf("n = ");
    scanf("%d", &n);
    printf("r = ");
    scanf("%d", &r);
    printf("m = ");
    scanf("%d", &m);
    printf("t = ");
    scanf("%d", &type);
    printf("s = ");
    scanf("%s", &sim);
    s = (strcmp(sim, "s") == 0);
  }
  p = malloc(sizeof(int)*n);
  w = malloc(sizeof(int)*n);
  x = malloc(sizeof(int)*n);
  c = malloc(sizeof(int)*m);
  
  trace = fopen("trace.mul", "a");
  fprintf(trace,"\nMULKNAP: n: %d, r: %d, m: %d, type: %d, s: %c\n",
          n, r, m, type, (s ? 's' : 'd'));

  for (v = 1; v <= TESTS; v++) {
    srand(v);
    printf("test %d\n", v);
    /* fprintf(trace,"\nTEST %d\n", v); */
    maketest(n, m, p, w, x, c, type, r, s);
    z = mulknap(n, m, p, w, x, c);
    /* showitems(n, m, p, w, x, c); */
    csum = sumitems(n, m, p, w, x, c, z); 
    fprintf(trace," %2d: itr %ld, z %ld\n", v, iterates, z);
    sumdata(n, m, r, type, s, iterates, tightened, reduced, coresize,
            gub, z, csum, tottime); 
  }
  free(c);
  free(x); 
  free(w); 
  free(p); 

  sumdata(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
  fclose(trace);
}