From e7fcca35efae60ca2e24225b046ab4e9a801b031 Mon Sep 17 00:00:00 2001
From: Alexandre Jesus <adbjesus@gmail.com>
Date: Thu, 22 Sep 2016 02:02:20 +0100
Subject: Create tree structure, adapt dfs to use tree (with iterative
 technique), fix random sort

---
 include/common.h  |  1 +
 include/structs.h |  9 +++++++
 src/common.c      | 18 +++++++++----
 src/dfs.c         | 80 ++++++++++++++++++++++++++++++++++++++-----------------
 4 files changed, 78 insertions(+), 30 deletions(-)

diff --git a/include/common.h b/include/common.h
index 9332e6e..b188955 100644
--- a/include/common.h
+++ b/include/common.h
@@ -12,6 +12,7 @@ void print_front(struct front_item *);
 void free_data(struct data *);
 void free_front(struct front_item *);
 struct front_item * new_front_item(double,  double, struct front_item *, struct front_item *);
+struct tree_item * new_tree_item(long int, long int, double, double, struct tree_item *, struct tree_item *);
 double dist_items(struct item *, struct item *);
 int len_front(struct front_item *);
 int cmp_items_ratio(const void * a, const void * b);
diff --git a/include/structs.h b/include/structs.h
index 035af45..7c39b4d 100644
--- a/include/structs.h
+++ b/include/structs.h
@@ -21,4 +21,13 @@ struct front_item {
   struct front_item * prev;
   clock_t time;
 };
+
+struct tree_item {
+  long int depth;
+  long int itemi;
+  struct item values;
+  struct tree_item * prev;
+  struct tree_item * next;
+};
+
 #endif
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;
 }
-- 
cgit v1.2.3