treap_tree.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442
  1. /*!
  2. Temelia - Treap tree implementation source file.
  3. Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
  4. @author Dascalu Laurentiu
  5. This program is free software; you can redistribute it and
  6. modify it under the terms of the GNU General Public License
  7. as published by the Free Software Foundation; either version 3
  8. of the License, or (at your option) any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with this program; if not, write to the Free Software
  15. Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16. */
  17. #include "include/treap_tree.h"
  18. #include "include/stack.h"
  19. #include <stdlib.h>
  20. /*
  21. * Treap, type of binary tree has this name because it respects conditions imposed
  22. * by binary search tree([1] and [2]) and heap([3]) :
  23. * 1. if u is left descendant of v, key[u] < key[v]
  24. * 2. if u is right descendant of v, key[u] > key[v]
  25. * 3. if u is a child of v, priority[u] <= priority[v]
  26. */
  27. struct _treap_node_t
  28. {
  29. /*! user's key */
  30. void *key;
  31. /*! priority */
  32. unsigned int priority;
  33. };
  34. typedef struct _treap_node_t *treap_node;
  35. #define GET_TREAP_MEMBER(x, member) (((treap_node)(x))->member)
  36. #define MAX_PRIORITY (10000)
  37. extern stack_t iterating_handlers;
  38. extern stack_t compare_stack;
  39. /*!
  40. * Encapsulates user's key into a treap node.
  41. */
  42. static treap_node_t _treap_node_new(void *key, unsigned int priority);
  43. static void _treap_node_delete_node(treap_node_t);
  44. static void _treap_internal_handling(void *x, void *context);
  45. static void _treap_internal_printing_level(void *x, int level, void *context);
  46. static int _treap_internal_compare(void *x, void *y, void *context);
  47. treap_tree_t treap_tree_new(void *key)
  48. {
  49. return _binary_tree_new(_treap_node_new(key, _rand() % MAX_PRIORITY + 1));
  50. }
  51. void treap_tree_delete_node(treap_tree_t treap)
  52. {
  53. _ASSERT(treap, ==, NULL, NULL_POINTER,);
  54. _treap_node_delete_node(_binary_tree_get_key(treap));
  55. _delete(treap);
  56. }
  57. void treap_tree_delete(treap_tree_t treap)
  58. {
  59. _ASSERT(treap, ==, NULL, NULL_POINTER,);
  60. treap_tree_delete(_binary_tree_get_left_child(treap));
  61. treap_tree_delete(_binary_tree_get_right_child(treap));
  62. treap_tree_delete_node(treap);
  63. }
  64. int treap_tree_compare_trees(treap_tree_t treap1, treap_tree_t treap2,
  65. int(*compare)(void *x, void *y, void *context), void *context)
  66. {
  67. int result;
  68. stack_push(compare_stack, compare);
  69. result = _binary_tree_compare_trees(treap1, treap2,
  70. _treap_internal_compare, context);
  71. stack_pop(compare_stack);
  72. return result;
  73. }
  74. int treap_tree_is_empty(treap_tree_t treap)
  75. {
  76. _ASSERT(treap, ==, NULL, NULL_POINTER, 1);
  77. return (_binary_tree_get_parent(treap) == NULL)
  78. && (_binary_tree_get_left_child(treap) == NULL)
  79. && (_binary_tree_get_right_child(treap) == NULL)
  80. && (GET_TREAP_MEMBER(_binary_tree_get_key(treap), key) == NULL);
  81. }
  82. int treap_tree_is_leaf(treap_tree_t treap)
  83. {
  84. return _binary_tree_leaf(treap);
  85. }
  86. int treap_tree_get_size(treap_tree_t treap)
  87. {
  88. return _binary_tree_get_size(treap);
  89. }
  90. treap_tree_t treap_tree_get_root(treap_tree_t treap)
  91. {
  92. return _binary_tree_get_root(treap);
  93. }
  94. void *treap_tree_get_key(treap_tree_t treap)
  95. {
  96. treap_node_t node;
  97. _ASSERT(treap, ==, NULL, NULL_POINTER, NULL);
  98. node = _binary_tree_get_key(treap);
  99. return node->key;
  100. }
  101. unsigned int treap_tree_get_priority(treap_tree_t treap)
  102. {
  103. treap_node_t node;
  104. _ASSERT(treap, ==, NULL, NULL_POINTER, 0);
  105. node = _binary_tree_get_key(treap);
  106. return node->priority;
  107. }
  108. treap_tree_t treap_tree_get_parent(treap_tree_t treap)
  109. {
  110. return _binary_tree_get_parent(treap);
  111. }
  112. treap_tree_t treap_tree_get_left_child(treap_tree_t treap)
  113. {
  114. return _binary_tree_get_left_child(treap);
  115. }
  116. treap_tree_t treap_tree_get_right_child(treap_tree_t treap)
  117. {
  118. return _binary_tree_get_right_child(treap);
  119. }
  120. int treap_tree_get_height(treap_tree_t treap)
  121. {
  122. return _binary_tree_get_height(treap);
  123. }
  124. int treap_tree_get_depth(treap_tree_t treap)
  125. {
  126. return _binary_tree_get_depth(treap);
  127. }
  128. treap_tree_t treap_tree_search(treap_tree_t treap, void *key, int compare(
  129. void *x, void *y, void *context), void *context)
  130. {
  131. treap_node search_node = _treap_node_new(key, -1);
  132. treap_tree_t result;
  133. stack_push(compare_stack, compare);
  134. result = _binary_search_tree_search(treap, search_node,
  135. _treap_internal_compare, context);
  136. _treap_node_delete_node(search_node);
  137. stack_pop(compare_stack);
  138. return result;
  139. }
  140. treap_tree_t treap_tree_insert(treap_tree_t *treap, void *key, int compare(
  141. void *x, void *y, void *context), void *context, int adjust_root)
  142. {
  143. treap_tree_t add = NULL, parent = NULL, aux = NULL;
  144. treap_node_t add_node = NULL;
  145. _ASSERT(compare, ==, NULL, INVALID_INPUT, NULL);
  146. /*
  147. * The algorithm is :
  148. * Treap-Insert(k,p)
  149. * if void *== null then void *<- new_node()
  150. * void *-> [key, priority, lchild, rchild] <- [k, p, tnull, tnull]
  151. * else if k < void *->key then Treap-Insert((k,p), void *->lchild)
  152. * if void *->lchild->priority > void *->priority then Rotate-Right(void *)
  153. * else if k > void *->key then Treap-Insert((k,p), void *->rchild)
  154. * if void *->rchild->priority > void *->priority then Rotate-Left(void *)
  155. * else
  156. * key is already in the treap
  157. */
  158. stack_push(compare_stack, compare);
  159. add_node = _treap_node_new(key, _rand() % MAX_PRIORITY + 1);
  160. aux = add = _binary_search_tree_insert(*treap, add_node,
  161. _treap_internal_compare, context);
  162. // key already exists - no adding in performed
  163. if (aux == NULL)
  164. {
  165. _treap_node_delete_node(add_node);
  166. return NULL;
  167. }
  168. while (add != *treap)
  169. {
  170. parent = _binary_tree_get_parent(add);
  171. if (_treap_internal_compare(_binary_tree_get_key(parent),
  172. _binary_tree_get_key(add), context) > 0
  173. && GET_TREAP_MEMBER(_binary_tree_get_key(parent), priority)
  174. > GET_TREAP_MEMBER(_binary_tree_get_key(add), priority))
  175. _self_balanced_binary_search_tree_rotate_right(parent);
  176. if (_treap_internal_compare(_binary_tree_get_key(parent),
  177. _binary_tree_get_key(add), context) < 0
  178. && GET_TREAP_MEMBER(_binary_tree_get_key(parent), priority)
  179. > GET_TREAP_MEMBER(_binary_tree_get_key(add), priority))
  180. _self_balanced_binary_search_tree_rotate_left(parent);
  181. add = parent;
  182. }
  183. while (adjust_root && _binary_tree_get_parent(*treap))
  184. (*treap) = _binary_tree_get_parent(*treap);
  185. stack_pop(compare_stack);
  186. return aux;
  187. }
  188. treap_tree_t treap_tree_remove(treap_tree_t *treap, void *key, int compare(
  189. void *x, void *y, void *context), void *context, int adjust_root)
  190. {
  191. /*
  192. * The algorithm is :
  193. * Treap-Delete(k, void *)
  194. * tnull->key <- k
  195. * Rec-Treap-Delete(k, void *)
  196. *
  197. * Rec-Treap-Delete(k, void *)
  198. * if k < void *->key then Rec-Treap-Delete(k, void *->lchild)
  199. * else if k > void *->key then Rec-Treap-Delete(k, void *->rchild)
  200. * else Root-Delete(void *)
  201. *
  202. * Root-Delete(void *)
  203. * if is_leaf(void *) then void *<- tnull
  204. * else if void *->lchild->priority > void *->rchild->priority
  205. * then Rotate-Right(void *) and Root-Delete(void *->rchild)
  206. * else Rotate-Left(void *) and Root-Delete(void *->lchild)
  207. */
  208. treap_tree_t deleted, parent, aux;
  209. treap_node_t key_encapsulated;
  210. _ASSERT(treap, ==, NULL, NULL_POINTER, NULL);
  211. _ASSERT(*treap, ==, NULL, NULL_POINTER, NULL);
  212. _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
  213. stack_push(compare_stack, compare);
  214. // Remove the node as in a binary search tree and then start tree balancing.
  215. key_encapsulated = _treap_node_new(key, -1);
  216. deleted = _binary_search_tree_remove(treap, key_encapsulated,
  217. _treap_internal_compare, context, &aux);
  218. _treap_node_delete_node(key_encapsulated);
  219. _ASSERT(aux, ==, NULL, ELEMENT_NOT_FOUND, NULL);
  220. if (aux == *treap && _binary_tree_get_parent(*treap) == NULL
  221. && _binary_tree_get_left_child(*treap) == NULL
  222. && _binary_tree_get_right_child(*treap) == NULL)
  223. {
  224. treap_tree_delete_node(aux);
  225. *treap = NULL;
  226. return NULL;
  227. }
  228. treap_tree_delete_node(aux);
  229. _ASSERT(deleted, ==, NULL, ELEMENT_NOT_FOUND, NULL);
  230. parent = aux = deleted;
  231. while (parent && (parent = _binary_tree_get_parent(deleted)) != *treap)
  232. {
  233. if (_binary_tree_get_left_child(parent)
  234. && _binary_tree_get_right_child(parent))
  235. {
  236. if (GET_TREAP_MEMBER(_binary_tree_get_key(_binary_tree_get_left_child(parent)), priority)
  237. > GET_TREAP_MEMBER(_binary_tree_get_key(_binary_tree_get_right_child(parent)), priority))
  238. _self_balanced_binary_search_tree_rotate_right(parent);
  239. else
  240. _self_balanced_binary_search_tree_rotate_left(parent);
  241. deleted = _binary_tree_get_parent(parent);
  242. }
  243. else
  244. deleted = parent;
  245. }
  246. while (adjust_root && _binary_tree_get_parent(*treap))
  247. (*treap) = _binary_tree_get_parent(*treap);
  248. stack_pop(compare_stack);
  249. return aux;
  250. }
  251. treap_tree_t treap_tree_get_min(treap_tree_t treap)
  252. {
  253. return _binary_search_tree_get_min(treap);
  254. }
  255. treap_tree_t treap_tree_get_max(treap_tree_t treap)
  256. {
  257. return _binary_search_tree_get_max(treap);
  258. }
  259. void treap_tree_preorder(treap_tree_t treap, void key_handler(void *x,
  260. void *context), void *context)
  261. {
  262. stack_push(iterating_handlers, key_handler);
  263. _binary_tree_preorder(treap, _treap_internal_handling, context);
  264. stack_pop(iterating_handlers);
  265. }
  266. void treap_tree_inorder(treap_tree_t treap, void key_handler(void *x,
  267. void *context), void *context)
  268. {
  269. stack_push(iterating_handlers, key_handler);
  270. _binary_tree_inorder(treap, _treap_internal_handling, context);
  271. stack_pop(iterating_handlers);
  272. }
  273. void treap_tree_reverse_inorder(treap_tree_t treap, void key_handler(void *x,
  274. void *context), void *context)
  275. {
  276. stack_push(iterating_handlers, key_handler);
  277. _binary_tree_reverse_inorder(treap, _treap_internal_handling, context);
  278. stack_pop(iterating_handlers);
  279. }
  280. void treap_tree_postorder(treap_tree_t treap, void key_handler(void *x,
  281. void *context), void *context)
  282. {
  283. stack_push(iterating_handlers, key_handler);
  284. _binary_tree_postorder(treap, _treap_internal_handling, context);
  285. stack_pop(iterating_handlers);
  286. }
  287. void treap_tree_level_order(treap_tree_t treap, void key_handler(void *x,
  288. void *context), void *context)
  289. {
  290. stack_push(iterating_handlers, key_handler);
  291. _binary_tree_level_order(treap, _treap_internal_handling, context);
  292. stack_pop(iterating_handlers);
  293. }
  294. void treap_tree_show_indented(treap_tree_t treap, void key_handler(void *x,
  295. int level, void *context), void *context)
  296. {
  297. stack_push(iterating_handlers, key_handler);
  298. _binary_tree_show_indented(treap, _treap_internal_printing_level, context,
  299. 0);
  300. stack_pop(iterating_handlers);
  301. }
  302. static treap_node_t _treap_node_new(void *key, unsigned int priority)
  303. {
  304. treap_node_t treap;
  305. treap = (struct _treap_node_t *) _new(sizeof(struct _treap_node_t));
  306. treap->key = key;
  307. treap->priority = priority;
  308. return treap;
  309. }
  310. static void _treap_node_delete_node(treap_node_t treap_node)
  311. {
  312. _ASSERT(treap_node, ==, NULL, NULL_POINTER,);
  313. _delete(treap_node);
  314. }
  315. static void _treap_internal_handling(void *x, void *context)
  316. {
  317. void (*user_handling_function)(void *, void *);
  318. user_handling_function = stack_top(iterating_handlers);
  319. _ASSERT(user_handling_function, ==, NULL, NULL_POINTER,);
  320. user_handling_function(GET_TREAP_MEMBER(x, key), context);
  321. }
  322. static void _treap_internal_printing_level(void *x, int level, void *context)
  323. {
  324. void (*user_printing_function_level)(void *, int, void *);
  325. user_printing_function_level = stack_top(iterating_handlers);
  326. _ASSERT(user_printing_function_level, ==, NULL, NULL_POINTER,);
  327. user_printing_function_level(GET_TREAP_MEMBER(x, key), level, context);
  328. }
  329. static int _treap_internal_compare(void *x, void *y, void *context)
  330. {
  331. /*
  332. * This is the delegate function and can compare treap tree nodes.
  333. *
  334. * For comparing key from nodes, i save the user comparison function in a global pointers stack.
  335. */
  336. int (*user_comparison_function)(void *, void *, void *);
  337. user_comparison_function = stack_top(compare_stack);
  338. _ASSERT(user_comparison_function, ==, NULL, NULL_POINTER, -1);
  339. return user_comparison_function(GET_TREAP_MEMBER(x, key),
  340. GET_TREAP_MEMBER(y, key), context);
  341. }