aboutsummaryrefslogtreecommitdiffstats
path: root/src/nem_ull.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/nem_ull.c')
-rw-r--r--src/nem_ull.c172
1 files changed, 86 insertions, 86 deletions
diff --git a/src/nem_ull.c b/src/nem_ull.c
index 9a6b328..f08506b 100644
--- a/src/nem_ull.c
+++ b/src/nem_ull.c
@@ -4,96 +4,96 @@
#include "common.h"
struct front_item * nem_ull(struct data * d){
- struct front_item * begin;
- int i;
+ struct front_item * begin;
+ int i;
- begin = new_front_item(0,0,NULL,NULL);
+ begin = new_front_item(0,0,NULL,NULL);
- for(i=0;i<d->N;++i){
- begin = nem_ull_step(begin,d,i);
- }
+ for(i=0;i<d->N;++i){
+ begin = nem_ull_step(begin,d,i);
+ }
- return begin;
+ return begin;
}
struct front_item * nem_ull_step(struct front_item * b, struct data * d, int it){
- unsigned long int i,l0t,l1t,n;
- double pmax;
- struct item * l0;
- struct item * l1;
- struct front_item * p = b;
-
- for(n=0;p!=NULL;p=p->next,++n);
- p = b;
-
- l0 = (struct item *)malloc(n*sizeof(struct item));
- 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;
-
- l1[i].p=p->i.p + d->items[it].p;
- l1[i].w=p->i.w + d->items[it].w;
-
- b = p;
- p = p->next;
- free(b);
- }
-
- pmax = -1;
- l0t = 0;
- l1t = 0;
- p = new_front_item(0,0,NULL,NULL);
-
- while(1){
- for(;l0t<n;++l0t){
- if(l0[l0t].p > pmax){
- break;
- }
- }
-
- for(;l1t<n;++l1t){
- if(l1[l1t].p > pmax){
- break;
- }
- }
-
- if(l0t == n){
- for(;l1t<n;++l1t){
- p = new_front_item(l1[l1t].p, l1[l1t].w, p, NULL);
- p->prev->next = p;
- }
- break;
- }
-
- if(l1t == n){
- for(;l0t<n;++l0t){
- p = new_front_item(l0[l0t].p, l0[l0t].w, p, NULL);
- p->prev->next = p;
- }
- break;
- }
-
- 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->prev->next = p;
- pmax = l0[l0t].p;
- ++l0t;
- } else {
- p = new_front_item(l1[l1t].p, l1[l1t].w , p, NULL);
- p->prev->next = p;
- pmax = l1[l1t].p;
- ++l1t;
- }
- }
-
- free(l0);
- free(l1);
-
- for(;p->prev!=NULL;p=p->prev);
- p=p->next;
- free(p->prev);
- p->prev=NULL;
- return p;
+ unsigned long int i,l0t,l1t,n;
+ double pmax;
+ struct item * l0;
+ struct item * l1;
+ struct front_item * p = b;
+
+ for(n=0;p!=NULL;p=p->next,++n);
+ p = b;
+
+ l0 = (struct item *)malloc(n*sizeof(struct item));
+ 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;
+
+ l1[i].p=p->i.p + d->items[it].p;
+ l1[i].w=p->i.w + d->items[it].w;
+
+ b = p;
+ p = p->next;
+ free(b);
+ }
+
+ pmax = -1;
+ l0t = 0;
+ l1t = 0;
+ p = new_front_item(0,0,NULL,NULL);
+
+ while(1){
+ for(;l0t<n;++l0t){
+ if(l0[l0t].p > pmax){
+ break;
+ }
+ }
+
+ for(;l1t<n;++l1t){
+ if(l1[l1t].p > pmax){
+ break;
+ }
+ }
+
+ if(l0t == n){
+ for(;l1t<n;++l1t){
+ p = new_front_item(l1[l1t].p, l1[l1t].w, p, NULL);
+ p->prev->next = p;
+ }
+ break;
+ }
+
+ if(l1t == n){
+ for(;l0t<n;++l0t){
+ p = new_front_item(l0[l0t].p, l0[l0t].w, p, NULL);
+ p->prev->next = p;
+ }
+ break;
+ }
+
+ 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->prev->next = p;
+ pmax = l0[l0t].p;
+ ++l0t;
+ } else {
+ p = new_front_item(l1[l1t].p, l1[l1t].w , p, NULL);
+ p->prev->next = p;
+ pmax = l1[l1t].p;
+ ++l1t;
+ }
+ }
+
+ free(l0);
+ free(l1);
+
+ for(;p->prev!=NULL;p=p->prev);
+ p=p->next;
+ free(p->prev);
+ p->prev=NULL;
+ return p;
}