#include <stdio.h>
#include <string.h>
#include <math.h>
#include <errno.h>
#include <stdlib.h>
#include <time.h>

typedef enum {
  FALSE, TRUE
}               boolean;

#define  G       20

time_t          time(time_t *);
char            DateiAlt[15], Datei[15], Zeile[80];
FILE           *fid, *stream;
int           **nof4, **fct, *graph, *x, **sc, **c, *subs, *SumNof, **nof;
int             l[G], org[G], sl[G], cl[G];
int             leapfrog, b, B, Bmax, Bsave, Cmax, Gmax, Test = 2407;
//Test = 997;
//Test = 5737;
//Test = 13483;
//Test = 3311;

void
fatal(char *msg)
{
  fprintf(stderr, "Not enough memory for array %s  available !!\n", msg);
  exit(1);
}

int
getarrays()
{
  int             j;

  /***** define the structure to compute coefficient, i.e. C_k*C_l, C_k+C_l **/
  if ((graph = (int *) calloc(Bmax, sizeof(int))) == NULL) {
    printf("Not enough memory for array %s available\n", "graph");
    exit(1);
  }
  fct = (int **) calloc(4, sizeof(int));
  for (j = 0; j < 4; j++) {
    fct[j] = (int *) calloc(Bmax, sizeof(int));
    if (fct == NULL)
      fatal("fct");
  }
  /** none output fundamentals or factor in mag coding ***/
  nof4 = (int **) calloc(10, sizeof(int));
  for (j = 0; j < 10; j++) {
    nof4[j] = (int *) calloc(Bmax, sizeof(int));
    if (nof4 == NULL)
      fatal("nof4");
  }
  /** cost arrays store all integers of cost c ***/
  c = (int **) calloc(Gmax + 1, sizeof(int));
  for (j = 0; j <= Gmax; j++) {
    c[j] = (int *) calloc(Cmax, sizeof(int));
    if (c == NULL)
      fatal("c");
  }
  /** signed cost arrays store all positive first than negative ***/
  sc = (int **) calloc(Gmax + 1, sizeof(int));
  for (j = 0; j <= Gmax; j++) {
    sc[j] = (int *) calloc(2 * Cmax, sizeof(int));
    if (sc == NULL)
      fatal("sc");
  }
  return (0);
}
/********** sort array ********/
void
sort(int *x, int l1)
{
  int             k, j, t;

  for (k = 1; k < l1; k++) {
    t = x[j = k + 1];
    while (j != 1 && x[j - 1] > t) {
      x[j] = x[j - 1];
      j--;
    }
    x[j] = t;
  }
}
/********** ADSIP.M ********/
void
adisp(char *str, int *x, int l1)
{
  int             k;
  printf("%s = ", str);
  for (k = 1; k <= l1; k++) {
    printf(" %d", x[k]);
    if ((k % 15) == 0)
      printf("\n");
  }
  printf("\n");
}

/***** Compute odd fundamental *************/
int
oddfund(int coeff)
{
  int             x;
  x = abs(coeff);
  if (x == 0)
    return (x);
  while ((x % 2) == 0) {
    x = x / 2;
  }
  return (x);
}

void
find(int g)
{
  int             k = 0;
  printf("*** Find factor with costs %d\n", g);
  fprintf(fid, "*** Find factor with costs %d\n", g);
  /*
   * printf("*** First 5 costs factors\n"); for (k=1;k<6;k++) printf("C(0)=%d
   * C(1)=%d C(2)=%d C(3)=%d
   * C(4)=%d\n",c[0][k],c[1][k],c[2][k],c[3][k],c[4][k]);
   */
}

int
maxx()
{
  int             k;
  int             opt = 0;
  /**** First maximum of vector x ***/
  for (k = 1; k <= Bsave; k++)
    if (x[k] > opt)
      opt = x[k];
  return (opt);
}

void
csdcheck()
{
  int             g, k0, B2, improve = 0, i;
  B2 = B / 2;
  for (k0 = 1; k0 <= B2; k0++) {
    g = 2 * k0;
    while (g < B) {
      if (x[g] > x[k0]) {
	x[g] = x[k0];
	for (i = 1; i < 9; i++)
	  nof[g][i] = nof[k0][i];
	improve++;
      }
      g *= 2;
    }
  }
  printf("*** Check CSD table done.  Found %d improvements.\n", improve);
  fprintf(fid, "*** Check CSD table done.  Found %d improvements.\n", improve);
}

void
found(int g)
{
  int             k;
  if (g >= Gmax) {
    printf("Index Overflow for g\n");
    exit(1);
  }
  sl[g] = 0;
  l[g] = 0;
  /**** First place postive then negative ***/
  for (k = 1; k <= B; k++)
    if (x[k] == g) {
      l[g]++;
      c[g][l[g]] = k;
      sl[g]++;
      if (l[g] >= (Cmax - 5)) {
	printf("Index Overflow sc\n");
	exit(1);
      }
      sc[g][sl[g]] = k;
    }
  for (k = 1; k <= B; k++)
    if (x[k] == g) {
      sl[g]++;
      sc[g][sl[g]] = -k;
    }
  printf("*** Found %d factors with costs %d\n", l[g], g);
  fprintf(fid, "*** Found %d factors with costs %d\n", l[g], g);
}

int
CSDload(int b)
{
  int             r, v, i, B, l;
  if (leapfrog==-1)
  sprintf(DateiAlt, "csd%d.dat", b); 
  else
  sprintf(DateiAlt, "nof%dl%d.dat", b, leapfrog); 
  /*sprintf(DateiAlt, "nof%d.dat", b);*/
//  printf("  New loading function NOF : %s\n", DateiAlt);
//  sprintf(DateiAlt, "nof%dl%d.dat", b, leapfrog);
    stream = fopen(DateiAlt, "r");
    if (stream == NULL) {
      printf("File %s does not exist !!!\n", DateiAlt);
      exit(1);
    } else
{
      printf("File %s wird geladen\n", DateiAlt);
}
  /******* Datei NOF costs lesen und anzeigen  *************/
  /******* File has Cost, SumNof, nof array ****************/
  i = 0;
  l = -1;			/** linecounter l **/
  while (!feof(stream)) {
    fscanf(stream, "%s", Zeile);
    v = atoi(Zeile);
    l++;
    if (l == 11)
      l = 0;
    if (l == 0)
      i++;
    if (l == 0) {		/** first is cost entry **/
      if (i >= (Bmax - 5)) {
	printf("Array Overflow in load x");
	exit(1);
      }
      x[i] = v;
      if ((v >= 0) && (v < G)) {
	cl[x[i]]++;
	if (i <= Bsave)
	  org[v]++;
      } else
	x[i] = G - 2;
    }
    if (l == 1) {		/** second is Sum None output fundamental **/
      SumNof[i] = v;
    }
    if (l > 1) {		/** next are fundamentals **/
      nof[i][l - 1] = v;
    }
  }
  cl[x[i]]--;
  i--;
  B = i;
  printf("B= %d\n", B);
  fclose(stream);
  printf("*** Display of last 5 lines of input file \n");
  for (r = B - 5; r < B; r++) {
    printf("row=%d:  c=%d Sum=%d  NOF=", r, x[r], SumNof[r]);
    for (l = 1; l < 10; l++)
      printf("%d ", nof[r][l]);
    printf("\n");
  }
  fclose(stream);

  printf("  End of LOAD! \n");
  return (B);
}				/****** Ende Laden ************/

int
main()
{
  int             Sum = 0, k, j, k1;
  int             g;
  float           avg = 0.0;
  time_t          t1, t2;
  boolean         same = FALSE;

  printf("Determine the NOF statistic. \n");
  time(&t1);
  printf("Define mag table bit width =\n");
  scanf("%d", &b);
  printf("Leapfrog Graphs number =\n");
  scanf("%d", &leapfrog);

  Bmax = (1 << (b + 1)) + 10;
  Bsave = 1 << b;
  /***** define the cost function **/
  if ((x = (int *) calloc(Bmax, sizeof(int))) == NULL) {
    printf("Not enough memory for array %s available\n", "x");
    exit(1);
  }
  /***** define the number of subs **/
  if ((subs = (int *) calloc(Bmax, sizeof(int))) == NULL) {
    printf("Not enough memory for array %s available\n", "subs");
    exit(1);
  }
  /***** define the sum of NOFs **/
  if ((SumNof = (int *) calloc(Bmax, sizeof(int))) == NULL) {
    printf("Not enough memory for array %s available\n", "SumNof");
    exit(1);
  }
  /** none output fundamentals list ***/
  nof = (int **) calloc(Bmax, sizeof(int));
  for (j = 0; j <= Bmax; j++) {
    nof[j] = (int *) calloc(10 + 1, sizeof(int));
    if (nof == NULL)
      fatal("nof");
  }

B = CSDload(b);
  Gmax = (int) ceil(maxx()) + 3;
  if (Gmax >= G) {
    printf("Gmax to small\n");
    exit(1);
  }
  Cmax = Bmax;
  k = getarrays();
  Bsave=4;
  //******** Start analysis of data
  do {
  k=floor(log(Bsave)/log(2.)+.1);
  Sum=0;
printf("--> Range = 0 ... %d eqv %d bits (File b=%d) \n", Bsave, k , b);
  for (k = 0; k < G; k++)
    l[k] = 0;
  for (k = 0; k < Bsave; k++)
    if ((x[k] >= 0) && (x[k] < G))
      l[x[k]]++;
  for (k = 0; k < G; k++)
    if (l[k] > 0) {
      printf(" l[%d]=%d ", k, l[k]);
      Sum += l[k];
    }
  printf("\n Check Sum = %d ", Sum);
  Sum = 0;
  for (k = 1; k <= Bsave; k++) {
    avg += SumNof[k];
    if (SumNof[k] > Sum) {
      Sum = SumNof[k];
      j = k;
    }
  }
  avg /= Bsave;
  printf("Max. NOF Sum = %d for %d Average = %6.2f\n", Sum, j, avg);
  Bsave = Bsave*2;
  } while (Bsave<=B);

  return 0;
}