summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/dfs.c11
-rw-r--r--src/main/online.c9
-rw-r--r--src/random_heuristic.c66
3 files changed, 45 insertions, 41 deletions
diff --git a/src/dfs.c b/src/dfs.c
index b0bda53..12f4ee2 100644
--- a/src/dfs.c
+++ b/src/dfs.c
@@ -92,11 +92,12 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s
front_last->next = new_front_item(tree->values.p, tree->values.w, front_last, NULL);
front_last = front_last->next;
+ /* Adjust prev and next */
+ if(tree->prev != NULL) tree->prev->next = tree->next;
+ if(tree->next != NULL) tree->next->prev = tree->prev;
+
struct tree_item * old = tree;
tree = tree->next;
- if(tree != NULL) {
- tree->prev = old->prev;
- }
free(old);
change++;
@@ -125,6 +126,10 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s
/* Update left next */
left->next = right;
+ /* Adjust prev and next */
+ if(tree->prev != NULL) tree->prev->next = left;
+ if(tree->next != NULL) tree->next->prev = right;
+
/* Update tree to left node and free old node */
struct tree_item * old = tree;
tree = left;
diff --git a/src/main/online.c b/src/main/online.c
index ba8a94c..fb400ef 100644
--- a/src/main/online.c
+++ b/src/main/online.c
@@ -13,13 +13,13 @@ int main(int argc, char * argv[]){
struct front_item * front = NULL;
struct online_return ret;
- if(argc!=5){
+ if(argc!=6){
printf("Wrong number of arguments!\n");
- printf("Example usage: %s algorithm1 algorithm2 sort_method data_file\n",argv[0]);
+ printf("Example usage: %s algorithm1 algorithm2 sort_method cut_pointa data_file\n", argv[0]);
return 0;
}
- data = input(argv[4]);
+ data = input(argv[5]);
/* Sort data */
srand(time(NULL));
@@ -29,10 +29,11 @@ int main(int argc, char * argv[]){
qsort(data->items, data->N, sizeof(struct item), cmp_items_ratio);
}
+ printf("%d\n", atoi(argv[4]));
clock_t t = clock();
/* Choose algorithm1 */
if(strcmp(argv[1], "dfs") == 0) {
- ret = dfs_online(data, NULL, NULL, 20);
+ ret = dfs_online(data, NULL, NULL, atoi(argv[4]));
} else if(strcmp(argv[1], "random_heuristic") == 0) {
ret = random_heuristic_online(data, NULL, NULL);
}
diff --git a/src/random_heuristic.c b/src/random_heuristic.c
index 0076728..529a186 100644
--- a/src/random_heuristic.c
+++ b/src/random_heuristic.c
@@ -9,12 +9,13 @@ struct front_item * random_heuristic(struct data * data) {
struct front_item * front_last = front;
struct tree_item * tree = new_tree_item(0, 0, 0, 0, NULL, NULL);
long int tree_size = 1;
+
+ /* 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);
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) {
@@ -35,6 +36,13 @@ struct front_item * random_heuristic(struct data * data) {
free(old);
/* Reduce tree_size */
tree_size--;
+
+ if(tree != NULL) {
+ /* Select new random node */
+ position = rand() % tree_size;
+ node = tree;
+ for(int i = 0; i < position; i++,node=node->next);
+ }
continue;
}
@@ -73,6 +81,13 @@ struct front_item * random_heuristic(struct data * data) {
tree = left;
}
free(old);
+
+ /* Choose left or right randomly for node */
+ if(rand() % 2 == 0) {
+ node = left;
+ } else {
+ node = right;
+ }
/* Increment tree_size */
tree_size++;
@@ -87,8 +102,6 @@ struct front_item * random_heuristic(struct data * data) {
}
struct online_return random_heuristic_online(struct data * data, struct front_item * front, struct tree_item * tree) {
-
-
if(front == NULL) {
front = new_front_item(0, 0, NULL, NULL);
}
@@ -100,7 +113,7 @@ struct online_return random_heuristic_online(struct data * data, struct front_it
}
long int tree_size = 0;
for(struct tree_item * tree_node = tree; tree_node != NULL; tree_node = tree_node->next, tree_size++);
-
+
/* Choose tree node randomly */
long int position = rand() % tree_size;
struct tree_item * node = tree;
@@ -112,18 +125,12 @@ struct online_return random_heuristic_online(struct data * data, struct front_it
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->prev != NULL) node->prev->next = node->next;
+ if(node->next != NULL) node->next->prev = node->prev;
+
+ if(tree == node) tree = node->next;
+ free(node);
- 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--;
@@ -146,9 +153,6 @@ struct online_return random_heuristic_online(struct data * data, struct front_it
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(
@@ -159,28 +163,22 @@ struct online_return random_heuristic_online(struct data * data, struct front_it
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);
+ if(node->prev != NULL) node->prev->next = left;
+ if(node->next != NULL) node->next->prev = right;
+
+ if(tree == node) tree = left;
+ free(node);
/* Choose left or right randomly for node */
- if(rand() % 2 == 0) {
- node = left;
- } else {
- node = right;
- }
+ node = rand() % 2 == 0 ? left : right;
/* Increment tree_size */
tree_size++;
+
} while(tree != NULL);
struct online_return ret;
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-22 07:34:29 +0000