path: root/src/nem_ull.c

#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;
}