#include <stdlib.h>
#include "nem_ull.h"
#include "structs.h"
#include "common.h"

struct front_item * nem_ull(struct data * d){
  struct front_item * begin;
  int i;

  begin = new_front_item(0,0,NULL,NULL);

  for(i=0;i<d->N;++i){
    begin = nem_ull_step(begin,d,i);
  }

  return begin;
}

struct front_item * nem_ull_step(struct front_item * b, struct data * d, int it){
  unsigned long int i,l0t,l1t,n;
  double pmax;
  struct item * l0;
  struct item * l1;
  struct front_item * p = b;

  for(n=0;p!=NULL;p=p->next,++n);
  p = b;

  l0 = (struct item *)malloc(n*sizeof(struct item));
  l1 = (struct item *)malloc(n*sizeof(struct item));

  for(i=0;i<n;++i){
    l0[i].p=p->i.p;
    l0[i].w=p->i.w;

    l1[i].p=p->i.p + d->items[it].p;
    l1[i].w=p->i.w + d->items[it].w;

    b = p;
    p = p->next;
    free(b);
  }

  pmax = -1;
  l0t = 0;
  l1t = 0;
  p = new_front_item(0,0,NULL,NULL);

  while(1){
    for(;l0t<n;++l0t){
      if(l0[l0t].p > pmax){
        break;
      }
    }

    for(;l1t<n;++l1t){
      if(l1[l1t].p > pmax){
        break;
      }
    }

    if(l0t == n){
      for(;l1t<n;++l1t){
        p = new_front_item(l1[l1t].p, l1[l1t].w, p, NULL);
        p->prev->next = p;
      }
      break;
    }

    if(l1t == n){
      for(;l0t<n;++l0t){
        p = new_front_item(l0[l0t].p, l0[l0t].w, p, NULL);
        p->prev->next = p;
      }
      break;
    }

    if((l0[l0t].w < l1[l1t].w) || ((l0[l0t].w == l1[l1t].w) && (l0[l0t].p > l1[l1t].p))){
      p = new_front_item(l0[l0t].p, l0[l0t].w , p, NULL);
      p->prev->next = p;
      pmax = l0[l0t].p;
      ++l0t;
    } else {
      p = new_front_item(l1[l1t].p, l1[l1t].w , p, NULL);
      p->prev->next = p;
      pmax = l1[l1t].p;
      ++l1t;
    }
  }

  free(l0);
  free(l1);

  for(;p->prev!=NULL;p=p->prev);
  p=p->next;
  free(p->prev);
  p->prev=NULL;
  return p;
}