From 6c620091ec068c31e4ed5e7e480b5abdd2329b0f Mon Sep 17 00:00:00 2001
From: Alexandre Jesus <adbjesus@gmail.com>
Date: Fri, 23 Sep 2016 09:34:49 +0100
Subject: Add random heuristic method

---
 CMakeLists.txt              |  5 +++
 src/main/random_heuristic.c | 36 ++++++++++++++++++++
 src/random_heuristic.c      | 82 +++++++++++++++++++++++++++++++++++++++++++--
 3 files changed, 121 insertions(+), 2 deletions(-)
 create mode 100644 src/main/random_heuristic.c

diff --git a/CMakeLists.txt b/CMakeLists.txt
index da3c722..5144b83 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -41,6 +41,7 @@ set(INCLUDE_FILES
   ${INCLUDE_DIR}/dfs.h
   ${INCLUDE_DIR}/structs.h
   ${INCLUDE_DIR}/common.h
+  ${INCLUDE_DIR}/random_heuristic.h
 )
 
 set(SRC_DIR ${CMAKE_CURRENT_SOURCE_DIR}/src)
@@ -48,6 +49,7 @@ set(SRC_FILES
   ${SRC_DIR}/nem_ull.c
   ${SRC_DIR}/dfs.c
   ${SRC_DIR}/common.c
+  ${SRC_DIR}/random_heuristic.c
 )
 
 set(MAIN_SRC_DIR ${CMAKE_CURRENT_SOURCE_DIR}/src/main)
@@ -58,11 +60,14 @@ add_library(uknapsack STATIC ${SRC_FILES})
 
 add_executable(nem_ull ${MAIN_SRC_DIR}/nem_ull.c)
 add_executable(dfs ${MAIN_SRC_DIR}/dfs.c)
+add_executable(random_heuristic ${MAIN_SRC_DIR}/random_heuristic.c)
 
 target_link_libraries(nem_ull uknapsack)
 target_link_libraries(dfs uknapsack)
+target_link_libraries(random_heuristic uknapsack)
 
 install(TARGETS nem_ull DESTINATION bin)
 install(TARGETS dfs DESTINATION bin)
+install(TARGETS random_heuristic DESTINATION bin)
 install(TARGETS uknapsack DESTINATION lib)
 install(FILES ${INCLUDE_FILES} DESTINATION include)
diff --git a/src/main/random_heuristic.c b/src/main/random_heuristic.c
new file mode 100644
index 0000000..9f3c683
--- /dev/null
+++ b/src/main/random_heuristic.c
@@ -0,0 +1,36 @@
+#include <stdio.h>
+#include <time.h>
+#include <stdlib.h>
+#include "common.h"
+#include "structs.h"
+#include "random_heuristic.h"
+
+int main(int argc, char * argv[]){
+  struct data * d;
+  struct front_item * b;
+
+  if(argc!=2){
+    printf("Wrong number of arguments!\n");
+    printf("Example usage: %s data_file\n",argv[0]);
+    return 0;
+  }
+
+  d = input(argv[1]);
+
+  /* srand() and qsort data  */
+  srand(time(NULL));
+  qsort(d->items, d->N, sizeof(struct item), cmp_items_ratio);
+
+  clock_t t = clock();
+  b = random_heuristic(d);
+
+  t = clock() - t;
+  printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(b));
+
+  print_front(b);
+
+  free_front(b);
+  free_data(d);
+
+  return 0;
+}
diff --git a/src/random_heuristic.c b/src/random_heuristic.c
index 4e3e47f..bd3efa5 100644
--- a/src/random_heuristic.c
+++ b/src/random_heuristic.c
@@ -3,7 +3,85 @@
 #include "structs.h"
 #include "common.h"
 
-struct front_item * random_heuristic(struct data * d) {
-  
+struct front_item * random_heuristic(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);
+  long int tree_size = 1;
+
+  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);
+ 
+  /* Remove first item from front (only a placeholder) */
+  front=front->next;
+  free(front->prev);
+  front->prev = NULL;
+
+  return front;
   return NULL;
 }
-- 
cgit v1.2.3