Treap: a binary search tree on the keys that is at the same time a max-heap on per-node priorities.
More...
|
| tr_tree * | tr_tree_new (dict_compare_func compare_func, dict_prio_func prio_func) |
| | Create an empty treap that orders keys with |compare_func| (must not be NULL) and takes node priorities from |prio_func|, or at random if |prio_func| is NULL.
|
| |
| dict * | tr_dict_new (dict_compare_func compare_func, dict_prio_func prio_func) |
| | Like tr_tree_new(), but wrapped in a generic dict for use with the dict_* macros.
|
| |
| size_t | tr_tree_free (tr_tree *tree, dict_delete_func delete_func) |
| | Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL, and free the tree.
|
| |
| dict_insert_result | tr_tree_insert (tr_tree *tree, void *key) |
| | Insert |key| unless an equal key is present.
|
| |
| void ** | tr_tree_search (tr_tree *tree, const void *key) |
| | Return the address of the datum stored for |key|, or NULL if |key| is not present.
|
| |
| void ** | tr_tree_search_le (tr_tree *tree, const void *key) |
| | Return the address of the datum of the greatest key less than or equal to |key|, or NULL if there is none.
|
| |
| void ** | tr_tree_search_lt (tr_tree *tree, const void *key) |
| | Return the address of the datum of the greatest key less than |key|, or NULL if there is none.
|
| |
| void ** | tr_tree_search_ge (tr_tree *tree, const void *key) |
| | Return the address of the datum of the least key greater than or equal to |key|, or NULL if there is none.
|
| |
| void ** | tr_tree_search_gt (tr_tree *tree, const void *key) |
| | Return the address of the datum of the least key greater than |key|, or NULL if there is none.
|
| |
| dict_remove_result | tr_tree_remove (tr_tree *tree, const void *key) |
| | Remove the element with key |key|.
|
| |
| size_t | tr_tree_clear (tr_tree *tree, dict_delete_func delete_func) |
| | Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL.
|
| |
| size_t | tr_tree_traverse (tr_tree *tree, dict_visit_func visit, void *user_data) |
| | Call |visit|(key, datum, |user_data|) for each element in key order, stopping early if |visit| returns false.
|
| |
| bool | tr_tree_select (tr_tree *tree, size_t n, const void **key, void **datum) |
| | Store the key and datum of the |n|th element in key order (0-based) through |key| and |datum| and return true, or store NULL through them and return false if |n| is out of range.
|
| |
| size_t | tr_tree_count (const tr_tree *tree) |
| | Return the number of elements.
|
| |
| size_t | tr_tree_min_path_length (const tr_tree *tree) |
| | Return the shallowest depth at which a child link is absent, the root being at depth 1, or 0 for an empty tree.
|
| |
| size_t | tr_tree_max_path_length (const tr_tree *tree) |
| | Return the greatest depth of any node, the root being at depth 1, or 0 for an empty tree: the height of the tree.
|
| |
| size_t | tr_tree_total_path_length (const tr_tree *tree) |
| | Return the sum of the depths of all nodes, the root being at depth 1, or 0 for an empty tree.
|
| |
| bool | tr_tree_verify (const tr_tree *tree) |
| | Check the internal invariants of the tree and return true if they hold, or print the first failed check to stderr and return false.
|
| |
| tr_itor * | tr_itor_new (tr_tree *tree) |
| | Create an iterator over |tree| that is not positioned on any element yet.
|
| |
| dict_itor * | tr_dict_itor_new (tr_tree *tree) |
| | Like tr_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.
|
| |
| void | tr_itor_free (tr_itor *itor) |
| | Free an iterator.
|
| |
| bool | tr_itor_valid (const tr_itor *itor) |
| | Return whether |itor| is positioned on an element.
|
| |
| void | tr_itor_invalidate (tr_itor *itor) |
| | Unposition |itor|, so that it is not positioned on any element.
|
| |
| bool | tr_itor_next (tr_itor *itor) |
| | Move |itor| to the next element in key order and return true, or unposition it and return false if there is none.
|
| |
| bool | tr_itor_prev (tr_itor *itor) |
| | Move |itor| to the previous element in key order and return true, or unposition it and return false if there is none.
|
| |
| bool | tr_itor_nextn (tr_itor *itor, size_t count) |
| | Move |itor| |count| elements forward and return whether it is still positioned.
|
| |
| bool | tr_itor_prevn (tr_itor *itor, size_t count) |
| | Move |itor| |count| elements back and return whether it is still positioned.
|
| |
| bool | tr_itor_first (tr_itor *itor) |
| | Position |itor| on the first element in key order and return true, or unposition it and return false if the tree is empty.
|
| |
| bool | tr_itor_last (tr_itor *itor) |
| | Position |itor| on the last element in key order and return true, or unposition it and return false if the tree is empty.
|
| |
| bool | tr_itor_search (tr_itor *itor, const void *key) |
| | Position |itor| on |key| and return true, or unposition it and return false if |key| is not present.
|
| |
| bool | tr_itor_search_le (tr_itor *itor, const void *key) |
| | Position |itor| on the greatest key less than or equal to |key| and return true, or unposition it and return false if there is none.
|
| |
| bool | tr_itor_search_lt (tr_itor *itor, const void *key) |
| | Position |itor| on the greatest key less than |key| and return true, or unposition it and return false if there is none.
|
| |
| bool | tr_itor_search_ge (tr_itor *itor, const void *key) |
| | Position |itor| on the least key greater than or equal to |key| and return true, or unposition it and return false if there is none.
|
| |
| bool | tr_itor_search_gt (tr_itor *itor, const void *key) |
| | Position |itor| on the least key greater than |key| and return true, or unposition it and return false if there is none.
|
| |
| const void * | tr_itor_key (const tr_itor *itor) |
| | Return the key |itor| is positioned on, or NULL if it is not positioned.
|
| |
| void ** | tr_itor_datum (tr_itor *itor) |
| | Return the address of the datum |itor| is positioned on, through which it can be read or replaced, or NULL if it is not positioned.
|
| |
| int | tr_itor_compare (const tr_itor *i1, const tr_itor *i2) |
| | Compare the positions of two iterators over the same tree: return a negative value, zero, or a positive value as |i1| is before, at, or after |i2| in key order.
|
| |
| bool | tr_itor_remove (tr_itor *itor) |
| | Remove the element |itor| is positioned on and unposition |itor|; return false if it was not positioned.
|
| |
Treap: a binary search tree on the keys that is at the same time a max-heap on per-node priorities.
With random priorities (the default) the tree has the shape of a randomly built search tree, so insert, search and remove take expected O(log n) time. A dict_prio_func makes the shape deterministic; a larger priority places a key closer to the root. Random priorities come from random(), which libdict does not seed. Selecting the nth element takes O(n).
Definition in file tr_tree.h.
1.12.0