Andrew Kesterson
5793f6a178
Some checks failed
libakstdlib CI Build / cmake_build (push) Failing after 2m41s
97 lines
2.9 KiB
C
97 lines
2.9 KiB
C
#include <stdio.h>
|
|
#include <akstdlib.h>
|
|
|
|
#define MAX_LEAVES 7
|
|
|
|
typedef struct TreeSearchParams
|
|
{
|
|
void *value;
|
|
int steps;
|
|
aksl_TreeNode *node;
|
|
} TreeSearchParams;
|
|
|
|
// This iterator does nothing but print the node names it is visiting
|
|
akerr_ErrorContext AKERR_NOIGNORE *myiter(aksl_TreeNode *node, void *data)
|
|
{
|
|
int count = 0;
|
|
TreeSearchParams *parms = NULL;
|
|
PREPARE_ERROR(e);
|
|
FAIL_ZERO_RETURN(e, node, AKERR_NULLPOINTER, "node");
|
|
FAIL_ZERO_RETURN(e, data, AKERR_NULLPOINTER, "data");
|
|
parms = (TreeSearchParams *)data;
|
|
parms->steps += 1;
|
|
if ( node->leaf == parms->value ) {
|
|
parms->node = node;
|
|
FAIL_RETURN(e, AKERR_ITERATOR_BREAK, "stop");
|
|
}
|
|
SUCCEED_RETURN(e);
|
|
}
|
|
|
|
int main(void)
|
|
{
|
|
PREPARE_ERROR(e);
|
|
aksl_TreeNode tree[MAX_LEAVES];
|
|
TreeSearchParams parms = {
|
|
.value = (void *)17336,
|
|
.steps = 0,
|
|
.node = NULL
|
|
};
|
|
|
|
ATTEMPT {
|
|
memset((void *)&tree, 0x00, sizeof(aksl_TreeNode) * MAX_LEAVES);
|
|
/*
|
|
* Here we build a 3 level tree
|
|
*
|
|
* LEFT RIGHT
|
|
* TREE[0]
|
|
* +--------^^---------+
|
|
* | |
|
|
* TREE[1] TREE[2]
|
|
* +---^^---+ +---^^---+
|
|
* | | | |
|
|
*TREE[3] TREE[4] TREE[5] TREE[6]
|
|
*/
|
|
tree[0].left = &tree[1];
|
|
tree[0].right = &tree[2];
|
|
tree[1].left = &tree[3];
|
|
tree[1].right = &tree[4];
|
|
tree[2].left = &tree[5];
|
|
tree[2].right = &tree[6];
|
|
|
|
// Hide a value in tree[6]
|
|
tree[6].leaf = (void *)17336;
|
|
|
|
// Search for the value 17336 using DFS_PREORDER
|
|
CATCH(e, aksl_tree_iterate(&tree[0], &myiter, NULL, NULL, AKSL_TREE_SEARCH_DFS_PREORDER, &parms, NULL));
|
|
if ( parms.node != &tree[6] ) {
|
|
FAIL_BREAK(e, AKERR_API, "DFS_PREORDER_SEARCH didn't find the node");
|
|
}
|
|
if ( parms.steps != 7 ) {
|
|
FAIL_BREAK(e, AKERR_API, "DFS_PREORDER_SEARCH should've found the node in 7 steps, instead took %d", parms.steps);
|
|
}
|
|
|
|
// Search for the value 17336 using DFS_INORDER
|
|
CATCH(e, aksl_tree_iterate(&tree[0], &myiter, NULL, NULL, AKSL_TREE_SEARCH_DFS_INORDER, &parms, NULL));
|
|
if ( parms.node != &tree[6] ) {
|
|
FAIL_BREAK(e, AKERR_API, "DFS_INORDER_SEARCH didn't find the node");
|
|
}
|
|
if ( parms.steps != 7 ) {
|
|
FAIL_BREAK(e, AKERR_API, "DFS_INORDER_SEARCH should've found the node in 7 steps, instead took %d", parms.steps);
|
|
}
|
|
|
|
// Search for the value 17336 using DFS_PREORDER
|
|
CATCH(e, aksl_tree_iterate(&tree[0], &myiter, NULL, NULL, AKSL_TREE_SEARCH_DFS_POSTORDER, &parms, NULL));
|
|
if ( parms.node != &tree[6] ) {
|
|
FAIL_BREAK(e, AKERR_API, "DFS_POSTORDER_SEARCH didn't find the node");
|
|
}
|
|
if ( parms.steps != 7 ) {
|
|
FAIL_BREAK(e, AKERR_API, "DFS_POSTORDER_SEARCH should've found the node in 7 steps, instead took %d", parms.steps);
|
|
}
|
|
|
|
} CLEANUP {
|
|
} PROCESS(e) {
|
|
} FINISH_NORETURN(e);
|
|
|
|
return 0;
|
|
}
|