diff options
| -rw-r--r-- | include/common.h | 1 | ||||
| -rw-r--r-- | include/structs.h | 9 | ||||
| -rw-r--r-- | src/common.c | 18 | ||||
| -rw-r--r-- | src/dfs.c | 80 |
4 files changed, 78 insertions, 30 deletions
diff --git a/include/common.h b/include/common.h index 9332e6e..b188955 100644 --- a/include/common.h +++ b/include/common.h @@ -12,6 +12,7 @@ void print_front(struct front_item *); void free_data(struct data *); void free_front(struct front_item *); struct front_item * new_front_item(double, double, struct front_item *, struct front_item *); +struct tree_item * new_tree_item(long int, long int, double, double, struct tree_item *, struct tree_item *); double dist_items(struct item *, struct item *); int len_front(struct front_item *); int cmp_items_ratio(const void * a, const void * b); diff --git a/include/structs.h b/include/structs.h index 035af45..7c39b4d 100644 --- a/include/structs.h +++ b/include/structs.h @@ -21,4 +21,13 @@ struct front_item { struct front_item * prev; clock_t time; }; + +struct tree_item { + long int depth; + long int itemi; + struct item values; + struct tree_item * prev; + struct tree_item * next; +}; + #endif diff --git a/src/common.c b/src/common.c index ee98bba..7a8b316 100644 --- a/src/common.c +++ b/src/common.c @@ -5,8 +5,6 @@ #include "structs.h" #include "common.h" -#define RAND_MAX 1 - struct data * input(char fp[]){ int i,j; FILE *f; @@ -39,9 +37,7 @@ int cmp_items_ratio(const void * a, const void * b){ } int cmp_items_random(const void *a, const void *b) { - struct item c = *(struct item *)a; - struct item d = *(struct item *)b; - if(rand() > 0.5){ + if(rand() % 2 == 0){ return 1; } return -1; @@ -94,6 +90,18 @@ struct front_item * new_front_item(double p, double w, struct front_item * prev, return f; } +struct tree_item * new_tree_item(long int depth, long int itemi, double w, double p, struct tree_item * prev, struct tree_item * next) { + struct tree_item * t = (struct tree_item *)malloc(sizeof(struct tree_item)); + t->depth = depth; + t->itemi = itemi; + t->values.w = w; + t->values.p = p; + t->prev = prev; + t->next = next; + + return t; +} + double dist_items(struct item * a, struct item * b){ return sqrt((a->p - b->p)*(a->p - b->p) + (a->w - b->w)*(a->w - b->w)); } @@ -3,34 +3,64 @@ #include "structs.h" #include "common.h" -struct front_item * rec(struct data * d, int i, struct item * it) { - if(i == d->N) { - return new_front_item(it->p, it->w, NULL, NULL); - } +struct front_item * dfs(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); - // Go left (select item) - it->p += d->items[i].p; - it->w += d->items[i].w; - struct front_item * f1 = rec(d, i+1, it); - it->p -= d->items[i].p; - it->w -= d->items[i].w; + /* 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); - // Go right (do not select item) - struct front_item * f2 = rec(d, i+1, it); + continue; + } - // Merge - struct front_item * f1_end = f1; - for(;f1_end->next!=NULL; f1_end = f1_end->next); - f1_end->next = f2; - f2->prev = f1_end; - - return f1; -} + /* 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); -struct front_item * dfs(struct data * d) { - struct item * it = (struct item *)malloc(sizeof(struct item)); - it->p = 0; - it->w = 0; + /* Remove first item from front (only a placeholder) */ + front=front->next; + free(front->prev); + front->prev = NULL; - return rec(d, 0, it); + return front; } |