From d8ea8dc5fa670477cb6a3c64a9fe7dbbb0c44898 Mon Sep 17 00:00:00 2001
From: Alexandre Jesus <adbjesus@gmail.com>
Date: Thu, 15 Sep 2016 00:32:24 +0100
Subject: Add dfs

---
 src/dfs.c          | 35 +++++++++++++++++++++++++++++++++++
 src/main/dfs.c     | 31 +++++++++++++++++++++++++++++++
 src/main/nem_ull.c |  2 +-
 3 files changed, 67 insertions(+), 1 deletion(-)
 create mode 100644 src/dfs.c
 create mode 100644 src/main/dfs.c

(limited to 'src')

diff --git a/src/dfs.c b/src/dfs.c
new file mode 100644
index 0000000..3f34001
--- /dev/null
+++ b/src/dfs.c
@@ -0,0 +1,35 @@
+#include <stdlib.h>
+#include "dfs.h"
+#include "structs.h"
+#include "common.h"
+
+struct front_item * rec(struct data * d, int i, struct item * it) {
+  if(i == d->N) {
+    return new_front_item(it->p, it->w, NULL, NULL);
+  }
+
+  // Go left (select item)
+  it->p += d->items[i].p;
+  it->w += d->items[i].w;
+  struct front_item * f1 = rec(d, i+1, it);
+  it->p -= d->items[i].p;
+  it->w -= d->items[i].w;
+  // Go right (do not select item)
+  struct front_item * f2 = rec(d, i+1, it);
+
+  // Merge
+  struct front_item * f1_end = f1;
+  for(;f1_end->next!=NULL; f1_end = f1_end->next);
+  f1_end->next = f2;
+  f2->prev = f1_end;
+  
+  return f1;
+}
+
+struct front_item * dfs(struct data * d) {
+  struct item * it = (struct item *)malloc(sizeof(struct item));
+  it->p = 0;
+  it->w = 0;
+
+  return rec(d, 0, it);
+}
diff --git a/src/main/dfs.c b/src/main/dfs.c
new file mode 100644
index 0000000..36faa25
--- /dev/null
+++ b/src/main/dfs.c
@@ -0,0 +1,31 @@
+#include <stdio.h>
+#include <time.h>
+#include "common.h"
+#include "structs.h"
+#include "dfs.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 = dfs(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/main/nem_ull.c b/src/main/nem_ull.c
index 1bf183a..b267422 100644
--- a/src/main/nem_ull.c
+++ b/src/main/nem_ull.c
@@ -22,7 +22,7 @@ int main(int argc, char * argv[]){
 	t = clock() - t;
 	printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(b));
 
-	//print_front(b);
+	print_front(b);
 
 	free_front(b);
 	free_data(d);
-- 
cgit v1.2.3