1 files changed, 99 insertions, 0 deletions
diff --git a/src/nem_ull.c b/src/nem_ull.c
new file mode 100644
index 0000000..9a6b328
--- /dev/null
+++ b/src/nem_ull.c
@@ -0,0 +1,99 @@
+#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;
+}