diff options
Diffstat (limited to 'libdimension')
| -rw-r--r-- | libdimension/dimension_impl.h | 27 | ||||
| -rw-r--r-- | libdimension/kD_splay_tree.c | 68 | ||||
| -rw-r--r-- | libdimension/kD_splay_tree.h | 47 |
3 files changed, 142 insertions, 0 deletions
diff --git a/libdimension/dimension_impl.h b/libdimension/dimension_impl.h new file mode 100644 index 0000000..216302a --- /dev/null +++ b/libdimension/dimension_impl.h @@ -0,0 +1,27 @@ +/************************************************************************* + * Copyright (C) 2009 Tavian Barnes <tavianator@gmail.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser 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 Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +#ifndef DIMENSION_IMPL_H +#define DIMENSION_IMPL_H + +#include "dimension.h" +#include "kD_splay_tree.h" + +#endif /* DIMENSION_IMPL_H */ diff --git a/libdimension/kD_splay_tree.c b/libdimension/kD_splay_tree.c new file mode 100644 index 0000000..24987c4 --- /dev/null +++ b/libdimension/kD_splay_tree.c @@ -0,0 +1,68 @@ +/************************************************************************* + * Copyright (C) 2009 Tavian Barnes <tavianator@gmail.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser 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 Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +#include "dimension_impl.h" +#include <stdlib.h> + +static dmnsn_kD_splay_node * +dmnsn_new_kD_splay_node() +{ + dmnsn_kD_splay_node *node = malloc(sizeof(dmnsn_kD_splay_node)); + if (!node) { + dmnsn_error(DMNSN_SEVERITY_HIGH, "kD splay tree node allocation failed."); + } + return node; +} + +static void +dmnsn_delete_kD_splay_node(dmnsn_kD_splay_node *node) +{ + free(node); +} + +/* Return an empty tree */ +dmnsn_kD_splay_node * +dmnsn_new_kD_splay_tree() +{ + return NULL; +} + +/* Copy a kD splay tree */ +dmnsn_kD_splay_node *dmnsn_kD_splay_copy(dmnsn_kD_splay_node *root) +{ + dmnsn_kD_splay_node *node = NULL; + if (root) { + node = dmnsn_new_kD_splay_node(); + *node = *root; + node->left = dmnsn_kD_splay_copy(node->left); + node->right = dmnsn_kD_splay_copy(node->right); + } + return node; +} + +void +dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_node *root) +{ + if (root) { + dmnsn_delete_kD_splay_tree(root->left); + dmnsn_delete_kD_splay_tree(root->right); + dmnsn_delete_kD_splay_node(root); + } +} diff --git a/libdimension/kD_splay_tree.h b/libdimension/kD_splay_tree.h new file mode 100644 index 0000000..2b778fa --- /dev/null +++ b/libdimension/kD_splay_tree.h @@ -0,0 +1,47 @@ +/************************************************************************* + * Copyright (C) 2009 Tavian Barnes <tavianator@gmail.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser 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 Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +#ifndef DIMENSION_IMPL_KD_SPLAY_TREE_H +#define DIMENSION_IMPL_KD_SPLAY_TREE_H + +typedef struct dmnsn_kD_splay_node dmnsn_kD_splay_node; + +struct dmnsn_kD_splay_node { + /* Tree children */ + dmnsn_kD_splay_node *left, *right; + + /* Parent node for easy backtracking */ + dmnsn_kD_splay_node *parent; + + /* Bounding box corners */ + dmnsn_vector min, max; + + /* Node payload */ + dmnsn_object *object; +}; + +dmnsn_kD_splay_node *dmnsn_new_kD_splay_tree(); +dmnsn_kD_splay_node *dmnsn_kD_splay_copy(dmnsn_kD_splay_node *root); +void dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_node *root); + +dmnsn_kD_splay_node *dmnsn_kD_splay_insert(dmnsn_kD_splay_node *root, + dmnsn_object *object); + +#endif /* DIMENSION_IMPL_KD_SPLAY_TREE_H */ |