#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <unistd.h>

enum { UNSORTED = 0, SORT_WR, SORT_VR, SORT_RW, SORT_RV};
enum { DESC = 0, ASC };
enum { NO_RELAX = 0, RELAX };

static int debug;
static int sort;
static int sort_order;
static int relax;

typedef struct _Item
{
   int i;
   int v;
   int w;
} Item;

typedef struct _SolverData {
     int v;    /* cumulated value */
     int w;    /* cumulated weight */
     float r;  /* relaxed max value */
     int i;    /* index of the selected item */
} SolverData;

typedef struct _Solver
{
   int k;               /* capacity */
   int n;               /* items # */
   int sum_w;           /* sum of weight of all items */
   Item *items;         /* items */
   SolverData *column;  /* solver column */
} Solver;

static int
item_cmp(const void *p1, const void *p2)
{
   int ret;
   float r1, r2;
   const Item *i1, *i2;

   i1 = (const Item *) p1;
   i2 = (const Item *) p2;

   ret = ((sort_order == ASC) ? 1 : -1);

   if (sort == SORT_WR)
     {
        if (i1->w > i2->w) return  ret;
        if (i1->w < i2->w) return -ret;
     }
   else if (sort == SORT_VR)
     {
        if (i1->v > i2->v) return  ret;
        if (i1->v < i2->v) return -ret;
     }
   else  // SORT_RW | SORT_RV
     {
        r1 = i1->v / (float)i1->w;
        r2 = i2->v / (float)i2->w;
        if (r1 > r2) return  ret;
        if (r1 < r2) return -ret;
     }

   if (sort == SORT_RW)
     {
        if (i1->w > i2->w) return  ret;
        if (i1->w < i2->w) return -ret;
     }
   else if (sort == SORT_RV)
     {
        if (i1->v > i2->v) return  ret;
        if (i1->v < i2->v) return -ret;
     }
   else  // SORT_WR | SORT_VR
     {
        r1 = i1->v / (float)i1->w;
        r2 = i2->v / (float)i2->w;
        if (r1 > r2) return  ret;
        if (r1 < r2) return -ret;
     }

   return 0;
}

static void reset_output(char *output, int bits)
{
   char *ch;
   char *end;

   end = output + bits;
   for (ch = output; ch < end; )
     {
        (*ch++) = '0';
        (*ch++) = ' ';
     }
   ch--;
   *ch = '\0';
}

static int print(Solver* solver)
{
   int ret;
   int v, w;
   char *output;
   const Item *item;
   const SolverData *data;

   output = calloc((solver->n * 2), sizeof(char));
   if (!output)
     {
        fprintf(stderr, "ERROR: output calloc\n");
        return EXIT_FAILURE;
     }
   reset_output(output, (solver->n * 2));

   data = solver->column + solver->k;
   printf("%d %d\n", data->v, 0);

   v = 0;
   w = 0;
   for (data = solver->column + solver->k; data->i != -1 ; data -= item->w)
     {
        item = &solver->items[data->i];
        output[(item->i) * 2] = '1';
        if (debug > 1)
          printf("  from % 6d  - take % 4d (% 4d % 4d)\n",
                 data->v, item->i, item->v, item->w);
        v += item->v;
        w += item->w;
     }
   printf("%s\n", output);

   free(output);

   ret = EXIT_SUCCESS;
   data = solver->column + solver->k;
   if (v != data->v)
     {
        fprintf(stderr, "ERROR: value %d != %d\n", v, data->v);
        ret = EXIT_FAILURE;
     }
   if (w > solver->k)
     {
        fprintf(stderr, "ERROR: weight %d > %d\n", w, solver->k);
        ret = EXIT_FAILURE;
     }

   return ret;

}

static inline void relax_item(Solver* solver, SolverData* data, int start)
{
   int w;
   int i;
   const Item *item;

   w = data->w;
   data->r = data->v;
   item = &solver->items[start];
   for (i = start; i < solver->n; i++, item++)
     {
        if ((w + item->w) <= solver->k)
          {
             w += item->w;
             data->r += item->v;
          }
        else
          {
             data->r += (item->v * ((solver->k - w) / (float)item->w));
             break;
          }
     }
}

static void solve(Solver* solver)
{
   int n, k;
   int v, w;
   int i, j;
   int max_c, upper_bound;
   const Item *item;
   SolverData *data;
   const SolverData *up_left;

   unsigned int counter;

   n = solver->n;
   k = solver->k;
   max_c = solver->sum_w;

   /* RELAXATION */
   if (relax == RELAX)
     {
        data = solver->column;
        for (j = 0; j <= k; j++, data++)
          relax_item(solver, data, 0);
     }

   if (debug > 2)
     {
        printf("\ncurrent V(i,s,W,r)\n");
     }

   /* SOLVE */
   counter = 0;
   item = solver->items;
   for (i = 0; i < n; i++, item++)
     {
        v = item->v;
        w = item->w;
        data = NULL;
        data = solver->column + solver->k;
        up_left = solver->column + (solver->k - w);

        // this computes the top-left bottom-right diagonal,
        // values above this don't need to be computed
        max_c -= w;
        upper_bound = (((k - max_c) > w) ? (k - max_c) : w );
        for (j = k; j >= upper_bound; j--, data--, up_left--)
          {
             // FIXME
             /* if ((relax == RELAX) && (data->v == (int)data->r)) */
             /* if ((relax == RELAX) && (data->v <= (int)data->r)) */
             /* if ((relax == RELAX) && (data->v < (int)data->r)) */
             /*   { */
             /*      /1* fprintf(stderr,"RELAX\n"); *1/ */
             /*      continue; */
             /*   } */

             counter++;

             if (data->v < (v + up_left->v))
               {
                  data->i = i;
                  data->v = v + up_left->v;
                  data->w = w + up_left->w;
                  /* if (j == k) */
                  /*   { */
                  /*      for (critical = data; critical->i != -1 ; */
                  /*           critical -= solver->items[data->i].w) */
                  /*        { */
                  /*           critical->c = critical->i; */
                  /*        } */
                  /*      print_vector(solver, i + 1, 0); */
                  /*      print_vector(solver, i + 1, 1); */
                  /*   } */
               }

             /* RELAXTION must be cached */
             if (relax == RELAX)
               {
                  relax_item(solver, data, (i + 1));
               }
          }

        if (debug > 2)
          {
             printf("i=%d; j=k; j<=%d:\n", i, upper_bound);
             data = solver->column;
             for (j = 0; j <= k; j++, data++)
               printf("  % 4d(% 2d % 2d %.1f)\n",
                      data->v, data->i, data->w, data->r);
             printf("\n");
          }
     }

   if (debug > 0)
     printf("loops count: %u\n", counter);

   if (debug == 2)
     {
        printf("i=%d:\n", solver->n - 1);
        data = solver->column;
        for (j = 0; j <= k; j++, data++)
          printf("  % 4d(% 2d % 2d %.1f)\n",
                 data->v, data->i, data->w, data->r);
     }
}

int main(int argc, char** argv, char** env)
{
   FILE *fp;

   int opt;
   int ret;
   int i;
   uint64_t dt;
   struct timespec t0;
   struct timespec t1;

   Solver solver;
   Item *item;

   sort = UNSORTED;
   sort_order = DESC;
   relax = NO_RELAX;
   debug = 0;
   while ((opt = getopt(argc, argv, "d:s:SR")) != -1) {
        switch (opt) {
           case 's':
              sort = atoi(optarg);
              break;
           case 'd':
              debug = atoi(optarg);
              break;
           case 'S':
              sort_order = ASC;
              break;
           case 'R':
              relax = RELAX;
              break;
           default: /* '?' */
              fprintf(stderr, "Usage: %s [-d level] [-s 0|1] [-S] [-R]input\n",
                      argv[0]);
              return EXIT_FAILURE;
        }
   }

   if (sort > SORT_RV) sort = UNSORTED;
   if (sort_order > ASC) sort = DESC;

   if (optind >= argc) {
        fprintf(stderr,"input file missing\n");
        return EXIT_FAILURE;
   }

   if (debug > 0) printf("%s\n", argv[optind]);
   fp = fopen(argv[optind], "r");
   if (fp == NULL)
     {
        fprintf(stderr, "I couldn't open results.dat for reading.\n");
        return EXIT_FAILURE;
     }

   /* read k and n */
   if (fscanf(fp, "%d %d\n", &solver.n, &solver.k) != 2)
     {
        fprintf(stderr, "ERROR: read first line\n");
        return EXIT_FAILURE;
     }
   if (debug > 0) printf("  K:%d N:%d\n", solver.k, solver.n);

   /* allocate */
   solver.items = calloc(solver.n, sizeof(Item));
   if (!solver.items)
     {
        fprintf(stderr, "ERROR: items calloc\n");
        return EXIT_FAILURE;
     }

   solver.column = calloc((solver.k + 1), sizeof(SolverData));
   if (!solver.column)
     {
        free(solver.items);
        fprintf(stderr, "ERROR: column calloc\n");
        return EXIT_FAILURE;
     }
   for (i = 0; i < (solver.k + 1); i++)
     solver.column[i].i = -1;

   /* read items */
   solver.sum_w = 0;
   item = solver.items;
   for (i = 0; i < solver.n; i++, item++)
     {
        item->i = i;
        fscanf(fp, "%d %d\n", &item->v, &item->w);
        solver.sum_w += item->w;
     }
   fclose(fp);

   if (sort != UNSORTED)
     qsort(solver.items, solver.n, sizeof(Item), item_cmp);

   if (debug > 1)
     {
        printf("  Items ");
        if (sort == UNSORTED)
          {
              printf("unsorted\n");
          }
        else
          {
             printf("sorted ");
             switch(sort){
                  case SORT_VR:
                     printf("Value,ratio(V/W)");
                     break;
                  case SORT_WR:
                     printf("Weight,ratio(V/W)");
                     break;
                  case SORT_RW:
                     printf("ratio(V/W),Weight");
                     break;
                  case SORT_RV:
                     printf("ratio(V/W),Value");
                     break;
                  default:
                     break;
             }
            if (sort_order == ASC)
              printf(" asc\n");
            else
              printf(" desc\n");
          }
        item = solver.items;
        printf("     index    Value   Weight\n");
        for (i = 0; i < solver.n; i++, item++)
          printf("  % 8d % 8d % 8d\n", item->i, item->v, item->w);
     }

   clock_gettime(CLOCK_MONOTONIC, &t0);
   solve(&solver);
   clock_gettime(CLOCK_MONOTONIC, &t1);
   ret = print(&solver);

   if (debug > 0)
     {
        dt = ((t1.tv_sec * 1000000000) + t1.tv_nsec) -
           ((t0.tv_sec * 1000000000) + t0.tv_nsec);
        printf(" time %7u [ms]\n", (unsigned int)(dt/1000000));
     }

   free(solver.items);
   free(solver.column);

   return ret;
}