Create tree structure, adapt dfs to use tree (with iterative technique), fix random sort

2 files changed, 68 insertions, 30 deletions

diff --git a/src/common.c b/src/common.c
index ee98bba..7a8b316 100644
--- a/src/common.c
+++ b/src/common.c
@@ -5,8 +5,6 @@
 #include "structs.h"
 #include "common.h"
 
-#define RAND_MAX 1
-
 struct data * input(char fp[]){
   int i,j;
   FILE *f;
@@ -39,9 +37,7 @@ int cmp_items_ratio(const void * a, const void * b){
 }
 
 int cmp_items_random(const void *a, const void *b) {
-  struct item c = *(struct item *)a;
-  struct item d = *(struct item *)b;
-  if(rand() > 0.5){
+  if(rand() % 2 == 0){
     return 1;
   }
   return -1;
@@ -94,6 +90,18 @@ struct front_item * new_front_item(double p, double w, struct front_item * prev,
   return f;
 }
 
+struct tree_item * new_tree_item(long int depth, long int itemi, double w, double p, struct tree_item * prev, struct tree_item * next) {
+  struct tree_item * t = (struct tree_item *)malloc(sizeof(struct tree_item));
+  t->depth = depth;
+  t->itemi = itemi;
+  t->values.w = w;
+  t->values.p = p;
+  t->prev = prev;
+  t->next = next;
+  
+  return t;
+}
+
 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));
 }
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;
 }