28,7 → 28,7 |
|
#include <test.h> |
#include <print.h> |
#include <adt/extavlreltree.h> |
#include <adt/extavlrel.h> |
#include <debug.h> |
|
#include <panic.h> |
53,17 → 53,17 |
|
|
|
static int extreltree_test_height(extrelavltree_node_t *node,bool timeout); |
static extavlreltree_node_t *extreltree_test_parents(extavlireltree_node_t *node); |
static int extreltree_test_height(extavlreltree_node_t *node,bool timeout); |
static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node); |
static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level); |
static bool extreltree_test_link(int node_count); |
static void print_extreltree_link(int node_count); |
static bool extreltree_test_link(extavlreltree_t *tree, int node_count); |
static void print_extreltree_link(extavlreltree_t *tree); |
static extavlreltree_node_t *alloc_extavlreltree_node(void); |
|
|
|
//vraci hloubku stromu |
static int extreltree_test_height(extavltree_node_t *node,bool timeout) |
static int extreltree_test_height(extavlreltree_node_t *node,bool timeout) |
{ |
int h1, h2; |
|
90,7 → 90,7 |
*/ |
static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node) |
{ |
extavltree_node_t *tmp; |
extavlreltree_node_t *tmp; |
|
if (!node) return NULL; |
|
112,21 → 112,21 |
/** Checks list of nodes |
* |
*/ |
static bool extreltree_test_link(int node_count) |
static bool extreltree_test_link(extavlreltree_t *tree, int node_count) |
{ |
extavltree_node_t *node; |
extavlreltree_node_t *node; |
int i; |
bool test_link = true; |
|
for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next) |
for (i = 0,node = tree->head.next; node != &(tree->head); i++,node = node->next) |
; |
if (node_count && i != node_count) { |
if (i != node_count) { |
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count); |
test_link = false; |
} |
for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) |
for (i = 0,node = tree->head.prev; node != &(tree->head); i++,node = node->prev) |
; |
if (node_count && i != node_count) { |
if (i != node_count) { |
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count); |
test_link = false; |
} |
145,18 → 145,17 |
return sum + node->key; |
} |
|
static int extreltree_test_maxsum(extavlreltree_node_t *node) |
static int extreltree_test_rgtsum(extavlreltree_node_t *node) |
{ |
int rs, ls; |
|
if (!node) return 0; |
|
rs = extreltree_test_maxsum(node->rgt); |
ls = extreltree_test_maxsum(node->lft); |
rs = extreltree_test_rgtsum(node->rgt); |
ls = extreltree_test_rgtsum(node->lft); |
|
if (rs != node->rgt_max_key) { |
printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_max_key,rs,node->key,node); |
getchar(); |
if (rs != node->rgt_sum) { |
printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_sum,rs,node->key,node); |
} |
return rs + ls + node->key; |
} |
181,19 → 180,19 |
for (tmp = node->next,i = 0; (tmp->key == 0) && (tmp != &(extreltree.head)); tmp = tmp->next,i++) |
; |
|
printf ("%d[%d,%d]", node->key,node->rgt_max_key,i); |
printf ("%d[%d,%d]", node->key,node->rgt_sum,i); |
if (node->lft != NULL || node->rgt != NULL) |
{ |
putchar ('('); |
printf ("("); |
|
print_extreltree_structure_flat (node->lft, level + 1); |
if (node->rgt != NULL) |
{ |
putchar (','); |
printf(","); |
print_extreltree_structure_flat (node->rgt, level + 1); |
} |
|
putchar (')'); |
printf(")"); |
} |
} |
|
200,20 → 199,20 |
/** Prints list of nodes |
* |
*/ |
static void print_extreltree_link(int node_count) |
static void print_extreltree_link(extavlreltree_t *tree) |
{ |
extavltree_node_t *node; |
extavlreltree_node_t *node; |
printf("\n"); |
for (node = exttree.head.next; node != &(exttree.head); node = node->next) { |
for (node = tree->head.next; node != &(tree->head); node = node->next) { |
printf(" %d,",node->key); |
} |
for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) { |
for (node = tree->head.prev; node != &(tree->head); node = node->prev) { |
printf(" %d,",node->key); |
} |
} |
|
//**************************************************************** |
static void alloc_extavltree_node_prepare(void) |
static void alloc_extavlreltree_node_prepare(void) |
{ |
int i; |
|
280,7 → 279,7 |
*/ |
extavlreltree_create(tree); |
|
if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count); |
if (!quiet) printf("\nInserting %d nodes ...\n", node_count); |
|
for (i = 0; i < node_count; i++) { |
newnode = alloc_extavlreltree_node(); |
288,8 → 287,8 |
|
extavlreltree_insert(tree, newnode); |
if (!quiet) { |
if (!extreltree_test_link(i+1)) { |
print_extreltree_link(i+1); |
if (!extreltree_test_link(tree,i+1)) { |
print_extreltree_link(tree); |
printf("\n"); |
} |
extreltree_test_parents(tree->root); |
311,14 → 310,14 |
|
switch(node_position) { |
case 0: //mazani vzdy korene |
if (!quiet) printf("\n\nDelete root nodes\n"); |
i = node_count; |
if (!quiet) printf("\nDelete root nodes\n"); |
i = node_count - 1; |
while(tree->root != NULL) { |
delnode = tree->root; |
extavlreltree_delete(tree,delnode); |
if (!quiet) { |
if (!extreltree_test_link(i)) { |
print_extreltree_link(i); |
if (!extreltree_test_link(tree,i)) { |
print_extreltree_link(tree); |
printf("\n"); |
} |
extreltree_test_parents(tree->root); |
330,12 → 329,12 |
|
break; |
case 1: |
if (!quiet) printf("\n\nDelete nodes according to their time of origin\n"); |
if (!quiet) printf("\nDelete nodes according to their time of origin\n"); |
for (i = 0; i < node_count; i++) { |
extavlreltree_delete(tree,&(extavlreltree_nodes[i])); |
if (!quiet) { |
if (!extreltree_test_link(i+1)) { |
print_extreltree_link(i+1); |
if (!extreltree_test_link(tree,node_count-i-1)) { |
print_extreltree_link(tree); |
printf("\n"); |
} |
extreltree_test_parents(tree->root); |
352,15 → 351,15 |
|
static void timeout_extreltree(extavlreltree_t *tree, int node_count, bool quiet) |
{ |
int i = node_count; |
int i = node_count - 1; |
|
if (!quiet) printf("Timeout tree ...\n"); |
if (!quiet) printf("\nTimeout tree ...\n"); |
|
while(tree->head.next != &(tree->head)) { |
extavlreltree_delete_min(tree); |
if (!quiet) { |
if (!extreltree_test_link(i)) { |
print_extreltree_link(i); |
if (!extreltree_test_link(tree,i)) { |
print_extreltree_link(tree); |
printf("\n"); |
} |
extreltree_test_parents(tree->root); |
370,7 → 369,7 |
i--; |
} |
|
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!"); |
if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n"); |
|
if (!quiet) printf("Timeout tree finished\n"); |
} |