From 3c8f9385498611df123d5f07d0e52035b568d415 Mon Sep 17 00:00:00 2001
From: Alexandre Jesus <adbjesus@gmail.com>
Date: Mon, 22 Aug 2016 16:35:31 +0100
Subject: Initial code

---
 src/common.c       | 88 ++++++++++++++++++++++++++++++++++++++++++++++++
 src/main/nem_ull.c | 31 +++++++++++++++++
 src/nem_ull.c      | 99 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 218 insertions(+)
 create mode 100644 src/common.c
 create mode 100644 src/main/nem_ull.c
 create mode 100644 src/nem_ull.c

(limited to 'src')

diff --git a/src/common.c b/src/common.c
new file mode 100644
index 0000000..92bd467
--- /dev/null
+++ b/src/common.c
@@ -0,0 +1,88 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include "structs.h"
+#include "common.h"
+
+struct data * input(char fp[]){
+	int i,j;
+	FILE *f;
+	struct data * d = (struct data *)malloc(sizeof(struct data));
+
+	f = fopen(fp,"r");
+	j = fscanf(f,"%ld",&(d->N));
+	if(j!=1){
+		printf("Error reading data\n");
+		exit(0);
+	}
+	d->items = (struct item *)malloc(d->N*sizeof(struct item));
+	for(i=0;i<d->N;++i){
+		j = fscanf(f,"%lf %lf",&(d->items[i].p),&(d->items[i].w));
+		d->allp += d->items[i].p;
+		d->allw += d->items[i].w;
+	}
+
+	fclose(f);
+	return d;
+}
+
+int cmp_items_ratio(const void * a, const void * b){
+  struct item c = *(struct item *)a;
+  struct item d = *(struct item *)b;
+  if(c.p / c.w < d.p / d.w){
+    return 1;
+  }
+	return -1;
+}
+
+void print_data(struct data * d){
+	int i;
+	printf("### PRINTING DATA - BEGINNING ###\n");
+	printf("N:\t%ld\n\n",d->N);
+	printf("Profit\tWeight\n");
+	for(i=0;i<d->N;++i){
+		printf("%.02f\t%.02f\n",d->items[i].p,d->items[i].w);
+	}
+	printf("### PRINTING DATA - ENDING ###\n");
+}
+
+void print_front(struct front_item * b){
+	while(b!=NULL){
+		printf("%.02f\t%.02f\n",b->i.p,b->i.w);
+		b = b->next;
+	}
+}
+
+void free_data(struct data * d){
+	free(d->items);
+	free(d);
+}
+
+void free_front(struct front_item * b){
+	struct front_item * tmp;
+	for(;b!=NULL;){
+		tmp = b;
+		b = b->next;
+		free(tmp);
+	}
+}
+
+struct front_item * new_front_item(double p, double w, struct front_item * prev, struct front_item * next){
+	struct front_item * f = (struct front_item *)malloc(sizeof(struct front_item));
+	f->i.p = p;
+	f->i.w = w;
+	f->next = next;
+	f->prev = prev;
+
+	return f;
+}
+
+double dist_items(struct item * a, struct item * b){
+	return sqrt((a->p - b->p)*(a->p - b->p) + (a->w - b->w)*(a->w - b->w));
+}
+
+int len_front(struct front_item * f){
+	int N;
+	for(N=0;f!=NULL;f=f->next,N++);
+	return N;
+}
diff --git a/src/main/nem_ull.c b/src/main/nem_ull.c
new file mode 100644
index 0000000..1bf183a
--- /dev/null
+++ b/src/main/nem_ull.c
@@ -0,0 +1,31 @@
+#include <stdio.h>
+#include <time.h>
+#include "common.h"
+#include "structs.h"
+#include "nem_ull.h"
+
+int main(int argc, char * argv[]){
+	struct data * d;
+	struct front_item * b;
+
+	if(argc!=2){
+		printf("Wrong number of arguments!\n");
+		printf("Example usage: %s data_file\n",argv[0]);
+		return 0;
+	}
+
+	d = input(argv[1]);
+	
+  clock_t t = clock();
+	b = nem_ull(d);
+
+	t = clock() - t;
+	printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(b));
+
+	//print_front(b);
+
+	free_front(b);
+	free_data(d);
+
+	return 0;
+}
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;
+}
-- 
cgit v1.2.3