1 files changed, 73 insertions, 0 deletions
diff --git a/src/dfs.c b/src/dfs.c
index 3e14362..b0bda53 100644
--- a/src/dfs.c
+++ b/src/dfs.c
@@ -1,4 +1,5 @@
 #include <stdlib.h>
+#include <stdio.h>
 #include "dfs.h"
 #include "structs.h"
 #include "common.h"
@@ -64,3 +65,75 @@ struct front_item * dfs(struct data * data) {
 
   return front;
 }
+
+
+struct online_return dfs_online(struct data * data, struct front_item * front, struct tree_item * tree, long int change_at){
+  if(front == NULL) {
+    front = new_front_item(0, 0, NULL, NULL);
+  }
+  struct front_item * front_last = front;
+  for(;front_last->next != NULL; front_last=front_last->next);
+  
+  if(tree == NULL) {
+    tree = new_tree_item(0, 0, 0, 0, NULL, NULL);
+  }
+
+  long int change=0;
+
+  /* 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);
+
+      change++;
+
+      continue;
+    }
+
+    /* 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 && change < change_at);
+
+  struct online_return ret;
+  ret.front = front;
+  ret.tree = tree;
+
+  return ret;
+}