123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323 |
- /*!
- Temelia - Splay tree implementation source file.
- Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
- @author Dascalu Laurentiu
- This program is free software; you can redistribute it and
- 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.
- This program 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, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
- #include "include/splay_tree.h"
- #include "include/common.h"
- #include <stdlib.h>
- static splay_tree_t _splay_tree_splay(void *key, splay_tree_t tree,
- int compare(void *x, void *y, void *context), void *context);
- splay_tree_t splay_tree_new(void *key)
- {
- return _binary_tree_new(key);
- }
- void splay_tree_delete_node(splay_tree_t splay_tree)
- {
- _ASSERT(splay_tree, ==, NULL, NULL_POINTER,);
- _delete(splay_tree);
- }
- void splay_tree_delete(splay_tree_t splay_tree)
- {
- _ASSERT(splay_tree, ==, NULL, NULL_POINTER,);
- splay_tree_delete(_binary_tree_get_left_child(splay_tree));
- splay_tree_delete(_binary_tree_get_right_child(splay_tree));
- splay_tree_delete_node(splay_tree);
- }
- int splay_tree_compare_trees(splay_tree_t splay_tree1,
- splay_tree_t splay_tree2, int compare(void *x, void *y, void *context),
- void *context)
- {
- return _binary_tree_compare_trees(splay_tree1, splay_tree2, compare,
- context);
- }
- int splay_tree_is_empty(splay_tree_t splay_tree)
- {
- return (_binary_tree_get_parent(splay_tree) == NULL)
- && (_binary_tree_get_left_child(splay_tree) == NULL)
- && (_binary_tree_get_right_child(splay_tree) == NULL)
- && (_binary_tree_get_key(splay_tree) == NULL);
- }
- int splay_tree_is_leaf(splay_tree_t splay_tree)
- {
- return _binary_tree_leaf(splay_tree);
- }
- splay_tree_t splay_tree_get_root(splay_tree_t splay_tree)
- {
- return _binary_tree_get_root(splay_tree);
- }
- void *splay_tree_get_key(splay_tree_t splay_tree)
- {
- void *node;
- _ASSERT(splay_tree, ==, NULL, NULL_POINTER, NULL);
- node = _binary_tree_get_key(splay_tree);
- return node;
- }
- int splay_tree_get_size(splay_tree_t splay_tree)
- {
- return _binary_tree_get_size(splay_tree);
- }
- splay_tree_t splay_tree_get_parent(splay_tree_t splay_tree)
- {
- return _binary_tree_get_parent(splay_tree);
- }
- splay_tree_t splay_tree_get_left_child(splay_tree_t splay_tree)
- {
- return _binary_tree_get_left_child(splay_tree);
- }
- splay_tree_t splay_tree_get_right_child(splay_tree_t splay_tree)
- {
- return _binary_tree_get_right_child(splay_tree);
- }
- int splay_tree_get_height(splay_tree_t splay_tree)
- {
- return _binary_tree_get_height(splay_tree);
- }
- int splay_tree_get_depth(splay_tree_t splay_tree)
- {
- return _binary_tree_get_depth(splay_tree);
- }
- splay_tree_t splay_tree_search(splay_tree_t splay_tree, void *key, int compare(
- void *x, void *y, void *context), void *context)
- {
- return _binary_search_tree_search(splay_tree, key, compare, context);
- }
- splay_tree_t splay_tree_insert(splay_tree_t _splay_tree, void *key,
- int compare(void *x, void *y, void *context), void *context)
- {
- splay_tree_t new;
- _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
- new = splay_tree_new(key);
- if (_splay_tree == NULL)
- {
- new->left = new->right = new->parent = NULL;
- return new;
- }
- _splay_tree = _splay_tree_splay(key, _splay_tree, compare, context);
- if (compare(key, _splay_tree->key, context) < 0)
- {
- new->left = _splay_tree->left;
- new->right = _splay_tree;
- _splay_tree->left = NULL;
- if (new->left)
- new->left->parent = new;
- if (new->right)
- new->right->parent = new;
- return new;
- }
- else if (compare(key, _splay_tree->key, context) > 0)
- {
- new->right = _splay_tree->right;
- new->left = _splay_tree;
- _splay_tree->right = NULL;
- if (new->left)
- new->left->parent = new;
- if (new->right)
- new->right->parent = new;
- return new;
- }
- else
- {
- splay_tree_delete_node(new);
- return _splay_tree;
- }
- return NULL;
- }
- splay_tree_t splay_tree_remove(splay_tree_t splay_tree, void *key,
- int compare(void *x, void *y, void *context), void *context)
- {
- splay_tree_t x = NULL;
- LOGGER("[splay tree remove] tree %p, key %p, compare %p, context %p\n",
- splay_tree, key, compare, context);
- _ASSERT(splay_tree, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
- splay_tree = _splay_tree_splay(key, splay_tree, compare, context);
- if (compare(key, splay_tree->key, context) == 0)
- {
- if (splay_tree->left == NULL)
- x = splay_tree->right;
- else
- {
- x = _splay_tree_splay(key, splay_tree->left, compare, context);
- x->right = splay_tree->right;
- if (x->right)
- x->right->parent = x;
- }
- splay_tree_delete_node(splay_tree);
- return x;
- }
- return splay_tree;
- }
- splay_tree_t splay_tree_get_min(splay_tree_t splay_tree)
- {
- return _binary_search_tree_get_min(splay_tree);
- }
- splay_tree_t splay_tree_get_max(splay_tree_t splay_tree)
- {
- return _binary_search_tree_get_max(splay_tree);
- }
- void splay_tree_preorder(splay_tree_t splay_tree, void key_handler(void *x,
- void *context), void *context)
- {
- _binary_tree_preorder(splay_tree, key_handler, context);
- }
- void splay_tree_inorder(splay_tree_t splay_tree, void key_handler(void *x,
- void *context), void *context)
- {
- _binary_tree_inorder(splay_tree, key_handler, context);
- }
- void splay_tree_reverse_inorder(splay_tree_t splay_tree, void key_handler(
- void *x, void *context), void *context)
- {
- _binary_tree_reverse_inorder(splay_tree, key_handler, context);
- }
- void splay_tree_postorder(splay_tree_t splay_tree, void key_handler(void *x,
- void *context), void *context)
- {
- _binary_tree_postorder(splay_tree, key_handler, context);
- }
- void splay_tree_level_order(splay_tree_t splay_tree, void key_handler(void *x,
- void *context), void *context)
- {
- _binary_tree_level_order(splay_tree, key_handler, context);
- }
- void splay_tree_show_indented(splay_tree_t splay_tree, void key_handler(
- void *x, int level, void *context), void *context)
- {
- _binary_tree_show_indented(splay_tree, key_handler, context, 0);
- }
- static splay_tree_t _splay_tree_splay(void *key, splay_tree_t tree,
- int compare(void *x, void *y, void *context), void *context)
- {
- splay_tree_t left, right;
- struct _bt_node_t new_node;
- int comp;
- _ASSERT(tree, ==, NULL, NULL_POINTER, NULL);
- new_node.left = new_node.right = NULL;
- left = right = &new_node;
- for (;;)
- {
- comp = compare(key, splay_tree_get_key(tree), context);
- if (comp < 0)
- {
- if (_binary_tree_get_left_child(tree) == NULL)
- break;
- if (compare(key, _binary_tree_get_key(_binary_tree_get_left_child(
- tree)), context) < 0)
- {
- tree = _self_balanced_binary_search_tree_rotate_right(tree);
- if (_binary_tree_get_left_child(tree) == NULL)
- break;
- }
- _binary_tree_set_left_child(right, tree);
- right = tree;
- tree = _binary_tree_get_left_child(tree);
- }
- else if (comp > 0)
- {
- if (_binary_tree_get_right_child(tree) == NULL)
- break;
- if (compare(key, _binary_tree_get_key(_binary_tree_get_right_child(
- tree)), context) > 0)
- {
- tree = _self_balanced_binary_search_tree_rotate_left(tree);
- if (_binary_tree_get_right_child(tree) == NULL)
- break;
- }
- _binary_tree_set_right_child(left, tree);
- left = tree;
- tree = _binary_tree_get_right_child(tree);
- }
- else
- break;
- }
- _binary_tree_set_right_child(left, _binary_tree_get_left_child(tree));
- _binary_tree_set_left_child(right, _binary_tree_get_right_child(tree));
- _binary_tree_set_left_child(tree, new_node.right);
- if (tree->right)
- tree->right->parent = tree;
- _binary_tree_set_right_child(tree, new_node.left);
- if (tree->left)
- tree->left->parent = tree;
- tree->parent = NULL;
- return tree;
- }
|