path: root/src/nem_ull.c

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

struct front_item * nem_ull(struct data * d){
  struct front_item * front;
  struct front_item * ret_front;
  struct front_item * it;
  struct front_item * tmp;
  struct front_item * jt;
  int i;

  front = new_front_item(0,0,NULL,NULL);
  ret_front = new_front_item(0,0,NULL,NULL);

  for(i=0;i<d->N;++i){
    front = nem_ull_step(front,d,i);
    
    it = ret_front;
    jt = front;
    while(it != NULL && jt != NULL) {
      if(it->i.p == jt->i.p && it->i.w == jt->i.w) {
        jt = jt->next;
        if(it->next == NULL) break;
        it = it->next;
      } else if(it->i.p < jt->i.p || (it->i.p == jt->i.p && it->i.w < jt->i.w)) {
        if(it->next == NULL) break;
        it = it->next;
      } else if(it->i.p > jt->i.p || (it->i.p == jt->i.p && it->i.w > jt->i.w)) {
        tmp = new_front_item(jt->i.p, jt->i.w, it->prev, it);
        tmp->time = jt->time;
        tmp->prev->next = tmp;
        tmp->next->prev = tmp;
        jt = jt->next;
      }
    }

    for(; jt != NULL; jt = jt->next) {
      it->next = new_front_item(jt->i.p, jt->i.w, it, NULL);
      it->next->time = jt->time;
      it = it->next;
    }
  }

  return ret_front;
}

struct front_item * nem_ull_online_shuffle(struct data * d, int rand_i){
  struct front_item * front;
  struct front_item * ret_front;
  struct front_item * it;
  struct front_item * tmp;
  struct front_item * jt;
  int i;

  ret_front = new_front_item(0,0,NULL,NULL);
  front = new_front_item(0,0,NULL,NULL);

  for(i=0;i<d->N;++i){
    if (i == rand_i) {
      shuffle_items(d, i);
    }
    front = nem_ull_step(front,d,i);

    it = ret_front;
    jt = front;
    while(it != NULL && jt != NULL) {
      if(it->i.p == jt->i.p && it->i.w == jt->i.w) {
        jt = jt->next;
        if(it->next == NULL) break;
        it = it->next;
      } else if(it->i.p < jt->i.p || (it->i.p == jt->i.p && it->i.w < jt->i.w)) {
        if(it->next == NULL) break;
        it = it->next;
      } else if(it->i.p > jt->i.p || (it->i.p == jt->i.p && it->i.w > jt->i.w)) {
        tmp = new_front_item(jt->i.p, jt->i.w, it->prev, it);
        tmp->time = jt->time;
        tmp->prev->next = tmp;
        tmp->next->prev = tmp;
        jt = jt->next;
      }
    }

    for(; jt != NULL; jt = jt->next) {
      it->next = new_front_item(jt->i.p, jt->i.w, it, NULL);
      it->next->time = jt->time;
      it = it->next;
    }
  }

  return ret_front;
}

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;
  clock_t * c0;
  struct front_item * p = b;

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

  l0 = (struct item *)malloc(n*sizeof(struct item));
  c0 = (clock_t *)malloc(n*sizeof(clock_t));
  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;
    c0[i] = p->time;

    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->time = c0[l0t];
        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->time = c0[l0t];
      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(c0);
  free(l1);

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