Add nem_ull with shuffle

8 files changed, 129 insertions, 2 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 03d1063..e646d55 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -59,11 +59,14 @@ include_directories (${INCLUDE_DIR})
 add_library(uknapsack STATIC ${SRC_FILES})
 add_executable(uknapsack_bin ${MAIN_SRC_DIR}/uknapsack.c)
 add_executable(online ${MAIN_SRC_DIR}/online.c)
+add_executable(nem_ull_shuffle ${MAIN_SRC_DIR}/nem_ull_shuffle.c)
 
 target_link_libraries(uknapsack_bin uknapsack)
 target_link_libraries(online uknapsack)
+target_link_libraries(nem_ull_shuffle uknapsack)
 
 install(TARGETS uknapsack_bin DESTINATION bin)
 install(TARGETS online DESTINATION bin)
+install(TARGETS nem_ull_shuffle DESTINATION bin)
 install(TARGETS uknapsack DESTINATION lib)
 install(FILES ${INCLUDE_FILES} DESTINATION include)
diff --git a/include/common.h b/include/common.h
index b188955..f00a269 100644
--- a/include/common.h
+++ b/include/common.h
@@ -17,5 +17,6 @@ double dist_items(struct item *, struct item *);
 int len_front(struct front_item *);
 int cmp_items_ratio(const void * a, const void * b);
 int cmp_items_random(const void * a, const void * b);
+void shuffle_items(struct data *, int);
 
 #endif
diff --git a/include/nem_ull.h b/include/nem_ull.h
index fd1b829..5e86c1f 100644
--- a/include/nem_ull.h
+++ b/include/nem_ull.h
@@ -5,5 +5,6 @@
 
 struct front_item * nem_ull(struct data *);
 struct front_item * nem_ull_step(struct front_item *, struct data *, int);
+struct front_item * nem_ull_online_shuffle(struct data *, int);
 
 #endif
diff --git a/src/common.c b/src/common.c
index 7a8b316..5fc944e 100644
--- a/src/common.c
+++ b/src/common.c
@@ -111,3 +111,33 @@ int len_front(struct front_item * f){
   for(N=0;f!=NULL;f=f->next,N++);
   return N;
 }
+
+/* Shuffle data items starting on a certain index, in place */
+void shuffle_items(struct data * d, int start) {
+  int i, ind;
+  struct item * new_items;
+
+  if (start < 0) return;
+  if (start >= d->N) return;
+
+  new_items = (struct item *)malloc(d->N * sizeof(struct item));
+
+  /* These stay the same */
+  for(i = 0; i < start; i++) {
+    new_items[i].p = d->items[i].p;
+    new_items[i].w = d->items[i].w;
+  }
+
+  /* Shuffle the rest */
+  for(i = start; i < d->N; i++) {
+    ind = rand() % (d->N - i);
+    new_items[i].p = d->items[i+ind].p;
+    new_items[i].w = d->items[i+ind].w;
+    d->items[i+ind].p = d->items[i].p;
+    d->items[i+ind].w = d->items[i].w;
+  }
+
+  /* Replace old array */
+  free(d->items);
+  d->items = new_items;
+}
diff --git a/src/dfs.c b/src/dfs.c
index 12f4ee2..172ac0b 100644
--- a/src/dfs.c
+++ b/src/dfs.c
@@ -88,6 +88,8 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s
      *   Free leaf;
      *   Continue;
      */
+    change++;
+
     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;
@@ -100,8 +102,6 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s
       tree = tree->next;
       free(old);
 
-      change++;
-
       continue;
     }
 
diff --git a/src/main/nem_ull_shuffle.c b/src/main/nem_ull_shuffle.c
new file mode 100644
index 0000000..e0996ba
--- /dev/null
+++ b/src/main/nem_ull_shuffle.c
@@ -0,0 +1,43 @@
+#include <stdio.h>
+#include <time.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/time.h>
+#include "common.h"
+#include "structs.h"
+#include "nem_ull.h"
+
+int main(int argc, char * argv[]){
+  struct data * data;
+  struct front_item * front = NULL;
+
+  if(argc!=3){
+    printf("Wrong number of arguments!\n");
+    printf("Example usage: %s cut_point data_file\n", argv[0]);
+    return 0;
+  }
+
+  data = input(argv[2]);
+
+  struct timeval tv;
+  gettimeofday(&tv, NULL);
+  srand(tv.tv_sec + tv.tv_usec);
+
+  /* Sort data */
+  qsort(data->items, data->N, sizeof(struct item), cmp_items_ratio);
+
+  printf("%d\n", atoi(argv[1]));
+  clock_t t = clock();
+  front = nem_ull_online_shuffle(data, atoi(argv[1]));
+  
+  /* Remove first item from front (only a placeholder) */
+  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/main/online.c b/src/main/online.c
index fbec660..7dec27c 100644
--- a/src/main/online.c
+++ b/src/main/online.c
@@ -13,6 +13,8 @@ int main(int argc, char * argv[]){
   struct data * data;
   struct front_item * front = NULL;
   struct online_return ret;
+  ret.tree = NULL;
+  ret.front = NULL;
 
   if(argc!=6){
     printf("Wrong number of arguments!\n");
diff --git a/src/nem_ull.c b/src/nem_ull.c
index f08506b..6405fc2 100644
--- a/src/nem_ull.c
+++ b/src/nem_ull.c
@@ -1,4 +1,5 @@
 #include <stdlib.h>
+#include <stdio.h>
 #include "nem_ull.h"
 #include "structs.h"
 #include "common.h"
@@ -16,6 +17,52 @@ struct front_item * nem_ull(struct data * d){
   return begin;
 }
 
+struct front_item * nem_ull_online_shuffle(struct data * d, int rand_i){
+  struct front_item * front;
+  struct front_item * ret_front;
+  struct front_item * it;
+  struct front_item * tmp;
+  struct front_item * jt;
+  int i;
+
+  ret_front = new_front_item(0,0,NULL,NULL);
+  front = new_front_item(0,0,NULL,NULL);
+
+  for(i=0;i<d->N;++i){
+    if (i == rand_i) {
+      shuffle_items(d, i);
+    }
+    front = nem_ull_step(front,d,i);
+
+    it = ret_front;
+    jt = front;
+    while(it != NULL && jt != NULL) {
+      if(it->i.p == jt->i.p && it->i.w == jt->i.w) {
+        jt = jt->next;
+        if(it->next == NULL) break;
+        it = it->next;
+      } else if(it->i.p < jt->i.p || (it->i.p == jt->i.p && it->i.w < jt->i.w)) {
+        if(it->next == NULL) break;
+        it = it->next;
+      } else if(it->i.p > jt->i.p || (it->i.p == jt->i.p && it->i.w > jt->i.w)) {
+        tmp = new_front_item(jt->i.p, jt->i.w, it->prev, it);
+        tmp->time = jt->time;
+        tmp->prev->next = tmp;
+        tmp->next->prev = tmp;
+        jt = jt->next;
+      }
+    }
+
+    for(; jt != NULL; jt = jt->next) {
+      it->next = new_front_item(jt->i.p, jt->i.w, it, NULL);
+      it->next->time = jt->time;
+      it = it->next;
+    }
+  }
+
+  return ret_front;
+}
+
 struct front_item * nem_ull_step(struct front_item * b, struct data * d, int it){
   unsigned long int i,l0t,l1t,n;
   double pmax;