Online method

7 files changed, 239 insertions, 2 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index dca0a4d..03d1063 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -57,10 +57,13 @@ set(MAIN_SRC_DIR ${CMAKE_CURRENT_SOURCE_DIR}/src/main)
 include_directories (${INCLUDE_DIR})
 
 add_library(uknapsack STATIC ${SRC_FILES})
-add_executable(uknapsack_bin ${MAIN_SRC_DIR}/uknapsack)
+add_executable(uknapsack_bin ${MAIN_SRC_DIR}/uknapsack.c)
+add_executable(online ${MAIN_SRC_DIR}/online.c)
 
 target_link_libraries(uknapsack_bin uknapsack)
+target_link_libraries(online uknapsack)
 
 install(TARGETS uknapsack_bin DESTINATION bin)
+install(TARGETS online DESTINATION bin)
 install(TARGETS uknapsack DESTINATION lib)
 install(FILES ${INCLUDE_FILES} DESTINATION include)
diff --git a/include/dfs.h b/include/dfs.h
index 340f5c8..2a2c187 100644
--- a/include/dfs.h
+++ b/include/dfs.h
@@ -4,5 +4,6 @@
 #include "structs.h"
 
 struct front_item * dfs(struct data *);
+struct online_return dfs_online(struct data *, struct front_item *, struct tree_item *, long int);
 
 #endif
diff --git a/include/random_heuristic.h b/include/random_heuristic.h
index 586777e..9e9dac6 100644
--- a/include/random_heuristic.h
+++ b/include/random_heuristic.h
@@ -4,5 +4,6 @@
 #include "structs.h"
 
 struct front_item * random_heuristic(struct data *);
+struct online_return random_heuristic_online(struct data *, struct front_item *, struct tree_item *);
 
 #endif
diff --git a/include/structs.h b/include/structs.h
index 7c39b4d..1d15084 100644
--- a/include/structs.h
+++ b/include/structs.h
@@ -30,4 +30,9 @@ struct tree_item {
   struct tree_item * next;
 };
 
+struct online_return {
+  struct front_item * front;
+  struct tree_item * tree;
+};
+
 #endif
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;
+}
diff --git a/src/main/online.c b/src/main/online.c
new file mode 100644
index 0000000..ba8a94c
--- /dev/null
+++ b/src/main/online.c
@@ -0,0 +1,64 @@
+#include <stdio.h>
+#include <time.h>
+#include <stdlib.h>
+#include <string.h>
+#include "common.h"
+#include "structs.h"
+#include "dfs.h"
+#include "random_heuristic.h"
+#include "nem_ull.h"
+
+int main(int argc, char * argv[]){
+  struct data * data;
+  struct front_item * front = NULL;
+  struct online_return ret;
+
+  if(argc!=5){
+    printf("Wrong number of arguments!\n");
+    printf("Example usage: %s algorithm1 algorithm2 sort_method data_file\n",argv[0]);
+    return 0;
+  }
+
+  data = input(argv[4]);
+
+  /* Sort data */
+  srand(time(NULL));
+  if(strcmp(argv[3], "random") == 0) {
+    qsort(data->items, data->N, sizeof(struct item), cmp_items_random);
+  } else if(strcmp(argv[3], "ratio") == 0) {
+    qsort(data->items, data->N, sizeof(struct item), cmp_items_ratio);
+  }
+
+  clock_t t = clock();
+  /* Choose algorithm1 */
+  if(strcmp(argv[1], "dfs") == 0) {
+    ret = dfs_online(data, NULL, NULL, 20);
+  } else if(strcmp(argv[1], "random_heuristic") == 0) {
+    ret = random_heuristic_online(data, NULL, NULL);
+  }
+
+  /* Run algorithm2, if it hasn't finished yet*/
+  if(ret.tree!=NULL){
+    if(strcmp(argv[2], "dfs") == 0) {
+      ret = dfs_online(data, ret.front, ret.tree, 100);
+    } else if(strcmp(argv[2], "random_heuristic") == 0) {
+      ret = random_heuristic_online(data, ret.front, ret.tree);
+    }
+  }
+  front = ret.front;
+  
+  /* Remove first item from front (only a placeholder) */
+  front=front->next;
+  free(front->prev);
+  front->prev = NULL;
+
+  t = clock() - t;
+  printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(front));
+
+  print_front(front);
+
+  free_front(front);
+  free_data(data);
+
+  return 0;
+}
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;
 }