From 0292d46621e374fd350b789b66ef0d2fd433c2a7 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Tue, 6 Oct 2009 04:06:47 +0000 Subject: New kD splay tree test. --- tests/libdimension/Makefile.am | 6 ++- tests/libdimension/kD_splay_tree.c | 93 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 98 insertions(+), 1 deletion(-) create mode 100644 tests/libdimension/kD_splay_tree.c (limited to 'tests/libdimension') diff --git a/tests/libdimension/Makefile.am b/tests/libdimension/Makefile.am index e9293ff..393e338 100644 --- a/tests/libdimension/Makefile.am +++ b/tests/libdimension/Makefile.am @@ -20,7 +20,8 @@ INCLUDES = -I$(top_srcdir)/libdimension check_PROGRAMS = error-test \ - warning-test + warning-test \ + kD_splay_tree-test TESTS = $(check_PROGRAMS) XFAIL_TESTS = error-test @@ -29,3 +30,6 @@ error_test_LDADD = $(top_srcdir)/libdimension/libdimension.la warning_test_SOURCES = warning.c warning_test_LDADD = $(top_srcdir)/libdimension/libdimension.la + +kD_splay_tree_test_SOURCES = kD_splay_tree.c +kD_splay_tree_test_LDADD = $(top_srcdir)/libdimension/libdimension.la diff --git a/tests/libdimension/kD_splay_tree.c b/tests/libdimension/kD_splay_tree.c new file mode 100644 index 0000000..6da4d10 --- /dev/null +++ b/tests/libdimension/kD_splay_tree.c @@ -0,0 +1,93 @@ +/************************************************************************* + * Copyright (C) 2009 Tavian Barnes * + * * + * This file is part of The Dimension Test Suite. * + * * + * The Dimension Test Suite is free software; you can redistribute it * + * and/or modify it under the terms of the GNU General Public License as * + * published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Test Suite is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program. If not, see . * + *************************************************************************/ + +/* + * Basic tests of our fancy k-D splay tree framework + */ + +#include "../../libdimension/dimension_impl.h" +#include + +void +dmnsn_print_kD_splay_tree(dmnsn_kD_splay_node *root) +{ + printf("((%g, %g, %g) - (%g, %g, %g)", + root->min.x, root->min.y, root->min.z, + root->max.x, root->max.y, root->max.z); + if (root->left || root->right) { + printf(": "); + if (root->left) + dmnsn_print_kD_splay_tree(root->left); + else + printf("?"); + printf(" - "); + if (root->right) + dmnsn_print_kD_splay_tree(root->right); + else + printf("?"); + } + printf(")"); +} + +int +main() +{ + dmnsn_kD_splay_node *tree; + dmnsn_object *obj1, *obj2, *obj3; + + obj1 = dmnsn_new_object(); + obj2 = dmnsn_new_object(); + obj3 = dmnsn_new_object(); + + obj1->min = dmnsn_vector_construct(0.0, 0.0, 0.0); + obj1->max = dmnsn_vector_construct(1.0, 1.0, 1.0); + + obj2->min = dmnsn_vector_construct(-2.0, -2.0, -2.0); + obj2->max = dmnsn_vector_construct(1.0, 1.0, 1.0); + + obj3->min = dmnsn_vector_construct(-1.0, -1.0, -1.0); + obj3->max = dmnsn_vector_construct(0.0, 0.0, 0.0); + + tree = dmnsn_new_kD_splay_tree(); + + tree = dmnsn_kD_splay_insert(tree, obj1); + if (tree->object != obj1) { + fprintf(stderr, "Wrong kD splay tree built.\n"); + return EXIT_FAILURE; + } + + tree = dmnsn_kD_splay_insert(tree, obj2); + if (tree->object != obj2 || tree->left->object != obj1) { + fprintf(stderr, "Wrong kD splay tree built.\n"); + return EXIT_FAILURE; + } + + tree = dmnsn_kD_splay_insert(tree, obj3); + if (tree->object != obj3 || tree->left->object != obj1 + || tree->right->object != obj2) { + fprintf(stderr, "Wrong kD splay tree built.\n"); + return EXIT_FAILURE; + } + + dmnsn_delete_object(obj3); + dmnsn_delete_object(obj2); + dmnsn_delete_object(obj1); + dmnsn_delete_kD_splay_tree(tree); + return EXIT_SUCCESS; +} -- cgit v1.2.3