123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442 |
- /*!
- Temelia - Treap 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/treap_tree.h"
- #include "include/stack.h"
- #include <stdlib.h>
- /*
- * Treap, type of binary tree has this name because it respects conditions imposed
- * by binary search tree([1] and [2]) and heap([3]) :
- * 1. if u is left descendant of v, key[u] < key[v]
- * 2. if u is right descendant of v, key[u] > key[v]
- * 3. if u is a child of v, priority[u] <= priority[v]
- */
- struct _treap_node_t
- {
- /*! user's key */
- void *key;
- /*! priority */
- unsigned int priority;
- };
- typedef struct _treap_node_t *treap_node;
- #define GET_TREAP_MEMBER(x, member) (((treap_node)(x))->member)
- #define MAX_PRIORITY (10000)
- extern stack_t iterating_handlers;
- extern stack_t compare_stack;
- /*!
- * Encapsulates user's key into a treap node.
- */
- static treap_node_t _treap_node_new(void *key, unsigned int priority);
- static void _treap_node_delete_node(treap_node_t);
- static void _treap_internal_handling(void *x, void *context);
- static void _treap_internal_printing_level(void *x, int level, void *context);
- static int _treap_internal_compare(void *x, void *y, void *context);
- treap_tree_t treap_tree_new(void *key)
- {
- return _binary_tree_new(_treap_node_new(key, _rand() % MAX_PRIORITY + 1));
- }
- void treap_tree_delete_node(treap_tree_t treap)
- {
- _ASSERT(treap, ==, NULL, NULL_POINTER,);
- _treap_node_delete_node(_binary_tree_get_key(treap));
- _delete(treap);
- }
- void treap_tree_delete(treap_tree_t treap)
- {
- _ASSERT(treap, ==, NULL, NULL_POINTER,);
- treap_tree_delete(_binary_tree_get_left_child(treap));
- treap_tree_delete(_binary_tree_get_right_child(treap));
- treap_tree_delete_node(treap);
- }
- int treap_tree_compare_trees(treap_tree_t treap1, treap_tree_t treap2,
- int(*compare)(void *x, void *y, void *context), void *context)
- {
- int result;
- stack_push(compare_stack, compare);
- result = _binary_tree_compare_trees(treap1, treap2,
- _treap_internal_compare, context);
- stack_pop(compare_stack);
- return result;
- }
- int treap_tree_is_empty(treap_tree_t treap)
- {
- _ASSERT(treap, ==, NULL, NULL_POINTER, 1);
- return (_binary_tree_get_parent(treap) == NULL)
- && (_binary_tree_get_left_child(treap) == NULL)
- && (_binary_tree_get_right_child(treap) == NULL)
- && (GET_TREAP_MEMBER(_binary_tree_get_key(treap), key) == NULL);
- }
- int treap_tree_is_leaf(treap_tree_t treap)
- {
- return _binary_tree_leaf(treap);
- }
- int treap_tree_get_size(treap_tree_t treap)
- {
- return _binary_tree_get_size(treap);
- }
- treap_tree_t treap_tree_get_root(treap_tree_t treap)
- {
- return _binary_tree_get_root(treap);
- }
- void *treap_tree_get_key(treap_tree_t treap)
- {
- treap_node_t node;
- _ASSERT(treap, ==, NULL, NULL_POINTER, NULL);
- node = _binary_tree_get_key(treap);
- return node->key;
- }
- unsigned int treap_tree_get_priority(treap_tree_t treap)
- {
- treap_node_t node;
- _ASSERT(treap, ==, NULL, NULL_POINTER, 0);
- node = _binary_tree_get_key(treap);
- return node->priority;
- }
- treap_tree_t treap_tree_get_parent(treap_tree_t treap)
- {
- return _binary_tree_get_parent(treap);
- }
- treap_tree_t treap_tree_get_left_child(treap_tree_t treap)
- {
- return _binary_tree_get_left_child(treap);
- }
- treap_tree_t treap_tree_get_right_child(treap_tree_t treap)
- {
- return _binary_tree_get_right_child(treap);
- }
- int treap_tree_get_height(treap_tree_t treap)
- {
- return _binary_tree_get_height(treap);
- }
- int treap_tree_get_depth(treap_tree_t treap)
- {
- return _binary_tree_get_depth(treap);
- }
- treap_tree_t treap_tree_search(treap_tree_t treap, void *key, int compare(
- void *x, void *y, void *context), void *context)
- {
- treap_node search_node = _treap_node_new(key, -1);
- treap_tree_t result;
- stack_push(compare_stack, compare);
- result = _binary_search_tree_search(treap, search_node,
- _treap_internal_compare, context);
- _treap_node_delete_node(search_node);
- stack_pop(compare_stack);
- return result;
- }
- treap_tree_t treap_tree_insert(treap_tree_t *treap, void *key, int compare(
- void *x, void *y, void *context), void *context, int adjust_root)
- {
- treap_tree_t add = NULL, parent = NULL, aux = NULL;
- treap_node_t add_node = NULL;
- _ASSERT(compare, ==, NULL, INVALID_INPUT, NULL);
- /*
- * The algorithm is :
- * Treap-Insert(k,p)
- * if void *== null then void *<- new_node()
- * void *-> [key, priority, lchild, rchild] <- [k, p, tnull, tnull]
- * else if k < void *->key then Treap-Insert((k,p), void *->lchild)
- * if void *->lchild->priority > void *->priority then Rotate-Right(void *)
- * else if k > void *->key then Treap-Insert((k,p), void *->rchild)
- * if void *->rchild->priority > void *->priority then Rotate-Left(void *)
- * else
- * key is already in the treap
- */
- stack_push(compare_stack, compare);
- add_node = _treap_node_new(key, _rand() % MAX_PRIORITY + 1);
- aux = add = _binary_search_tree_insert(*treap, add_node,
- _treap_internal_compare, context);
- // key already exists - no adding in performed
- if (aux == NULL)
- {
- _treap_node_delete_node(add_node);
- return NULL;
- }
- while (add != *treap)
- {
- parent = _binary_tree_get_parent(add);
- if (_treap_internal_compare(_binary_tree_get_key(parent),
- _binary_tree_get_key(add), context) > 0
- && GET_TREAP_MEMBER(_binary_tree_get_key(parent), priority)
- > GET_TREAP_MEMBER(_binary_tree_get_key(add), priority))
- _self_balanced_binary_search_tree_rotate_right(parent);
- if (_treap_internal_compare(_binary_tree_get_key(parent),
- _binary_tree_get_key(add), context) < 0
- && GET_TREAP_MEMBER(_binary_tree_get_key(parent), priority)
- > GET_TREAP_MEMBER(_binary_tree_get_key(add), priority))
- _self_balanced_binary_search_tree_rotate_left(parent);
- add = parent;
- }
- while (adjust_root && _binary_tree_get_parent(*treap))
- (*treap) = _binary_tree_get_parent(*treap);
- stack_pop(compare_stack);
- return aux;
- }
- treap_tree_t treap_tree_remove(treap_tree_t *treap, void *key, int compare(
- void *x, void *y, void *context), void *context, int adjust_root)
- {
- /*
- * The algorithm is :
- * Treap-Delete(k, void *)
- * tnull->key <- k
- * Rec-Treap-Delete(k, void *)
- *
- * Rec-Treap-Delete(k, void *)
- * if k < void *->key then Rec-Treap-Delete(k, void *->lchild)
- * else if k > void *->key then Rec-Treap-Delete(k, void *->rchild)
- * else Root-Delete(void *)
- *
- * Root-Delete(void *)
- * if is_leaf(void *) then void *<- tnull
- * else if void *->lchild->priority > void *->rchild->priority
- * then Rotate-Right(void *) and Root-Delete(void *->rchild)
- * else Rotate-Left(void *) and Root-Delete(void *->lchild)
- */
- treap_tree_t deleted, parent, aux;
- treap_node_t key_encapsulated;
- _ASSERT(treap, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(*treap, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
- stack_push(compare_stack, compare);
- // Remove the node as in a binary search tree and then start tree balancing.
- key_encapsulated = _treap_node_new(key, -1);
- deleted = _binary_search_tree_remove(treap, key_encapsulated,
- _treap_internal_compare, context, &aux);
- _treap_node_delete_node(key_encapsulated);
- _ASSERT(aux, ==, NULL, ELEMENT_NOT_FOUND, NULL);
- if (aux == *treap && _binary_tree_get_parent(*treap) == NULL
- && _binary_tree_get_left_child(*treap) == NULL
- && _binary_tree_get_right_child(*treap) == NULL)
- {
- treap_tree_delete_node(aux);
- *treap = NULL;
- return NULL;
- }
- treap_tree_delete_node(aux);
- _ASSERT(deleted, ==, NULL, ELEMENT_NOT_FOUND, NULL);
- parent = aux = deleted;
- while (parent && (parent = _binary_tree_get_parent(deleted)) != *treap)
- {
- if (_binary_tree_get_left_child(parent)
- && _binary_tree_get_right_child(parent))
- {
- if (GET_TREAP_MEMBER(_binary_tree_get_key(_binary_tree_get_left_child(parent)), priority)
- > GET_TREAP_MEMBER(_binary_tree_get_key(_binary_tree_get_right_child(parent)), priority))
- _self_balanced_binary_search_tree_rotate_right(parent);
- else
- _self_balanced_binary_search_tree_rotate_left(parent);
- deleted = _binary_tree_get_parent(parent);
- }
- else
- deleted = parent;
- }
- while (adjust_root && _binary_tree_get_parent(*treap))
- (*treap) = _binary_tree_get_parent(*treap);
- stack_pop(compare_stack);
- return aux;
- }
- treap_tree_t treap_tree_get_min(treap_tree_t treap)
- {
- return _binary_search_tree_get_min(treap);
- }
- treap_tree_t treap_tree_get_max(treap_tree_t treap)
- {
- return _binary_search_tree_get_max(treap);
- }
- void treap_tree_preorder(treap_tree_t treap, void key_handler(void *x,
- void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_preorder(treap, _treap_internal_handling, context);
- stack_pop(iterating_handlers);
- }
- void treap_tree_inorder(treap_tree_t treap, void key_handler(void *x,
- void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_inorder(treap, _treap_internal_handling, context);
- stack_pop(iterating_handlers);
- }
- void treap_tree_reverse_inorder(treap_tree_t treap, void key_handler(void *x,
- void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_reverse_inorder(treap, _treap_internal_handling, context);
- stack_pop(iterating_handlers);
- }
- void treap_tree_postorder(treap_tree_t treap, void key_handler(void *x,
- void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_postorder(treap, _treap_internal_handling, context);
- stack_pop(iterating_handlers);
- }
- void treap_tree_level_order(treap_tree_t treap, void key_handler(void *x,
- void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_level_order(treap, _treap_internal_handling, context);
- stack_pop(iterating_handlers);
- }
- void treap_tree_show_indented(treap_tree_t treap, void key_handler(void *x,
- int level, void *context), void *context)
- {
- stack_push(iterating_handlers, key_handler);
- _binary_tree_show_indented(treap, _treap_internal_printing_level, context,
- 0);
- stack_pop(iterating_handlers);
- }
- static treap_node_t _treap_node_new(void *key, unsigned int priority)
- {
- treap_node_t treap;
- treap = (struct _treap_node_t *) _new(sizeof(struct _treap_node_t));
- treap->key = key;
- treap->priority = priority;
- return treap;
- }
- static void _treap_node_delete_node(treap_node_t treap_node)
- {
- _ASSERT(treap_node, ==, NULL, NULL_POINTER,);
- _delete(treap_node);
- }
- static void _treap_internal_handling(void *x, void *context)
- {
- void (*user_handling_function)(void *, void *);
- user_handling_function = stack_top(iterating_handlers);
- _ASSERT(user_handling_function, ==, NULL, NULL_POINTER,);
- user_handling_function(GET_TREAP_MEMBER(x, key), context);
- }
- static void _treap_internal_printing_level(void *x, int level, void *context)
- {
- void (*user_printing_function_level)(void *, int, void *);
- user_printing_function_level = stack_top(iterating_handlers);
- _ASSERT(user_printing_function_level, ==, NULL, NULL_POINTER,);
- user_printing_function_level(GET_TREAP_MEMBER(x, key), level, context);
- }
- static int _treap_internal_compare(void *x, void *y, void *context)
- {
- /*
- * This is the delegate function and can compare treap tree nodes.
- *
- * For comparing key from nodes, i save the user comparison function in a global pointers stack.
- */
- int (*user_comparison_function)(void *, void *, void *);
- user_comparison_function = stack_top(compare_stack);
- _ASSERT(user_comparison_function, ==, NULL, NULL_POINTER, -1);
- return user_comparison_function(GET_TREAP_MEMBER(x, key),
- GET_TREAP_MEMBER(y, key), context);
- }
|