1 files changed, 40 insertions, 4 deletions

diff --git a/src/nem_ull.c b/src/nem_ull.c
index 6405fc2..2605e69 100644
--- a/src/nem_ull.c
+++ b/src/nem_ull.c
@@ -5,16 +5,46 @@
 #include "common.h"
 
 struct front_item * nem_ull(struct data * d){
-  struct front_item * begin;
+  struct front_item * front;
+  struct front_item * ret_front;
+  struct front_item * it;
+  struct front_item * tmp;
+  struct front_item * jt;
   int i;
 
-  begin = new_front_item(0,0,NULL,NULL);
+  front = new_front_item(0,0,NULL,NULL);
+  ret_front = new_front_item(0,0,NULL,NULL);
 
   for(i=0;i<d->N;++i){
-    begin = nem_ull_step(begin,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 begin;
+  return ret_front;
 }
 
 struct front_item * nem_ull_online_shuffle(struct data * d, int rand_i){
@@ -68,17 +98,20 @@ struct front_item * nem_ull_step(struct front_item * b, struct data * d, int it)
   double pmax;
   struct item * l0;
   struct item * l1;
+  clock_t * c0;
   struct front_item * p = b;
 
   for(n=0;p!=NULL;p=p->next,++n);
   p = b;
 
   l0 = (struct item *)malloc(n*sizeof(struct item));
+  c0 = (clock_t *)malloc(n*sizeof(clock_t));
   l1 = (struct item *)malloc(n*sizeof(struct item));
 
   for(i=0;i<n;++i){
     l0[i].p=p->i.p;
     l0[i].w=p->i.w;
+    c0[i] = p->time;
 
     l1[i].p=p->i.p + d->items[it].p;
     l1[i].w=p->i.w + d->items[it].w;
@@ -117,6 +150,7 @@ struct front_item * nem_ull_step(struct front_item * b, struct data * d, int it)
     if(l1t == n){
       for(;l0t<n;++l0t){
         p = new_front_item(l0[l0t].p, l0[l0t].w, p, NULL);
+        p->time = c0[l0t];
         p->prev->next = p;
       }
       break;
@@ -124,6 +158,7 @@ struct front_item * nem_ull_step(struct front_item * b, struct data * d, int it)
 
     if((l0[l0t].w < l1[l1t].w) || ((l0[l0t].w == l1[l1t].w) && (l0[l0t].p > l1[l1t].p))){
       p = new_front_item(l0[l0t].p, l0[l0t].w , p, NULL);
+      p->time = c0[l0t];
       p->prev->next = p;
       pmax = l0[l0t].p;
       ++l0t;
@@ -136,6 +171,7 @@ struct front_item * nem_ull_step(struct front_item * b, struct data * d, int it)
   }
 
   free(l0);
+  free(c0);
   free(l1);
 
   for(;p->prev!=NULL;p=p->prev);