1 files changed, 55 insertions, 25 deletions

diff --git a/src/dfs.c b/src/dfs.c
index bdf2b7e..3e14362 100644
--- a/src/dfs.c
+++ b/src/dfs.c
@@ -3,34 +3,64 @@
 #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);
-  }
+struct front_item * dfs(struct data * data) {
+  struct front_item * front = new_front_item(0, 0, NULL, NULL);
+  struct front_item * front_last = front;
+  struct tree_item * tree = new_tree_item(0, 0, 0, 0, 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;
+  /* Iterative dfs */
+  do {
+    /* Check if tree is leaf. If true: 
+     *   Add item to front_item;
+     *   Update tree to tree->next;
+     *   Free leaf;
+     *   Continue;
+     */
+    if(tree->depth == data->N) {
+      front_last->next = new_front_item(tree->values.p, tree->values.w, front_last, NULL);
+      front_last = front_last->next;
+      
+      struct tree_item * old = tree;
+      tree = tree->next;
+      if(tree != NULL) {
+        tree->prev = old->prev;
+      }
+      free(old);
 
-  // Go right (do not select item)
-  struct front_item * f2 = rec(d, i+1, it);
+      continue;
+    }
 
-  // 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;
-}
+    /* Make left node (select item) */
+    struct tree_item * left = new_tree_item(
+      tree->depth + 1,
+      tree->itemi + 1,
+      tree->values.w + data->items[tree->itemi].w,
+      tree->values.p + data->items[tree->itemi].p,
+      tree->prev,
+      tree
+    );
+    /* Make right node (do not select item) */
+    struct tree_item * right = new_tree_item(
+      tree->depth + 1,
+      tree->itemi + 1,
+      tree->values.w,
+      tree->values.p,
+      left,
+      tree->next
+    );
+    /* Update left next */
+    left->next = right;
+
+    /* Update tree to left node and free old node */
+    struct tree_item * old = tree;
+    tree = left;
+    free(old);
+  } while(tree != NULL);
 
-struct front_item * dfs(struct data * d) {
-  struct item * it = (struct item *)malloc(sizeof(struct item));
-  it->p = 0;
-  it->w = 0;
+  /* Remove first item from front (only a placeholder) */
+  front=front->next;
+  free(front->prev);
+  front->prev = NULL;
 
-  return rec(d, 0, it);
+  return front;
 }