Online method

1 files changed, 91 insertions, 1 deletions

diff --git a/src/random_heuristic.c b/src/random_heuristic.c
index bd3efa5..a2d0747 100644
--- a/src/random_heuristic.c
+++ b/src/random_heuristic.c
@@ -2,6 +2,7 @@
 #include "random_heuristic.h"
 #include "structs.h"
 #include "common.h"
+#include <stdio.h>
 
 struct front_item * random_heuristic(struct data * data) {
   struct front_item * front = new_front_item(0, 0, NULL, NULL);
@@ -83,5 +84,94 @@ struct front_item * random_heuristic(struct data * data) {
   front->prev = NULL;
 
   return front;
-  return NULL;
+}
+
+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);
+  }
+  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 tree_size = 0;
+  for(struct tree_item * tree_node = tree; tree_node != NULL; tree_node = tree_node->next, tree_size++);
+
+  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) {
+      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->next != NULL) {
+        node->next->prev = node->prev;
+      }
+      if(node->prev != NULL) {
+        node->prev->next = node->next;
+      }
+      free(old);
+      /* Reduce tree_size */
+      tree_size--;
+
+      continue;
+    }
+    
+    /* Make left node (select item) */
+    struct tree_item * left = new_tree_item(
+      node->depth + 1,
+      node->itemi + 1,
+      node->values.w + data->items[node->itemi].w,
+      node->values.p + data->items[node->itemi].p,
+      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(
+      node->depth + 1,
+      node->itemi + 1,
+      node->values.w,
+      node->values.p,
+      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);
+
+    /* Increment tree_size */
+    tree_size++;
+  } while(tree != NULL);
+
+  struct online_return ret;
+  ret.front = front;
+  ret.tree = tree;
+ 
+  return ret;
 }