Fix issues that would lead to seg fault on the online method

3 files changed, 45 insertions, 41 deletions

diff --git a/src/dfs.c b/src/dfs.c
index b0bda53..12f4ee2 100644
--- a/src/dfs.c
+++ b/src/dfs.c
@@ -92,11 +92,12 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s
       front_last->next = new_front_item(tree->values.p, tree->values.w, front_last, NULL);
       front_last = front_last->next;
       
+      /* Adjust prev and next */
+      if(tree->prev != NULL) tree->prev->next = tree->next;
+      if(tree->next != NULL) tree->next->prev = tree->prev;
+      
       struct tree_item * old = tree;
       tree = tree->next;
-      if(tree != NULL) {
-        tree->prev = old->prev;
-      }
       free(old);
 
       change++;
@@ -125,6 +126,10 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s
     /* Update left next */
     left->next = right;
 
+    /* Adjust prev and next */
+    if(tree->prev != NULL) tree->prev->next = left;
+    if(tree->next != NULL) tree->next->prev = right;
+
     /* Update tree to left node and free old node */
     struct tree_item * old = tree;
     tree = left;
diff --git a/src/main/online.c b/src/main/online.c
index ba8a94c..fb400ef 100644
--- a/src/main/online.c
+++ b/src/main/online.c
@@ -13,13 +13,13 @@ int main(int argc, char * argv[]){
   struct front_item * front = NULL;
   struct online_return ret;
 
-  if(argc!=5){
+  if(argc!=6){
     printf("Wrong number of arguments!\n");
-    printf("Example usage: %s algorithm1 algorithm2 sort_method data_file\n",argv[0]);
+    printf("Example usage: %s algorithm1 algorithm2 sort_method cut_pointa data_file\n", argv[0]);
     return 0;
   }
 
-  data = input(argv[4]);
+  data = input(argv[5]);
 
   /* Sort data */
   srand(time(NULL));
@@ -29,10 +29,11 @@ int main(int argc, char * argv[]){
     qsort(data->items, data->N, sizeof(struct item), cmp_items_ratio);
   }
 
+  printf("%d\n", atoi(argv[4]));
   clock_t t = clock();
   /* Choose algorithm1 */
   if(strcmp(argv[1], "dfs") == 0) {
-    ret = dfs_online(data, NULL, NULL, 20);
+    ret = dfs_online(data, NULL, NULL, atoi(argv[4]));
   } else if(strcmp(argv[1], "random_heuristic") == 0) {
     ret = random_heuristic_online(data, NULL, NULL);
   }
diff --git a/src/random_heuristic.c b/src/random_heuristic.c
index 0076728..529a186 100644
--- a/src/random_heuristic.c
+++ b/src/random_heuristic.c
@@ -9,12 +9,13 @@ struct front_item * random_heuristic(struct data * data) {
   struct front_item * front_last = front;
   struct tree_item * tree = new_tree_item(0, 0, 0, 0, NULL, NULL);
   long int tree_size = 1;
+  
+  /* Choose tree node randomly */
+  long int position = rand() % tree_size;
+  struct tree_item * node = tree;
+  for(int i = 0; i < position; i++,node=node->next);
 
   do {
-    /* Choose tree node randomly */
-    long int position = rand() % tree_size;
-    struct tree_item * node = tree;
-    for(int i = 0; i < position; i++,node=node->next);
     
     /* Check if node is leaf */
     if(node->depth == data->N) {
@@ -35,6 +36,13 @@ struct front_item * random_heuristic(struct data * data) {
       free(old);
       /* Reduce tree_size */
       tree_size--;
+      
+      if(tree != NULL) {
+        /* Select new random node */
+        position = rand() % tree_size;
+        node = tree;
+        for(int i = 0; i < position; i++,node=node->next);
+      }
 
       continue;
     }
@@ -73,6 +81,13 @@ struct front_item * random_heuristic(struct data * data) {
       tree = left;
     }
     free(old);
+    
+    /* Choose left or right randomly for node */
+    if(rand() % 2 == 0) {
+      node = left;
+    } else {
+      node = right;
+    }
 
     /* Increment tree_size */
     tree_size++;
@@ -87,8 +102,6 @@ struct front_item * random_heuristic(struct data * data) {
 }
 
 struct online_return random_heuristic_online(struct data * data, struct front_item * front, struct tree_item * tree) {
-
-  
   if(front == NULL) {
     front = new_front_item(0, 0, NULL, NULL);
   }
@@ -100,7 +113,7 @@ struct online_return random_heuristic_online(struct data * data, struct front_it
   }
   long int tree_size = 0;
   for(struct tree_item * tree_node = tree; tree_node != NULL; tree_node = tree_node->next, tree_size++);
-  
+
   /* Choose tree node randomly */
   long int position = rand() % tree_size;
   struct tree_item * node = tree;
@@ -112,18 +125,12 @@ struct online_return random_heuristic_online(struct data * data, struct front_it
       front_last->next = new_front_item(node->values.p, node->values.w, front_last, NULL);
       front_last = front_last->next;
       
-      struct tree_item * old = node;
-      if(tree == old) {
-        tree = node->next;
-      }
+      if(node->prev != NULL) node->prev->next = node->next;
+      if(node->next != NULL) node->next->prev = node->prev;
+      
+      if(tree == node) tree = node->next;
+      free(node);
 
-      if(node->next != NULL) {
-        node->next->prev = node->prev;
-      }
-      if(node->prev != NULL) {
-        node->prev->next = node->next;
-      }
-      free(old);
       /* Reduce tree_size */
       tree_size--;
 
@@ -146,9 +153,6 @@ struct online_return random_heuristic_online(struct data * data, struct front_it
       node->prev,
       node
     );
-    if(node->prev != NULL){
-      node->prev->next = left;
-    }
 
     /* Make right node (do not select item) */
     struct tree_item * right = new_tree_item(
@@ -159,28 +163,22 @@ struct online_return random_heuristic_online(struct data * data, struct front_it
       left,
       node->next
     );
-    if(node->next != NULL) {
-      node->next->prev = right;
-    }
 
     /* Adjust left->next to right */
     left->next = right;
 
-    struct tree_item * old = node;
-    if(node == tree) {
-      tree = left;
-    }
-    free(old);
+    if(node->prev != NULL) node->prev->next = left;
+    if(node->next != NULL) node->next->prev = right;
+
+    if(tree == node) tree = left;
+    free(node);
 
     /* Choose left or right randomly for node */
-    if(rand() % 2 == 0) {
-      node = left;
-    } else {
-      node = right;
-    }
+    node = rand() % 2 == 0 ? left : right;
 
     /* Increment tree_size */
     tree_size++;
+
   } while(tree != NULL);
 
   struct online_return ret;