1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
#include <stdlib.h>
#include <stdio.h>
#include "dfs.h"
#include "structs.h"
#include "common.h"
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);
/* 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);
continue;
}
/* 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);
/* Remove first item from front (only a placeholder) */
front=front->next;
free(front->prev);
front->prev = NULL;
return front;
}
struct online_return dfs_online(struct data * data, struct front_item * front, struct tree_item * tree, long int change_at){
if(front == NULL) {
front = new_front_item(0, 0, NULL, NULL);
}
struct front_item * front_last = front;
for(;front_last->next != NULL; front_last=front_last->next);
if(tree == NULL) {
tree = new_tree_item(0, 0, 0, 0, NULL, NULL);
}
long int change=0;
/* 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;
/* 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;
free(old);
change++;
continue;
}
/* 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;
/* 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;
free(old);
} while(tree != NULL && change < change_at);
struct online_return ret;
ret.front = front;
ret.tree = tree;
return ret;
}
|
