Rev 2416 | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2416 | Rev 2421 | ||
---|---|---|---|
1 | /* |
1 | /* |
2 | * Copyright (c) 2007 Vojtech Mencl |
2 | * Copyright (c) 2007 Vojtech Mencl |
3 | * All rights reserved. |
3 | * All rights reserved. |
4 | * |
4 | * |
5 | * Redistribution and use in source and binary forms, with or without |
5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions |
6 | * modification, are permitted provided that the following conditions |
7 | * are met: |
7 | * are met: |
8 | * |
8 | * |
9 | * - Redistributions of source code must retain the above copyright |
9 | * - Redistributions of source code must retain the above copyright |
10 | * notice, this list of conditions and the following disclaimer. |
10 | * notice, this list of conditions and the following disclaimer. |
11 | * - Redistributions in binary form must reproduce the above copyright |
11 | * - Redistributions in binary form must reproduce the above copyright |
12 | * notice, this list of conditions and the following disclaimer in the |
12 | * notice, this list of conditions and the following disclaimer in the |
13 | * documentation and/or other materials provided with the distribution. |
13 | * documentation and/or other materials provided with the distribution. |
14 | * - The name of the author may not be used to endorse or promote products |
14 | * - The name of the author may not be used to endorse or promote products |
15 | * derived from this software without specific prior written permission. |
15 | * derived from this software without specific prior written permission. |
16 | * |
16 | * |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
27 | */ |
28 | 28 | ||
29 | #include <test.h> |
29 | #include <test.h> |
30 | #include <print.h> |
30 | #include <print.h> |
31 | #include <adt/extavlreltree.h> |
31 | #include <adt/extavlrel.h> |
32 | #include <debug.h> |
32 | #include <debug.h> |
33 | 33 | ||
34 | #include <panic.h> |
34 | #include <panic.h> |
35 | 35 | ||
36 | 36 | ||
37 | #define NODE_COUNT 100 |
37 | #define NODE_COUNT 100 |
38 | 38 | ||
39 | /* |
39 | /* |
40 | * wrapper structure with a pointer to extended avl tree root |
40 | * wrapper structure with a pointer to extended avl tree root |
41 | */ |
41 | */ |
42 | static extavlreltree_t extreltree; |
42 | static extavlreltree_t extreltree; |
43 | 43 | ||
44 | /* |
44 | /* |
45 | * extavltree nodes in array for faster allocating |
45 | * extavltree nodes in array for faster allocating |
46 | */ |
46 | */ |
47 | static extavlreltree_node_t extavlreltree_nodes[NODE_COUNT]; |
47 | static extavlreltree_node_t extavlreltree_nodes[NODE_COUNT]; |
48 | 48 | ||
49 | /* |
49 | /* |
50 | * head of free nodes' list: |
50 | * head of free nodes' list: |
51 | */ |
51 | */ |
52 | static extavlreltree_node_t *first_free_node = NULL; |
52 | static extavlreltree_node_t *first_free_node = NULL; |
53 | 53 | ||
54 | 54 | ||
55 | 55 | ||
56 | static int extreltree_test_height(extrelavltree_node_t *node,bool timeout); |
56 | static int extreltree_test_height(extavlreltree_node_t *node,bool timeout); |
57 | static extavlreltree_node_t *extreltree_test_parents(extavlireltree_node_t *node); |
57 | static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node); |
58 | static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level); |
58 | static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level); |
59 | static bool extreltree_test_link(int node_count); |
59 | static bool extreltree_test_link(extavlreltree_t *tree, int node_count); |
60 | static void print_extreltree_link(int node_count); |
60 | static void print_extreltree_link(extavlreltree_t *tree); |
61 | static extavlreltree_node_t *alloc_extavlreltree_node(void); |
61 | static extavlreltree_node_t *alloc_extavlreltree_node(void); |
62 | 62 | ||
63 | 63 | ||
64 | 64 | ||
65 | //vraci hloubku stromu |
65 | //vraci hloubku stromu |
66 | static int extreltree_test_height(extavltree_node_t *node,bool timeout) |
66 | static int extreltree_test_height(extavlreltree_node_t *node,bool timeout) |
67 | { |
67 | { |
68 | int h1, h2; |
68 | int h1, h2; |
69 | 69 | ||
70 | if (!node) return -1; |
70 | if (!node) return -1; |
71 | 71 | ||
72 | h1 = extreltree_test_height(node->lft,timeout) + 1; |
72 | h1 = extreltree_test_height(node->lft,timeout) + 1; |
73 | if (!timeout && node->lft_height != h1) { |
73 | if (!timeout && node->lft_height != h1) { |
74 | printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node); |
74 | printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node); |
75 | } |
75 | } |
76 | h2 = extreltree_test_height(node->rgt,0) + 1; |
76 | h2 = extreltree_test_height(node->rgt,0) + 1; |
77 | if (node->rgt_height != h2) { |
77 | if (node->rgt_height != h2) { |
78 | printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node); |
78 | printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node); |
79 | } |
79 | } |
80 | if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) { |
80 | if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) { |
81 | printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node); |
81 | printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node); |
82 | } |
82 | } |
83 | 83 | ||
84 | return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height); |
84 | return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height); |
85 | } |
85 | } |
86 | 86 | ||
87 | 87 | ||
88 | /** Tests par atribute of every tree node |
88 | /** Tests par atribute of every tree node |
89 | * |
89 | * |
90 | */ |
90 | */ |
91 | static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node) |
91 | static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node) |
92 | { |
92 | { |
93 | extavltree_node_t *tmp; |
93 | extavlreltree_node_t *tmp; |
94 | 94 | ||
95 | if (!node) return NULL; |
95 | if (!node) return NULL; |
96 | 96 | ||
97 | if (node->lft) { |
97 | if (node->lft) { |
98 | tmp = extreltree_test_parents(node->lft); |
98 | tmp = extreltree_test_parents(node->lft); |
99 | if (tmp != node) { |
99 | if (tmp != node) { |
100 | printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft); |
100 | printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft); |
101 | } |
101 | } |
102 | } |
102 | } |
103 | if (node->rgt) { |
103 | if (node->rgt) { |
104 | tmp = extreltree_test_parents(node->rgt); |
104 | tmp = extreltree_test_parents(node->rgt); |
105 | if (tmp != node) { |
105 | if (tmp != node) { |
106 | printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt); |
106 | printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt); |
107 | } |
107 | } |
108 | } |
108 | } |
109 | return node->par; |
109 | return node->par; |
110 | } |
110 | } |
111 | 111 | ||
112 | /** Checks list of nodes |
112 | /** Checks list of nodes |
113 | * |
113 | * |
114 | */ |
114 | */ |
115 | static bool extreltree_test_link(int node_count) |
115 | static bool extreltree_test_link(extavlreltree_t *tree, int node_count) |
116 | { |
116 | { |
117 | extavltree_node_t *node; |
117 | extavlreltree_node_t *node; |
118 | int i; |
118 | int i; |
119 | bool test_link = true; |
119 | bool test_link = true; |
120 | 120 | ||
121 | for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next) |
121 | for (i = 0,node = tree->head.next; node != &(tree->head); i++,node = node->next) |
122 | ; |
122 | ; |
123 | if (node_count && i != node_count) { |
123 | if (i != node_count) { |
124 | printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count); |
124 | printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count); |
125 | test_link = false; |
125 | test_link = false; |
126 | } |
126 | } |
127 | for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) |
127 | for (i = 0,node = tree->head.prev; node != &(tree->head); i++,node = node->prev) |
128 | ; |
128 | ; |
129 | if (node_count && i != node_count) { |
129 | if (i != node_count) { |
130 | printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count); |
130 | printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count); |
131 | test_link = false; |
131 | test_link = false; |
132 | } |
132 | } |
133 | return test_link; |
133 | return test_link; |
134 | } |
134 | } |
135 | 135 | ||
136 | static int _sum_extreltree(extavlreltree_node_t *node) |
136 | static int _sum_extreltree(extavlreltree_node_t *node) |
137 | { |
137 | { |
138 | int sum = 0; |
138 | int sum = 0; |
139 | 139 | ||
140 | if (node->rgt) |
140 | if (node->rgt) |
141 | sum += _sum_extreltree(node->rgt); |
141 | sum += _sum_extreltree(node->rgt); |
142 | if (node->lft) |
142 | if (node->lft) |
143 | sum += _sum_extreltree(node->lft); |
143 | sum += _sum_extreltree(node->lft); |
144 | 144 | ||
145 | return sum + node->key; |
145 | return sum + node->key; |
146 | } |
146 | } |
147 | 147 | ||
148 | static int extreltree_test_maxsum(extavlreltree_node_t *node) |
148 | static int extreltree_test_rgtsum(extavlreltree_node_t *node) |
149 | { |
149 | { |
150 | int rs, ls; |
150 | int rs, ls; |
151 | 151 | ||
152 | if (!node) return 0; |
152 | if (!node) return 0; |
153 | 153 | ||
154 | rs = extreltree_test_maxsum(node->rgt); |
154 | rs = extreltree_test_rgtsum(node->rgt); |
155 | ls = extreltree_test_maxsum(node->lft); |
155 | ls = extreltree_test_rgtsum(node->lft); |
156 | 156 | ||
157 | if (rs != node->rgt_max_key) { |
157 | if (rs != node->rgt_sum) { |
158 | printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_max_key,rs,node->key,node); |
158 | printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_sum,rs,node->key,node); |
159 | getchar(); |
- | |
160 | } |
159 | } |
161 | return rs + ls + node->key; |
160 | return rs + ls + node->key; |
162 | } |
161 | } |
163 | 162 | ||
164 | /** Prints the structure of node, which is level levels from the top of the tree. |
163 | /** Prints the structure of node, which is level levels from the top of the tree. |
165 | * |
164 | * |
166 | */ |
165 | */ |
167 | static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level) |
166 | static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level) |
168 | { |
167 | { |
169 | extavlreltree_node_t *tmp; |
168 | extavlreltree_node_t *tmp; |
170 | int i; |
169 | int i; |
171 | 170 | ||
172 | if (level > 16) |
171 | if (level > 16) |
173 | { |
172 | { |
174 | printf ("[...]"); |
173 | printf ("[...]"); |
175 | return; |
174 | return; |
176 | } |
175 | } |
177 | 176 | ||
178 | if (node == NULL) |
177 | if (node == NULL) |
179 | return; |
178 | return; |
180 | 179 | ||
181 | for (tmp = node->next,i = 0; (tmp->key == 0) && (tmp != &(extreltree.head)); tmp = tmp->next,i++) |
180 | for (tmp = node->next,i = 0; (tmp->key == 0) && (tmp != &(extreltree.head)); tmp = tmp->next,i++) |
182 | ; |
181 | ; |
183 | 182 | ||
184 | printf ("%d[%d,%d]", node->key,node->rgt_max_key,i); |
183 | printf ("%d[%d,%d]", node->key,node->rgt_sum,i); |
185 | if (node->lft != NULL || node->rgt != NULL) |
184 | if (node->lft != NULL || node->rgt != NULL) |
186 | { |
185 | { |
187 | putchar ('('); |
186 | printf ("("); |
188 | 187 | ||
189 | print_extreltree_structure_flat (node->lft, level + 1); |
188 | print_extreltree_structure_flat (node->lft, level + 1); |
190 | if (node->rgt != NULL) |
189 | if (node->rgt != NULL) |
191 | { |
190 | { |
192 | putchar (','); |
191 | printf(","); |
193 | print_extreltree_structure_flat (node->rgt, level + 1); |
192 | print_extreltree_structure_flat (node->rgt, level + 1); |
194 | } |
193 | } |
195 | 194 | ||
196 | putchar (')'); |
195 | printf(")"); |
197 | } |
196 | } |
198 | } |
197 | } |
199 | 198 | ||
200 | /** Prints list of nodes |
199 | /** Prints list of nodes |
201 | * |
200 | * |
202 | */ |
201 | */ |
203 | static void print_extreltree_link(int node_count) |
202 | static void print_extreltree_link(extavlreltree_t *tree) |
204 | { |
203 | { |
205 | extavltree_node_t *node; |
204 | extavlreltree_node_t *node; |
206 | printf("\n"); |
205 | printf("\n"); |
207 | for (node = exttree.head.next; node != &(exttree.head); node = node->next) { |
206 | for (node = tree->head.next; node != &(tree->head); node = node->next) { |
208 | printf(" %d,",node->key); |
207 | printf(" %d,",node->key); |
209 | } |
208 | } |
210 | for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) { |
209 | for (node = tree->head.prev; node != &(tree->head); node = node->prev) { |
211 | printf(" %d,",node->key); |
210 | printf(" %d,",node->key); |
212 | } |
211 | } |
213 | } |
212 | } |
214 | 213 | ||
215 | //**************************************************************** |
214 | //**************************************************************** |
216 | static void alloc_extavltree_node_prepare(void) |
215 | static void alloc_extavlreltree_node_prepare(void) |
217 | { |
216 | { |
218 | int i; |
217 | int i; |
219 | 218 | ||
220 | for (i = 0; i < NODE_COUNT - 1; i++) { |
219 | for (i = 0; i < NODE_COUNT - 1; i++) { |
221 | extavlreltree_nodes[i].next = &(extavlreltree_nodes[i+1]); |
220 | extavlreltree_nodes[i].next = &(extavlreltree_nodes[i+1]); |
222 | } |
221 | } |
223 | /* |
222 | /* |
224 | * Node keys which will be used for insertion. Up to NODE_COUNT size of array. |
223 | * Node keys which will be used for insertion. Up to NODE_COUNT size of array. |
225 | */ |
224 | */ |
226 | 225 | ||
227 | // First tree node and same key |
226 | // First tree node and same key |
228 | extavlreltree_nodes[0].key = 60; |
227 | extavlreltree_nodes[0].key = 60; |
229 | extavlreltree_nodes[1].key = 60; |
228 | extavlreltree_nodes[1].key = 60; |
230 | extavlreltree_nodes[2].key = 60; |
229 | extavlreltree_nodes[2].key = 60; |
231 | //LL rotation |
230 | //LL rotation |
232 | extavlreltree_nodes[3].key = 50; |
231 | extavlreltree_nodes[3].key = 50; |
233 | extavlreltree_nodes[4].key = 40; |
232 | extavlreltree_nodes[4].key = 40; |
234 | extavlreltree_nodes[5].key = 30; |
233 | extavlreltree_nodes[5].key = 30; |
235 | //LR rotation |
234 | //LR rotation |
236 | extavlreltree_nodes[6].key = 20; |
235 | extavlreltree_nodes[6].key = 20; |
237 | extavlreltree_nodes[7].key = 20; |
236 | extavlreltree_nodes[7].key = 20; |
238 | extavlreltree_nodes[8].key = 25; |
237 | extavlreltree_nodes[8].key = 25; |
239 | extavlreltree_nodes[9].key = 25; |
238 | extavlreltree_nodes[9].key = 25; |
240 | //LL rotation in lower floor |
239 | //LL rotation in lower floor |
241 | extavlreltree_nodes[10].key = 35; |
240 | extavlreltree_nodes[10].key = 35; |
242 | //RR rotation |
241 | //RR rotation |
243 | extavlreltree_nodes[11].key = 70; |
242 | extavlreltree_nodes[11].key = 70; |
244 | extavlreltree_nodes[12].key = 80; |
243 | extavlreltree_nodes[12].key = 80; |
245 | //RL rotation |
244 | //RL rotation |
246 | extavlreltree_nodes[13].key = 90; |
245 | extavlreltree_nodes[13].key = 90; |
247 | extavlreltree_nodes[14].key = 85; |
246 | extavlreltree_nodes[14].key = 85; |
248 | extavlreltree_nodes[15].key = 100; |
247 | extavlreltree_nodes[15].key = 100; |
249 | extavlreltree_nodes[16].key = 200; |
248 | extavlreltree_nodes[16].key = 200; |
250 | extavlreltree_nodes[17].key = 300; |
249 | extavlreltree_nodes[17].key = 300; |
251 | extavlreltree_nodes[18].key = 400; |
250 | extavlreltree_nodes[18].key = 400; |
252 | extavlreltree_nodes[19].key = 500; |
251 | extavlreltree_nodes[19].key = 500; |
253 | extavlreltree_nodes[20].key = 600; |
252 | extavlreltree_nodes[20].key = 600; |
254 | 253 | ||
255 | for (i = 21; i < NODE_COUNT; i++) |
254 | for (i = 21; i < NODE_COUNT; i++) |
256 | extavlreltree_nodes[i].key = i * 3; |
255 | extavlreltree_nodes[i].key = i * 3; |
257 | 256 | ||
258 | extavlreltree_nodes[i].next = NULL; |
257 | extavlreltree_nodes[i].next = NULL; |
259 | first_free_node = &(extavlreltree_nodes[0]); |
258 | first_free_node = &(extavlreltree_nodes[0]); |
260 | } |
259 | } |
261 | 260 | ||
262 | static extavlreltree_node_t *alloc_extavlreltree_node(void) |
261 | static extavlreltree_node_t *alloc_extavlreltree_node(void) |
263 | { |
262 | { |
264 | extavlreltree_node_t *node; |
263 | extavlreltree_node_t *node; |
265 | 264 | ||
266 | node = first_free_node; |
265 | node = first_free_node; |
267 | first_free_node = first_free_node->next; |
266 | first_free_node = first_free_node->next; |
268 | 267 | ||
269 | return node; |
268 | return node; |
270 | } |
269 | } |
271 | //**************************************************************** |
270 | //**************************************************************** |
272 | 271 | ||
273 | static void test_extreltree_insert(extavlreltree_t *tree, unsigned int node_count, int quiet) |
272 | static void test_extreltree_insert(extavlreltree_t *tree, unsigned int node_count, int quiet) |
274 | { |
273 | { |
275 | unsigned int i; |
274 | unsigned int i; |
276 | extavlreltree_node_t *newnode; |
275 | extavlreltree_node_t *newnode; |
277 | 276 | ||
278 | /* |
277 | /* |
279 | * Initialize tree before using. |
278 | * Initialize tree before using. |
280 | */ |
279 | */ |
281 | extavlreltree_create(tree); |
280 | extavlreltree_create(tree); |
282 | 281 | ||
283 | if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count); |
282 | if (!quiet) printf("\nInserting %d nodes ...\n", node_count); |
284 | 283 | ||
285 | for (i = 0; i < node_count; i++) { |
284 | for (i = 0; i < node_count; i++) { |
286 | newnode = alloc_extavlreltree_node(); |
285 | newnode = alloc_extavlreltree_node(); |
287 | //if (!quiet) printf("[[[%d]]]\n",newnode->key); |
286 | //if (!quiet) printf("[[[%d]]]\n",newnode->key); |
288 | 287 | ||
289 | extavlreltree_insert(tree, newnode); |
288 | extavlreltree_insert(tree, newnode); |
290 | if (!quiet) { |
289 | if (!quiet) { |
291 | if (!extreltree_test_link(i+1)) { |
290 | if (!extreltree_test_link(tree,i+1)) { |
292 | print_extreltree_link(i+1); |
291 | print_extreltree_link(tree); |
293 | printf("\n"); |
292 | printf("\n"); |
294 | } |
293 | } |
295 | extreltree_test_parents(tree->root); |
294 | extreltree_test_parents(tree->root); |
296 | extreltree_test_height(tree->root,1); |
295 | extreltree_test_height(tree->root,1); |
297 | extreltree_test_rgtsum(tree->root); |
296 | extreltree_test_rgtsum(tree->root); |
298 | } |
297 | } |
299 | } |
298 | } |
300 | 299 | ||
301 | if (!quiet) printf("Inserting was finished\n"); |
300 | if (!quiet) printf("Inserting was finished\n"); |
302 | } |
301 | } |
303 | 302 | ||
304 | static void test_extreltree_delete(extavlreltree_t *tree, int node_count, int node_position, bool quiet) |
303 | static void test_extreltree_delete(extavlreltree_t *tree, int node_count, int node_position, bool quiet) |
305 | { |
304 | { |
306 | extavlreltree_node_t *delnode; |
305 | extavlreltree_node_t *delnode; |
307 | unsigned int i; |
306 | unsigned int i; |
308 | 307 | ||
309 | //aktualni pocet tiku: |
308 | //aktualni pocet tiku: |
310 | if (!quiet) printf("Deleting tree...\n"); |
309 | if (!quiet) printf("Deleting tree...\n"); |
311 | 310 | ||
312 | switch(node_position) { |
311 | switch(node_position) { |
313 | case 0: //mazani vzdy korene |
312 | case 0: //mazani vzdy korene |
314 | if (!quiet) printf("\n\nDelete root nodes\n"); |
313 | if (!quiet) printf("\nDelete root nodes\n"); |
315 | i = node_count; |
314 | i = node_count - 1; |
316 | while(tree->root != NULL) { |
315 | while(tree->root != NULL) { |
317 | delnode = tree->root; |
316 | delnode = tree->root; |
318 | extavlreltree_delete(tree,delnode); |
317 | extavlreltree_delete(tree,delnode); |
319 | if (!quiet) { |
318 | if (!quiet) { |
320 | if (!extreltree_test_link(i)) { |
319 | if (!extreltree_test_link(tree,i)) { |
321 | print_extreltree_link(i); |
320 | print_extreltree_link(tree); |
322 | printf("\n"); |
321 | printf("\n"); |
323 | } |
322 | } |
324 | extreltree_test_parents(tree->root); |
323 | extreltree_test_parents(tree->root); |
325 | extreltree_test_height(tree->root,1); |
324 | extreltree_test_height(tree->root,1); |
326 | extreltree_test_rgtsum(tree->root); |
325 | extreltree_test_rgtsum(tree->root); |
327 | } |
326 | } |
328 | i--; |
327 | i--; |
329 | } |
328 | } |
330 | 329 | ||
331 | break; |
330 | break; |
332 | case 1: |
331 | case 1: |
333 | if (!quiet) printf("\n\nDelete nodes according to their time of origin\n"); |
332 | if (!quiet) printf("\nDelete nodes according to their time of origin\n"); |
334 | for (i = 0; i < node_count; i++) { |
333 | for (i = 0; i < node_count; i++) { |
335 | extavlreltree_delete(tree,&(extavlreltree_nodes[i])); |
334 | extavlreltree_delete(tree,&(extavlreltree_nodes[i])); |
336 | if (!quiet) { |
335 | if (!quiet) { |
337 | if (!extreltree_test_link(i+1)) { |
336 | if (!extreltree_test_link(tree,node_count-i-1)) { |
338 | print_extreltree_link(i+1); |
337 | print_extreltree_link(tree); |
339 | printf("\n"); |
338 | printf("\n"); |
340 | } |
339 | } |
341 | extreltree_test_parents(tree->root); |
340 | extreltree_test_parents(tree->root); |
342 | extreltree_test_height(tree->root,1); |
341 | extreltree_test_height(tree->root,1); |
343 | extreltree_test_rgtsum(tree->root); |
342 | extreltree_test_rgtsum(tree->root); |
344 | } |
343 | } |
345 | } |
344 | } |
346 | 345 | ||
347 | break; |
346 | break; |
348 | } |
347 | } |
349 | 348 | ||
350 | if (!quiet) printf("Deletion was finished\n"); |
349 | if (!quiet) printf("Deletion was finished\n"); |
351 | } |
350 | } |
352 | 351 | ||
353 | static void timeout_extreltree(extavlreltree_t *tree, int node_count, bool quiet) |
352 | static void timeout_extreltree(extavlreltree_t *tree, int node_count, bool quiet) |
354 | { |
353 | { |
355 | int i = node_count; |
354 | int i = node_count - 1; |
356 | 355 | ||
357 | if (!quiet) printf("Timeout tree ...\n"); |
356 | if (!quiet) printf("\nTimeout tree ...\n"); |
358 | 357 | ||
359 | while(tree->head.next != &(tree->head)) { |
358 | while(tree->head.next != &(tree->head)) { |
360 | extavlreltree_delete_min(tree); |
359 | extavlreltree_delete_min(tree); |
361 | if (!quiet) { |
360 | if (!quiet) { |
362 | if (!extreltree_test_link(i)) { |
361 | if (!extreltree_test_link(tree,i)) { |
363 | print_extreltree_link(i); |
362 | print_extreltree_link(tree); |
364 | printf("\n"); |
363 | printf("\n"); |
365 | } |
364 | } |
366 | extreltree_test_parents(tree->root); |
365 | extreltree_test_parents(tree->root); |
367 | extreltree_test_height(tree->root,1); |
366 | extreltree_test_height(tree->root,1); |
368 | extreltree_test_rgtsum(tree->root); |
367 | extreltree_test_rgtsum(tree->root); |
369 | } |
368 | } |
370 | i--; |
369 | i--; |
371 | } |
370 | } |
372 | 371 | ||
373 | if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!"); |
372 | if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n"); |
374 | 373 | ||
375 | if (!quiet) printf("Timeout tree finished\n"); |
374 | if (!quiet) printf("Timeout tree finished\n"); |
376 | } |
375 | } |
377 | 376 | ||
378 | char * test_extavlreltree1(bool quiet) |
377 | char * test_extavlreltree1(bool quiet) |
379 | { |
378 | { |
380 | alloc_extavlreltree_node_prepare(); |
379 | alloc_extavlreltree_node_prepare(); |
381 | test_extreltree_insert(&extreltree, NODE_COUNT, quiet); |
380 | test_extreltree_insert(&extreltree, NODE_COUNT, quiet); |
382 | test_extreltree_delete(&extreltree, NODE_COUNT, 0, quiet); |
381 | test_extreltree_delete(&extreltree, NODE_COUNT, 0, quiet); |
383 | 382 | ||
384 | alloc_extavlreltree_node_prepare(); |
383 | alloc_extavlreltree_node_prepare(); |
385 | test_extreltree_insert(&extreltree, NODE_COUNT, quiet); |
384 | test_extreltree_insert(&extreltree, NODE_COUNT, quiet); |
386 | test_extreltree_delete(&extreltree, NODE_COUNT, 1, quiet); |
385 | test_extreltree_delete(&extreltree, NODE_COUNT, 1, quiet); |
387 | 386 | ||
388 | alloc_extavlreltree_node_prepare(); |
387 | alloc_extavlreltree_node_prepare(); |
389 | test_extreltree_insert(&extreltree, NODE_COUNT, quiet); |
388 | test_extreltree_insert(&extreltree, NODE_COUNT, quiet); |
390 | timeout_extreltree(&extreltree, NODE_COUNT, quiet); |
389 | timeout_extreltree(&extreltree, NODE_COUNT, quiet); |
391 | 390 | ||
392 | return NULL; |
391 | return NULL; |
393 | } |
392 | } |
394 | 393 |